Дискретные каналы без шума: теоремы о кодировании неравнозначными символами

Министерство цифрового развития, связи и массоввхх коммуникаций Российской Федерации
Федералвное государственное бюджетное образователвное учреждение










ввхсшего образования










«Сибирский государственнвхй университет телекоммуникаций и










информатики» (СибГУТИ)










Трофимов Виктор Куприянович Храмова Татьяна Викторовна





            Дискретные каналы без шума: теоремы о кодировании неравнозначными символами





Монография













Новосибирск

2021

   УДК 621.391



Утверждено редакционно-издательским советом СибГУТИ


Рецензент доктор техн, наук, проф. А.Л. Резник Рецензент доктор техн, наук, доц. И.В. Нечта



Трофимов В. К., Храмова Т. В. Дискретные каналы без шума: теоремы о кодировании неравнозначными символами: монография / В. К. Трофимов, Т. В. Храмова; Сибирский государственный университет телекоммуникаций и информатики; каф. высшей математики. - Новосибирск, 2021. - 103 с.

   В монографии дан обзор основнвхх методов кодирования равнозначнвхми символами; представлен метод кодирования известного источника неравнозначными символами; пред став ленвх основаннвхе на предложенном в работах Р.Е. Кричевского и В.К. Трофимова распределении методах построения универсальных кодирований сообщений символами неравной длительности. Работа содержит оценки избыточности и доказательство оптимальности предложенных алгоритмов кодирования для различных типов источников.





                                    © Трофимов В.К., 2021
                                    © Храмова Т.В., 2021
                                    © Сибирский государственный университет телекоммуникаций и информатики, 2021

2

                Содержание




1  Канал передачи информации                                  9
   1.1 Общая схема канала без шума.......................... 9
   1.2 Понятие источника информации.........................10
   1.3 Энтропия источника информации........................11
   1.4 Кодирование источника сообщений......................14
   1.5 Пропускная способность канала и избыточность кодирования
       информации...........................................15

2  Некоторые методы кодирования известного источника равнозначными символами                                         17
   2.1 Код Хаффмана.........................................17
   2.2 Арифметическое кодирование...........................20
   2.3 Код Лемпела-Зива.....................................22

3  Кодирование известного источника неравнозначными символами                                                       26
   3.1 Предварительные построения...........................26
   3.2 Схема кодирования неравнозначными символами .........31
   3.3 Оценка стоимости кодирования известного источника неравнозначными символами.......................................36

4  Универсальное кодирование бернуллиевских источников буквами кодового алфавита с неравными длительностями 38 4.1 Схема кодирования множества бернуллиевских источников бук-
       вами кодового алфавита с неравными длительностями ...39
   4.2 Верхняя оценка избыточности универсального кодирования множества бернуллиевских источников ........................43
   4.3 Нижняя оценка избыточности универсального кодирования множества бернуллиевских источников ........................44
   4.4 Асимптотика избыточности универсального кодирования множества бернуллиевских источников ........................45

5  Универсальное кодирование марковских источников буквами кодового алфавита с неравными длительностями                53
   5.1 Кодирование неравнозначными символами информации, порож-
       денной неизвестным марковским источником.............53
   5.2 Верхняя оценка избыточности универсального кодирования марковских источников символами неравнозначных длительностей 58
   5.3 Нижняя оценка избыточности универсального кодирования марковских источников неравнозначными символами.............59
   5.4 Асимптотика избыточности универсального кодирования марковских источников неравнозначными символам..............60

3

Слабо универсальное кодирование стационарных источников символами с неравнозначными длительностями              62

7 Оптимальное универсальное кодирование объединения различных множеств источников символами неравной длитель-

   ности                                                        64
   7.1 Адаптивное кодирование объединения различнвхх множеств источников..................................................64
   7.2 Универсалвное кодирование для объединения множеств марковских источников .........................................65

8  Универсальное кодирование произвольного множества источников без памяти                                68
   8.1 Основнвхе определения. Постановка задачи................68
   8.2 s-энтропия множества источников без памяти .............69
   8.3 Метод кодирования и оценка его эффективности............70


9  Кодирование неравнозначными символами
   источников Мура и Мили при неизвестной статистике сообщений                                                     74
   9.1  Основнвхе определения и обозначения..................74
   9.2  Универсалвное кодирование марковских источников......76
   9.3  Источники Мура.......................................77
   9.4  Кодирование источников Мили..........................83

10 Кодирование геометрических источников
   при неизвестной статистике                                86
   10.1 Основнвхе определения................................86
   10.2 Энтропия геометрического источника. Кодирование близких источников .................................................88
   10.3 Метод кодирования и оценка его эффективности.........90
   10.4 Оценки избвхточности универсалвного кодирования геометрических источников.........................................93

Литература                                                    95

4

                Предисловие




Вопросы сжатия информации возникают при решении многих задач. Например, сжатие информации позволяет в несколвко раз уменвшитв ее объем при передаче. Так, хорошо известные факсимильные аппаратах при работе примерно в 3,5-4 раза уменьшают объем передаваемой информации. При факсимильной передаче больших текстов (таких, например, как газетные) удается уменьшить объем передаваемых данных до 10 раз. Отметим также широкое использование методов сжатия информации в криптографии. Можно считать, что первым алгоритмом, позволяющим сжать сообщение, явился известный код Морзе. В дальнейшем появились новые возможности передачи сообщений, такие как телефон, радио, телевидение, интернет. С их помощью передаются ограниченные потоки информации. Задача сжатия приобрела огромное значение, и для её решения в различных случаях была создана наука, названная теорией информации.
   Теория информации излагается во многих книгах. В них нашли отражение универсальные коды, которые позволяют сжимать тексты различной природы, не требуя знания их точной закономерности.
   Проведем анализ между степенью сжатия и сложностью реализации этих алгоритмов. Все методы сжатия информации, описанные в литературе, как правило излагаются для случая, когда символы, используемые при передаче по каналам связи равнозначны. Если же эти символы не равнозначны, то в монографиях описаны методы сжатия информации, когда структура этой информации известна. К последним относятся работы К. Шеннона, И. Чиссара, Г. Катоны.
   Изучению вопросов сжатия информации символами различной стоимости и посвящена настоящая монография. Книга может быть полезна для специалистов по теории информации, информатике, программированию, базам данных.

5

                Введение





В условиях современной реалвности мы постоянно сталкиваемся с лавинообразным потоком информации, которую необходимо обрабатывать, хранитв и передаватв. Передача информации по каналам связи сопровождается ее пред-варителвной обработкой с целвю уменвшения объема информации, подлежащей передаче, защитах ее от искажения в процессе передачи, и т.д. Уменьшение объема передаваемой информации напрямую связано с увеличением скорости передачи, а также экономией процессорного времени, затрачиваемого на дальнейшую обработку. Задача уменьшения объема памяти, занимаемого информацией, частично решается за счет использования методов сжатия данных и кодирования дискретных источников. Следует отметить, что решение задач кодирования источников используется также в теории управления, при выявлении скрытой информации, при создании большемасштабных вычислительных систем, в криптографии.
   Теория информации, основанная в 1948 г. К. Шенноном, служит для получения различных методов сжатия данных. Разработанные К. Шенноном 78, 42], Р. Фано [35], Д. А. Хаффманом [39], И. Чисаром [40], Г. Катоной 62] алгоритмы кодирования дискретных источников существенно использовали статистику сообщений, что частично препятствовало их практическому применению.
   Вопросы кодирования источников с неизвестной статистикой впервые рассматривались в работах А.Н. Колмогорова [5] и Б.М. Фитингофа [37]. В случае неизвестной статистики источника кодирование называется универсальным. Точная постановка задачи универсального кодирования принадлежит Р.Е. Кричевскому [6].
   Исследованию свойств универсального кодирования также посвящены работы Л.Д. Дэвиссона [53, 54], Т.Д. Линча [68, 69], Т. Ковера [52], Н. Фаллера [56] , Р.Г. Галлагера [3], Д. Кнута [63], Й.С. Виттера [81], Б.Я. Рябко, А. Н. Фи-онова [23, 24, 25, 26, 27, 75, 76], М. Борроуза и Д. Виллера [51], А. Лемпела, Я. Зива [67, 84], Й. Риссайнена [72, 73, 74], Ф. Уиллемса, Ю.М. Штарькова и Ч. Чокенса [45, 46, 82], В. Ф. Бабкина [79], В. К. Трофимова [29, 30, 31, 65, 66], С. Савари [77], С. Верду [80], В.Н. Потапова [17, 20]. Последним двум авторам принадлежат подробные обзорные работы.

6

            Предварительные сведения


Ниже приведены основные понятия, используемые в данной работе.
   Рассмотрим источник сообщений 0, генерирующий последователвноств из букв некоторого конечного алфавита X = {x1,x₂, ...,xₖ}. Последователвноств должна быть закодирована и передана по каналу связи. Для решения нашей задачи оптималвного кодирования разобвем исходящую последователвноств букв источника на блоки (слова) фиксированной длинвх N.
   Процедура кодирования источника заключается в том, что каждому блоку w G XN ставится в соответствие некоторое кодовое слово ^(w) G Y* из букв кодового алфавита Y = {y1,y₂, ...,yₘ} (здесв Y* обозначает множество Y
ние, при котором блокам источника ставится в соответствие кодовое слов нефиксированной длинвх, назвхвается равномерным по входу.
   Разнвхе букввх кодового алфавита имеют разную длительность или, другими словами, стоимоуть передачи: tj = t(yj), j = 1,m. Таким образом, каждому кодовому алфавиту можно поставитв в соответствие вектор длительностей букв t = (ti ,t₂, ••• , tₘ), (tj- = t(yj), j = 1,m). В частности, длителвности кодоввхх символов могут бвхтв одинаковы, в этом случае соответствующий алфавиту вектор обозначим через t1 = (1,1, • • • , 1).
                                                  m
   Самвхм популярнвхм примером кода с неравнвхми длителвностями является код Морзе, актуалвноств которого не теряется и в наше время: на основе кода Морзе созданвх широко исполвзуемвхе штрихкоды.
    Длительностью кодового слова будем считатв величину, равную сумме длителвностей входящих в слово букв:
l 7 ⁽w⁾ ,t) = ^ t ⁽y).
yG^(w)
   Стоимость кодирования определяется как отношение средней длителвности кодового слова к средней длителвности слова источника и в рассматриваемом случае принимает следующий вид:
L "\. ⁰,^R) = N ^ pₑ (w) IД (w) , j).
wGX N
Эффективности метода кодирования ^ : XN ^ Y определяется избыточностью
R (N, 0,<p, t) = L (N, 0, <p,t) - H (0) /C (t),
где H (0) — энтропия источника, определяемая законом распределения вероятностей появления букв алфавита X на выходе источника 0, C (t) — пропускная способность канала передачи информации, зависящая только от кодового алфавита Y.

7

   В классической работе К. Шеннона [42] были заложены основы теории кодирования, сформулированы основные понятия и получены многие базоввхе результаты, явившиеся опорной точкой для дальнейшего развития. Фундаментальными трудами в изучаемой области являются работы А. Н. Колмогорова [5], Р. Фано [35], Б. Фитингофа [37], Н. Абрамсона [49], Р. Г. Галлагера [3], А. А. Маркова [15], Р. Е. Кричевского [10] и др.

8

Канал передачи информации




            1.1  Общая схема канала без шума


Дискретным каналом передачи информации называют совокупность средств, предназначенных для передачи дискретных сигналов: источник сообщений — кодер — передающее устройство — декодер — получатель (рисунок 1).


Рисунок 1 — Схема капала передачи информации

Дискретные последовательности, состоящие из букв алфавита источника сообщений — информационных сигналов, преобразуются в кодирующем устройстве в последовательности символов кодового алфавита.
   Цель кодирования информации может быть различна: шифрование с целью защиты от утечки информации, сжатие с целью уменьшения объема, преобразование с целью защиты от помех. Точное определение кодирования будет приведено ниже. Полученные кодовые слова передаются посредством некоторого устройства получателю. Переданный сигнал подвергается декодированию из кодового алфавита в исходный алфавит. Рассматривается только дешифруемое кодирование.
   При передаче сигналов возможны помехи (шумы), сигнал при этом может подвергаться искажению. В случае отсутствия помех при передаче капал называется каналом без шума. В данной работе рассматривается задача кодирования информации с целью сжатия. В этом случае целесообразно предположить, что капал является бесшумным (рисунок 2).



Рисунок 2 — Схема капала без шума

Источник сообщений однозначно определяется алфавитом и законом распределения вероятностей, заданном па символах алфавита. Основной характеристикой источника сообщений является энтропия Н. Кодирование источника характеризуется стоимостью L (средним числом кодовых символов, приходящимся па одну букву сообщения источника). Пропускная способность

9

канала С в рассматриваемом случае полноствю определяется кодовым алфавитом Y (длительности символов которого могут быть как одинаковы, так и различив:). Величина R определяемая равенством R = L — H/С, называется избыточностью кодирования и является показателем его эффективности.
   Величинах Н, L, С и R нуждаются в аккуратных и корректных определениях, которые, так же как и определение кодирования, будут даны в ближайших секциях.
   Если закон распределения неизвестен, источник сообщений также называется неизвестным и речь идет об универсальном кодировании. Универсальное кодирование впервые рассматривалось в работах А. Н. Колмогорова [5] и Б. М. Фитингофа [37]. В данной работе рассматривается равномерное по входу универсальное кодирование сообщений источника. Длину сообщения источника обозначим как N.


            1.2    Понятие источника информации


Под источником информации подразумевается некоторое устройство, порождающее по определенному закону сообщения (слова), состоящие из букв некоторого алфавита. Для полного описания источника информации требуется:

  • задать входной алфавит;

  • задать закон распределения вероятностей появления букв входного алфавита в сообщениях источника.

Пусть в дальнейшем А* — множество всех конечных последовательностей, состоящих из элементов множества A. a An — множество всех последовательностей длины п, состоящих из элементов множества А.
   Источник информации 0 представлявт собой пару (А, р), где А — некоторый входной алфавит, р : А ^ [0; 1] — закон распределения вероятностей появления букв входного алфавита X в сообщениях источника w Е А*.
   Входной алфавит А = {xi, x₂,..., Xk} может быть как конечным, так и бесконечным. Один из частных случаев — бинарный входной алфавит Ав = {0; 1}. В случае конечного алфавита число букв алфавита А = {x1,x₂,..., xₖ} будем обозначать как |А |, |А | = k.
   Закон распределения вероятности появления букв алфавита А источника 0 в сообщении — это функция


ре : А ^ [0; 1],ре (x\) = P (x, Е w) ,w е А *.


(1)

Закон распределения вероятности появления слов из букв алфавита А источника 0 — это функция


ре : АN ^ [0; 1], ре (w) = P (w), w Е А*.


(2)

10

Источник называется неизвестным, если закон распределения вероятностей появления букв входного алфавита в сообщениях неизвестен.
   Среди различных типов источников выделим следующие: бернуллиевский, марковский и стационарный.
   Бернуллиевский источник информации — это источник, для которого вероятности pe (xij) появления любой буквы xij Е X в слове

Wi

Е X* (wi = хг₁ хг2 • •• XiN,)

ч

порожденном источником, не зависит от того, какие буквы ей предшествова-

ли, т.е.

P (xij I xilxi2•••xij-1)   pe (xjj) •

(3)

Марковский источник информации порядка s — это источник, для которого вероятность pe (xij.) появления любой буквы xᵢⱼ Е X в слове wᵢ Е X* (wi = xᵢ₁ xi₂ • • • xiN^ порожденном источником, зависит от того, какие s букв ей предшествовали, т.е.

          P(xj.¹ xiixi2...xij-i) = P (xij¹ xij-ₛxij-ₛ₊i...xij-i) = pse (xi/) . (4)

Обозначим через Xj С X* множество всех последовательностей источника, xi                                                                       wi ⁼
xᵢ₁ xi₂ • • • xiN, представимо в виде

W = X1i П Xi², П ... П XN и ли wi = Xi Xi²,... XN.
 Стационарный источник информации — это источник, для закона распределения вероятностей которого имеет место равенство
P (xj¹ Xj²... XjN^ = P (xj¹⁻j⁰Xj²⁻j⁰... X'⁻j⁰^              (5)
i1    i2  iN         i1    i2       iN

для всех наборов iₓ, i₂,..., iN Е N и j₀, jₓ, j₂,..., jN Е N.


1.3 Энтропия источника информации
Энтропия случайной величины 4 определяется равенством


H (4 ) = -Е P (4 = xi)log р (4 = xi),                       (6)
i

(здесь и далее log x = log₂ x, 0 log0 = 0.)
    Из определения энтропии (6) непосредственно вытекает, что H (4) > 0. Кроме того, если H (4| п) _ условная энтропия, определяемая равенством (см. [62])
           H ⁽⁴ | П) = - ^ р ⁽⁴ = xi,n = y ⁾log р ⁽⁴ = xi,n = yj), i,j


11

то имеет место соотношение


                         H (<) > н (41 n), ve.n.                       (7)

Совокупность сообщений источника wi = xi1 xi₂ • • • xiNi можно представить в
                   ОО
виде объединения     Wₙ множеств последовательностей случайных величин
                  n=1
Wn = {<1,<2, • • • <n} •
Для каждого значения п рассмотрим величину
                           kⁿ
               Hn (®) = - £ P (Wn = wi) log P (Wn = wi).               (8)
                           i=1
Ннтропия H (0) стационарного источника сообщений 0 с алфавитом X и законом распределения р определяется равенством (см. [3, 35, 62])

                           H (0) = lim Hⁿ ⁽⁰⁾,                         (9)
n .-\.. n

   Hₙ (0)
    Humponufi H (0) марковского источника сообщений 0 с алфавитом X и законом распределения р определяется равенством (см. [3, 35, 62])
k
H ⁽⁰⁾ = — £ pV £Pvi logPvi,                     (¹⁰)
vexs  i=i
где pᵥi = P (xil v), v e Xs, p0 ~ стационарное распределение.
   Humponufi H (0) бернуллиевского источника сообщений 0 с алфавитом
X и законом распределения р определяется равенством (см. [3, 35, 62])
H (0) = — £ Ре (xi)logpe (xi)                   (11)
xi ex
где pe (xi) — вероятность появления буквы xi e X на выходе источника 0.
                                             0
          H (0)
H (0) = Hi (0) = - £ pe (xi) logpe (xi).
xieX
    Энтропия источника определяет среднее количество информации в сообщениях источника и является показателем его «непредсказуемости». Максимальное значение энтропии достигается при равномерном распределении

12