Научная литература
booksshare.net -> Добавить материал -> Математика -> Аршинов М.Н. -> "Коды и математика (рассказы о кодировании) " -> 11

Коды и математика (рассказы о кодировании) - Аршинов М.Н.

Аршинов М.Н., Садовский Л.Е. Коды и математика (рассказы о кодировании) — М.: Наука, 1983. — 144 c.
Скачать (прямая ссылка): kodiimatematika1983.pdf
Предыдущая << 1 .. 5 6 7 8 9 10 < 11 > 12 13 14 15 16 17 .. 50 >> Следующая


Задачи и дополнения

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. Постараемся выяснить, какими свойствами должен обладать двоичный код, если он оптимален.
Предыдущая << 1 .. 5 6 7 8 9 10 < 11 > 12 13 14 15 16 17 .. 50 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed