Лекция 7. Способы построения двоичных кодов. Алфавитное неравномерное двоичное кодирование сигналами равной длительности. Префиксные коды.

1. Постановка задачи оптимизации неравномерного кодирования

2. Неравномерный код с разделителем

3. Коды без разделителя. Условие Фано

4. Префиксный код Шеннона–Фано

5. Префиксный код Хаффмана

1. Постановка задачи оптимизации неравномерного кодирования

При двоичном кодировании знаки первичного алфавита (например, русского) кодируются комбинациями символов двоичного алфавита (то есть «0» и «1»). В случае неравномерности кодирования длины кодов (комбинаций символов вторичного алфавита, представляющих буквы первичного алфавита) могут различаться. Соответственно, длительности передачи отдельных кодов тоже могут различаться. Длительности элементарных сигналов (например, импульсов и пауз) при этом одинаковы (). Очевидно, что для передачи информации, в среднем приходящейся на один знак первичного алфавита, необходимо время. Таким образом,задачу оптимизации неравномерного кодированияможно сформулировать следующим образом:

Необходимо построить такую схему кодирования, в которой суммарная длительность кодов при передаче (или суммарное число кодов при хранении) данного сообщения была бы наименьшей.

За счет чего возможна такая оптимизация? Очевидно, что суммарная длительность сообщения будет меньше, если применить следующий подход:

Тем знакам первичного алфавита, которые встречаются в сообщении чаще, присвоить меньшие по длине коды, а тем знакам первичного алфавита, частота которых меньше – присвоить коды более длинные.

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

Параллельно должна решаться проблема различимости кодов.

Допустим, что на выходе кодера (кодирующего устройства) получена, например, следующая последовательность элементарных сигналов:

00100010000111010101110000110

Каким образом такая последовательность элементарных сигналов может быть декодирована?

Если бы код был равномерным, приемное устройство (декодер) просто отсчитывало бы заданное (фиксированное) число элементарных сигналов и интерпретировало их в соответствии с кодовой таблицей.

При использовании неравномерного кодирования возможны два подхода к обеспечению различимости кодов.

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

Второй подходсостоит в применениипрефиксных кодов.

Ниже рассмотрим подробнее каждый из подходов.

2. Неравномерный код с разделителем

Условимся, что разделителем отдельных кодов букв первичного алфавита будет последовательность 00 (признак конца знака), а разделителем слов будет последовательность 000 (признак конца слова, он же – пробел). Таким образом, возможными оказываются, например, следующие правила построения кодов:

• Код признака конца знака не существует отдельно от знака, поэтому код признака конца знака может быть включен в код буквы. Поэтому коды всех букв будут заканчиваться на 00;

• Код любой буквы (кроме пробела) всегда должен начинаться с 1 (с единицы);

• Ясно, что разделителю слов всегда предшествует признак конца знака; при этом реализуется последовательность 00000 (пять нулей). Таким образом, если встречаются комбинации 000 или 0000, они не воспринимаются как разделитель слов. Таким образом, коды букв могут оканчиваться на 00, 000 или 0000 (до четырех нулей включительно).

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

Формула, по которой можно найти среднюю длину кода для русских букв при данном способе кодирования, имеет вид:

.

Для русского языка, как указывалось раньше, . Поэтому избыточность рассмотренного выше кода составляет:

.

Это означает, что при данном способе кодирования будет передаваться в виде кодов приблизительно на 14больше информации, чем содержит исходное сообщение.

Аналогичные вычисления для английского языка дают для средней длины кода для буквы первичного алфавита значение , что приприводит к избыточности кода в размере.

Табл. 5. Кодовая таблица для букв русского алфавита

Буква	Код			Буква	Код
Пробел	000	174	3	Я	1011000	18	7
О	100	90	3	Ы	1011100	16	7
Е	1000	72	4	З	1101000	16	7
А	1100	62	4	Ь, Ъ	1101100	14	7
И	10000	62	5	Б	1110000	14	7
Т	10100	53	5	Г	1110100	13	7
Н	11000	53	5	Ч	1111000	12	7
С	11100	45	5	Й	1111100	10	7
Р	101000	40	6	Х	11010100	9	8
В	101100	38	6	Ж	10101100	7	8
Л	110000	35	6	Ю	10110000	6	8
К	110100	28	6	Ш	10110100	6	8
М	111000	26	6	Ц	10111000	4	8
Д	111100	25	6	Щ	10111100	3	8
П	1010000	23	7	Э	11010000	3	8
У	1010100	21	7	Ф	11010100	2	8