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

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

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

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

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

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

Бит/символ

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

или %.

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

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

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

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

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

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

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

Расчет цифровой системы импульсно–фазового управления
Электрическая энергия вырабатывается на электрических станциях и передаётся потребителю главным образом в виде переменного трёхфазного тока промышленной частоты 50 Гц, однако как в промышленности, так и на транспорте имеются установки, для питания которых переменный ток с частотой 50 ...

Разделы

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