|
Читать в оригинале |
| << Предыдущая | Оглавление | Следующая >> |
3.3.1. Кодирование для дискретных источников без памяти
Предположим, что ДИБП выдает буквы или символы каждые 
секунд. Каждый символ выбирается из конечного алфавита 
, 
, с вероятностью 
, . Энтропия ДИБП в битах на символ
, (3.3.1)
причем равенство имеет место, если все символы равновероятны. 
определяет среднее число бит на символ источника, а производительность источника в битах определяется как 
.
Кодовые слова фиксированной длины. Сначала рассмотрим схему блокового кодирования, которая сопоставляет уникальный ряд из 
двоичных символов с каждым символом источника. Поскольку имеется 
возможных символов источника, то числа двоичных символов кодера на один символ источника при уникальном кодировании
, (3.3.2)
когда равно целой степени основания 2, и
, (3.3.3)
когда не равно целой степени основания 2.
Здесь 
означает наибольшее целое, меньшее, чем 
.
будем называть скоростью кодирования. Она определяет число символов кодера на один символ источника. Поскольку 
, то 
.
Эффективность кодирования для ДИБП определяется отношением 
. Видим, что если равнo степени числа 2 и символы источника равновероятны, то 
. Следовательно, код фиксированной длины с двоичными символами на символ источника в данном случае обеспечивает стопроцентную эффективность. Однако, если не равно степени 2, но символы источника всё ещё равновероятны, отличается от самое большее на один бит на символ. Если 
, эффективность такой схемы кодирования высока. С другой стороны, если мало, эффективность кода с фиксированной длиной можно увеличить путем кодирования последовательности из 
символов источника за время 
. Чтобы выполнить такое кодирование, мы должны выбрать 
уникальных кодовых слов. Используя кодовую последовательность из 
двоичных символов, мы можем образовать 
возможных кодовых слов. Число должно быть выбрано так, чтобы
.
Следовательно, требуется минимальное целое значение для , равное
. (3.3.4)
Теперь среднее число символов кода на символ источника 
, и, таким образом, неэффективность кодирования сокращается примерно в раз по сравнению с посимвольным кодированием, описанным выше. Взяв достаточно большим, можно делать эффективность процедуры кодирования, измеренную отношением 
, как годно близкой к единице. Методы кодирования, описанные выше, не приводят к искажениям, так как кодирование символов источника или блоков таких символов в кодовые слова выполняется однозначно (уникально). Такие типы кодов названы бесшумными.
Теперь предположим, что мы пытаемся уменьшить скорость кодирования путем смягчения условия однозначности процесса кодирования. Например, предположим, что только доля блоков символов источника кодируется однозначно. Конкретно, выберем 
наиболее вероятных -символьных блоков и будем кодировать каждый из них однозначно, в то время как оставшиеся 
блоков длины будем представлять одним оставшимся кодовым словом. Эта процедура кодирования вызовет ошибку декодирования каждый раз, когда источник выдаст такой маловероятный блок. Пусть 
означает вероятность такой ошибки. Отталкиваясь от этой процедуры кодирования, Шеннон (1948) доказал следующую теорему кодирования источника.
Теорема кодирования источника I. Пусть 
- это ансамбль символов ДИБП с конечной энтропией . Блоки из символов источника кодируются в двоичные кодовые слова длиной . Для любого 
вероятность ошибки декодирования можно сделать сколь угодно малой, если
(3.3.5)
достаточно велико.
Наоборот, если
, (3.3.6)
тогда сколь угодно близка к 1 при достаточно больших .
Исходя из этой теоремы мы видим, что среднее число бит на символ источника требуемое для кодирования выхода ДИБП с произвольно малой вероятностью ошибки декодирования, ограничено снизу энтропией источника . С другой стороны, если 
, вероятность ошибки декодирования приближается к 100%, если произвольно увеличивать.
Кодовые слова переменной длины. Если символы источника неравновероятны, более эффективный метод кодирования сводится к использованию кодовых слов переменной длины. Примером такого кодирования является код Морзе, который восходит к девятнадцатому веку. В коде Морзе символам, возникающим более часто, сопоставляются более короткие кодовые слова, а символам, возникающим менее часто, сопоставляются более длинные кодовые слова. Следуя этой общей идее, мы можем учесть вероятность различных символов источника при выборе кодовых слов. Проблема в том, чтобы предложить метод выбора кодовых слов для символов источника. Этот метод кодирования назван энтропийным кодированием.
Таблица 3.3.1. Коды переменной длины
|
Символ |
|
Код I |
Код II |
Код III |
|
|
1/2 |
1 |
0 |
0 |
|
|
1/4 |
00 |
10 |
01 |
|
|
1/8 |
01 |
110 |
011 |
|
|
1/8 |
10 |
111 |
111 |
Для примера предположим, что выходные символы ДИБП 
,
,
,
соответствующими вероятностями 
, 
, 
кодируются так как показано в табл. 3.3.1. Код I имеет переменную длину и имеет принципиальный недостаток. Чтобы увидеть этот недостаток, предположим, что мы приняли последовательность 001001... Ясно, что 00 декодируется как . Однако последующие четыре бита декодируются неоднозначно. Они могут декодироваться или как 
, или как 
. Возможно, неоднозначность может быть разрешена путем ожидания последующих битов, но такое декодирование крайне нежелательно. Мы должны рассмотреть только коды, которые допускают немедленное декодирование, т.е. без задержки в декодере.
Код II в табл. 3.3.1 обеспечивает однозначное и немедленное декодирование. Удобно представлять кодовые слова этого кода графически как узлы на дереве, как показано на рис. 3.3.1. Видно, что 0 указывает на окончание кодового слова в первых трех кодовых словах. Эта характеристика вместе с тем обстоятельством, что ни одно кодовое слово не содержит более трех двоичных символов, что делает этот код немедленно декодируемым. Заметим, что ни одно кодовое слово этого кода не является префиксом (началом) другого кодового слова. В общем, префиксное условие кода требует, чтобы для данного кодового слова 
длины 
с элементами 
не существовало других кодовых слов длинны 
с элементами 
для 
.
Рис. 3.3.1. Кодовое дерево для кода II в табл.3.3.1
Рис. 3.3.2. Кодовое дерево для кода III в табл.3.3.1
Другими словами, нет кодовых слов длины , которые совпадают с первыми 
двоичными символами другого кодового слова длины 
. Это свойство делает кодовые слова немедленно декодируемыми.
Код III из табл. 3.3.1 имеет кодовое дерево, показанное на рис. 3.3.2. Видим, что в этом случае имеет место однозначное декодирование, однако требующее задержки.
Ясно, что этот код не удовлетворяет префиксному условию.
Наша главная цель – создать систематическую процедуру для конструирования однозначных декодирующих кодов переменной длины, эффективных в том смысле, что среднее число бит на один символ источника, определяемое соотношением
, (3.3.7)
было бы минимальным. Условие существования кода переменной длины, которое удовлетворяет префиксному условию, дается неравенством Крафта.
Неравенство Крафта. Необходимым и достаточным условием существования двоичного кода с кодовыми символами длины 
, удовлетворяющего условию префиксности, является
. (3.3.8)
Сначала мы докажем, что (3.3.8) является достаточным условием для существования префиксного кода. Чтобы построить такой код, мы начнем с полного двоичного дерева порядка 
, которое имеет 
конечных узлов, причем от каждого узла порядка 
«растут» по два узла порядка , 
.
Выберем некоторый узел порядка в качестве первого кодового слова 
. Этот выбор устраняет 
конечных узлов (т.е. долю 
от конечных узлов). От остающихся доступных узлов порядка 
мы выбираем один узел для второго кодового слова 
. Этот выбор устраняет 
конечных узлов (т.е. долю 
от конечных узлов). Этот процесс продолжается, пока последнее кодовое слово не определено в конечном узле . Следовательно, в узле порядка 
доля числа отсечённых конечных узлов
.
Всегда имеется узел порядка 
, который может быть выбран для следующего слова. Таким образом, мы создали кодовое дерево, которое встроено в полное дерево из узлов, как иллюстрируется на рис. 3.3.3, для дерева, имеющего 16 конечных узлов, и источника, состоящего из пяти символов, отображаемых кодовыми словами длиной 
, 
, 
, 
.
Рис. 3.3.3. Конструирование двоичного дерева, встроенного в полное дерево
Чтобы доказать, что (3.3.8) является необходимым условием, мы заметим, что в дереве порядка , число конечных узлов, отсечённых от общего числа конечных узлов равно
. Следовательно, ,
и доказательство (3.3.8) закончено. Неравенство Крафта можно использовать для доказательства следующей теоремы кодирования источника (без шумов), которое применяется к кодам, удовлетворяющим префиксному условию.
Теорема кодирования источника II. Пусть - ансамбль символов двоичного источника без памяти с конечной энтропией и выходными символами 
, 
с соответствующими вероятностями выбора 
, . Существует возможность создать код, который удовлетворяет префиксному условию и имеет среднюю длину 
, которое удовлетворяет неравенству
. (3.3.9)
Чтобы установить нижнюю границу в (3.3.9), обратим внимание на то, что для кодовых слов, которые имеют длину 
, , разность 
может быть выражена в виде
. (3.3.10)
Используя неравенство 
, из (3.3.10) находим
,
где последнее неравенство следует из неравенства Крафта. Равенство имеет место, если только если 
для .
Верхняя граница в (3.3.9) может быть установлена при предположении что , - целые числа, выбираемые из условия 
. Но если 
просуммированы по , получаем неравенство Крафта, для которого демонстрировали, что там существует код, удовлетворяющий префиксному условию другой стороны, если мы берем логарифм 
, получаем
или, что эквивалентно,
. (3.3.11)
Если умножить обе части неравенства (3.3.11) на и просуммировать по , получаем желательную верхнюю границу, данную в (3.3.9). Это завершает доказательство (3.3.9).
Мы установили, что коды переменной длины, которые удовлетворяют префиксному условию, - это эффективные коды для любого дискретного источника без памяти (ДИБП) с символами, имеющими различную априорную вероятность. Опишем теперь алгоритм для построения таких кодов.
Алгоритм кодирования Хаффмена. Хаффмен (1952) разработал алгоритм кодирования переменной длины, основанный на знании априорных вероятностей символов , . Этот алгоритм оптимален в том смысле, что среднее число двоичных символов, требуемых для представления исходных символов, минимально. Получаемые кодовые слова удовлетворяют префиксному условию, определенному выше, что позволяет уникально и мгновенно декодировать полученную последовательность. Мы проиллюстрируем этот алгоритм кодирования посредством двух примеров.
Пример 3.3.1. Рассмотрим ДИБГТ с семью возможными символами 
, имеющими вероятности выбора, иллюстрируемые рис. 3.3.4.
Рис. 3.3.4. Пример кодирования ДИБП кодом переменной длины
Мы упорядочили символы источника в порядке убывания вероятностей, т.е. 
. Процесс кодирования начинаем с двух наименее вероятных символов 
и 
. Эти два символа объединяем, как показано на рис. 3.3.4, причем верхнему ветвлению присваиваем «0», а нижнему - «1». Вероятности этих двух ветвей складываются, и общему узлу присваивается суммарная вероятность, равная в данном случае 0,01. Теперь мы имеем исходные символы плюс новый символ, обозначим его 
, полученный объединением и . На следующем шаге снова объединяются два наименее вероятных символа из набора 
,
,
,
,
,. Это и которые имеют объединенную вероятность 0,05. Переходу от присваиваем «0», а переходу от - «1». Эта процедура продолжается, пока мы не исчерпаем все возможные символы источника. Результат – кодовое дерево с ветвями, которые содержат требуемые кодовые слова. Кодовые слова получаются, если двигаться от самого правого узла дерева переходя к самому левому узлу. Результирующие кодовые слова приведены на рис. 3.3 Среднее число двоичных элементов на символ этого кода 
бит/символ. Энтропия источника – 2,11 бит/символ.
Заметим, что полученный код не единственно возможный. Например, на предпоследнем шаге процедуры кодирования мы имеем равный выбор между , и имеющими одинаковые вероятности. В этом пункте мы соединили и . В альтернативном коде мы можем соединить и 
. Результирующий код для этого случая иллюстрируется на рис. 3.3.5.
Рис. 3.3.5. Альтернативный код для ДИБП в примере 3.3.1
Среднее число бит на символ для этого кода также равно 2.21. Следовательно, полученные коды одинаково эффективны. Кроме того, назначение «0» верхнему переходу и «1» нижнему (менее вероятному) переходу выбрано произвольно. Мы можем просто поменять местами 0 и 1 и получить ещё эффективный код, удовлетворяющий префиксному условию.
Пример 3.3.2. В качестве второго примера определим код Хаффмена для выхода ДИБП, иллюстрируемый на рис. 3.3.6. Энтропия этого источника 
бит/символ. Код Хаффмена, показанный на рис. 3.3.6, имеет среднюю длину 
бит/символ. Следовательно, его эффективность составляет 0,97.
Алгоритм кодирования переменной длины (Хаффмена), описанный в предыдущих примерах, генерирует префиксный код, имеющий среднюю длину , который удовлетворяет (3.3.9). Однако вместо посимвольного кодирования более эффективной является процедура, основанная на кодировании блоков из символов одновременно, таком случае границы в (3.3.9) в теореме кодирования источника II становятся другими:
, (3.3.12)
так как энтропия -символьного блока от ДИБП равна 
, и 
- среднее число бит в -символьном блоке. Если мы разделим (3.3.12) на , то получим
, (3.3.13)
где 
- среднее число битов на исходный символ. Следовательно, можно сделать как угодно близким к , выбирая достаточно большим.
Рис. 3.3.6. Код Хаффмена для примера 3.3.2
Пример 3.3.3. Выход ДИБП состоит из символов и , и с вероятностями 0,45, 0,35 и 0,20 соответственно. Энтропия этого источника 
бит/символ. Код Хаффмена для этого источника, данный в табл. 3.3.2, требует 
бит/символ и приводят к эффективности 97,9%, Если посредством алгоритма Хаффмена символы закодированы парами, результирующий код выглядит так, как показано в табл. 3.3.3. Энтропия источника для пар символов 
бит/пара символов. С другой стороны, код Хаффмена требует 
бит/пара символов. Таким образом, эффективность кодирования увеличилась до 
(до 99,0 %).
Таблица 3.3.2. Код Хаффмена для примера 3.3.3
|
Символ |
Вероятность |
Собственная информация |
Код |
|
|
0,45 |
1,156 |
1 |
|
|
0,35 |
1,520 |
00 |
|
|
0,20 |
2,33 |
01 |
|
|
|||
|
|
|||
|
Эффективность 97,9 % |
|||
=1,518 бит/символ
=1,55 бит/символИтак, мы продемонстрировали, что эффективное кодирование для ДИБП может быть выполнено на посимвольной основе, если использовать неравномерный код, основанный на алгоритме Хаффмена. Кроме того, эффективность процедуры кодирования увеличивается при кодировании блоков из символов одновременно. Таким образом, выход ДИБП с энтропией может быть закодирован неравномерным кодом со средним числом битов на исходный символ, которое может быть сделано как угодно близким к .
Таблица 3.3.3. Код Хаффмена для кодирования пар символов
|
Пара символов |
Вероятность |
Собственная информация |
Код |
|
|
0,2025 |
2,312 |
10 |
|
|
0,1575 |
2,676 |
001 |
|
|
0,1575 |
2,676 |
010 |
|
|
0,1225 |
3,039 |
011 |
|
|
0,09 |
3,486 |
111 |
|
|
0,09 |
3,486 |
0000 |
|
|
0,07 |
3,486 |
0001 |
|
|
0,07 |
3,850 |
1100 |
|
|
0,04 |
4,660 |
1101 |
|
|
|||
|
|
|||
бит/пара символов; 
бит/пара символ; Эффективность 99,0 %
| << Предыдущая | Оглавление | Следующая >> |