Статистическое кодирование

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

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

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

Для вычисления энтропии воспользуемся формулой (6.2):

Максимальная энтропия (6.5) при двоичном коде равна:

Бит/символ

Тогда коэффициент избыточности в соответствии с формулой (6.4)

или %.

Таким образом, получили достаточно низкий коэффициент избыточности (меньше 20%), значит не нужно применять статистическое кодирование.

Конструктивные методы построения эффективных кодов были даны впервые американскими учеными Шенноном и Фано. Их методики существенно не различаются и поэтому соответствующий код получил название Шеннона-Фано.

Код строят следующим образом: знаки алфавита сообщений выписывают в таблицу в порядке убывания вероятности. Затем их разделяют на две группы так, чтобы суммы вероятностей каждой из групп были по возможности одинаковы. Всем знакам верхней половины, в качестве первого символа приписывают 0, а всем нижним - 1. Каждую из полученных групп, в свою очередь, разбивают на две подгруппы с одинаковыми суммарными вероятностями и т.д. Процесс повторяется до тех пор, пока в каждой подгруппе не останется по одному знаку. Важным свойством кода Шеннона-Фано является то, что, несмотря на его неравномерность, здесь не требуется разделительных знаков. Это обусловлено тем, что короткие комбинации не являются началом наиболее длинных комбинаций. Основной принцип оптимального кодирования сводится к тому, что наиболее вероятным сообщениям должны присваиваться короткие комбинации, а сообщениям с малой вероятностью более длинные комбинации. Рассмотренная методика Шеннона-Фано не всегда приводит к однозначному построению кода. Ведь при разбиении на подгруппы можно сделать большей по вероятности, как одну, так и другую подгруппы.

От указанного недостатка свободна методика Хаффмана. Она гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.

Другие стьтьи в тему

Расчёт эффективности коротковолновой радиолинии на группе частот
К коротким волнам (КВ) относятся радиоволны с частотами 3…30 МГц (длинами волн 10…100 м соответственно). В отличие от более коротких волн, которые распространяются земной волной, декаметровые волны распространяются, в основном, путем отражения от ионосферы. Радиус действия земной вол ...

Регулятор мощности
На современном этапе научно-технического прогресса огромную роль играет развитие электроники. Электронная промышленность определяет научно-технический и экономический потенциал Республики Беларусь. В данную отрасль промышленности входит множество объединений, заводов, конструкторских ...