Эффективное статистическое кодирование сообщений. Теорема Шеннона для каналов без помех

Для дискретных каналов без помех К. Шенноном была доказана следующая теорема (первая теорема Шеннона):

Если производительность источника R = C – ε, где ε – сколь угодно малая величина, то всегда существует способ кодирования, позволяющий передавать по каналу все сообщения источника. Передачу всех сообщений при R > C осуществить невозможно.

Как бы ни была велика избыточность источника, все его сообщения могут быть переданы по каналу, если R < C.

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

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

При эффективном кодировании фактическая скорость передачи информации приближается к пропускной способности канала.

Рассмотрим основные принципы оптимального кодирования для двоичного канала без помех. Пусть источник оперирует алфавитом символов a_i, i=1…M. Вероятность каждого символа P(a_i). Кодер преобразует символ a_i в двоичную последовательность длиной n_i. Средняя длительность кодовой комбинации одного символа первичного алфавита вычисляется так:

, где τ₀ – длительность одного элемента кода.

При этом средняя длина кода определяется как . (4.5)

Соответственно тогда τ = K∙τ₀.

Величина V/K определена ранее как среднее число знаков первичного алфавита, транслируемых по каналу в единицу времени. Соответственно, величина K/V – это средняя длительность трансляции одного знака первичного алфавита, т.е. τ = K/V.

Значит, в соответствии с формулой (4.4) скорость передачи в канале . Подставляя выражения для средней длительности и энтропии, получим:

. (4.6)

В выражении (4.6) значение числителя определяется исключительно статистическими свойствами источника, а τ₀ – свойствами канала связи. Возникает вопрос: можно ли так закодировать сообщение, чтобы скорость передачи достигала своего максимального значения? Максимальная скорость передачи определяется пропускной способностью канала связи. Для двоичного канала: . Чтобы J равнялось С надо чтобы n_i = - log₂P(a_i). Применение неравномерного кодирования (например, кода Шеннона-Фано) может приблизить длину кода n_i к величине - log₂P(a_i).

Пример 4.2. Первичный алфавит состоит из трех знаков A, B, C с вероятностями p_A = 0,2; p_B = 0,7; p_C = 0,1. Для передачи по каналу без помех используются код Шеннона-Фано. Частота тактового генератора 500 Гц. Какова пропускная способность канала и скорость передачи?

Решение. Поскольку код Шеннона-Фано – двоичный, то m = 2; C =V = 500 бит/с.

Энтропия источника: H = – 0,2·log₂0,2 – 0,7·log₂0,7 – 0,1·log₂0,1 = 1,16 бит

Длительность одного бинарного разряда в канале τ₀=1/V=0.002 c.

Закодируем первичный алфавит кодом Шеннона-Фано: A→10, B→0, C→11, длины кодов будут равны: n_A = 2; n_B = 1; n_C = 2

Средняя длина кода K = 0.2·2 + 0.7·1 + 0.1·2 = 1.3

Следовательно, получаем:

(бит/с).

По сравнению с равномерным двоичным кодом (см. пример 4.1) скорость передачи возросла на 54% и приблизилась к пропускной способности.

Пример 4.3. Можно ли с помощью кодирования еще больше увеличить скорость передачи?

Решение. Первичный алфавит из примера 4.2 будем кодировать по парам символов (это так называемое укрупнение кодов). Пары символов, их вероятности, коды Шеннона-Фано и длины кодовых последовательностей приведены в таблице:

Символ	Вероятность	код	длина
BB	0.7∙0.7=0.49
AB	0.2∙0.7=0.14
BA	0.14
BC	0.07
CB	0.07
AA	0.04
CA	0.02
AC	0.02
CC	0.01

Средняя длина кодового слова для пары (см. формулу (4.5)) равна 2.42, следовательно, для одного символа – 1.21.

Скорость передачи (бит/с).

Скорость передачи еще больше приблизилась к своему пределу – пропускной способности канала.

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