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

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

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

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

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

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

Бит/символ

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

или %.

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

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

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

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

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

Разработка устройства управления на базе микроконтроллера AVR семейства Classic фирмы Atmel
Микропроцессором (МП) называют построенное на одной или нескольких БИС/СБИС программно-управляемое устройство, осуществляющее процесс обработки информации и управление им. МП - центральный процессорный элемент микропроцессорной системы, в которую также входят память и устройства вв ...

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