Равномерное по выходу кодирование.

Рассмотренные выше методы кодирования являются оптимальными в том смысле, что эти методы кодирования позво пиот затратить в среднем наименьшее число символов и «1» на одно сообщение.

Рис. 5.3 Принцип построения кода Хафмена

Однако и метод Хафмена, и метод Шеннона — Фано обладает следующими существенными недостатками:

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

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

Перечисленными выше недостатками не страдают так называемые равномерные коды. Эти коды используют для кодирования каждого сообщения одно и то же число символов «0» и «1», поэтому, если где-то произойдет ошибка, то она будет локализована именно в этом сообщении и на другие сообщения не распространяется. Опишем метод равномерного по выходу кодирования на примере, когда буквы входного алфавита появляются независимо с вероятностями , причем 1/2.

Предположим, что при кодировании допускается хотя и малая, но отличная от нуля вероятность ошибки. Рассмотрим множество всех блоков длины . Число таких блоков . Пусть — это подмножество блоков из таких, что для них выполнено неравенство

где k — число букв в блоке длины

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

Кодирование построим следующим образом. Рассмотрим множество блоков из «0» и «1», число которых равно числу элементов в (число элементов в обозначим ).

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

Среднее число символов «0» и «1», приходящихся на одну букву алфавита А, при этом кодировании равно Эта величина эквивалентна величине I, определяемой (5 3). Можно показать, что при , величина стремится к т. е. основная теорема К. Шеннона справедлива и при описанном выше кодировании.

При для передачи сообщения из букв потребуется символов «0» и «1», что примерно в 2 раза меньше, чем , при этом вероятность ошибки с ростом стремится к нулю.

Рассмотренные выше методы кодирования источников нашли свое применение в основном в факсимильной связи (см. гл. 10).