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

Но из самой теоремы никоим образом не следует, как такое кодирование осуществить практически. Важно, что теорема открывает принципиальную возможность оптимального кодирования.

Возможны следующие особенности вторичного алфавита, используемые при кодировании:

- элементарные сигналы (0,1) могут иметь одинаковые длительности
(t₀ = t₁) или разные (t₀ ¹ t₁);

- длина кода может быть одинаковой для всех знаков первичного алфавита (такой называется равномерным) или же коды разных знаков первичного алфавита могут иметь различную длину (неравномерный код);

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

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

4.2 Алфавитное неравномерное двоичное кодирование сигналами равной длительности

Как следует из названия, в способах кодирования, относящихся к этой группе, знаки первичного алфавита кодируются комбинациями символов двоичного алфавита (0,1), причем длина кодов и, соответственно, длительность передачи отдельного кода могут различаться. Длительности элементарных сигналов при этом одинаковы (t₀ = t₁ = t).

Очевидно, для передачи информации, в среднем приходящейся на знак первичного алфавита, необходимо время К(А,2) × t.

Таким образом, задачу оптимизации неравномерного кодирования можно сформулировать так:

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

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

Параллельно должна решаться проблема различимости кодов. Представим, что на выходе кодера получена следующая последовательность сигналов «0010001000011101010111000011».

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

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

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

· применяются префиксные коды.

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

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

Довольно очевидными являются следующие правила построения кодов:

- код признака конца знака может быть включен в код буквы, поскольку не существует отдельно (то есть коды всех букв будут заканчиваться на 00);

- коды букв не должны содержать 2-х и более нулей подряд в середине (иначе они будут восприниматься как конец знака);

- код буквы всегда должен начинаться с 1;

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

В соответствии с перечисленными правилами построим кодовую таблицу для букв русского алфавита (таблица 4.1), основываясь на приведенных ранее в таблице 3.1 вероятностях появления отдельных букв.

Таблица 4.1 Неравномерный код с разделителем

Буква	Код	Частота P i ×103	Буква	Код	Частота P i ×103
пробел			я
о			ы
е			з
а			ь, ъ
и			б
т			г
н			ч
с			й
р			х
в			ж
л			ю
к			ш
м			ц
д			щ
п			э
у			ф

Средняя длина кода К(ru, 2) = .

Поскольку для русского языка I₁ ^r = 4,356 бит, избыточность данного кода составляет

Q(ru, 2) = - 1 = 0,14.

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

Аналогичные вычисления для английского языка К(en, 2) = 4,716, что при I₁ ^(e) = 4,036 бит приводит к избыточности кода Q(еn, 2) = 0,168.

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

Сообщение «МАМА МЫЛА РАМУ»

Построим таблицу повторений символов.

Символ	Число повторений	Вероятность	код
пробел		2/14
М		4/14
А		4/14
Р		1/14
Ы		1/14
У		1/14
Л		1/14

Средняя длина кода:

×3 + ×3 + ×4 + ×4 + ×5 + ×5+ ×5 = = 3.79.

Среднее количество информации на знак этого первичного алфавита

I = - = 2,518.

Избыточность кода = (50%).

4.2.2 Префиксное неравномерное кодирование

Возможно ли такое кодирование, которое не использует разделители? Существует ли оптимальный способ неравномерного двоичного кодирования?

Суть первого вопроса состоит в нахождении такого варианта кодирования, при котором последующее выделение из него каждого отдельного знака оказывается однозначным без специальных указателей разделения знаков.

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

Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом) какого-либо иного более длинного кода.

Например, если имеется код 110, то уже не могут использоваться коды 11, 1, 1101, 11001, и т.п.

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

Наиболее известны 2 схемы построения префиксных кодов.