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

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

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

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

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

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

Бит/символ

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

или %.

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

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

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

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

Перейти на страницу: 1 2 3 4 5

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

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

Расчет параметров выпрямительно-инверторного преобразователя, выполненного по шестипульсовой мостовой схеме
Трёхфазный мостовой выпрямительно-инверторный преобразователь (ВИП) питается от сети с номинальным напряжением UС=U1Л и заданными пределами колебания этого напряжения %UС Известна мощность короткого замыкания SКЗ, характеризующая реактанс связи точки подключения ВИП и шин бесконечной ...

Разделы

Радиоэлектроника и телекоммуникации © 2018 : www.techelements.ru