1.8. Оптимальное статистическое кодирование в канале без помех.

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

Пример источник независимых сообщений, который необходимо согласовать с двоичным каналом

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

Усреднив длительности, получим среднюю продолжительность сигнала:

.

Далее определим скорость передачи :

Пропускная способность двоичного канала равна:

.

Для того, чтобы приблизить скорость передачи к пропускной способности канала следует сообщения источника, имеющие большие априорные вероятности кодировать короткими комбинациями, а сообщения с малыми априорными вероятностями –длинными. Это правило построения оптимального статистического кода. Остановимся на некоторых его особенностях.

Во-первых, оптимальный код неравномерный; его комбинации имеют различное количество двоичных разрядов.

Во-вторых, такой код, хотя и повышает скорость передачи по каналу, совершенно не защищен от воздействия помех. Это не помехоустойчивый код.

1.9. Статистические коды Шеннона-Фано и Хаффмена

Для облегчения формирования кодовых комбинаций существуют алгоритмы Шеннона-Фано и Хафмена. Рассмотрим алгоритм статистического кодирования Хафмена. Заполняется таблица по следующему принципу.

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

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

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

4. По данным таблице строится граф с вершиной "1". Ребра графа отражают вероятности, причем ребру с большей вероятностью присваивается значение "1", а с меньшей – "0".

.Код сообщения получим проходя по ребрам от сообщения к вершине и фиксируя присвоенные значения.

Сообщение		Вспомогательные столбцы			Код
		1	2	3
	0.6	0.6	0.6	1	1
	0.15	0.25	0.4		00
Сумма	0.13	0.15			110
Сумма	0.12				010

По данным таблицы построим граф.

1.11. Энтропия канала с помехами, пропускная способность.

Рассмотрим смысл двойных сумм. Внутренняя сумма по i в первой - по смыслу частная энтропия при фиксированном , . Внешняя же сумма по j приводит нас к условной энтропии со знаком минус. Во второй двойной сумме действие над условной вероятностью дает 1, так как это составляет полную группу событий и она равна . Таким образом, получаем следующую формулу для энтропии канала с помехами:

, или

.

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

, (бит/знак*с).

Величина -пропускная способность канала.

Пропускная способность канала зависит от следующих факторов:

от статических свойств источника,

от интенсивности помех,

3. от полосы пропускания , которая определяет среднее время передачи сигнала.

В качестве примера найдем энтропию и пропускную способность двоичного канала. Его граф показан на рис.5.

Рис.5

Предполагаем , что длительность нулевых и единичных сигналов равны .

Тогда .

Согласно свойству энтропии и

Найдем информационные потери, ненадежность:

.

Выше обозначено: - ошибочный переход, - правильный переход. После чего получим

Если p₀=0, то и при p₀=0.5 , то есть передача невозможна.