Лабораторная работа №4 Эффективное кодирование сообщений. Коды Шеннона – Фано, Хаффмена

Цель работы: Изучение методов эффективного кодирования.

1. Краткие теоретические сведения

Задачи эффективного кодирования заключаются в следующем :

1. Запоминание максимального количества информации в ограниченной памяти.

2. Обеспечение максимальной пропускной способности источника сообщений.

Максимальное количество информации I, которое может передаться сигналом, определяется по формуле:

(1)

где m_y - количество состояний сигнала.

Фактический объем переносимой информации определяется энтропией его множества сообщений Н. В связи с тем, что в основном в передаваемом наборе сообщений присутствуют типичные последовательности, сообщения передаются с относительной избыточностью D:

(2)

Для уменьшения избыточности символов необходимо применить эффективное кодирование. Эффективным называется способ кодирования, при котором :

Не возникает потери информации.

Требуется минимальное количество кодовых символов.

Для выполнения второго условия используются неравномерные коды, где длина кодового слова обратно пропорциональна вероятности его появления в сообщении.

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

Эффективное кодирование достигается благодаря учету априорных статистических характеристик источника информации.

Предельные возможности эффективного кодирования определяются:

(3)

При неравновероятности сообщений канал оказывается несогласованным с источником информации, в результате чего он не используется в полной мере.

Например, если на вход двоичного дискретного канала поступают преимущественно нули, то реле, выступающее в роли дискретного демодулятора, практически всегда находится в обесточенном состоянии, т.е. без дела. Наоборот, в случае передач одних единиц реле будет под током всегда, и его можно было бы не ставить, закоротив выход канала. Таким образом, если считать, что скорость передачи через дискретный канал есть среднее количество информации, проходящее через канал в единицу времени, то в рассмотренных случаях она мала. С другой стороны максимальная пропускная способность ДК определяется через полосу пропускания непрерывного канала Δf_k и может быть определена:

бит,

где τ₀ - длительность одного символа.

Такая пропускная способность ДК будет реализована тогда, когда среднее количество информации, приходящееся на символ источника тоже максимально, например, если удельная энтропия двоичного источника равна 1 бит/символ.

Если энтропия источника меньше, канал недогружен даже в том случае, когда через него проходит 2Δfk символов в секунду. Производительность источника R будет меньше пропускной способности канала С.

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

В соответствии с определением, , где - энтропия источника, T - средняя продолжительность кодовой комбинации: , здесь n_i- длина i-ой кодовой комбинации.

Отсюда,

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

Алгоритм оптимального статистического кодирования предложили Фано и Хаффмен. Методика Фано заключается в следующем:

1. Подлежащие кодированию сообщения располагают в первом столбце в порядке убывания их вероятностей .

2. Сообщения разбиваются на две группы с примерно равными суммарными вероятностями. Группе, имеющей большую суммарную вероятность, приписывается наиболее вероятный символ кодовой комбинации, например - 0, второй группе - 1.

3. Сообщения, входящие в каждую из групп, вновь разбиваются на две группы с примерно равными вероятностями. И здесь, группе с большей вероятностью присваивается символ - 0, с меньшей - 1.

Этот процесс продолжается до тех пор, пока в каждой группе не останется по одному элементу.

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

Рассмотрим методику такого кодирования. Пусть статистика цифрового потока такова: вероятность нуля P(0)= 0,9, тогда P(1)=0,1 .По таблице приложения 1 определяем энтропию источника. Н=0,469 бит/символ. Скорость передачи значительно меньше пропускной способности канала. Для согласования источника с каналом Шеннон предлагает укрупнять кодируемые последовательности.

Закодируем сообщения группами из двух символов. Получим четыре сообщения, которые вместе с их вероятностями представим таблицей:

Таблица 1

00	0.81	0			0
01	0.09	1	1		11
10	0.09		0	0	100
11	0.01			1	101

Найдем энтропию источника, пользуясь той же таблицей приложения.

Н=0,246+0,312+0,312+0,066=0,938 бит/сообщение. Средняя длина кодовой комбинации n = 0,81+0,09 *2+ 0,09 *3+ 0,01 *3 = 1,29 сим./сообщ. Удельная энтропия источника равна энтропии источника сообщений, деленной на среднюю длину комбинаций: Н/n=0,727 бит/сим. Эта энтропия существенно выше, чем была получена ранее (0,469), соответственно, стала выше и скорость передачи информации. При кодировании группами из трех сообщений удельная энтропия будет еще больше, а при дальнейшем укрупнении кодируемых последовательностей скорость передачи будет как угодно близка к пропускной способности канала, т.е. к 1/τ.Естественно, повышение скорости требует соответствующих затрат.

Кодирующее устройство в соответствии с таблицей 6.1 работает следующим образом. При поступлении на его вход комбинации 00 оно выдает в линию связи 0, при комбинации 01 – 11 и т.д. При кодировании группами из трех символов кодирующее устройство становится сложнее, оно должно формировать восемь групп выходных символов. При изменении входной статистики схемы кодирования продолжают кодирование, но с меньшей скоростью.