Статистическое (эффективное) кодирование

 

Для дискретных каналов без помех К.Шенноном была доказана следующая теорема: если производительность источникаR_И<C_-e,где e - сколь угодно малая величина, то всегда существует способ кодирования, позволяющий передавать по каналу все сообщения источника. Передачу всех сообщений при R_И>Cосуществить невозможно.

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

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

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

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

 

Количество информации

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

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

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

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

(6.1)

 

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

(6.2.)

 

Таким образом, определение количества информации в элементарном сообщении x_K сводится к вычислению логарифма вероятности появления (выбора) этого сообщения.

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

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

(6.3)

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

Энтропия источника сообщений.

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

(6.5)

Как видно из формулы, энтропия источника определяется распределением вероятностей выбора элементарных сообщений из общей совокупности. Обычно отмечают, что энтропия характеризует источник с точки зрения неопределенности выбора того или иного сообщения. Энтропия всегда величина вещественная, ограниченная и неотрицательная: H(x)>0.

Найдем энтропию источника сообщений:

m-объем алфавита дискретного источника = 2;

вероятность приема “1” (Р(1)) = 0,8;

вероятность приема “0” (Р(0)) = 0,2.

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

 

Производительность источника сообщений.

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

; (6.6)

воспользуемся данной формулой для вычисления производительности источника.

 

 

Статистическое кодирование элементов сообщения.

Осуществим статистическое кодирование трехбуквенных комбинаций, состоящих из элементов двоичного кода 1 и 0: 000, 001, 010, 011, 100, 101, 110, 111. Для кодирования воспользуемся алгоритмом неравномерного кодирования Хаффмана, что практически более удобно с целью повышения производительности. Для этого вычислим вероятности этих комбинаций и расположим их в порядке убывания вероятностей. Результаты вычислений и кодовые комбинации объединим в таблицу 2:

 

Таблица 2.

Символы	Z1	Z2	Z3	Z4	Z5	Z6	Z7	Z8
Кодовые комбинации
Вероятности	0,512	0,128	0,128	0,128	0,032	0,032	0,032	0,008

 

 

Составим сводную таблицу ветвления кодовых комбинаций.

Таблица 3.

Символ и нач. вероятность
Z1	0.512	0.512	0,512	0.512	0.512	0.512	0.512
Z2	0.128	0.128	0.128	0.128	0.232	0.256	0.488
Z3	0.128	0.128	0.128	0.128	0.128	0.232
Z4	0.128	0.128	0.128	0.128	0.128
Z5	0.032	0.04	0.064	0.104
Z6	0.032	0.032	0.04
Z7	0.032	0.032
Z8	0.008

 

Согласно таблицы 3 составляем граф кодового дерева, из точки «1» с вероятностью 1 направляем две ветви с большей вероятностью – влево, с меньшей – вправо. Такое ветвление продолжаем до тех пор, пока не дойдем до вероятности р каждой буквы.

 

 

Для наглядности построим кодовое граф-дерево.

 

 

Рисунок 14. Кодовое граф-дерево по методу Хаффмена.

 

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

 

Таблица 4.

Символы	Z1	Z2	Z3	Z4	Z5	Z6	Z7	Z8
Вероятность	0,512	0,128	0,128	0,128	0,032	0,032	0,032	0,008
Кодовые комбинации
Количество элементов
Произведение кол-ва эл-тов на вероятность	0,512	0,384	0,384	0,384	0,16	0,16	0,16	0,04
Энтропия источника	-0,494	-0,38	-0,38	-0,38	-0,159	-0,159	-0,159	-0,056

 

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

 

 

Определяем среднюю длину полученных кодовых комбинаций:

 

(6.7)

 

Полученные комбинации неравномерного кода фактически содержат информацию о трех элементах сигнала, поэтому разделив N_ср на 3 получим среднюю длину новых комбинаций в расчете на одну букву первоначального двоичного кода.

 

в результате получили среднюю скорость, меньше Т. Это и есть эффект, который даёт статистическое кодирование.

Энтропия сообщения источника

Поделив величину энтропии на новое значение средней длительности, найдем производительность источника после кодирования.

 

(6.8)

 

В результате производительность источника после статистического кодирования возросла в 13,7 раз.

Определим минимальную среднюю длину кодовой комбинации

 

(6.9)

 

Вычислим коэффициент избыточности

(6.10)

Как видно из этого выражения построенный код практически не имеет избыточности.

ПРОПУСКНАЯ СПОСОБНОСТЬ.

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

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

Пропускная способность канала будет вычисляться по формуле:

 

(7.1)

 

в частном случае для двоичного канала (m=2) получим формулу:

 

, где р =0.065014, Т=3,4*10^-6 (7.2)

 

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