4.Оптимальное эффективное кодирование.

Уменьшение избыточности сообщений называется их сжатием

Коды, предназначенные для сжатия информации, делятся на коды без потерь и коды с потерями.

Кодирование без потерь подразумевает абсолютно точное восстановление данных после декодирования и может применяться для сжатия любой информации.

Кодирование с потерями имеет обычно гораздо более высокую степень сжатия, чем кодирование без потерь, но допускает некоторое отклонение декодированных данных от исходных

Если известны вероятности появления символов входного алфавита, используются эффективные коды.

Сущность эффективного (статистического) кодирования заключается в минимизации средней длины кодового слова источника при одновременном выравнивании вероятностей появления “0” и “1” в закодированном сообщении.

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

Применительно к средней длине кодового слова источника, последнее равенство можно переписать в виде .

В общем виде минимальная средняя длина кодового слова источника символов.

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

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

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

Указанный недостаток устранен в коде Хаффмена,

5.Матнматическая модель дискретного канала

Дискретный канал (рис. 3.1) считается заданным, если известны алфавит m_A и априорные вероятности p(a_i) появления символов a_i на входе канала, скорость передачи символов по каналу v_k алфавит m_B на приемном конце и условные вероятности переходов p(b_k/a_i) для всех возможных пар (i,k), т.е. условные вероятности появления символов b_k при условии, что был передан символ a_i.

Рис. 3.1. Упрощенная модель дискретного канала

Основной задачей, решаемой на приеме, является определение символа a_i, который был передан, в том случае, если на приемном конце зафиксирован символ b_k. Это событие характеризуется величиной апостериорной вероятности p(a _i /b_k) или обратной вероятности.

Определение символа, который был передан по известному принятому, осуществляется по критерию максимума апостериорной вероятности:

max[p(a_i/b_k)]=p(a_j/b_k), (3.1)

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

Установление связи между абонентами, т.е. факт передачи символа по каналу, характеризуется совместным появлением символов b_k и a_i; вероятность этого события можно определить, используя данные

либо передающая, либо приемного концов.

p(b_k;a_i) = p(a_i )p(b_k/a_i ) = p(b_k) p(a_i/b_k).

Безусловные вероятности появления символов на передающем конце p(a_i) определяются на основе статистических свойств источника информации, а на приемном конце их можно рассчитать, зная свойства дискретного канала:

(3.3)

Апостериорная вероятность формально определяется по формуле Байеса:

(3.4)

Дискретный канал называется однородным, если для любых сочетаний a_i и b_k условные вероятности переходов не зависят от времени.

Если для каждой пары a_i и b_k условные вероятности не зависят от того, какие символы передавались и принимались ранее, то канал считается каналом без памяти.

Графически двоичные каналы передачи информации удобно изображать в виде прямого (рис. 3.2,а) и обратного (рис. 3.2,б) графов.