Параграф 2.3. Второй способ доказательства прямой теоремы Шеннона для канала без шума. Метод Фано. Оптимальные коды

Второй способ доказательства прямой теоремы предполагает другой способ эффективного кодирования, который заключается в следующем: по-прежнему рассматриваем сообщение a_i представляющее собой последовательность элементарных сообщений u_j длинной К. Расположим все сообщения a _i в порядке убывания их вероятностей, пусть эти вероятности будут P1³ P2 ³ ¼ ³ PL, где L = N u_k число сообщений a_i. Пусть

,

т.е. Q_s накопленная вероятность до P (S-1) включительно. Закодируем сначала все сообщения в двоичную систему. Двоичный код для сообщения a_s получиться путем записи дробной части разложения Q_s, как двоичного числа (при S=1, Q_s =0). Разложение производиться до m_s позиции, где m_s целое число, удовлетворяющее соотношению

(2.7).

Пример: Пусть мы имеем 4 сообщения

1	2	3	4
P(1) = 1/2	P(2) = 1/4	P(3) = 1/8	P(4) = 1/8
Q1 = 0	Q2 = 1/2	Q3 = 3/4	Q4 = 7/8
m1 = 1	m2 = 2	m3 = 3	m4 = 4
код 0	код 10	код 110	код 111

Коды показанные в последней строчке таблицы - это коды Шеннона дробной части. Таким образом высоко вероятные сообщения представляются короткими кодами, а маловероятные длинными (это видно из (2.7)). Из этих неравенств вытекает следующая система неравенств (2.8). Оно показывает, что при выборе m_s в соответствии с системой неравенств (2.7) вероятность сообщения с номером s P_s не меньше веса последнего младшего разряда двоичного разложения Q_s. Вследствие этого код для Q_s будет отличаться от всех последующих кодов одной и более из своих m_s позиций, т.к. все остающиеся Q_i, по крайней мере, на величину больше и поэтому их двоичное разложение отличается от кода для Q_s, ходя бы в младшем разряде. Это говорит об однозначности предложенного способа кодирования. Среднее количество символов кода приходящихся на одно сообщение a можно определить, как (2.9), а среднее количество символов кода, приходящихся на одно элементарное сообщение U_k . Умножая все части системы неравенств (2.7) на и усредняя их по ансамблю сообщений a_i приходим к неравенствам

(2.10),

Но

,

где Н_a - энтропия источника укрупненных сообщений a представляющих собой объединение К элементных независимых сообщений Ui (рассматриваем источник без памяти). Поэтому вследствие свойства аддитивности энтропии H_α = K× H(U). В свою очередь

.

Таким образом неравенство (2.10) можно записать в виде

(2.11).

Неравенство (2.11) показывает, что с неограниченным ростом значение К, среднее количество h символов кода приходиться на одно элементарное сообщение источника, сколь угодно близко приближается к значению энтропии этого источника. Поскольку мы рассматривали двоичный код с объемом алфавита равного 2 и log₂M=log₂2=1 выполнение неравенства (2.11) эквивалентно выполнению условия (2.2), это и доказывает прямую теорему. Полученный результат позволяет дать следующее толкование энтропии: энтропия источника есть наименьшее количество двоичных символов на сообщение, на выходе наилучшего кодера для этого источника при условии, что сообщения могут быть восстановлены по выходу кодера сколь угодно точно. Два рассмотренных варианта доказательства прямой теоремы иллюстрируют два возможных подхода к построению эффективных кодов, основанных на использовании равномерного и неравномерного кодирования. При неравномерном кодировании обеспечивается однозначное декодирование всех сообщений. Второй способ доказательства мы рассмотрели в той же трактовке, в которой он был дан Шенноном, а именно на основе построения двоичного эффективного кода возможен более общий подход, базируется на построении неравномерного статистического кода с произвольным основанием М непосредственно приводящей к результату (2.2). Такой вариант доказательства дан в книге Колесник-Бондарев. Предложенный Шенноном метод эффективного кодирования практически совпадает с методом предложенным другим американским ученым Фано по которому сообщение длинны К, записанное в порядке не возрастания вероятностей разделяется на две части так, чтобы суммарные вероятности сообщений в каждой части были по возможности равны. Сообщениям первой части приписывается в качестве первого символа 0, сообщениям второй части 1. Затем каждая из этих частей (если она содержит более одного сообщения) опять делится на две примерно равные части и в качестве второго символа для первой из них берется 0, а для второй 1. Этот процесс повторяется до тех пор, пока в каждой из полученных частей не останется по одному сообщению. Существуют и другие методы эффективного кодирования. Кодирование по методу Шеннона – Фано так же как и другими методами может применятся не только к последовательностям из К элементных сообщений, но и непосредственно к источникам не равновероятных элементарных сообщений. При этом уменьшается выигрыш в эффективности. В том случае, когда левая часть системы неравенств (2.11) обращается в равенство, имеем h_min = H(U) (2.12). Код, обладающий h_min называется оптимальным для того, чтобы сообщение источника можно было закодировать двоичным оптимальным кодом необходимо и достаточно, чтобы все вероятности источника сообщения представляли собой числа равные целой отрицательной степени числа 2, т.е. Pi= , где аi - целое. Действительно как видно из неравенства (2.8) в таком случае вероятности Ps при выбранном нами способе определении длины кодового слова ms определятся, как . При этом среднее число символов кода приходящихся на одно сообщение в соответствии с (2.9) равно . В свою очередь энтропия источника сообщений Нa равна . Таким образом получили, что h_с = h с min = Н_α откуда после деления обеих частей последнего равенства на К можно придти к выражению (2.12). Рассуждая аналогичным образом можно показать, что и в случае кодирования сообщений источника неравномерным кодом с произвольным основанием М оптимальный код может быть получен при условии равенства вероятности всех сообщений целым отрицательным степеням числа М, т.е. при , где аi - целое и при этом . Если распределение вероятностей кодированного источника не обладает указанным свойством, эффективный код не будет оптимальным и соответствующая ему h > h _min. Величина Y = h_min/ h (2.12а), характеризующая степень близости неравномерного статистического кода к оптимальному называется эффективностью кода. Таким образом нижний предел в условии теоремы, может быть, достигнут лишь при определенном распределении вероятности источника сообщений. Однако приближение к нему может быть сколь угодно близким при увеличении длинны К последовательности кодируемых сообщений. При этом рост эффективности системы передачи информации сопровождается увеличением задержки сообщений. И так из рассмотренной теоремы вытекает, что для любого источника дискретных сообщений (т.е. характеризуется любым многомерным распределением вероятностей) скорость передачи информации по идеальному каналу может быть сделана сколь угодно близкой к пропускной способности канала при отсутствии потерь информации. При этом приближение тем больше, чем больше длина сообщения К, что указывает на возможность обмена задержки на скорость передачи информации.