Прокис Дж. - Цифровая связь (1266501), страница 20
Текст из файла (страница 20)
кодовые слова выполняется однозначно (уникально). Такие типы кодов названы ' 4';!, бесшумными Теперь предположим, что мы пытаемся уменьшить скорость кодирования Я путем смягчения условия однозначности процесса кодирования. Например, предположим, что только доля Е блоков символов источника кодируется однозначно. Конкретно, выберем 2» 1 наиболее вероятных,У-символьных блоков и будем кодировать каждый из них пдиозначно, в то время как оставшиеся У' -(2 — 1) блоков длины,У будем представлять Одним оставшимся кодовым словом.
Эта процедура кодирования вызовет ошибку (3.3.6) л <Н(Х)-е, тогда Р„сколь угодно близка к 1 црн достаточно больших Х Исходя из этой теоремы мы видим, что среднее число бит на символ источника, требуемое для кодирования выхода ДИБП с произвольно малой вероятностью ошибки декодирования, ограничено снизу энтропией источника Н(Х). С другой стороны, если !! < Н(Х1, вероятность ошибки декодирования приближается к 100 %, если,У произвольно увеличивать.
Кодовые слова переменной длины. Если символы источника неравновероятны, более эффективный метод кодирования сводится к использованию кодовых слов переменной длины. Примером такого кодирования является код Морзе, который восходит к девятнадцатому веку. В коде Морзе символам, возникающим более часто, сопоставляются более короткие кодовые слова, а символам, возникающим менее часто, сопоставляются более длинные кодовые слова. Следуя этой общей идее, мы можем учесть вероятности различных символов источника при выборе кодовых слов. Проблема в том, чтобы предложить метод выбора кодовых слов для символов источника.
Этот метод кодирования назван энтропийным кодированием. Таблица ЗЗЛ. Коды пе емеиной длины Символ Р~а„) Код 1 Код 11 Код !!! 1/2 1/4 1л3 1/8 0 О) 011 111 0 10 110 111 1 .ОО 01 10 Для примера предположим, что выходные символы ДИБП о„а„а„а, с соответствующими вероятностями Р(а,) = —,, Р(а,) = -„, Р~а,) = Р~а,1)= 8 кодируются так, как показано в табл.3.3.1. Код 1 имеет переменную длину и имеет принципиальный недостаток.
Чтобы увидеть этот недостаток, предположим, что мы приняли последовательность 001001... Ясно, что ОО декодируется как аз. Однако последующие четыре бита декодируются неоднозначно. Они могут декодироваться или как а4а„или как а,а,а,. Возможно, неоднозначность может быть разрешена путем ожидания последующих битов„но такое декодирование крайне нежелательно.
Мы должны рассмотреть только коды, которые допускают немедленное декодирование, т.е. без задержки в декодере. Код!1 в табл. 3.3.1 обеспечивает однозначное и немедленное декодирование. Удобно представлять кодовые слова этого кода графически как узлы на дереве, как показано на рис. 3.3.1.
Видно, что 0 указывает на окончание кодового слова в первых трех кодовых словах. Эта характеристика вместе с тем обстоятельством, что ни одно кодовое слово не содержит более трех двоичных символов, делает этот код немедленно декодируемым. Заметим, что ни одно кодовое слово этого кода не является префиксом (началом) другого кодового слова. В общем, префиксное условие кода требует, чтобы для данного кодового слова С„длины й с элементами ~Ь„Ь„... Ь„) не существовало других кодовых слов длины 1< 1 с элементами (Ь„Ь„...
Ь,)для 15! <Й вЂ” 1. Рис. 3.3.2. Кодовое дерево для кода И ! в табл.З.З. ! Рис. 3.3. !. Кодовое дерево для кода П в таблЗ.З. ! Другими словами, нет кодовых слов длины 1<Ф, которые совпадают с первыми 1 '-!!:,,: двоичными символами другого кодового слова длины,М. Это свойство делает кодовые слова немедленно декодируемыми. Код 111 из табл. 3.3.1 имеет кодовое дерево, показанное на рис. 3.3,2. Видим, что в этом случае имеет место однозначное декодирование„однако требующее задеряски Ясно, что этот код не удовлетворяет префиксному условию.
Наша главная цель — создать систематическую процедуру для конструирования однозначных декодирующих кодов переменной длины, эффективных в том смысле, что ';: ', среднее число бит на один символ источника, определяемое соотношением А л =~~! и„Р(а„), (3.3.7) : бидо бы минимальным. Условие существования кода переменной длины, которое :;:; ':;,--: удовлетворяет префиксному условию, дается неравенством Крафта. Неравенство Крафта. Необходимым и достаточным условием существования ;::; двоичного кода с кодовыми символами длины и! < л! «....
л,, удовлетворяющего условию ,; -'-' арефиксности, является с ~ 2" <1. (3.3.8) «.! м, что ( бы по ое имеет а !с, зел по узлов ка из мы а мы докаже о кода, Что два узла порядк м некоторый у 2" "' конечных узлов поряд аняет 2 ' конечных уз я, пока последнее ко в узле порядка ! < ~~> 2 й=! ся узел порядка 1с всегда имеет '1:;;::.")аким образом '-.,',,::."!а!к иллюстрир ";;Звстоящего из "..'!1,':=.3 и и, =и, = дали кодовое рис. 3.3.3, дл мволов, ото , мы соз уется на пяти си 85 Сначал ::- "", ярефиксног .!, Вврядка и=и,, котор ;-'.: ..'расту!" по Выбере ;:-'!усп!зияет '"'„'абступных ::.;,;:;::амбар устр '=„'3!ррдолжаетс !..'следовательно, 3.3.8) является достаточным условием для существования строить такой код, мы начнем с полного двоичного дерева 2" конечных узлов, причем от каждого узла порядка /с — 1 1< !с <и, рядка и! в качестве первого кодового слона С!.
Этот выбор (т.е, долю 2 "' от 2" конечных узлов), От остающихся выбираем один узел для второго кодового слова Сь Этот лов (т,е, долю 2 "' от 2" конечных узлов), Этот процесс донос слово не определено в конечном узле и =и,. Е доля числа отсеченных конечных узлов <~~! 2" <1. я ! > г, который может быть выбран для следующего слона. дерево„которое встроено в полное дерево из 2" узлов, я дерева, имеющего 16 конечных узлов, и источника, бражаемых кодовыми словами длиной л! =1, л, =2, с,, о ' ° °- -в с, о.
о,с, рис. З.З.З. Конструирование двоичногодерева, встроенного в полное дерево Чтобы доказать, что (3.3.8) является необходимым условием, мы заметим, что в дереве порядка и = и, число конечных узлов, отсеченных от общего числа 2"' конечных узлов, равно з с ,'г' 2"" <2". Следовательно, ~~> 2" <1, и доказательство (3.3.8) закончено, Неравенство Крафта можно использовать для доказательства следующей теоремы кодирования источника (без шумов), которая применяется к кодам, удовлетворяющим префиксному условию. Теорема кодировании источника 11. Пусть Х- ансамбль символов двоичного источника без памяти с конечной энтропией Н(Х) и выходными символами х„1 < lг < А, с соответствующими вероятностями выбора р„, 1 < Й < Е.
Существует возможность создать код, который удовлетворяет префиксному условию и имеет среднюю длину Я, которая удовлетворяет неравенству Н(Х) < Я < Н(Х) +1. (3.3.9) Чтобы установить нижнюю границу в (3.3.9), обратим внимание на то, что для кодовых '":--.' '. слов; которые имеют длину и„, 1< й < Е, разность Н(Х) — Я может быть выражена в виде е с з-ид Н(Х)-Я=~~> Р, 1ой,— -Ч~ Р,п„=",) Р„1ойт: (3.3.10) Рг г ~ ьн Р» Используя неравенство 1пх < х-1, из (3.3 10) находим ( л н<х)-магог:)ур,( — 1 .6~,.>(2 т. 1),в, Рг Ф ! где последнее неравенство следует из неравенства Крафта.
Равенство имеет место, если, и:,' . только если Р, = 2 '" для 1 < 1г < А. Верхняя граница в (33.9) может быль установлена при предположении что гг„, 1< lг < А,,г ", — целые числа, выбираемые из условия 2 " < р„<2 "'". Но если Р >2 '"".:;!:,'„ просуммированы по 1 < 1г < А, получаем неравенство Крафта, для которого мй 'р '., демонстрировали, что там существует код, удовлетворяющий префиксному условию.
С:- 5' пя <1 — 1ояр„. 13.3.1 1) Если умножить обе части неравенства 13.3.11) на ря и просуммировать по 1< « < А, получаем желательную верхнюю границу, данную в 13.3.9). Это завершает доказательство СЗЗ 9). Мы установили, что коды переменной длины, которые удовлетворяют префиксному условию, — это эффективные коды для любого дискретного источника без памяти 1ДИБП) с символами, имеющими различную априорную вероятность.
Опишем теперь алгоритм для построения таких кодов, или, что эквивалентно, Алгоритм кодирования Хаффмеиа, Хаффмен (1952) разработал алгоритм кодирования переменной длины, основанный на знании априорных вероятностей символов Р(х,), ! =1,2...„1.. Этот алгоритм оптимален в том смысле, что среднее число двоичных символов„требуемых для представления исходных символов, минимально. Получаемые кодовые слова удовлетворяют префиксному условию„определенному выше, что позволяет уникально и мгновенно декодировать полученную последовательность.
Мы проиллюстрируем этот алгоритм кодирования посредством двух примеров. Пример 3,3.1. Рассмотрим ДИБП с семью возможными символами х,.х„...,х,. имеющими вероятности выбора, иллюстрируемые рис. 3.3.4. Сиияоя Псрояпюстя Собственная Коя инфо!»!я о»я 0.30 00 0! опо !0 !!0 !!!0 !1110 Ц 1!1 х, 0,!0 0.005 0,005 и1х7= 2п1 Мы упорядочили символы источника в порядке убывания вероятностей, т.с.
!'(я!)> Р(х!)>..;> Р(хт). Процесс кодирования начинаем с двух наименее вероятных символов х и х,. Эти два символа объединяем, как показано на рис. 3,3.4, причем верхнему ветвлению присваиваем «О», а нижнему — «1». Вероятности этих двух ветвей складываются, и общему узлу присваивается суммарная вероятность, равная в данном случае 0,01, Теперь мы имеем исходные символы х„х„...,х, плюс новый символ, обозначим его х,', полученный объединением хя и х,.
На следующем шаге снова вбъединяются два наименее вероятных символа из набора х„х„х,.х„х,,х,'. Это х, их„', которые имеют объединенную вероятность 0,05. Переходу от х, присваиваем «О», а ":," -:,::;:..' переходу от х,' — «1». Эта процедура продолжается, пока мы не исчерпаем все возможные :г ",: символы источника. Результат — кодовое дерево с ветвями, которые содержат требуемые другой стороны, если мы берем логарифм ря < 2 "' ", получаем 1ояря с-и»+1 0,35 0,30 020 0.Ш 0.04 0,005 0,005 Рис 3.3.4. Пример кодирования ДИБП кодам переменной длины 1,5146 1.7370 2.3219 3,3219 4,б439 7,б439 7,б439 кодовые слова. Кодовые слова получаются, если двигаться от самого правого узла дерева и переходя к самому левому узлу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
