Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
Задачи и дополнения
1. Каково минимальное число слов полного двоичного префиксного кода с максимальной длиной L? Какими будут длины кодовых слов такого минимального кода? (Ответы на эти вопросы подска-вывает рис. 9.)
Решить те же вопросы в случае d-ичного кода.
2. Доказать, что префиксный код является полным тогда и только тогда, когда в неравенстве Крафта достигается равенство:
Указание. То, что из предыдущего равенства вытекает полнота, очевидно. Для доказательства обратного утверждения следует предположить, что неравенство (6) строгое, Тогда из него выводится
30строгое же неравенство
nL < dL — dL-1n1~dL-in2~dnL^b
которое показывает (почему?), что можно добавить по крайней мерс еще одно слово, не нарушая префиксности.
3. Утверждение предыдущей задачи допускает следующую забавную интерпретацию, являющуюся одновременно и его доказательством (она заимствована из книги [6]).
Рассмотрим дерево, соответствующее полному префиксному коду. Представим себе, что на это дерево взбирается обезьяна. Начав с корня, она наугад выбирает любую из d исходящих из него ветвей; вероятность такого выбора равна 1 Id. Добравшись до очередной развилки, обезьяна снова наугад выбирает некоторую ветвь с вероятностью Ud (напомним, что из каждой промежуточной вершины дерева полного кода исходит ровно d ветвей). Тогда вероятность того, что обезьяна достигнет какой-то определенной концевой вершины, находящейся на высоте k, равна (\id)k. Если таких вершин пто с вероятностью п^-к обезьяна остановится на высоте k. На какой-то Еысоте от 1 до L обезьяне придется
L
остановиться (вероятность этого равна 1). Поэтому ^ =
і
(В приведенном рассуждении мы использовали правила сложения и умножения вероятностей.)
4. Префиксный код с данными длинами кодовых слоз может быть построен далеко не единственным способом. Пусть d-ичный префиксный код (не обязательно полный) имеет пJ1 слов длины k (IcAcL). Доказать, что число различных таких кодов с фиксированными L и ид. равно произведению
/ d\ (&-йпЛ (,P-Pn1-HnA Ul/ V «2 / V «3 /
"' V nL J'
где =CJ — число сочетаний из і элементов по /.
Например, число двоичных префиксных кодов с L~4, ^i1=O, п2= 1, «з=2, и4=4 равно
delete^ — 4200.
5. Выше было доказано, что если для чисел Z1, I2, . . /^выполняется неравенство Крафта, то существует префиксный код с длинами li, I2, . . ., Itf. Найти этот код можно, строя этаж за этажом его кодовое дерево. Другой более удобный метод решения этой задачи был придуман Шенноном, и (применительно к двоичным кодам) он состоит в следующем.
Пусть числа li, I2, , . ,, /jv удовлетворяют неравенству
N і 2 2" і= 1
Можно считать, что /і</2<. , Рассмотрим последовательность
чисел
/-1 , .V-I
?1 = 0; ?, = 2-''; ?,= 2 2~ '» •••• ^= 2 2"
i=l I= 1
31Заметим, что все эти числа заключены в пределах 0поэтому каждое из них может быть представлено двоичной дробью вида ' п
2 где каждое ak есть 0 или 1. При этом из (7) можно заклю-
к= 1
чить, что все эти дроби конечны, и двоичная запись для q: имеет не более Ij значащих цифр. Таким образом, любое число qj однозначно представимо в ввде:
1J
"J= S о*/2"'. ? = 1
где всякое Cij есть О или 1. Следовательно, каждому qj однозначно отвечает слово Uy=ClyC2/ . . . C1- длины Ij. Рассмотрим код 1/=(?, u2, ...
..., чдг}- Покажем, что он обладает свойством префикса. Пусть Vj- и Vk два
слова (?>/). Тогда, согласно (7), qk—/, а это означает, что Ij-й символ слова Vj не совпадает с Ij-м символом слова vk. Следовательно, Vj не является началом Vk, откуда и вытекает префиксность кода V.
Разъясним сказанное на примере. Построим префиксный код с длинами слов Z1=I, Z2=Z3= 3, '4=4. В этом случае
п 1 • 5 3
<71 = 0, ?2 = у . <7з = -§-; <74=
Двоичная запись этих чисел с нужным числом I,- знаков следующая:
1,0,0 1:0.1
<7i = 'J, <?2—у-+-gT-r-gT; = -2" і "p-'p-gj ;
-Ij-A. і Ai А
<74 2 ! 22 2а 24 '
В результате мы получим искомый код:
U1=O; V2= 100; H3=IOl; O4= 1100.
6. Используя метод Ше. .юна, найти префиксные коды с указанными ниже длинами слов:
а) Z1=Z2= 2; L=Ii= 3; Z5=Z6=Z7= 4;
б) Z1=I; Z2= 2; I3= Z4= I = Z6= 4.
Построить кодовые деревья для полученных кодов. Определить, какой из этих кодов является полным.
6. ОПТИМАЛЬНЫ ft КОД
Как уже говорилось, общее правило при построении экономного кода следующее: чаще встречающиеся сообщения нужно кодировать более короткими кодовыми словами, а более длинные слова использовать для кодирования редких сообщений. Это правило и было реализовано в рассмотренном выше методе кодирования Фано. Но всегда ли метод Фано приводит к наиболее экономному коду? Ока-
32зывается, нет. Способ построения оптимального кода, который мы здесь изложим, потребует от нас более тонких рассуждений.
Пусть сообщения Ai, ... , /4jV имеют вероятности Pг» ¦•• , Pn (Pi^P^-'-^Pn) и кодируются двоичными словами G1, ai, ... , aN, имеющими длины Z1, 1$, ... , lN. Постараемся выяснить, какими свойствами должен обладать двоичный код, если он оптимален.