Здесь [л; J означает наибольшее целое, К1еньшее, чем х

R будем называть скоростью кодирования . Она определяет число символов кодера на один символ источника. Поскольку Я(Л!)< logj Z, то R> н{х).

Эффективность кодирования для ДИБП определяется отношением H(X)/R. Видим, что если L равно степени числа 2 и символы источника равновероятны, то R-ЩХ). Следовательно, код фиксированной длины с R двоичными символами на символ источника в данном случае обеспечивает стопроцентную эффективность. Однако, если L не равно степени 2, но символы источника всё ещё равновероятны, R отличается от Н(Х) самое большее на один бит на символ. Если logL»l, эффективность такой схемы кодирования высока. С другой стороны, если L мало, эффективность кода с фиксированной ДJШнoй можно увеличить путем кодирования последовательности из J символов источника за время Jxs. Чтобы выполнить такое кодирование, мы должны выбрать L уникальных кодовых слов. Используя кодовую последовательность из N двоичных символов, мы можем образовать 2 возможных кодовых слов. Число iVдолжно быть выбрано так, чтобы

N>Jlog,L.

Следовательно, требуется минимальное целое значение для N, равное

iV = LyiogjiJ+l. (3.3.4)

Теперь среднее число символов кода на символ источника R=NIJ, и, таким образом, неэффективность кодирования сокращается примерно в У раз по сравнению с посимвольным кодированием, описанным выше. Взяв J достаточно большим, можно сделать эффективность процедуры кодирования, измеренную отношением JH(X)/h\ как угодно близкой к единице. Методы кодирования, описанные выше, не приводят к искажениям, так как кодирование символов источника или блоков таких символов в кодовые слова выполняется однозначно (уникально). Такие типы кодов названы бесшумными.

Теперь предположим, что мы пытаемся уменьшить скорость кодирования R путем смягчения условия однозначности процесса кодирования. Например, предположим, что только доля блоков символов источника кодируется однозначно. Конкретно, выберем 2 1 наиболее вероятных J-символьных блоков и будем кодировать каждый из них однозначно, в то время как оставшиеся -(2 -1) блоков длины J будем представлять одним оставшимся кодовым словом. Эта процедура кодирования вызовет ошибку декодирования каждый раз, когда источник выдаст такой маловероятный блок Пусть означает вероятность такой ошибки. Отталкиваясь от этой процедуры кодирования, Шеннон (1948) доказал следующую теорему кодирования источника.

Теорема кодирования источника I. Пусть Х-эио ансамбль символов ДИБП с конечной энтропией Н(Х) Блоки из J символов источника кодируются в двоичные кодовые слова длиной N. Для любого £>0 вероятность fj, ошибки декодирования можно сделать сколь угодно малой, если

R = - >HiX) + E (3.3.5)

И J достаточно велико. Наоборот, если

Этот параметр не следует путать со скоростью передачи информации от двоичного источника, используемой, в частности, в гл. 4. По своему смыслу используемый здесь параметр R можно было бы назвать гаатраты (на кодирование)» (прп).

R<H{X)-z, (3.3.6)

тогда сколь угодно близка к 1 при достаточно больших J.

Исходя из этой теоремы мы видим, что среднее число бит на символ источника, требуемое для кодирования выхода ДИБП с произвольно малой вероятностью ошибки декодирования, ограничено снизу энтропией источника Н{Х). С другой стороны, если R< Н{Х), вероятность ошибки декодирования приближается к 100 %, если J произвольно увеличивать.

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

Для примера предположим, что выходные символы ДИБП а,,а2.34 соответствующими вероятностями р(а,) = j, Pia-) j, P[ct)- Р{а)-i кодируются так, как показано в табл. 3.3.1. Код I имеет переменную длину и имеет принципиальный недостаток. Чтобы увидеть этот недостаток, предположим, что мы приняли последовательность 001001... Ясно, что 00 декодируется как aj. Однако последующие четыре бита декодируются неоднозначно. Они могут декодироваться или как аа, или как «,«20,. Возможно, неоднозначность может бьггь разрешена путем ожидания последующих битов, но такое декодирование крайне нежелательно. Мы должны рассмотреть только коды, которые допускают немедленное декодирование, т.е. без задержки в декодере.

Код II в табл. 3.3.1 обеспечивает однозначное и немедленное декодирование. Удобно представлять кодовые слова этого кода графически как узлы на дереве, как показано на рис. 3.3.1. Видно, что О указывает на окончание кодового слова в первых трех кодовых словах. Эта характеристика вместе с тем обстоятельством, что ни одно кодовое слово не содержит более трех двоичных символов, делает этот код немедленно декодируемым. Заметим, что ни одно кодовое слово этого кода не является префиксом (началом) другого кодового слова. В общем, префиксное условие кода требует, чтобы для данного кодового

слова С длины к с элементами (б,, б,.--- б) не существовало других кодовых слов длины I <к с элементами (б,, б,.--- 6/)для 1<1 <к-1.

«з, а, а. а \ а \ а

Ох О x О X О X

,-.--.-• а

1 1 1.1 1 1

Рис. 3.3.1. Кодовое дерево для кода II в табл.3.3.1 Рис. 3.3.2. Кодовое дерево для кода III в табл.3.3.1

Другими словами, нет кодовых слов длины 1<к, которые совпадают с первыми / двоичными символами другого кодового слова длины к>1 Это свойство делает кодовые слова немедленно декодируемыми.

Код III из табл. 3.3.1 имеет кодовое дерево, показанное на рис. 3.3.2. Видим, что в этом случае имеет место однозначное декодирование, однако требующее задержки.

Ясно, что этот код не удовлетворяет префиксному условию.

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

R = Y.,P{a,), (3.3.7)

было бы минимальным. Условие существования кода переменной длины, которое удовлетворяет префиксному условию, дается неравенством Крафта.

Неравенство Крафта. Необходимым и достаточным условием существования двоичного кода с кодовыми символами длины и, < <.. .< и,. удовлетворяющего условию префиксности, является

2-" <1. (3.3.8)

Сначала мы докажем, что (3.3.8) является достаточным условием для существования префиксного кода. Чтобы построить такой код, мы начнем с полного двоичного дерева порядка и = «i, которое имеет 2" конечных узлов, причем от каждого узла порядка к -1 растут" по два узла порядка к, \ <к<,п.

Выберем некоторый узел порядка щ в качестве первого кодового слова Сь Этот выбор устраняет 2""" конечных узлов (т.е. долю 2"" от 2" конечных узлов). От остающихся доступных узлов порядка ni мы выбираем один узел для второго кодового слова Ci. Этот выбор устраняет 2~конечных узлов (те долю 2от 2" конечных узлов). Этот процесс продолжается, пока последнее кодовое слово не определено в конечном узле и - . Следовательно, в узле порядка j <L доля числа отсечённых конечных узлов

4=1 к-\

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

Таким образом, мы создали кодовое дерево, которое встроено в полное дерево из 2" узлов, как иллюстрируется на рис. 3.3.3, для дерева, имеющего 16 конечных узлов, и источника, состоящего из пяти символов, отображаемых кодовыми словами длиной и, 1, = 2, «3 = 3 и «4 = «5 = 4.