Прокис Дж. - Цифровая связь (1266501), страница 21
Текст из файла (страница 21)
Результирующие кодовые слова приведены на рнс. 3.3 4. Среднее число двоичных элементов на символ этого кода Я = 2,21 бнт/символ. Энтропия источника — 2,11 бит/снмвол. Заметим, что полученный код не единственно возможный. Например, на предпоследнем шаге процедуры кодирования мы имеем равный выбор между х, н х,', имеющими одинаковые вероятности. В этом пункте мы соединили х, и х, . В альтернативном коде мы можем соединить х, и х,' . Результирующий код для этого случая иллюстрируется иа рис. 3.3.5. Симеед Код 0,35 х о х 1О 0,20 х. 110 х. гпо Х, пио х 111110 х 111111 о,10 0,04 О,ОО5 Рис. 3.3.5. Альтернативный код для ДИБП в примере 3.3.1 Среднее число бит на символ для этого кода также равно 2.21.
Следовательно, полученные коды одинаково эффективны. Кроме того, назначение «0» верхнему переходу н «1» нижнему (менее вероятному) переходу выбрано произвольно. Мы можем просто поменять местами 0 и 1 и получить еще эффективный код, удовлетворяющий префиксному условию. 88 Пример 3.32. В качестве второго примера определим код Хаффмеиа для выхода ", ДИБП, иллюстрируемый на рис.
3.3.6. Энтропия этого источника /21Х) = 2,63 бит/символ. Код Хаффмена, показанный на рис. 3.3.6, имеет среднюю длину Я=2,70 бит/символ. Следовательно, его эффективность составляет 0,97. Алгоритм кодирования переменной длины (Хаффмена), описанный в предыдущих примерах, генерирует префиксный код, имекзщий среднюю длину /1 „которая удовлетворяет (3.3.9). Однако вместо посимвольного кодирования более эффективной'..':;;!:.;:, является процедура, основанная на кодировании блоков из,У символов одновременно.
В 'зтаком случае границы в (3.3.9) в теореме кодирования источника П становятся другими: ,УН(Х) ~ 1Ь < ЛХ(Х)+1, (3.3.12) так как энтропия У-символьного блока от ДИБП равна,УН(Х), и лз — среднее число битов '';:~.." в У-символьном блоке. Если мы разделим (3.3.12) на У, то получим В 1 Н(Х) « — Н(Х)+ —, (3.3.13) у .у 0,3б Символ код Озы х О,13 0,12 О,1О 7/(Л3 2,бЗ й 2,70 0.02 Рис. 3.3.6.
Код Хаффв!еиа дяя примера 3.3.2 где Я, /.У ав Я вЂ” среднее число битов на исходный символ. Следовательно, Я можно сделать как угодно близким к Н(Х), выбирая, /достаточно большим. Пример ЗЗ.З. Выход ДИБП состоит из символов х„х, и х, с вероятностями 0,45, 0,35 и 0,20 соответственно. Энтропия этого источника Н(Х)-=1,518 бит/символ.
Код Хаффмена для этого источника, данный в табл. 3,3.2, требует Я,=1,55 бит/символ и приводят к эффективности 97,9%, Если посредством алгоритма Хаффмена символы закодированы парами, результирующий код выглядит так, как показано в табл. 3,3.3. Энтропия источника для пар символов 2Н(Х) = 3,03б бит/пара символов. С другой стороны, код Хаффмена требует Я, = 3,0б75 бит/пара символов.
Таким образом. эффективность кодирования увеличилась до 2Н(Х)/'Яв = 0,990 (до 99,0 %). Таблица 3.3.2. Код Хаффмена для примера 3.3.3 Символ Вероятность Собственная информация Код 1 ОО 01 Х1 Х2 Итак, мы про эффективное кодирование для ДИБП может быть ли использовать неравномерный код, основанный ого, эффективность процедуры кодирования в из,/ символов одновременно. Таким образом, ет быть закодирован неравномерным кодом со имвол, которое может быть сделано как угодно демонстрировали, что символьной основе, ес Хаффмена, Кроме т ри кодировании блоко энтропией Н(Х) мож битов на исходный с 1:.;::;,',: выполнено на по :-':,:::;.яяа алгоритме '-; .увеличивается п ';.".'; выход ДИБП с ."'::; средним числом "' близким к Н(Х) 0,45 1,15б 0,35 1,520 0,20 НЩ--1,518 бит/символ Я 1-"1,55 бит/символ Э ективность 97,9 % оа 010 011 100 ци по !1!О 1111 Таблица З.ЗЗ.
Код Хаффмена для кодирования пар символов Собственная ин о 'мация Код Вероятность Пара символов 10 001 010 011 111 ОООО 0001 1100 1101 ЗЗ.2. Дискретные стационарные источники В предыдущем разделе мы описали эффективное кодирование выхода дискретного источника без памяти (ДИБП). В этом разделе мы рассмотрим дискретные источники, для которых последовательность символов выхода является статистически зависимой. Мы ограничим наше исследование источниками, которые являются статистически стационарными (однородными во времени). Оценим энтропию некоторой последовательности символов от стационарного источника. Из определения в (3.2.13) и результата, данного в (3.2.15), энтропия блока случайных переменных Х, Х, ...Х, равна н(х,хг...х„)=') н(х,~х,х,...х,,), (3.3.14) ~! где Н(Х, , 'Х,Хг ...Х,,) — условная энтропия 1-го символа при условии, что источник выдал предыдущие 1 — 1 символов.
Энтропия на символ для х-символьного блока определяется как Н,(Х) = — Н(Х,Хг ...Х,). 1 (3.3.15) Мы определяем количество информации стационарного источника как энтропию на символ в (3.3.15) в пределе при Й-+сс, т.е. Н„(Х) = 1шз Н (Х) = 11пз — Н(Х,Х.. Х, ) . 1 (3.3.16) Ф-эв Ф-» о /~ Существование этого предела установлено ниже. В казестве альтернативы мы можем определять энтропию на символ источника как условную энтропию Н(Х, ~х,хг" Х,,) в пределе при Ф вЂ” мю.
К счастью, этот предел также существует и идентичен пределу в (3.3.16). То есть (3.3.17) Н„(Х)=11пзн(Х, ~х,хг...хьч). Этот результат также установлен ниже. Наше изложение использует подход Гвллагера (1968). Во-первых, мы покажем, что Н(х„! Х,Хг ...Х„,) < Н(Х„, ~ Х,Хг ...Х,,) (3.3.18) для М2. С учетом предыдущего результата, согласно которому наложение условий на случайную переменную не может увеличивать ей энтропию, мы имеем 9о х~ х1 0,2025 х~ хг 0,1575 хг х1 0,1575 хг хг 0,1225 х1 хз 0,09 хз х1 0,09 хг хз 0,07 хз хг 0,07 хз хз 0,04 2Н(Х)=3,036 бит/пара символов; гг Я, = 1,534 бит/символ; 2,312 2,676 2,676 3,039 3,486 3,486 3,850 3.850 4,660 Я, = 3,0675 бит/пара символов Эффективность 99,0 % (3.3.19) н,(х) < н,,(х). (3.3.22) Следовательно, Н„(Х) — не возрастающая последовательность (с ростом й).
Поскольку Н„(Х) и условная энтропия Н(Х„1Х,Х,,Х,,) не отрицательны и не возрастающие (с ростом й), оба предела должны существовать. Их предельные выражения могут быть установлены с использованием (3.3.14) и (3.3.15), чтобы выразить Н„,(Х) как Н„,(Х) =. Н(Х,Х, ...Х,,)+ 1 к+у + (Н(х„. ~Х, ...Х„,)+Н(Х „~ Х„...Х,)+...+Н(Х„,, ! Х, ...Х„,Я. ! 'Ф / Так как условная энтропия не возрастает, первый член в квадратных скобках является верхней границей для других слагаемых. Следовательно, Н„„(Х) ~ — Н(Х,Х, ...Х„,)+ Н(х„~ Х,Х, ...Х~,). (3.3.23) 1 /+1 й+ /' 1+у Для фиксированного /г в пределе для (3.3.23) при / -+ о получаем Н.(Х) <Н(А 1Х~Х2- А-ю) (3.3.24) Но (3.3.24) справедливо для всех /г, следовательно, это справедливо и для Ф-+ '. Поэтому Н„(Х) < 1ип Н(Х 1Х,Х ...Х„,) . (3.3.25) С другой стороны, с учетом (3.3.21) мы получаем в пределе для Ф -э ю Н„(Х) < 11~ Н(Х,! Х,Х, ...Х, ~), (3.3.2б) что устанавливает (3.3.17).
Теперь предположим, что мы имеем дискретный стационарный источник, который выдает .У символов с энтропией на символ Н,(Х). Мы можем кодировать последовательность ,У символов кодом Хаффмена переменной длины, который удовлетворяет префиксному условию прн использовании процедуры, описанной в предыдущем разделе. Результирующий код имеет среднее число бит для блока с,У 91 н(х, 1хх,...х,,) < н(х, ~х х,...х„,).
В силу сгационарности источника имеем Н(Х, ~ Х,Х, ...Х~,,) = Н(Хя, ~ Х,Х,. Х,,), (3.3.2О) Следовательно, (3,3.18) следует немедленно. Этот результат демонстрирует, что Н(Х, 1 Х,Х, " Хьч) — не возрастающая последовательность (с ростом й). Во-вторых, мы имеем результат Н,(Х) > Н(Х,1Х,Х, ".Х,,), (3 3.21) который следует непосредственно из (3.3.14) и (3.3.15) и того факта, что последний член в сумме (3.3.14) является нижней границей для каждого из остальных й — 1 членов.
В-третьих, по определению Н, (Х) мы можем записать Н,(Х) — — (Н(Х,Х, ...Хьч)+Н(Х, ~ Х, ...Х,,)1= 1 г(/' 1)Н~-~(х)+Н(Хк!Х~""Хьч)3- Нк-И)+ Ня(х) 1 /~ — 1 1 что приводит к символами, который удовлетворяет условию Н(Х, ...Х,) ь У1, < Н(Х, ...Х,)+1. (3.3.27) У1= Я,/.У битца Деля обе части (3.3.27) на,У, мы получаем границы для среднего числа исходный символ как 1 Н,(Х) <Я < Н,(Х)+ —.
(3.3.28) Увеличивая размер блока.У, мы можем приближаться к Н, (Х) сколь угодно близко, и в пределе, когда .У -+ о, Я удовлетворяет соотношению Н„(Х) < Я < Н„(Х) + а, (33.29) где с стремится к нулю как 1/У. Таким образом, эффективное кодирование стационарных источников может быть выполнено, если кодировать большие блоки символов в кодовые слова.
Мы должны подчеркнуть, однако, что конструкция кода Хаффмена требует знания совместных ФПВ для.У-символьных блоков. 3.3.3. Алгоритм Лемпела-Зива Из нашего предшествующего обсуждения следует, что алгоритм кодирования Хаффмена приводит к оптимальному кодированию источника в том смысле, что кодовые слова удовлетворяют префиксному условию и средняя длина кодового блока минимальна. Конструируя код Хаффмена для ДИБП, мы должны знать вероятности появления всех исходных символов. В случае дискретного источника с памятью мы должны знать совместные вероятности всех блоков длины л > 2.
Однако на практике статистика выхода источника чаще всего неизвестна. В принципе возможно оценить вероятности выхода дискретного источника, наблюдая длинную информационную последовательность, выдаваемую источником, и получая требуемые вероятности опытным пугем. Такой метод пригоден для оценки вероятностей отдельных символов (р„~. Однако вычислительная сложность оценки совместных вероятностей чрезвычайно высока, Следовательно„ использование метода кодирования Хаффмена для многих реальных источников с памятью вообще непрактично. В отличие от алгоритма кодирования Хаффмена алгоритм кодирования Лемпела — Зива разработан так„чтобы бьггь независимым от статистики источника. Следовательно, алгоритм Лемпела-Зива принадлежит классу универсальных алгоритмов кодироваинн источника.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
