Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
1. В оптимальном коде менее вероятное сообщение не может кодироваться более коротким СЛОВОМ, Т. е. если Pi<. <pj, ТО
Действительно, в противном случае поменяем ролями кодовые обозначения для Ai и Aj. При этом средняя длина кодовых слов изменится на величину
Pili+Pih—Pilj—Pili = (Pi—Pj)(l;—h)> 0.
т. е. уменьшится, что противоречит определению оптимального кода.
2. Если код оптимален, то всегда можно так перенумеровать сообщения и соответствующие им кодовые слова, что Рі^Р^-.-^Pn и при этом
/!</»<•..</*. (1)
В самом деле, если pi~>pi + ь то из свойства 1 следует, что h^h + i- Если же Рі=Рі + і, но /;>/; + і. то переставим сообщения Ai и Ai+1 и соответствующие им кодовые слова. Повторяя эту процедуру нужное число раз, мы и получим требуемую нумерацию.
Из неравенств (1) следует, что сообщение An кодируется словом aN наибольшей длины lN.
3. В оптимальном двоичном коде всегда найдется, по крайней мере, два слова наибольшей длины, равной lN, и таких, что они отличаются друг ст друга лишь в последнем символе.
Действительно, если бы это было не так, то можно было бы просто откинуть последний символ кодового слова aN, не нарушая свойства префиксности кода. При этом мы, очевидно, уменьшили бы среднюю длину кодового слова.
Пусть слово at имеет ту же длину, что и aN и отличается от него лишь в последнем знаке. Согласно свойствам 1 и 2 можно считать, что lt=lt + 1=...=lN. Если t=?N—1, то можно поменять ролями кодовые обозначения at и ь не нарушая при этом неравенств (1).
Итак, всегда существует такой оптимальный код, в котором кодовые обозначения двух (наименее вероятных)
2 М. И. Аглвнов, Л. Б. Садовский
33 сообщений ЛJV--I и An отличаются лишь в последнем символе.
Отмеченное обстоятельство позволяет для решения задачи рассматривать только такие двоичные коды, у которых кодовые обозначения aN_і и aN для двух наименее вероятных сообщений Л//-і и An имеют наибольшую длину, отличаясь лишь в последнем символе. Это "N-7 Qn ЗНачит, что концевые вершины aN_i и aN кодового дерева искомого кода должны быть соеди-,а нены с одной и той же вершиной а предыдущего
j «этажа» (см. рис. 12).
Рассмотрим новое множество сообщений Рис. 12. Aw={Ai, Аг, ... , /4jv_2. А} с вероятностями Pu Ph ¦¦¦ , pN-h P—Pn-1+Pn- О™ получается из множества {лі, A2, ... , An^2, ^n) объедине-
нием двух наименее вероятных сообщений лдт-ь An в одно сообщение л. Будем говорить, что л(1> получается сжатием из [A1, л 2, ... , л^_2, л дг_ f, лдг).
Пусть для Л(1) построена некоторая система кодовых обозначений Ka)={alt а2, ... , aN_2, ?}> иными словами, указано некоторое кодовое дерево с концевыми вершинами (ц, аг, ••¦ > aN-г. ct. Этой системе можно сопоставить код К. = [сч, CL2, -¦ > CLn-2, CLn „і, aN} для исходного множества сообщений, в котором слова ал--х и aN получаются из слова а добавлением соответственно 0 и 1. Процедуру aN-f <%• перехода от Кш к К назовем расщеплением.
V Справедливо следующее утверждение, откры-
вающее путь для построения оптимального
Jct кода:
J Если код Kw для множества сообщений Л(!)
Рис. 13. является оптимальным, то оптимален также и код К для исходного множества сообщений.
Для доказательства установим связь между средними длинами I и І слов кодов К и Kw. Она, очевидно, такова:
I=V + P- (2)
Предположим, что код К не является оптимальным, т, е. существует код Ki со средней длиной Z1C/. Как отмечалось, можно считать, что концевые вершины ojv-ї и aN его кодового дерева (см. рис. 13) соответствуют кодовым обозначениям для наименее вероятных сообщений An^1U An. Тогда эти обозначения отличаются лишь в последнем символе. Рассмотрим код /Ci1'= {а*, ... , aN_2, а), в котором слово а получается из aN_j и aN отбрасыванием последнего сим-
34 вола. Средние длины Z1 и V1 связаны соотношением, аналогичным (2):
к = ^ + P-
Из неравенства lj<.l следует 1[<J', что противоречит оптимальности кода Kw. Утверждение доказано.
Теперь ясно, что для построения оптимального кода можно использовать последовательные сжатия исходного множества сообщений.
Проиллюстрируем процесс последовательных сжатий и расщеплений на примере множества из пяти сообщений с вероятностями P1=O,4; Pi=P3=Pi=Pi=OtIS. Процесс этот отражен в следующей таблице:
Таблица 12
Сообщения Вероятности и кодовые обозначения
Исходное множество Сжатые множества
Л(Ч АО Л(')
0,4 I 0,4 ! 0,4 1 -0,6 0
A2 0,15 010 ->0,3 00 0,3— 00 0,4 1
A3 0,15 011 0,15~ OIO1- ->0,3 J 01
Ai 0,15-; 000 0,15-1 OU
A6 0,15-! 001
Каждое из множеств Л(1\ Л(?\ Л(3) получается сжатием предыдущего множества. Множество Л(3> состоит из двух сообщений, поэтому оптимальный код /С1з) содержит два кодовых обозначения — 0 и 1. Последовательное расщепление Ki3) дает оптимальный код для исходной системы сообщений.
Средняя длина! кодовых слов, равная 0,4+4x3x0,15= =2,2, является, как это следует из предыдущего, минимально возможной для данного множества сообщений.
Описанный метод кодирования был предложен в 1952 г. американским математиком Д. А. Хаффменом и называется его именем. Сравним теперь оптимальный код из таблицы 12 с кодом Фано для того же множества сообщений, который строится ниже.
