«ВВЕДЕНИЕ В ТЕОРИЮ ИНФОРМАЦИИ Учебное пособие 2 Содержание Введение Глава 1. Три подхода к понятию сложности сообщений 3 1.1. Алгоритмический подход 3 1.2. Комбинаторный подход 5 1.3. Вероятностный подход 7 Глава 2. ...»

При k = 2 утверждение очевидно. Из префиксности множества fH (A ) следует префиксность множества fH (A) = (fH (A ) {w0, w1}) \ {w}, где w = fH (ak ).

П р и м е р 12. Построим кодирование Хаффмена для источника с вероятностями появления букв P (a1 ) = 0, 3; P (a2 ) = 0, 2; P (a3 ) = P (a4 ) = 0, 15; P (a5 ) = P (a6 ) = = 0, 1. Процесс построения кода изображен в виде дерева на рис. 3. Слева от вершины указана соответствующая ей буква, а справа вероятность буквы. Кодовые слова fH (a1 ) = 00, fH (a2 ) = 10, fH (a3 ) = 010, fH (a4 ) = 011, fH (a5 ) = 110, fH (a6 ) = оказываются пометками листьев двоичного дерева, что подтверждает префиксность кода Хаффмана.

Т е о р е м а 8. (Хаффмен) Кодирование Хаффмена является оптимальным.

Д о к а з а т е л ь с т в о. Ясно, что кодирование Хаффмена является оптимальным для любого источника Бернулли с двухбуквенным алфавитом. Предположим, что найдутся источники Бернулли, для которых кодирование, построенное методом Хаффмена не является оптимальным. Тогда среди них найдётся источник A, P с минимальной мощностью алфавита |A| = k + 1. Без ограничения общности считаем, что буквы алфавита A занумерованы по убыванию вероятностей. Рассмотрим источник Бернулли A, P. Из предположения о минимальности k следует, что кодирование Хаффмена fH источника A, P является оптимальным. Справедливы равенства Рассмотрим оптимальное кодирование f0 источника A, P, удовлетворяющее условиям утверждения 43. Определим кодирование f0 источника A, P по правилу:

f0 (ai ) = f0 (ai ) при любом i = 1,..., k 1 и кодовое слово f0 (ak ) получено из кодового слова f0 (ak ) отбрасыванием последней буквы. Нетрудно видеть, что f0 является префиксным кодированием источника A, P и аналогично вычислениям (6.7) получаем равенство Тогда из равенства (6.7) и оптимальности кодирования f0 вытекает, что Это противоречит оптимальности кодирования Хаффмена fH источника A, P.

Выше были рассмотрены способы построения префиксного побуквенного кодирования и оценена эффективность побуквенного кодирования источников Бернулли. В модифицированной форме эти методы могут быть использованы для эффективного 6.5. Равноблочное на выходе кодирование кодирования произвольных стационарных источников. Пусть A, P некоторый источник сообщений. Будем рассматривать слова длины n как буквы алфавита An.

Побуквенное кодирование f : An {0, 1} по отношению к алфавиту An называется блочным по отношению к исходному алфавиту A.

У т в е р ж д е н и е 45. Для любого стационарного источника A, P и числа > 0 найдётся блочное кодирование с предельной избыточностью r(f, P ) <.

Д о к а з а т е л ь с т в о. Из утверждений 26, 27 и формулы (5.5) следует, что последовательность n Hn (P ), монотонно убывая, сходится к H(P ). Следовательно, найдётся такое натуральное m, что m Hm (P ) n Hn (P ) < /3 при любом n m и 1/m < /3. Из утверждения 41 следует, что найдётся побуквенное префиксное кодирование f источника Am, P с избыточностью, не превосходящей 1. Представим слово w An как конкатенацию слов w = w1... wl w, где |wi | = m, для всех i = 1,..., l и |w | < m. Будем кодировать слова wi посредством f, а остаток w произвольным способом. Поскольку слов длины менее m конечное число, то длины кодов таких слов не превосходят некоторой константы C. Из определений и утверждения 39 имеем равенства Cml (f, A, P ) = Cl (f, Am, P ) = lC1 (f, Am, P ) и Hm ( A, P ) = H1 ( Am, P ).

Из сказанного выше вытекают неравенства Тогда r(f, P ) = lim n Rn (f, A, P ) <.

З а д а ч а 18. Пусть A, P источник Бернулли с алфавитом мощности k, приlog k чём все буквы равновероятны. Докажите равенство C1 (fH, P ) = log k + 1 2 k.

З а д а ч а 19. Приведите пример источника Бернулли, для которого кодирование Шеннона Фано не является оптимальным.

6.5. Равноблочное на выходе кодирование В предыдущем параграфе было рассмотрено кодирование, которое отображает блоки из фиксированного числа букв в кодовые слова различной длины. В этом параграфе мы рассмотрим кодирование, ставящее в соответствие словам различной длины кодовые слова одинаковой длины. Такое кодирование называют кодированием типа VB в отличие от блочного кодирования, имеющего тип BV. Возможно также рассматривать кодирование типа VV, которое слова переменной длины отображает в слова переменной длины.

Кодирование типа VB обладает свойством некоторой помехоустойчивости: одна ошибка при кодировании приводит к неправильному восстановлению при декодировании только одного кодового слова и никак не влияет на декодирование других кодовых слов, поскольку разделение кодовой последовательности на кодовые слова одинаковой длины не зависит от самих кодовых слов. В то время как одна ошибка при кодировании типа BV может привести к неправильному разделению кодовой последовательности на кодовые слова и, следовательно, к неправильному восстановлению всего следующего за ошибкой текста.

Рассмотрим конечный алфавит A = {a1, a2,..., ak }. Вершины бесконечного полного k-ичного дерева T пометим словами в алфавите A, т. е. построим функцию : T A по следующему правилу: корень дерева пометим пустым словом; если вершина t T уже помечена словом u, то k её потомков пометим словами ua1, ua2,..., uak. В дальнейшем будем отождествлять вершины дерева и соответствующие им слова.

Через L(T ), как и прежде, будем обозначать множество слов, соответствующих листьям(висячим вершинам) дерева T. Будем назвать конечное k-ичное дерево полным, если любая его внутренняя вершина имеет ровно k потомков.

Д о к а з а т е л ь с т в о. Минимальное полное k-ичное дерево состоит из корня и листьев, помеченных буквами алфавита. Из определения источника сообщений имеем P (x) = 1. Докажем утверждение методом индукции по числу внутренних вершин дерева. Пусть для полных k-ичных деревьев с n внутренними вершинами равенство доказано. Рассмотрим произвольное полное k-ичное дерево T с n + 1 внутренней вершиной. Найдётся вершина v в дереве T, все потомки которой являются листьями. Тогда, удалив эти листья из дерева, получим полное k-ичное дерево T с n внутренними вершинами. Из определения источника сообщений и предположения индукции справедливы равенства Пусть 0 < q < 1 и A, P некоторый источник сообщений. Пусть множество W A таково, что для некоторого 0 < q < 1 справедливы включения {w A | P (w) > q} W {w A | P (w) q}. Поскольку для каждого слова из W его префиксы также содержатся в множестве W, этому множеству слов соответствует некоторое поддерево. Однако, это поддерево может оказаться неполным. Рассмотрим множество T (W ) = W {wa | w W, a A}. Ясно, что множество слов T (W ) соответствует полному k-ичному дереву. Нетрудно видеть, что для произвольного натурального числа t можно выбрать число q и множество W = Wq,t так, чтобы 2t k < |L(T (Wq,t ))| 2t. Введём обозначение T (Wq,t ) = Tq,t. Упорядочим слова из L(Tq,t ) произвольным образом и i-му слову v L(Tq,t ) поставим в соответствие двоичную запись h(v) его номера без единицы (i 1), состоящую из t двоичных символов.

Поскольку множество L(Tq,t ) соответствует листьям полного k-ичного дерева Tq,t, каждое слово w в алфавите A можно представить как конкатенацию w = w1 w2... wm, где wi L(Tq,t ) за исключением, возможно, последнего слова wm. Для упрощения изложения будем считать, что wm L(Tq,t ). Определим кодирование fKh равенством fKh (w) = h(w1 )h(w2 )... h(wm ). Кодирование fKh называется равноблочным на выходе кодированием Ходака (в англоязычной литературе кодированием Танстэла).

Префиксность кодирования Ходака непосредственно вытекает из того, что кодовые слова состоят из блоков фиксированной длины t.

гда избыточность кодирования Ходака удовлетворяет неравенству R (f, P ) t, где t длина блока, а число C зависит только от p0 и мощности n n Kh алфавита A.

6.6. Нумерационное кодирование Доказательство.

ся такое слово v L(Tq,t ), что P (v) 2t1. Если v L(Tq,t ), то v Wq,t. Тогда q P (v) 2t1. Поскольку A, P источник Бернулли, для любого u L(Tq,t ) имеем u = va для некоторого слова v Wq,t и Пусть fKh (w) = h(w1 )h(w2 )... h(wm ). Тогда |fKh (w)| = mt и log P (w) m log 2 pk.

Следовательно, имеем где число C зависит только от p0 и k.

6.6. Нумерационное кодирование Фактически все методы кодирования, имеющие цель уменьшить размер сообщения, основываются на простой идее: более вероятные слова должны иметь более короткие коды, по сравнению с менее вероятными словами. Ниже показано, что даже самая простая (не в смысле вычислительной сложности, а в смысле определения алгоритма) реализация этого принципа приводит к кодированию, которое асимптотически не улучшаемо.

Пусть A, P некоторый источник сообщений. Упорядочим слова длины n в алфавите A в порядке уменьшения вероятности и обозначим через wi i-е слово в данном порядке. Определим Fn (wi ) = PBin(i). По построению Fn (An ) префиксное множество. Следовательно, нумерационное кодирование определяемое формулой fN C (w) = = PBin(|w|)F|w| (w) является префиксным в сильном смысле, т. е. множество fN C (A ) является префиксным.

r(fN C, P ) = 0.

Доказательство.

Пусть слово wi, |wi | = n имеет i-й номер. По определению порядка все слова с меньшими номерами имеют вероятность большую либо равную P (wi ). Из определения источника сообщений имеем Тогда из неравенства Йенсена для функции f (x) = log log(1 + x) имеем Заметим, что доказательство утверждения 47 является другим независимым доказательством пункта 2) теоремы Шеннона.

6.7. Арифметическое кодирование Одним из наиболее эффективных методов построения префиксного кодирования со сколь угодно малой избыточностью для заданного стационарного источника является арифметическое кодирование. Основная идея арифметического кодирования состоит в следующем наблюдении. Все наборы из n букв алфавита A упорядочим лексикографически, т. е. ai1 ai2... ain aj1 aj2... ajn, если ik = jk при k < l и il jl.

Для каждого слова x An определим величины Разделим полуинтервал [0, 1) на полуинтервалы [L(x), R(x)). В каждом полуинтервале длины I, I 1 найдется двоично-рациональное число со знаменателем не большим, чем 2 log I, поскольку разность между любыми двумя ближайшими числами с таким знаменателем не превосходит I (2 log I 2log I = I). Каждому слову x An поставим в соответствие двоично-рациональное число q(x) [L(x), R(x)) со знаменателем, не большим 2 log p(x). В качестве кода f (x) рассмотрим двоичную запись числителя числа q(x), которая имеет длину, равную log p(x) (если число двоичных символов в записи числителя меньше, то нужно дописать слева недостающие нули). Тогда Поскольку полуинтервалы [L(x), R(x)), соответствующие различным словам x одинаковой длины, не пересекаются, все числа q(x), x An попарно различны, т. е.

отображение f : An E инъективно. Если для всех x An и ai A справедиво неравенство P (ai |x) 1/2, то при добавлении каждой следующей буквы интервал уменьшается не менее чем в два раза. Тогда |f (xai )| > |f (x)| и отображение f : A {0, 1} оказывается инъективным. Из равенства (6.9) следует, что избыточность Rn (f, P ) не превосходит единицы и предельная избыточность кодирования f равняется нулю.

6.7. Арифметическое кодирование Однако в таком виде арифметическое кодирование не может применяться на практике, поскольку требуемая точность арифметических вычислений экспоненциально растет с увеличением длины кодируемого слова. Действительно, при увеличении длины слова на одну букву, число различных слов данной длины возрастает в k раз, а значит соответствующий слову полуинтервал уменьшается в среднем в k раз. Тогда для кодирования слова на единицу большей длины нужно в k раз точнее определять границы соответствующего полуинтервала.

Первый вариант арифметического кодирования, использующий арифметические действия с заранее фиксированной точностью был предложен Й. Риссаненом. Ниже будет описан наиболее известный вариант этого метода. Для упрощения изложения положим, что A, P источник Бернулли и P (ai ) 1/4 для всех i, 1 i k. Длина t > 0 двоичной записи чисел, с которыми в процессе кодирования выполняются арифметические операции, является параметром кодирования и должна удовлетворять неравенству P (ai ) 1/2t2 для всех букв ai A.

Определим величины 1 = 0, i = i1 + P (ai1 ). Разделим полуинтервал [0, 1) на полуинтервалы i(ai ) = [l(ai ), r(ai )), где l(ai ) = i 2t /2t и r(ai ) = i+1 2t /2t. Каждой букве ai A соответствует i-й полуинтервал, длина которого приблизительно равна P (ai ). Пусть x = ai1 ai2... ain. Поскольку P (ai1 ) 1/4, т. е. длина полуинтервала не превышает 1/4, возможны три случая:

1) i(ai1 ) [0, 1/2);

2) i(ai1 ) [1/2, 1);

3) i(ai1 ) [1/4, 3/4).

Пусть I(x) полуинтервал, соответствующий слову x An. Тогда в первом случае имеем I(x) i(ai1 ) [0, 1/2) и первым символом после запятой в двоичной записи любого числа q I(x) является 0. Поэтому 0 первый символ кода fA (x).

Во втором случае первым символом кода fA (x) является 1. В третьем случае первый символ пока неизвестен.

Проведем операцию изменения масштаба (растяжения) полуинтервала. В первом случае новый полуинтервал [2l(ai1 ), 2r(ai1 )).

В третьем случае [2l(ai1 ) 1/2, 2r(ai1 ) 1/2).

В каждом случае новый полуинтервал длиннее полуинтервала i(ai1 ) в два раза.

Будем продолжать процедуру изменения масштаба до тех пор, пока растянутый полуинтервал укладывается целиком в правую, левую или среднюю половину полуинтервала [0, 1). При растяжении левой половины полуинтервала [0, 1) будем приписывать 0 в качестве следующего символа кода f (x), при растяжении правой половины [0, 1) будем приписывать 1. Если перед растяжением левой (правой) половины [0, 1) текущий полуинтервал оказывался h раз в средней половине, то после нуля (единицы) нужно приписать h единиц (нулей), т. е. в целом нужно приписать к коду слово l < r 2 и r l > 2. Из [l/2, r/2 ) выделим полуинтервал, соответствующий второй букве слова x: i(ai1 ai2 ) = [l(ai1 ai2 ), r(ai1 ai2 )), где l(ai1 ai2 ) = (l + (r l)i2 )/2t и r(ai1 ai2 ) = (l + (r l)1+i2 )/2t. Проделаем с полуинтервалом i(ai1 ai2 ) те же операции изменения масштаба, что и с полуинтервалом i(ai1 ). В результате получим начало кода fA (x), соответствующее двум начальным буквам. Выполнив такую же процедуру для букв ai3, ai4,... ain, получим код fA (x). Заметим, что при вычисления кода fA (x) мы использовали арифметические операции с числами, по модулю не превосходящими 2t, причем для кодирования каждой очередной буквы достаточно конечного числа арифметических операций.

Из процедуры арифметического кодирования непосредственно вытекает следующее утверждение.

У т в е р ж д е н и е 48. Полуинтервалы, соответствующие словам одинаковой длины, не пересекаются. Соответствующий слову x полуинтервал целиком содержится в полуинтервале, соответствующем каждому префиксу слова x.

В том случае, когда условие max P (ai ) 1/4 не выполняется, операция изменения масштаба не обязательно следует за добавлением очередной буквы. Очередные буквы необходимо добавлять, пока соответствующий полуинтервал не будет целиком укладываться в правую, левую или среднюю половину полуинтервала [0, 1). Если вероятности букв зависят от предыстории, то при кодировании буквы aij слова x = ai1 ai2... ain вместо чисел i следует использовать числа i, 1 j n, опредеj j j ленные равенствами 1 = 0, i = i1 + P (ai1 |ai1 ai2... aij1 ).

П р и м е р 13. Рассмотрим арифметическое кодирование при t = 4 слова a4 a1 a2, порожденного источником Бернулли с алфавитом A = {a1, a2, a3, a4, a5 } и вероятностями букв P (a1 ) = P (a3 ) = 1/4, P (a2 ) = P (a4 ) = P (a5 ) = 1/6.

Получаем равенства:

l(a4 ) = 16·2/3 = 10, r(a4 ) = 16·5/6 = 13, l(a4 a1 a5 ) = 12·5/6 = 16, r(a4 a1 a5 ) = 12·1 = 12.

Процесс построения арифметического кода изображен на рис. 4. Получаем fA (a4 a1 a5 ) = 1010101.

6.7. Арифметическое кодирование Декодирование арифметического кода осуществляется следующим образом. Сначала нужно определить первую букву закодированного слова. Затем нужно удалить начальные символы кода, соответствующие первой букве, и определить вторую букву закодированного слова и т. д. Например, определим первую букву слова, имеющего код 1010101. Так как первым символом кодового слова является 1, то первой буквой закодированного слова является a3, a4 или a5. Вторым символом кодового слова является 0, поэтому первой буквой закодированного слова является a3 или a4. Так как следующим символом кодового слова является 1, мы заключаем, что первой буквой закодированного слова является буква a4. Процесс декодирования изображен на рис. 5.

После повторения процедуры кодирования буквы a4 (см. пример выше) разделим полученный полуинтервал на части, соответствующие буквам a1, a2, a3, a4, a5, и определим вторую букву закодированного слова аналогичным образом.

Запишем формально рекуррентные формулы, определяющие процедуру арифметического кодирования источника Бернулли. Пусть x некоторое слово в алфавите A. Обозначим через xai слово, полученное из x добавлением буквы ai. Пусть d(x) количество изменений масштаба при кодировании слова x; L(x) и R(x) левая и правая границы полуинтервала, соответствующего слову x в первоначальном масштабе. Тогда арифметическое кодирование определяется следующими формулами:

R() = 1, L() = 0, d() = 0, Из формул (6.10) и (6.12) следует, что R(x)2d(x)+2 L(x)2d(x)+2 > 1. В качестве кода слова x можно взять состоящую ровно из d(x) + 3 символов1 двоичную запись такого целого числа N (x), что N (x), (N (x) + 1) [L(x)2d(x)+3, R(x)2d(x)+3 ). Таким образом, определим кодирование fA равенством 1 i k, выполнены неравенства 1/2 P (ai ) 1/4. Тогда отображение fA, определяемое формулами (6.10) (6.14), является префиксным кодированием.

Доказательство.

Пусть u, v {0, 1} и u префикс слова v. Тогда двоичные числа и, определенные равенствами Bin|u| = u и Bin|v| = v, удовлетворяют неравенствам Если двоичная запись содержит меньше символов, то допишем вначале нули.

6.7. Арифметическое кодирование Пусть x произвольное слово в алфавите A. Из неравенства (6.12) следует, что Докажем от противного, что отображение fA обладает свойством префиксности.

Пусть x, y A некоторые слова и слово fA (x) префикс слова fA (y). Так как |fA (x)| = d(x) + 3, то из формул (6.14)–(6.16) получаем т. е. полуинтервалы [L(x), R(x)) и [L(y), R(y)) пересекаются. Из утверждения 48 вытекает, что [L(y), R(y)) [L(x), R(x)) и слово x является префиксом слова y (противоположное включение противоречит тому, что кодовое слово fA (x) префикс кодового слова fA (y)). Следовательно, отображение fA обладает свойством префиксности.

Докажем инъективность отображения fA. Если fA (x) = fA (y), то x префикс слова y (или наоборот). Так как maxi P (ai ) 1/4, то справедливы неравенства I(y) I(xai ) I(x)/4. Тогда из неравенства (6.12) следует, что d(x) < d(y) и |fA (x)| < |fA (y)|. Таким образом, отображение fA инъективно.

Ограничение maxi P (ai ) 1/4 в условии утверждения 49 можно снять, несколько усложнив кодирование конца сообщения.

Т е о р е м а 10. (Риссанен) Пусть A, P такой источник Бернулли в алфавите A = {a1,..., ak }, что при любом i, 1 i k, выполнены неравенства 1/2t3 P (ai ) 1/4. Тогда для арифметического кодирования fA с параметром t справедливо неравенство при m n. Докажем методом индукции, что Из равенства (6.11) и неравенства > 1 следует, что Пусть неравенство (6.17) верно для m1 при m n. Тогда из (6.11) и (6.12) получаем т. е. неравенство (6.17) доказано. Из (6.12) и (6.17) следует, что откуда имеем Используя неравенство ln(1 + x) x при x > 1, получаем неравенства Тогда из (6.18) и условия теоремы 1/2t3 P (ai ) следует неравенство Из формулы (6.14) и предыдущего неравенства получаем оценку предельной избыточности кодирования f источника A, P Из теоремы Риссанена следует, что выбирая достаточно большой параметр t, можно получить кодирование со сколь угодно малой предельной избыточностью кодирования r. Причем параметр t, равный длине двоичной записи чисел, с которыми в процессе кодирования нужно выполнять арифметические операции, растет только как log 1/r + const при r 0, где r = r(fA, P ).

Аналогичная теорема об избыточности арифметического кодирования справедлива для широкого класса стационарных источников.

Арифметическое кодирование широко применяется в используемых на практике алгоритмах сжатия данных совместно с методами определения контекстной модели сообщения и её параметров. Такие схемы кодирования называются адаптивными, наиболее известной адаптивной схемой является метод разработанный Дж. Клири и Я. Уиттеном2, который в англоязычной литературе называется PPM.

6.8. Адаптивное и универсальное кодирования Рассмотренные выше методы кодирования сообщений требуют, чтобы заранее был известен источник сообщений, т. е. известны вероятности слов. Более того, для правильного декодирования кодов сообщений должны быть известны либо применённое кодирование, либо параметры источника сообщений, по которым кодирование можно восстановить. Если при побуквенном кодировании или при кодировании источника Бернулли эта дополнительная информация невелика по объёму, то при Вариант арифметического кодирования, описанный выше, принадлежит этим же авторам.

6.8. Адаптивное и универсальное кодирования использовании блочного кодирования количество кодовых слов растёт в экспоненциальной зависимости от длины блока, так же как количество параметров марковского источника k-го порядка экспоненциально зависит от k. Для того, чтобы не передавать эту дополнительную информацию, которая может компенсировать эффект сжатия сообщения, применяют адаптивные схемы кодирования или универсальные методы кодирования.

Адаптивные схемы кодирования характеризуются тем, что при кодировании следующей части текста используются статистические свойства предыдущей, уже закодированной, части текста. А именно, используя методы, которые были рассмотрены в главе 4, по началу текста строится модель источника сообщений и вычисляются параметры модели. Затем, исходя из этих данных, вычисляется вероятность очередной буквы или очередного блока сообщения и определяются следующие символы кода сообщения. Декодирование производится аналогичным образом: по уже декодированному началу текста тем же способом строится модель сообщения и вычисляются её параметры. Затем может производиться декодирование продолжения кодового слова, если применённое кодирование однозначно определяется найденными параметрами. Теорема Шеннона утверждает, что для эффективного кодирования сообщений достаточно знать их вероятности.

Универсальным называют такое кодирование, которое эффективно для кодирования источников сообщений с некоторой фиксированной моделью, независимо от параметров модели. Пусть M некоторая модель источника сообщений. Задача построения универсального относительно модели M кодирования состоит в нахождении префиксного кодирования f, минимизирующего величину sup Rn (f, P ). Благодаря методу арифметического кодирования (см. § 6.7), эта задача фактически сводится к задаче построения универсального источника A, Q, минимизирующего величины sup DAn (P Q) при достаточно больших n.

Пусть M некоторая модель источников сообщений. Любой источник сообщений в этой модели порождает распределение вероятностей P на разбиении An. Пусть n (M ) = inf sup DAn (P Q), где инфимум берётся по всевозможным распределениям вероятностей Q на множестве An.

Пусть B модель Бернулли с алфавитом A, |A| = k. Для оценки величины n (B) нам понадобится следующая формула.

Доказательство этого равенства нетрудно получить методом индукции по k, используя свойство (x + 1) = x(x) при x > 0. База индукции и шаг индукции обеспечиваются известным равенством t1 (1 t)1 dt =.

что где µ(U ) = U 1 dt мера Лебега множества U.

P является распределением вероятностей на разбиении An.

Тогда Из утверждения 31 следует, что Так как DAn (P Q) 0 из предыдущих неравенств имеем Оценим величину log P (x) nH(x). Из утверждения 50 имеем равенство P (x) = (n+k1)! (k 1)!. Тогда из утверждения 5 получаем неравенство Таким образом, для произвольного источника Q справедливо неравенство Докажем неравенство n k1 log n + O(1) при n.

Q(x) = 1 и Q(xa) = 1 для любого x A. Следовательно, распределение 6.8. Адаптивное и универсальное кодирования вероятностей Q, которое называется KT -распределением, порождает источник сообщений A, Q. Из утверждения 50 нетрудно получить явный вид распределения где ri количество букв ai в слове x An.

Оценим величину DAn (P Q). Из утверждения 31 имеем Применяя равенство (x + 1) = x(x) получаем, что (r + 1/2) = (1/2)(2r1)!! = (1/2)(2r)!

. Тогда из формулы Стирлинга следует, что ln (r + 1/2) = r log(re) + O(1) при r. Из последнего асимптотического равенства и формулы (6.19) получаем неравенство для любого x An. Из формул (6.20) и (6.21) вытекает требуемое неравенство.

Теорема Кричевского фактически объясняет известное правило сдвига на 1, которое обычно применяется при адаптивном кодировании. Правило состоит в следующем: если в обработанном начале wn длиной n кодируемого сообшения w буква ai встречалась ri раз, то следует полагать вероятность появления буквы ai на n + 1 позиции равной не ri, а n+ k. Дробь n+ k лучше чем ri приближает величину Q(wn ai )/Q(wn ).

Здесь следует отметить, что вычисление распределения вероятностей, решающего задачу универсального кодирования, тесно связано с задачей предсказания следующего элемента в последовательности. Действительно, если мы априори полагаем, что рассматриваемая последовательность является последовательностью испытаний Бернулли с неизвестными вероятностями букв, то величина Q(wn ai )/Q(wn ) оказывается в некотором смысле оптимальным прогнозом вероятности появления буквы ai на (n + 1)-й позиции в слове w. Построение распределения вероятностей, решающего задачу универсального кодирования для более сложных моделей, позволяет предсказывать очередные символы в последовательностях при гораздо более слабых априорных предположениях о стохастической природе последовательностей. Нетрудно видеть, что справедливо и обратное: если мы каким-то образом умеем эффективно предсказывать следующую букву в символьной последовательности, то нам уже не составит большого труда разработать эффективный алгоритм её сжатия.

Рассмотрим альтернативный подход к проблеме выбора распределения вероятностей на An для кодирования сообщения, порождённого неизвестным источником сообщений. Рассмотрим некоторую модель M параметрическое семейство источников сообщений с алфавитом A. Пусть P (x) = max P (x), где максимум берётся по всем возможным в этой модели распределениям вероятностей P. Для любого x An определим распределение Q (x) равенством ляется распределением вероятностей на An. Рассмотрим произвольное распределение вероятностей Q. Поскольку Q(x) = 1, найдется такое слово x An, что Q (x) Q(x). Тогда max log Q (x) = Q(x). Имеем Величина St(x, M ) = log Q (x) называется стохастической сложностью слова x An в модели M. Как видно из утверждения 51, величина n (M ) = log Kn (M ) = = log Q(x) не зависит от слова x An и соответствует дополнительному количеству битов, которое нужно затратить для кодирования слова x An, если неизвестны параметры источника сообщений.

Т е о р е м а 12. (Штарьков) Пусть B множество источников Бернулли с алфавитом A. Тогда n (B) = n (B) + O(1) при n.

Д о к а з а т е л ь с т в о. По определению величины P (x) имеем неравенство P (x) P (x) для любых распределений вероятностей P в модели Бернулли и слов x An. Тогда Пусть Q есть KT -распределение (6.19). Из утверждения 21 следует, что log P (x) = = nH(x), где H(x) эмпирическая энтропия слова x An. Тогда из неравенства (6.21) имеем и неравенство n (B) n (B) + O(1) следует из теоремы Кричевского.

Р. Е. Кричевский и В. К. Трофимов вычислили с точностью до константы величину n (M ), а Ю. М. Штарьков получил асимптотически точную верхнюю оценку величины n (M ) для моделей марковских источников конечного порядка. Й. Риссанен 6.9. Интервальное кодирование доказал, что теорема Штарькова остаётся справедливой для любых автоматных моделей и для любой автоматной модели M с числом независимых параметров d справедливо асимптотическое равенство n (M ) = d log n + O(1).

6.9. Интервальное кодирование Интервальное кодирование отличается простотой реализации. Оно оказывается эффективным при кодировании слов в алфавите большой мощности с длинными сериями одинаковых букв. При интервальном кодировании каждая буква исходной последовательности заменяется на число, равное количеству букв до предыдущего включения той же буквы. Чтобы можно было единообразно кодировать все, в том числе первое, включения буквы в слово предполагается, что перед началом каждого слова помещается весь алфавит.

П р и м е р 14. Слово (a1 a2 a3 )a3 a3 a3 a2 a2 a2 a1 a1 a1 a3 будет преобразовано в последовательность чисел 1115119117.

Числа можно кодировать произвольным префиксным кодом натурального ряда.

Определим интервальный код слова x = ai1... ain равенством где kj = min (j l) расстояние между aij и ближайшей слева такой же буквой.

и |PBin(1)| = 1. Пусть в слове w An буква ai встречается ri раз на t1, t2,..., tri местах. Тогда количество битов, затраченное на кодирование всех, за исключением первого, вхождений буквы ai, не превышает Из формулы (6.22) и неравенства Йенсена для выпуклых вверх функций log x и log log(x + 1) получаем, что количество битов, затраченных на кодирование всего слова w, за исключением первых вхождений каждой буквы, не превышает суммы Тогда из предыдущего неравенства имеем где C (k) стоимость кодирования первых вхождений k букв алфавита A. Из предыдущего неравенства и утверждений 30 и 31 получаем оценку Из предыдущего неравенства имеем limn n Rn (fI, P ) 2 log log k + 3.

Как видно из теоремы Рябко интервальное кодирование может быть эффективно для кодирования источников сообщений с большими алфавитами. Например, когда кодируется текст на естественном языке и в качестве алфавита рассматривается словарь. Кроме того, интервальное кодирование и особенно его модификации могут быть полезны при кодировании источников Бернулли с низкой энтропией, когда вероятность одной из букв близка к 1.

Интервальные методы кодирования не обеспечивают малую избыточность для источников c более сложными моделями, чем модели Бернулли. Однако для кодирования источников сообщений, имеющих сложную контекстную модель, также можно применять интервальное кодирование, предварительно выполнив преобразование Барроуза Уилера, которое будет определено в этом параграфе.

Пусть x = x1... xn некоторое слово в двоичном алфавите. Превратим слово x в циклическое слово, определив x0 = xn, x1 = xn1,..., xi = xni,.... Каждой букве xi поставим в соответствие контекст s(xi ) длины n: s(xi ) = xi1 xi2... xin.

6.10. Преобразование Барроуза Уилера Упорядочим контексты лексикографически (читая контекст справа налево). ПреУилера слова x называется слово BW(x) длины n, составобразованием Барроуза ленное из букв слова x в порядке их контекстов, т. е. BW(x) = xi1 xi2... xin, где s(xi1 ) s(xi2 ) · · · s(xin ). Другими словами, рассмотрим матрицу вращений слова x и расставим строки матрицы в лексикографическом (начиная справа) порядке. Первый столбец получившейся матрицы и есть слово BW(x). Для простоты изложения рассмотрим двухбуквенный алфавит {0, 1}.

П р и м е р 15. Пусть x = 1100110100. Тогда матрица вращений слова x имеет вид После упорядочения получаем матрицу Тогда BW(110110100) = 101111000.

Оказывается, что по слову BW(x) можно восстановить всю упорядоченную матрицу. Действительно, во всех столбцах (как и в строках) матрицы содержится одинаковое число 0 и 1. Последний столбец вследствие лексикографического порядка строк имеет вид 00... 011... 1, где число нулей и единиц известно. Поскольку строки зациклены, то пара, состоящая из последней и первой буквы каждой строки упорядоченной матрицы, содержится в слове x. Упорядочив множество пар мы получим предпоследний столбец упорядоченной матрицы. Аналогичным образом получая тройки, четверки и т. д. мы восстановим всю матрицу. Теперь, чтобы найти исходное слово x, нам нужен лишь номер строки упорядоченной матрицы, совпадающей со словом x. Таким образом, справедливо У т в е р ж д е н и е 52. Слово BW(x) и лексикографический номер слова x в соответствующей ему матрице вращений однозначно определяют слово x.

Нетрудно видеть, что преобразование Барроуза Уилера аналогичным образом можно определить для любого конечного алфавита A. Если рассмотреть слово x A, порожденное некоторым источником с контекстной моделью, то его преобразование BW(x) будет состоять из последовательности слов x(v1 )x(v2 )... x(vt ), где подслово, порожденное в состоянии vi, причем состояния vi лексикографиx(vi ) чески упорядоченны. Если энтропия источника сообщений мала и, следовательно, в каждом контексте имеется одна высоковероятная буква, то слово BW(x) можно эффективно сжимать интервальным методом и его модификациями.

Глава 7.

Сложность слова относительно программы В этой главе будут рассмотрены рекуррентные схемы (программы) сборки слова из подслов. Иногда, как в случае со схемой Лемпела Зива удобнее рассматривать схему разборки, которая взаимно однозначно соответствует обратной процедуре сборки. Описанные ниже алгоритмы вычислительно эффективны, т. е. для построения схемы сборки или, другими словами, вычисления кода для программы сборки слова, достаточно ограниченного числа операций, зависящего, конечно, от длины слова. Таким образом, можно эффективно вычислять сложность слов относительно этих программ. Более того, как будет показано ниже, эти схемы порождают эффективные методы кодирования слов.

А. Лемпелом и Я. Зивом была предложена следующая схема разделения слова на подслова. Через xr обозначим слово, состоящее из букв слова x = ai1... ain, начиная с l-ой и заканчивая r-ой, т. е. xr = ail... air. Разделим слово xn An на подслова i, i = 1,..., m по следующему правилу. Пусть начало слова xn уже разделено на подслова, т. е. представляет собой конкатенацию подслов 1 2... i1 и xn = 1... i1 xn. Выберем следующее подслово i = xli+1 так, чтобы слово xli+ было длиннейшим префиксом слова xn и уже содержалось как подслово в слове x1i+1, т. е. i = xli+1 i i aji, где di li. Каждое подслово i определяется тройкой чисел (di, li+1 li, ji ).

П р и м е р 16. Слово a1 a2 a2 a1 a2 a1 a1 a2 a1 a2 a1 a2 разделяется на подслова a1, a2, a2 a1, a2 a1 a1, a2 a1 a2 a1 a2 и кодируется последовательностью троек чисел (1, 1, 1), (2, 1, 2), (1, 2, 1), (2, 3, 1), (4, 5, 2).

Схема Лемпела Зива порождает программу PLZ, восстанавливающую слово по последовательности троек чисел. Чтобы двоичные коды натуральных чисел можно было однозначно разделять, первое число в каждой тройке целесообразно записывать в двоичном виде с использованием ровно log li битов1, второе можно кодировать произвольным префиксным кодом чисел натурального ряда, для записи третьего достаточно log |A| битов.

Отображение fLZ обратное программе PLZ называется кодированием Лемпела Можно использовать двоичную запись числа li дополненную слева нулями до длины log li.

Зива. Может существовать несколько различных кодов, которые программа PLZ переводит в одно слово w. Кодовым словом fLZ (w) будем считать то из них, которое построено в соответствии с приведённым выше алгоритмом.

У т в е р ж д е н и е 53. Пусть слово w A разделено на m подслов в соответствии со схемой Лемпела-Зива. Тогда где величина C зависит только от мощности алфавита.

Доказательство.

Рассмотрим тройку (di, li+1 li, ji ), кодирующую некоторое подслово. Из утверждения 36 следует, что для записи тройки чисел достаточно log li + log(li+1 li )+ +2 log log(li+1 li + 1) + 2 + log |A| битов.

Применяя неравенство Йенсена к функциям f1 (x) = log x, f2 (x) = log log(x + 1), получаем неравенства Определим условную сложность lLZ (u|w) слова u A относительно слова w A как количество подслов i в представлении слова wu = w1... m, где подслова i получены при разложении слова wu в соответствии с правилом Лемпела Зива.

В частности, lLZ (u|) количество подслов в разложении по правилу Лемпела Зива.

a) для любого слова u A и буквы a A справедливы неравенства lLZ (u|w) lLZ (au|w) и lLZ (u|w) lLZ (ua|w);

b) для любых слов u, v A справедливы неравенства lLZ (u|w) lLZ (vu|w) и lLZ (u|w) lLZ (uv|w).

З а д а ч а 21. Определим (u, w) = lLZ (u|w) + lLZ (w|u) 2 для пары слов u, w A. Докажите, что функция удовлетворяет всем свойствам расстояния (см., задачу 6).

Слово u называется максимальным суффиксом слова w A, если слово w представимо в виде w = vu, где u является либо подсловом слова v, либо буквой, отсутствующей в слове v, причем слово u имеет максимально возможную длину. Пусть w = = u(0)u(1)... u(m), где u(i) максимальный суффикс слова u(0)u(1)... u(i) при любом i = 0,..., m. Суффиксной сложностью слова w называется величина l (w) = m.

Рассмотрим схему разделения слова на подслова, совпадающую с описанной выше схемой Лемпела Зива, только без перекрытий и добавления к каждому выделенному подслову последней буквы2, которой не было в более раннем вхождении При первом вхождении буквы в слово однобуквенное подслово выделяется.

7.1. Схема Лемпела Зива этого подслова. Т. е. будем выбирать следующее подслово i = xli+1 так, чтобы слово xli+1 было длиннейшим префиксом слова xn и уже содержалось как подслоli во в слове xli 1. Обозначим через lLZ (u) количество подслов в представлении слова u A по этой схеме.

З а д а ч а 22. Докажите, что для любого слова u A справедливо равенство lLZ (u) = l (u).

lim mn = 0.

Отсюда видно, что |w| = n Cmn log mn, где C некоторая постоянная, зависящая только от мощности алфавита. Очевидно, что последовательность (mn ), а значит и последовательность (n ), n = log mn неограниченно возрастает при n. Тогда r(fLZ, P ) = 0.

Доказательство.

Обозначим через a0 некоторую букву, отсутствующую в алфавите A. Буква a будет играть роль запятой. Пусть слово x = 1... m разделено на подслова i в соответствии со схемой Лемпела Зива и x = 1... m, где i = i a0. Рассмотрим множество Sm перестановок длины m. При различных Sm слова y( ) = (1)... (m) различны, поскольку в соответствии со схемой Лемпела Зива все слова i получаются различными и не содержат добавочной буквы a0.

Количество различных перестановок y( ) не превосходит числа всевозможных различных перестановок букв в слове x, т. е.

где ri количество вхождений буквы ai, i = 0,..., k, в слово x. Учитывая, что r0 = m и количество вхождений буквы ai, i = 1,..., k, в словах x и x совпадает, из предыдущего неравенства и утверждения 5 имеем неравенства Тогда, применяя формулу Стирлинга и неравенство ln(1 + x) x при x > 1, получаем неравенство для эмпирической энтропии где C > 0 некоторая постоянная. Тогда из утверждения 53 и предыдущего неравенства имеем где число C зависит только от мощности алфавита, но не от распределения вероятностей P. Введём обозначение n = 4 mn log mn + C mn Из неравенства (7.1) и утверждения 31 получаем неравенства Поскольку lim t ln t = 0, из утверждения 54 следует, что lim n = 0.

А. Лемпел и Я. Зив доказали асимптотичекски нулевую избыточность кодирования fLZ для марковских источников с произвольной автоматной моделью.

Описанный выше метод кодирования нередко обозначают как LZ77 (статья с описанием метода была опубликована в 1977 году), чтобы отличить его от многочисленных модификаций, некоторые из которых описанны ниже.

Модификация схемы LZ77, предложенная П. Бендером и Дж. Вольфом заключается в том, что после нахождения длиннейшего подходящего подслова i в префиксе xli 1 слова x A нужно найти подходящее подслово i в слове xli длинное, не считая i. Вместо числа |i | нужно кодировать число |i | |i |. При декодировании, зная начало подслова i, нетрудно найти в слове xli 1 наиболее длинное подслово i, совпадающее с началом подслова i. Тогда длина подслова i легко восстанавливается из равенства Схема кодирования, предложенная А. Лемпелем и Я. Зивом в 1978 году отличается от LZ77 тем, что на каждом шаге выбирается наиболее длинное начало суффикса xn слова x A, которое совпадает с некоторым уже выделенным подслоli вом j, j < i, и к нему добавляется еще одна буква, т. е. i+1 = j api. Кодом подслова i+1 будет пара чисел (j, pi ). Например, слово a2 a1 a2 a1 a1 a2 a1 a2 a1 разделяется на подслова a2, a1, a2 a1, a1 a2, a1 a2 a1 и кодируется последовательностью пар чисел (0, 2), (0, 1), (1, 1), (2, 2), (4, 1). Этот метод удобно рассматривать как кодирование с динамическим словарем U. Сначала словарь U состоит из всех букв алфавита. На каждом шаге алгоритма отделяем от остатка кодируемого слова наиболее длинное слово y U и добавляем в словарь U все слова вида yai. Словарь U можно произвольным образом нумеровать и удалять из него слова, все продолжения которых уже имеются в словаре.

Ещё одна модификация кодирования Лемпела Зива предложена Т. А. Велчем.

Она отличается от последней схемы тем, что на каждом шаге в словарь добавляется только одно слово yai, где ai следующая за словом y буква в кодируемом слове x.

Кодирование Лемпела Зива и его модификации широко используются на практике. Достаточно сказать, что наиболее популярные семейства архиваторов arj, rar, zip основываются на алгоритме Лемпела Зива. Причиной широкого практического использования является высокая скорость выполнения этого кодирования. Существует алгоритм разделяющий слово w A на требуемые подслова i за линейное относительно длины слова w число операций над битами. Архиваторы, использующие арифметическое кодирование, в среднем уступают архиваторам, использующим кодирование Лемпела Зива, в скорости, но опережают их в степени сжатия сообщений.

7.2. Схема конкатенации 7.2. Схема конкатенации Схемой конкатенации слова w называется такая последовательность слов v(1),..., v(m) = w, что каждое слово v(i) является буквой или конкатенацией двух, встречавшихся ранее слов v(j1 ) и v(j2 ), т. е. v(i) = v(j1 )v(j2 ), где j1, j2 < i. Номера j1 и j2 могут совпадать. Аддитивной сложностью слова w называется величина l(w) = min m, где минимум берется по всем схемам конкатенации слова w.

Аналогичным образом можно определить аддитивную сложность l(M ) конечного множества M A, как минимальную длину схемы конкатенации, содержащей все слова из M. Непосредственно из определения схемы конкатенации вытекает У т в е р ж д е н и е 55. Пусть множество T A является множеством пометок вершин некоторого k-ичного дерева. Тогда l(T ) = |T | 1.

Докажем, что суффиксная сложность любого слова меньше аддитивной сложности того же слова.

Л е м м а 2. (Мерекин) Для любого слова w A справедливо неравенство l (w) l(w).

Д о к а з а т е л ь с т в о. Для однобуквенных слов неравенство очевидно справедливо. Пусть w A слово минимальной длины, для которого справедливо противоположное неравенство l (w) > l(w). Покажем, что для любого слова w найдётся такая схема конкатенации минимальной длины, что w = v(i1 )v(i2 ) и слово u = v(i2 ) является либо буквой, отсутствующей в слове v = v(i1 ), либо подсловом слова v.

Пусть для некоторой схемы конкатенации слова w минимальной длины это не выполняется, тогда слово u не участвует в схеме сборки слова v и не является буквой.

Поскольку u = v(i3 )v(i4 ), можно удалить из схемы конкатенации слово v(i2 ) = u, а слово v(i1 )v(i3 ) поставить на последнее место. Теперь w = v u, где v = v(i1 )v(i3 ), u = v(i4 ). Поскольку |u | < |u|, повторяя эту операцию некоторое число раз, придём к схеме конкатенации требуемого вида. Если u подслово слова v, то l (v) l (vu) 1.

Если u буква, отсутствующая в слове v, то l (v) = l (vu) 1. По предположению имеем l(v) l (v), тогда Пришли к противоречию.

Схему конкатенации будем называть правильной, если она удовлетворяет условию: слово v(i1 ) = v(j1 )v(j2 ) встречается в схеме конкатенации раньше слова v(i2 ) = v(j3 )v(j4 ), если max(j1, j2 ) < max(j3, j4 ). Перестройкой схемы будем называть такое переупорядочение последовательности, при котором последовательность остаётся схемой конкатенации.

У т в е р ж д е н и е 56. Любую схему конкатенации можно перестроить так, чтобы она стала правильной.

Д о к а з а т е л ь с т в о. Перестроим схему конкатенации следующим образом.

Сначала возьмём все используемые в схеме буквы алфавита и добавим в произвольном порядке все слова получающиеся конкатенацией двух букв. Потом добавим все слова, которые можно получить конкатенацией из букв и первого двухбуквенного слова v(i), затем все слова, которые получаются конкатенацией слова v(i+1) и любого из предыдущих слов. Ясно, что продолжая этот процесс мы получим правильную схему конкатенации, состоящую из тех же слов, что и первоначальная.

Каждое слово v(i) в схеме конкатенации задаётся парой чисел (j1, j2 ). Если схема конкатенации правильная, то последовательность из qi = max(j1, j2 ) является монотонной. Ниже будем рассматривать только правильные схемы. Целесообразно записывать вместо пары чисел (j1, j2 ) тройку чисел (qi qi1, ri, i ), где ri = min(j1, j2 ), а i указатель порядка конкатенации: i = 0, если v(i) = v(qi )v(ri ) и i = 1, если v(i) = v(ri )v(qi ). Будем считать, что q0 = 0, тогда число qi можно вычислить по Схема конкатенации порождает программу PSK, восстанавливающую слово по последовательности троек (qi qi1, ri, i ). Чтобы коды чисел можно было однозначно разделять, первое число в каждой тройке целесообразно кодировать произвольным префиксным кодом чисел натурального ряда, второе в виде двоичного представления с использованием ровно log qi битов, для записи третьего достаточно одного бита.

Каждому слову w A может соответствовать несколько правильных схем конкатенации. В качестве кода fSK (w) будем выбирать код, соответствующий одной из кратчайших правильных схем.

У т в е р ж д е н и е 57. Для любого слова w A справедливо неравенство где C некоторая константа.

Д о к а з а т е л ь с т в о. Рассмотрим тройку, кодирующую некоторое подслово (qi qi1, ri, i ). Из утверждения 36 следует, что для записи тройки чисел достаточно log qi + log(qi qi1 + 1) + 2 log log(qi qi1 + 2) + 3 бита. Здесь учтено, что величина qi qi1 принимает значение 0, поэтому префиксное кодирование натурального ряда следует применять к числу qi qi1 + 1.

Применяя неравенство Йенсена к функциям f1 (x) = log(x + 1), f2 (x) = log log(x + 2), получаем неравенства Таким образом, хотя аддитивная сложность слова и больше его суффиксной сложности, а значит число подслов в схеме конкатенации слова больше, чем в представлении Лемпела Зива, но для кодирования одного подслова в схеме конкатенации требуется не log |w|, а только log l(w) + C битов.

Т е о р е м а 15. Пусть A, P источник Бернулли. Тогда предельная избыточность кодирования fSK равняется нулю, т. е. r(fSK, P ) = 0.

q = log I. Рассмотрим множество слов Tq = {wa A | P (w) q, a A}. Как было замечено в § 6.6, множество Tq является множеством пометок вершин некоторого полного k-ичного дерева, где k = |A|. По определению множества Tq, для любого слова v L(Tq ) справедливы неравенства 7.2. Схема конкатенации где p0 = min P (a). Поскольку множество слов Tq соответствут полному k-ичному дереву, произвольное слово w A можно представить в виде конкатенации где wi L(Tq ) при всех i = 1,..., m1. Для упрощения рассуждений будем полагать, что и wm L(Tq ). Тогда из неравенства (7.2) имеем P (w) q m и, следовательно, m log 1. Из утверждений 46, 55 и неравенства (7.2) имеем l(Tq ) = |Tq | 1 <. Тогда по определению аддитивной сложности получаем неравенство Поскольку A, P источник Бернулли, то max P (w) (1 p0 )n 0 при n.

t 0 получаем где (n) 0 при n.

Из определения избыточности кодирования и утверждения 31 получаем З а д а ч а 23. Пусть NZ (n) множество циклических слов длины n в алфавите A, несодержащих подслова из множества Z, и lim log |NZ (n)| > 0. Докажите, что wNZ (n) Глава 8.

Недоопределённые данные Недоопределёнными данными называют последовательности, символы которых не вполне определены, например, известно, что на первой позиции в последовательности находится буква a1 или a2, на втором a2 или a4 и т. д. Недоопределённые данные рассматриваются если нам неизвестны точные данные или если нам не важны точные данные и подходит любое возможное доопределение исходной последовательности. Ниже рассматривается задача кодирования недоопределённых данных, которая состоит в том, чтобы каждой недоопределённой последовательности символов сопоставить двоичный код минимально возможной длины, так чтобы по коду можно было восстановить не саму исходную последовательность, а её произвольное возможное доопределение.

8.1. Энтропия недоопределённых данных Пусть A = {a1,..., ak } некоторый конечный алфавит. Определим множество T как множество подмножеств алфавита A. Буквы алфавита T можно рассматривать как события вероятностного пространства с множеством элементарных событий A.

Слова в алфавите T можно рассматривать как недоопределённые данные. Будем говорить, что буква aj A доопределяет ti T если aj ti. Соответственно слово aj1... ajn доопределяет слово ti1... tin, если ajm tim для любого m {1,..., n}.

Пусть P распределение вероятностей на T, а Q распределение вероятностей выражении HT |A (P, Q) обычно будем опускать.

Энтропией недоопределённых данных1 T относительно распределения P называется величина Энтропия разбиения является частным случаем энтропии недоопределённых данных, когда только одноэлементные подмножества ti имеют ненулевую вероятность.

H (T, P ) = H(A, P ).

Доказательство.

Это определение, а также все утверждения данной главы принадлежат Л. А. Шоломову (см.

[23].

8.1. Энтропия недоопределённых данных В этом случае справедливо равенство H(P, Q) H(P ) = DA (P Q). Из утверждения 6 имеем DA (P Q) 0 и DA (P Q) = 0 при P Q.

У т в е р ж д е н и е 59. Энтропия недоопределённых данных H (T, P ) неотрицательна, причём H (T, P ) = 0 тогда и только тогда, когда пересечение всех ti, для которых P (ti ) > 0 непусто.

Д о к а з а т е л ь с т в о. Неравенство 0 H (T, P ) непосредственно вытекает из определения энтропии.

Пусть a i ti, где пересечение берётся по всем событиям ti, для которых P (ti ) > 0. Определим распределение вероятностей Q на A равенством Q(a) = 1. Тогда H(P, Q) = 0.

Пусть равенство H(P, Q) = 0 достигается на некотором распределении Q0. Такое распределение найдётся, поскольку инфимум непрерывной функции достигается на любом компакте. Пусть t0 = {aj | Q0 (aj ) > 0}. Для любого события ti из P (ti ) > У т в е р ж д е н и е 60. Равенство H(P, Q) = H (T, P ) имеет место тогда и только тогда, когда причём строгое неравенство может иметь место только для тех j, для которых Q(aj ) = 0.

Доказательство.

такой точке (x1,..., xk ) = (Q(a1 ),..., Q(ak )), что H(P, Q) = H (T, P ).

на множестве U. Предположим qj > 0 для любого j = 1,..., k. Тогда известным необходимым условием экстремума функции на множестве U является равенство gradf (q) = grad( Предположим, что qj > 0 для любого j = 1,..., s, s < k и qj = 0 для любого j = s + 1,..., k. Аналогично предыдущему случаю имеем Пусть xs+1 (q) > 1. Тогда, используя дифференцируемость функции f по направлению внутрь множества U, имеем при 0 + 0. Тогда при достаточно малых > 0 имеем т. е. точка q не является максимумом функции f. Аналогично рассматриваются слуf чаи, когда xj (q) > 1 при произвольном j, j > s.

2) Достаточность (). Пусть в некоторой точке q U справедливы неравенства (8.1), т. е. xj (q) = 1 при qj > 0 и xj (q) 1 при qj = 0. Функция f выпукла вверх, поскольку функция ln x выпукла вверх, композиция выпуклой и линейной функции является выпуклой функцией и линейная комбинация (с положительными коэффициентами) выпуклых функций является выпуклой функцией. Пусть p U, тогда для любого [0, 1] из определения выпуклости вверх имеем Переходя к пределу при 0 + 0, имеем Доказательство.

Пусть Q(aj ) = P ({aj })/(1 P (A)) для любого j = 1,..., k. Тогда для любого j = 1,..., k. Из утверждения 60 получаем равенство Пусть M (r) T n множество слов состава r = (r1,..., rm ), т. е. в любом слове x M (r) имеется ровно ri букв ti при всех i = 1,..., m. Пусть P (ti ) = ri для любого 8.1. Энтропия недоопределённых данных Пусть M (r) T n. Существует такое множество D(n, r) An, что для любого x M (r) найдётся слово w D, которое доопределяет слово x, причём log |D(n, r)| = = nH (T, P ) + log n + C, где константа C зависит только от мощности алфавита T.

Д о к а з а т е л ь с т в о. Воспользуемся методом случайного кодирования. Пусть распределение вероятностей Q на A таково, что H (T, P ) = H(P, Q). Пусть слова w An порождаются источником Бернулли A, Q. Зафиксируем произвольное слово x T. Вероятность того, что слово w An доопределяет слово x равна i= ность того, что никакое из N случайных слов w An не доопределяет хотя бы одно то найдётся множество D(n, r) с требуемыми свойствами мощности |D(n, r)| = N.

Из неравенства ln(1 x) < x при x (0, 1) и утверждения 5 имеем Тогда, учитывая равенство H (T, P ) = H(P, Q), при таком N, для которого выполнено N 2nH (T,P ) H(T, P )n ln 2, будет справедливо неравенство pN < 1. Таким образом, найдётся требуемое множество D(n, r), причём log |D(n, r)| = nH (T, P ) + log n + C.

П р и м е р 17. Рассмотрим множество M (r), в котором каждое недоопределённое слово составлено только из таких ti T, которые включают ровно по s букв алфавита A, причём все такие ti T входят в слова из M (r) в одинаковом количестве по n/Ck вхождений. Пусть Q(a) = 1/k для любого a A. Для любого aj A имеем Тогда из утверждений 60 и 62 имеем Пример показывает, что достаточно примерно ( k )n слов для того, чтобы доопреs делить любое слово длины n, каждая буква которого допускает s различных доопределений.

ствующих множества подмножеств T1 и T2. Для разбиений T1 T2 и A1 A2 определим отношение a1 a2 t1 t2 тогда и только тогда, когда a1 t1 и a2 t2.

распределениях Q1 и Q2 соответственно. Опеределим Q(a1 a2 ) = Q1 (a1 )Q2 (a2 ). Используя формулу полной вероятности, покажем, что H2 (P, Q) = H(P, Q1 ) + H(P, Q2 ), где H2 (P, Q) = HT1 T2 |A1 A2 (P, Q).

ждения 62 в силу определения распределения Q имеем Причём строгое неравенство возможно лишь тогда, когда Q1 (a1 ) = 0 или Q2 (a2 ) = 0, т. е. когда Q(a1 a2 ) = Q1 (a1 )Q2 (a2 ) = 0.

Тогда из утверждения 62 заключаем, что 8.2. Энтропия разбиения, при заданной точности воспроизведения Рассмотрим задачу сложности воспроизведения данных с некоторой точностью.

Пусть имеется вероятностное пространство, F, P и два, заданных на нём разбиения A = {a1,..., ak1 } и B = {b1,..., bk2 }. Точность приближения разбиения B разбиением A определяется множеством допустимых совместных распределений W случайных величин, задающих разбиения A и B, т. е. предполагается, что набор вероятностей {P (ai, bj )} должен удовлетворять некоторым заранее заданным условиям.

8.2. Энтропия разбиения, при заданной точности воспроизведения разбиения B при заданной точности воспроизведения W (W -энтропия).

Рассмотрим в качестве пространства событий множество бесконечных слов в алфавите B. Предположим, что множество распределений W, в частности, налагает требование AB = B на допустимые распределения A. Другими словами элементами разбиения A являются непересекающиеся наборы букв алфавита B. Тогда Таким образом, в соответствии с теоремой Шеннона величина HW (B) является точной нижней гранью стоимости кодирования сообщений в алфавите B с допустимой точностью воспроизведения W. В дальнейшим подобная интерпретация величины HW (B, P ) будет обоснована для более широкого класса множеств W.

Предположим множество допустимых совместных распределений W (G) задано посредством двудольного графа G, долями которого являются два алфавита: A и B, причём AB W (G), если P (ai, bj ) > 0 только когда ребро (ai, bj ) G. В рассмотренном выше примере каждая вершина bj была инцидентна ровно одному ребру графа Пусть T = B есть множество подмножеств алфавита A. Рассмотрим граф E с долями A и T и рёбрами (ai, tj ) E тогда и только тогда, когда ai tj. Для краткости будем обозначать HW (E) через HE.

Доказательство.

1) Пусть I(A, T ) достигается на некотором допустимом разбиении A.

Тогда ции log x, из неравенства Йенсена имеем где распределение вероятностей Q определяется равенствами Q(aj ) = P (aj ) для любых j = 1,..., k. Таким образом, имеем HE (T, P ) H(P, Q) H (T, P ).

2) Предположим равенство H(P, Q) = H (T, P ) достигается на некотором распреP (ti )Q(aj ) в противном случае. Нетрудно видеть, что разбиение A определено корректно, т. е.

любого j = 1,..., k. Тогда Таким образом, имеем HE (T, P ) I(A, T ) = H(P, Q) = H (T, P ).

Нетрудно видеть, что утверждение 64 обобщается на любой граф G. Действительно, пусть G произвольный двудольный граф с долями B и A. Если вершина b инцидентна вершинам aj1, aj2,..., ajm, то переобозначим b = {aj1, aj2,..., ajm } T.

Вершины из B инцидентные одинаковым наборам вершин из A следует объединить и соответствующие им вероятности сложить. Следовательно множество вершин B графа G можно рассматривать как подмножество множества T.

З а д а ч а 24. Рассмотрим декартово произведение {1, 2,..., k}n и его подмножества вида {a11,..., a1s } · · · {an1,..., ans }, где aij {1, 2,..., k}. Пусть gs (n) минимальное число таких подмножеств, что их объединение покрывает всё множество {1, 2,..., k}n. Докажите, что lim log gs (n) = n log k (1 + o(1)) при n.

8.3. Кодирование недоопределённых данных Определение источника недоопределённых данных не отличается от данного ранее определения источника сообщений. Разница лишь в том, что сообщения источника в этом случае рассматриваются как недоопределённые и допускающие различные доопределения. Более высокая степень сжатия сообщений, когда они рассматриваются как недоопределённые данные, достигается за счёт возможности выбирать из различных допустимых доопределений самое простое.

Пусть A конечный алфавит и T множество подмножеств алфавита A. Отображение f : T {0, 1} называется кодированием источника недоопределённых данных T, A, P, если найдётся такое отображение g : (f (T )) A, что для любого слова x T слово w = g(f (x)) A является доопределением слова x. Отображение g будем называть декодированием источника недоопределённых данных.

Энтропией источника недоопределённых данных называется предел если он существует.

Покажем, что энтропия определена для стационарных источников недоопределённых данных.

1) Пусть последовательность чисел (xn ) удовлетворяет условию 0 xm+n xn + xm. Тогда существует конечный предел lim xn.

2) Пусть последовательность чисел (xn ), xn 0 удовлетворяет условию c xm+n xn + xm. Тогда существует конечный предел lim xn.

8.3. Кодирование недоопределённых данных 2) Вторая часть утверждения доказывается аналогично первой.

1) Для любого стационарного источника T, A, P существует конечный предел 2) Если T, A, P источник Бернулли, то для любого n N справедливы равенства 1) Неравенство xm+n xn + xm следует из утверждения 63. Тогда требуемое следует из утверждения 65.

2) Равенство xn+1 = xn + x1 = (n + 1)x1 для любого n N следует из утверждения 63.

У т в е р ж д е н и е 67. Если T, A, P источник Бернулли, то справедливо Д о к а з а т е л ь с т в о. Пусть x M (r) и распределения вероятностей Q и Q на A таковы, что H (T, P ) = H(P, Q) и H (T, P ) = H(P, Q ). Тогда Из утверждений 63, 64 и 66 имеем Стоимостью кодирования f источника недоопределённых данных T, A, P как и в случае обычного источника сообщений называются величины Без ограничения общности отображение g можно считать инъективным, поскольку если двоичные слова y = f (x) и y = f (x ) декодируются как одно слово w = g(y) = = g(y ), то отображение f не перестанет быть кодированием, если положим f (x) = f (x ), выбрав более короткое кодовое слово из двух, при этом стоимость кодирования может только уменьшиться. Определим распределение вероятностей на множестве слов A.

недоопределённых данных T, A, P. Тогда Cn (f, P ) = Доказательство.

Следующая теорема представляет собой аналог теоремы Шеннона для источника недоопределённых данных. В ней утверждается, что энтропия H ( T, A, P ) является точной нижней гранью количества битов, которые необходимо затратить для кодирования недоопределённых данных в расчёте на один символ исходной последовательности.

1) Для любого префиксного кодирования f стационарного источника недоопределённых данных T, A, P справедливо неравенство lim n Cn (f, P ) H ( T, A, P ).

2) Для любого источника Бернулли недоопределённых данных T, A, P найдётся такое префиксное кодирование f, что lim n Cn (f, P ) = H ( T, A, P ).

Доказательство.

1) Из теоремы Шеннона, определений и утверждений 63, 64, 68 имеем Домножая обе части неравенства на n и переходя к пределу при n, получаем требуемое.

эмпирическое распределение вероятностей, соответствующее набору r R(n), где R(n) множество всевозможных наборов частот букв в словах длины n. Как сказано в утверждении 62, существует такое множество D(n, r) An, что для любого x M (r) найдётся слово w D(n, r), которое доопределяет слово x, причём log |D(n, r)| = nH (T, P ) + log n + C. Пусть Nr : D(n, r) N некоторая нумерация множества D(n, r), а Nn : R(n) N некоторая нумерация множества R(n). Пусть w D(n, r) доопределяет слово x T n, тогда определим кодирование f равенством Кодирование f является префиксным, поскольку PBin является префиксным кодироm ванием натурального ряда. Нетрудно видеть, что |R(n)| = Cn+m1 < (n + m 1)m1, где m = |T |. Тогда из утверждения 36 и определения кодирования f имеем неравенство |f (x)| nH (T, P ) + Cm log n. Справедливы следующие асимптотические равенства при n Отметим, что построенное в доказательстве теоремы Шоломова кодирование является универсальным для множества всех источников Бернулли недоопределённых данных с фиксированным алфавитом.

Глава 9.

Передача сообщений по каналам связи, допускающим ошибки В этой главе рассматривается задача передачи сообщений, т. е. слов, порожденных некоторым источником, по допускающему ошибки каналу связи. Наиболее простым способом борьбы с ошибками при передаче сообщений является многократное повторение переданной буквы. Например, вместо сообщения 01101 можно передавать сообщение 000111111000111. Такой метод неэффективен, поскольку в несколько раз увеличивает длину сообщения при не очень значительном уменьшении вероятности его неправильного декодирования. Далее будет получена теоретическая оценка минимально возможного увеличения длины сообщений при кодировании, обеспечивающем чтобы вероятность ошибки декодирования после передачи сообщения по каналу связи не превышала сколь угодно малую заранее заданную величину.

9.1. Канал связи и его пропускная способность Дискретным каналом (связи) L называется пара из алфавита A = {a1,..., ak } на входе канала и алфавита B = {b1,..., bm } на выходе канала с набором условных вероятностей P (u|v) получения сообщения u B n при передаче сообщения1 v An.

Если имеется источник сообщений A, P с алфавитом A, то канал связи преобразует его сообщения в сообщения источника B, P, где вероятность порождения источником B, P сообщения u определяется по формуле Дискретный канал связи называется стационарным, если вероятность принять подслово u B при передаче подслова v A не зависит от места подслова в передаваемом сообщении, т. е. P (u|v) = P (bi1... bin ubin+1... bim |aj1... ajn vajn+1... ajm ), где сумма берётся по всевозможным префиксам и суффиксам фиксированной длины.

Дискретный канал называется каналом без памяти, если справедливо равенство Можно рассматривать и такие дискретные каналы, при передаче сообщений по которым изменяется число букв в сообщении.

88 Глава 9. Передача сообщений по каналам связи, допускающим ошибки Нетрудно видеть, что дискретный канал без памяти является стационарным и полностью определяется алфавитами A на входе и B на выходе канала и матрицей P переходных вероятностей pij = P (bi |aj ). Если мощности алфавитов A и B совпадают, иP единичная матрица, то канал не искажает сообщения. Заметим, что если по дискретному каналу без памяти передаются сообщения источника Бернулли, то источник сообщений на выходе канала также является источником Бернулли:

Введём обозначение cn = sup I(A, B ), где супремум берётся по всевозможным стационарным распределениям вероятностей на An, а вероятности на B n определяются по формуле (9.1). Другими словами, берётся супремум по всевозможным стационарным источникам сообщений на входе канала от взаимной информации между словами длины n на входе и выходе канала связи.

Пропускной способностью дискретного канала L называется предел если он существует.

У т в е р ж д е н и е 69. Для любого стационарного дискретного канала L существует конечный предел Д о к а з а т е л ь с т в о. Вначале покажем, что для любого разбиения B и независимых разбиений A1 и A2 справедливо неравенство Действительно, из утверждений 8, 9, 10 имеем H(A1 A2 |B) H(A1 |B) + H(A2 |B) и H(A1 A2 ) = H(A1 ) + H(A2 ). Тогда, используя определение взаимной информации, получаем неравенства Поскольку I(C, D) min{H(C), H(D)} для любых разбиений C и D, из утверждения 7 имеем cn /n min{log |A|, log |B|}. Покажем, что cm+n cn + cm для любых натуральных чисел n и m. Тогда существование конечного предела будет следствием утверждения 65. Пусть супремумы cn и cm достигаются на распределениях вероятностей Qn и Qm соответственно. Такие распределения найдутся по теореме о достижении максимального значения непрерывной функции на компакте. Определим распределение вероятностей Q(vw) = Qn (u)Qm (w) на множестве слов An+m. При таком определении разбиения An и Am оказываются независимыми. Здесь мы полагаем элементами разбиения An множества слов {uv | v Am } и элементами разбиения Am 9.1. Канал связи и его пропускная способность множества слов {uv | u An }. Используя стационарность канала связи и неравенство (9.4), получаем Определим дискретный канал с конечным числом состояний. Пусть заданы алфавит A = {a1,..., ak } на входе канала, алфавит B = {b1,..., bm } на выходе канала, S = {s} множество состояний и параметры канала связи p(b, s |a, s) вероятность получения b B и перехода канала связи в состояние s из состояния s после передачи буквы a A. Пусть задано некоторое начальное состояние s0, тогда переходные вероятности канала связи определяются рекуррентно равенствами Вообще говоря, дискретный канал с конечным числом состояний не является стационарным подобно тому как не всегда является стационарным марковский источник сообщений. Кроме того, разбиения B n зависят от выбора исходного состояния s0.

Определим величины cn = min I(An, B n |s0 = s). Аналогично доказательству утверsS ждения 69 можно показать, что для любого дискретного канала L с конечным числом состояний имеется предел c(L) = lim cn /n,. Стационарность канала связи использоn валась в доказательстве утверждения 69 только в неравенстве (9.5). Перепишем его для дискретного канала с конечным числом состояний И из утверждения 65 следует существование конечного предела c(L).

Аналогично определению неразложимого марковского источника, дискретный канал с конечным числом состояний называется неразложимым, если начиная с некоторой длины n для любого слова большей длины имеется ненулевая вероятность перевести канал из одного произвольного состояния в другое при передаче этого слова по каналу связи. Для неразложимого дискретного канала можно доказать (см., например, [4]) существование пропускной способности c(L) и равенство c(L) = c(L).

У т в е р ж д е н и е 70. Пусть L дискретный канал без памяти, тогда c(L) = c1 = max I(A, B), где максимум берётся по всевозможным распределениям вероятQ ностей на A.

Д о к а з а т е л ь с т в о. Из равенства (9.2) и утверждения 9 следует, что для пользуя утверждение 8 и симметричность взаимной информации, получаем соотношения I(An, B n ) = H(B n ) H(B n |An ) nH(B) nH(B|A) = nI(A, B) = nc1 для любого стационарного источника на входе канала связи. Таким образом, cn nc1.

Пусть величина c1 достигается при распределении вероятностей Q на A. Опредеn 90 Глава 9. Передача сообщений по каналам связи, допускающим ошибки любых слов aj1... ajn. Распределение вероятностей на выходе канала связи в соответствии с формулой (9.3) порождает источник Бернулли, знасчит H(B n ) = nH(B).

Тогда cn H(B n ) H(B n |An ) = nH(B) nH(B|A) = nc1.

У т в е р ж д е н и е 71. Пусть L канал связи без памяти с алфавитами A на входе и B на выходе канала. Если максимум max I(A, B) достигается на некотором распределении вероятностей P, то I(a, B) = I(A, B) для любой такой буквы a A, что P (a) > 0.

Доказательство.

что функция f достигает своего максимума на множестве что I(A, B) = c(L).

Пусть q = (q1,..., qk ) точка максимума функции f на U. Предположим qj > для любого j = 1,..., k. Тогда известным необходимым условием экстремума функk для любого j = 1,..., k. Тогда I(aj, B) = ( + 1)/ ln 2 для любого j = 1,..., k.

В случае когда в точке максимума q некоторые координаты равны нулю, т. е.

qj1,..., qjs = 0 для некоторых j1,..., js следует аналогичным образом рассмотреть условия максимума функции f на множестве U {qj1 = · · · = qjs = 0}.

В дальнейшем мы ограничимся рассмотрением каналов без памяти с алфавитами из двух букв на входе и выходе канала. Двоичный канал без памяти называется симметричным, если матрица P переходных вероятностей симметрична.

У т в е р ж д е н и е 72. Пусть L симметричный канал без памяти с алфавитами A = {a0, a1 } на входе и B = {b0, b1 } на выходе канала. Пусть P (b0 |a0 ) = P (b1 |a1 ) = = p, тогда c(L) = 1 + p log p + (1 p) log(1 p).

Д о к а з а т е л ь с т в о. Рассмотрим произвольный источник Бернулли A, P на входе канала и источник Бернулли B, P на выходе канала. Из определения условной энтропии имеем H(B|a0 ) = H(B|a1 ) = p log p (1 p) log(1 p) и H(B|A) = P (a0 )H(B|a0 ) + P (a1 )H(B|a1 ) = p log p (1 p) log(1 p).

Поскольку I(A, B) = H(B) H(B|A), то 9.2. Теорема кодирования для канала связи, допускающего ошибки Из утверждения 7 следует, что max H( B, P ) = 1 и он достигается при q = 1/ и P (b0 ) = P (b1 ) = 1/2. Тогда из утверждения 70 и равенства (9.6) получаем, что c(L) = max I(A, B) = 1 + p log p + (1 p) log(1 p).

9.2. Теорема кодирования для канала связи, допускающего ошибки Пусть задан некоторый канал связи, т. е. для любой пары слов одинаковой длины входного и выходного алфавита определена вероятность P (y|x) получения слова y B n при передаче по каналу слова x An. Предположим определён источник информации с алфавитом A, т. е. определены вероятности P (x) для всех слов x A.

Апостериорная вероятность передачи сообщения u An при условии получения сообщения v B n определяется по формуле Байеса Правило декодирования с минимальной вероятностью ошибки состоит в выборе такого u An, что P (u|v) = max P (x|v). Поскольку в формуле (9.7) знаменатель дроn би одинаков для всевозможных u An, то указанное правило эквивалентно выбору такого слова u An, что P (v|u)P (u) = max(P (v|x)P (x)).

Как правило, схема передачи сообщений по каналу связи предусматривает выбор некоторого множества кодовых слов, которые передаются по каналу связи с равной вероятностью. В этом случае правило декодирования с минимальной вероятностью ошибки совпадает с правилом декодирования по максимуму правдоподобия, состоящего в выборе такого слова u An, что P (v|u) = max P (v|x) для декодирования сообщения v B n.

Итак, предположим выбрано некоторое подмножество кодовых слов C An, которые предполагается передавать по каналу связи. Для каждого слова u C можно определить множество сообщений B(u) B n, которые будут декодироваться как u по правилу максимального правдоподобия. Если для какого-либо сообщения v B n максимальное правдоподобие max P (v|u) достигается сразу на нескольких словах u An, то считаем, что слово v не содержится ни в одном из множеств B(u) B n.

Вероятность неправильного декодирования по правилу максимального правдоподобия слова u An равна p(u) = Pr(ошибка|u) = P (y|u). Соответственно средняя вероятность ошибки передачи слов кода C An определяется как если предполагать одинаковою вероятность передачи для всех кодовых слов.

Далее будем рассматривать задачу передачи сообщений по двоичным симметричным каналам без памяти. Без ограничения общности можно считать, что вероятность ошибки при передаче буквы каналу связи не превышает 1/2, поскольку в противном случае буквы на выходе канала можно переименовать. Для любой пары слов одинаковой длины определим расстояние Хэмминга d(u, v) как число позиций, в которых 92 Глава 9. Передача сообщений по каналам связи, допускающим ошибки буквы слов u и v не совпадают. Из определения двоичного симметричного канала с вероятностью ошибки p нетрудно видеть, что P (u|v) = pd(u,v) (1 p)nd(u,v). Таким образом сообщение v {0, 1}n на выходе канала декодируется по правилу максимального правдоподобия как слово u C тогда и только тогда когда d(u, v) = min d(x, v), причём указанный минимум достигается на единственном слове u {0, 1}n.

ошибки p < 1/2, > 0 и Тогда для любого переданного по каналу L сообщения u An вероятность ошибки в более чем символах сообщения не превосходит /2.

Д о к а з а т е л ь с т в о. Рассмотрим случайную величину Из определения двоичного канала без памяти следует, что случайные величины i при i = 1,..., n независимы и одинаково распределены, причём Ei = p, Di = p(1p).

Из неравенства Чебышёва (A4, § 2) имеем Из равенств (A1, A3, § 2) следует, что E = nEi = np и D = nDi = np(1 p). Тогда Pr{ > } /2.

Пусть D семейство всех множеств C {0, 1}n мощности |C| M. Для канала L определим минимальную среднюю ошибку передачи данных p (M, n, L) = min p(C).

Т е о р е м а 17. (Шеннон) Пусть L двоичный канал без памяти, 0 < r < c(L) и Mn = 2nr. Тогда p (Mn, n, L) 0 при n.

Д о к а з а т е л ь с т в о. Зафиксируем некоторое натуральное число < n. Пусть B (x) = {y {0, 1}n | d(x, y) } множество слов длины n, отличающихся от слова x {0, 1}n не более чем в позициях. Нетрудно видеть, что величина b(, n) = |B (x)| не зависит от выбора слова x {0, 1}n. Из утверждения 3 имеем где h(p) = p log p (1 p) log(1 p). Определим функцию Рассмотрим произвольный код C D. Оценим вероятность ошибки при передаче сообщения u C. Пусть p1 (u) вероятность того, что при передаче сообщения u произошло более ошибок в двоичных символах, т. е. p1 (u) = P (y|u), а p2 (u) вероятность того, что принятое слово y {0, 1} находится на расстоянии меньшем или равным от некоторого слова v C, v = u. Тогда 9.2. Теорема кодирования для канала связи, допускающего ошибки Нетрудно видеть, что если не произошло ошибки ни одного из двух указанных видов, то по правилу максимального правдоподобия сообщение u будет декодировано правильно. Поэтому p(u) p1 (u) + p2 (u).

Для доказательства теоремы применим метод случайного кодирования. А именно, для того чтобы доказать существование кода C D, для которого P (C) <, покажем что среднее значение указанной величины для случайно выбранного кода не превосходит наперёд заданного > 0 при n.

Зафиксируем > 0, n N и определим = (p, n, ) в соответствии с формулой (9.9). Будем выбирать случайно2 и независимо из множества {0, 1}n i-е слово vi кода C. Тогда функции P (y|vi ) и f (y, vi ) будут случайными величинами относительно выбора кода C, причём независимыми при различных i = 1,..., |C|.

Из утверждения 73 следует, что при выборе = (p, n, ) для любого сообщения u {0, 1} справедливо неравенство p1 (u) /2. Тогда, оценивая математическое ожидания относительно случайных кодов, применяя формулу (9.11) и свойство (A2, § 2), имеем Тогда p (Mn, n, L) для достаточно больших n. Поскольку > 0 было выбрано произвольно, теорема доказана.

Заключение теоремы Шеннона о помехоустойчивом кодировании остаётся верным для произвольных стационарных каналов связи (см., например, [4]). Теорема Шеннона показывает, что по дискретному каналу связи с пропускной способностью c можно передавать сообщения со сколь угодно высокой точностью, при этом отношение количества передаваемой информации к числу переданных символов можно сделать сколь угодно близким к c. Действительно, пусть имеется источник сообщений с энтропией h, тогда по теореме кодирования Шеннона (см. § 6.3) исходное сообщение x длины n можно преобразовать в его код f (x) со средней длиной hn. Рассмотрим код C {0, 1}m, |C| = 2hn = 2mr, кодовые слова которого передаются по каналу связи с вероятностью ошибки меньшей заранее заданного числа. Установим взаимно однозначное соответствие между кодовыми словами f (x) и словами u кода C, тогда после передачи по каналу связи слова u мы можем однозначно восстановить исходное слово x. Таким образом, для передачи n букв исходного сообщения нам потребовалось передать в среднем m = hn/r двоичных символов по каналу связи, где число r В выбранном коде C могут встретиться одинаковые слова под разными номерами.

94 Глава 9. Передача сообщений по каналам связи, допускающим ошибки можно выбрать сколь угодно близким к пропускной способности канала c. Другими словами, если имеется некоторый физический канал со скоростью передачи двоичных символов v бит/сек, то скорость передачи информации по нему можно сделать сколь угодно близкой к величине vc бит/сек.

В теореме Шеннона о помехоустойчивом кодировании доказано существование, но не указано способа построения кода C с требуемыми свойствами. Такой код C, что множества Bd (x) для различных кодовых слов x C не пересекаются, называется кодом, исправляющим d ошибок. Область теории информации, занимающаяся построением и изучением свойств таких кодов называется теорией (помехоустойчивого) кодирования. Для знакомства с этой теорией можно рекомендовать книги [11], [17], [18].

9.3. Обращение теоремы о помехоустойчивом кодировании В этом разделе будет доказано, что невозможно передавать информацию по каналу связи со скоростью превышающей ту, которая определяется его пропускной способностью. Точнее будет показано, что в этом случае вероятность средней ошибки декодирования кодового слова не может быть меньше некоторой положительной константы.

Пусть задан некоторый канал связи, т. е. для любой пары слов одинаковой длины входного и выходного алфавита определена вероятность P (y|x) получения слова y B n при передаче по каналу слова x An. Предположим определены вероятности P (x) для всех слов x A и определена какая-либо процедура декодирования, т. е. определена функция g, ставящая в соответствие сообщениям в выходном алфавите B слова во входном алфавите A. В частности, как это было описано в предыдущем разделе, можно определить множество кодовых слов C An, придав им одинаковые вероятности и нулевые вероятности некодовым словам. Определим разбиение E = {e, e}, где событие e будет означать правильное декодирование e = {(g(y), y) | y B n }, а его дополнение событие e ошибку декодирования.

Ясно, что P (e|y) = P (x)P (y|x).

Т е о р е м а 18. (Фано) Пусть c пропускная способность дискретного стационарного канала, c cn для любого n N и энтропия стационарного источника сообщений A, P удовлетворяет неравенству H( A, P ) > c. Тогда вероятность ошибки при передаче сообщений источника A, P по каналу не меньше некоторой константы p0 > 0.

Доказательство.

Мы можем однозначно определить исходное сообщение по полученному если не было ошибки, поэтому H(An |B n e) = 0. Применяя утверждение 7 имеем H(An |B n E) = P (e)H(An |B n e) + P (e)H(An |B n e) P (e)n log |A|.

Из утверждения 8 и определения разбиения E получаем равенства H(An E|B n ) = H(An |B n E) + H(E|B n ) и Тогда для взаимной информации получаем неравенство 9.4. Избыточность универсального кодирования как пропускная способность некоторого канала Из определения энтропии источника сообщений следует, что H(An ) > c n для любых n и некоторого c > c. Из определения пропускной способности канала связи имеем I(An, B n ) cn n < cn. Тогда из неравенства (9.12) получаем неравенства В качестве следствия теоремы Фано нетрудно получить утверждение обратное теореме Шеннона.

У т в е р ж д е н и е 74. Пусть L двоичный канал без памяти, c(L) < r и Mn = 2. Тогда p (Mn, n, L) p0 > 0 при любом n.

Д о к а з а т е л ь с т в о. Рассмотрим произвольный код C {0, 1}n, |C| M n.

Формула (9.8) для вычисления p(C) средней вероятности ошибки, подразумевает, что кодовые слова используются при передаче по каналу с равной вероятностью, т. е.

в этом случае p(C) = P (e). Из утверждения 7 имеем H(An ) = log |C| = rn > c(L)n.

Тогда p(C) p0 > 0.

9.4. Избыточность универсального кодирования как пропускная способность некоторого канала деляет источник Бернулли с алфавитом B и вероятностями букв P (bi ) = ti при ство множества U. Определим на множестве T дискретную вероятностную меру, т. е. зададим числа (t) 0, t = (t1, t2,..., tk1 ) T так чтобы (t) = 1. Нетрудно видеть, что дискретную вероятностную меру : T [0, 1] всегда можно считать заданной на всём множестве U, доопределив во всех точках множества U \T нулём.

Множество всех дискретных мер на U будем обозначать через, а множество тех из них, которые равны 0 вне T будем обозначать через (T ).

Для любого слова x B обозначим через Pt (x) = P (x|t) вероятность слова x относительно источника Бернулли, заданного набором вероятностей t U. Тогда P (bi1... bin |t) = ti1 · · · tin. Таким образом, определён дискретный канал связи без памяти с входным алфавитом T и выходным алфавитом B. Заметим, что по-существу задача декодирования сообщений, передаваемых по такому каналу связи, рассматривалась в главе 4, когда по сообщениям требовалось распознать статистические характеристики их источника. Обозначим распределение вероятностей на словах алГлава 9. Передача сообщений по каналам связи, допускающим ошибки Обозначим пропускную способность рассматриваемого дискретного канала без памяти через cn (T ) = sup I(T, B n ). Определим величину которую можно рассматривать как пропускную способность канала связи с бесконечным входным алфавитом U. Отметим, что при задании источника набором параметров подразумевалась модель Бернулли, для обозначения которой ранее использовался символ B. Поэтому величину cn правильнее обозначать через cn (B).

Пусть n (B) = inf sup DB n (Pt Q) максимальная избыточность универсального кодирования источников Бернулли с алфавитом B, которая была рассмотрена в § 6.8.

Т е о р е м а 19. (Рябко) Для любого натурального числа n cправедливо равенство cn (B) = n (B).

Доказательство.

Рассмотрим произвольное конечное множество T U. Из утверждения 71 следует, что для распределения T, на котором достигается супремум cn (T ), справедливо равенство для любого набора t T. Для любых распределений вероятностей Q на B n и на U имеем равенства Тогда для любого распределения вероятностей Q на B n из утверждения 6 получаем неравенство Рассмотрим произвольное число > 0 и такое конечное множество T U, что cn (T ) + > cn = cn (B) и n (B) = n < inf sup DB n (Pt Q) +. Выбрать такое мноQ tT жество T возможно, так как без ограничения общности можно ограничиться только теми распределениями Q, для которых Q(x) > > 0 для всех x B n, а на суженном множестве распределений семейство отображений DB n (Pt Q) как функций Обычно в качестве множества рассматривают множество всех вероятностных мер на U, а не только дискретных. Здесь используется такое сужение множества мер, посколько оно не меняет значение величины cn и упрощает дальнейшие рассуждения.

9.4. Избыточность универсального кодирования от переменной t является равностепенно непрерывным. Поскольку множество параметров U компактно, найдётся распределение Q0, для которого inf sup DB n (Pt Q) = = sup DB n (Pt Q0 ).

Для одноэлементного множества T = {t} и определённой на нём вероятностной меры верно равенство DB n (Pt Q) = E DB n (Pt Q). Кроме того, максимум всегда больше либо равен чем среднее значение, т. е. sup DB n (Pt Q) E DB n (Pt Q) для любых и Q. Используя неравенство (9.15), получаем неравенства Используя неравенство (9.14), получаем нервенства Поскольку > 0 выбрано произвольно, имеем требуемое равенство cn = n.

Можно заметить, что в доказательстве теоремы нигде не используется формула для вычисления Pt (x), поэтому теорема остаётся верной для любого параметрического множества источников, в частности, для марковских источников с произвольной моделью. А именно, справедлива формула inf sup DB n (Pt Q) = sup E DB n (Pt Q ), где T произовольное дискретное (или приближаемое дискретным) семейство параметров. Эта формула указывает конструктивный метод вычисления точной теоретической границы избыточности универсального кодирования для параметрического семейства источников.

Предметный указатель вероятностное пространство 10 Шеннона декодирование недоопределённых данных по максимуму правдоподобия 91 лемма избыточность кодирования 46 марковская цепь информационная дивергенция 11 непериодическая с конечным числом состояний 89 автоматная недоопределённых данных 84 независимые равноблочное на выходе 53 период состояния преобразование Барроуза Уилера 69 вычислимая (программа) префикс пропускная способность разбиение расстояние Хэмминга слово сложность аддитивная колмогоровская относительно вероятности относительно модели относительно программы стохастическая 27, суффиксная случайная величина дискретная событие состояние автомата выходное марковской цепи стоимость кодирования cхема Лемпела Зива конкатенации сходимость в среднем по вероятности теорема Колмогорова 3, Кричевского Лемпела и Зива Рабина и Скотта Риссанена Рябко 67, Фано Ходака Шеннона 46, Шоломова Штарькова эргодическая трансфер-матрица формула Байеса полной вероятности Стирлинга функция Именной указатель А. Н. Колмогоров 3, Р. Е. Кричевский 63, В. И. Левенштейн А. Лемпел 71, 71, 73, Й. Риссанен 27, 57, К. Шеннон 11, 46, 49, Литература [1] Березнюк С. Л. Лекции по теории алгоритмов.

http://www.math.nsc.ru/LBRT/logic/aml/programs/index-w.html [2] Боровков А. А. Теория вероятностей. М.: Эдиториал УРСС, 1999.

[3] Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных.

Устройство архиваторов, сжатие изображений и видео. М.: Диалог МИФИ, [4] Галлагер Р. Теория информации и надежная связь. М.: Советское радио, 1974.

[5] Гоппа В. Д. Введение в алгебраическую теорию информации. М: Наука, 1995.

[6] Колмогоров А. Н. Три подхода к определению понятия количество информации // Проблемы передачи информации. 1966. т. 1, № 1. С. 3–11.

[7] Колмогоров А. Н. Теория информации и теория алгоритмов. М.: Наука, 1987.

[8] Кричевский Р. Е. Сжатие и поиск информации. М.: Радио и связь, 1989.

[9] Кричевский Р. Е. Лекции по теории информации. Новосибирск: Изд-во НГУ, [10] Лидовский В. В. Теория информации. М.:Компания Спутник+, 2004.

[11] Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов исправляющих ошибки.

М.: Связь, 1979.

[12] Марков А. А. Введение в теорию кодирования. М.: Наука, 1982.

[13] Натан А. А., Горбачёв О. Б., Гуз С. А. Основы теории случайных процессов.

М.: МЗ-Пресс, 2003.

[14] Нильсен М., Чанг И. Квантовые вычисления и квантовая информация. М.: Мир, [15] Потапов В. Н. Теория информации. Кодирование дискретных вероятностных источников. Новосибирск: Изд. центр НГУ. 1999.

[16] Потапов В. Н. Обзор методов неискажающего кодирования дискретных источников // Дискрет. анализ и исслед. операций. Сер. 1. 1999. Т. 6, № 4. C. 49–91.

[17] Сидельников В. М. Теория кодирования. М.: Физматлит, 2008.

[18] Соловьёва Ф. И. Введение в теорию кодирования. Новосибирск: Изд-во НГУ, [19] Стэнли Р. Перечислительная комбинаторика. М.: Мир, 1990.

[20] Фано Р. Передача информации. Статистическая теория связи. М.: Мир, 1965.

[21] Шеннон К. Е. Работы по теории информации и кибернетике. М.: Иностр. лит., [22] Шоломов Л. А. Основы теории дискретных логических и вычислительных устройств. М.: Наука, 1980.

[23] Шоломов Л. А. Информационные свойства недоопределённых данных // Дискретная математика и её приложения: Сборник лекций молодёжных научных школ по дискретной математике и её приложениям. Вып. IV. C. 26–50.

[24] Чисар И., Кёрнер Я. Теория информации: теоремы кодирования для дискретных систем без памяти. М.: Мир, 1985.

[25] Яглом А. М., Яглом И. М. Вероятность и информация. М.: Наука, 1973.