Прокис Дж. Цифровая связь (2000) (1151856), страница 21
Текст из файла (страница 21)
Следователь полученные коды одинаково эффективны. Кроме того, назначение «О» верхнему перехо «1» нижнему (менее вероятному) переходу выбрано произвольно. Мы можем пр поменять местами 0 н 1 и получить еще эффективный код, удовлетворяющий префиксно условию. увелич Та Пример 3.3.2. В качестве второго примера определим код Хаффыена для выхо ДИБП, нллюстрируемый на рис. 3.3.6. Энтропия этого источника Н(Х) = 2,63 бит/сим Код Хаффмена, показанный на рис.3.3.6, имеет среднюю длину Я=2,70 бит/симв Следовательно, его эффективность составляет 0,97. Алгоритм кодирования переменной длины (Хаффмеиа), описанный в предыду примерах, генерирует префиксный код, имеющий среднюю длину К, кото удовлетворяет (3.3.9).
Однако вместо посимвольного кодирования более эффективв является процедура, основанная на кодировании блоков из / символов одновременно. таком случае границы в (3.3.9) в теореме кодирования источника 11 становятся другими: Ит< .УН(Х) < Яэ <,УН(Х) +1, (3 3 12) !выпол! так как энтропия,/-символьного блока от ДИБП равна,/Н(Х), и Я< — среднее число бит~увелич в /-символьном блоке. Если мы разделим (3.3.12) на /, то получим !выход Н(Х) « — ' Н(Х)+ —, (3.3.13) 1 ,У ,/ лизки О,Зб Символ Кол 0,1Е О,!3 0,12 о,!о 0,09 о,оя Н(Л) = 2,бз Я = 2,70 0,02 Рис.
3.3.6. Код Хаффмеиа для примера 3.3.2 где Р, /./ вв Я вЂ” среднее число битов на исходный символ. Следовательно, Р можно сделать как угодно близким к Н(Х), выбирая, /достаточно большим. Пример 3.3.3. Выход ДИБП состоит из символов х„х, и х, с вероятностями 0,45, 0,35 н 0,20 соответственно. Энтропия этого источника Н(Х) =1„518 бит/символ. Код Хаффмена для этого источника, данный в табл.3.3.2, требует К=1,55бит/символ и приводят к эффективности 97,9о~о, Если посредством алгоритма Хаффмена символы закодированы ларами, результирующий код выглядит так, как показано в табл. 3.3.3. Энтропия источника , для пар символов 2Н(Х) = 3,036 бит/пара символов.
С другой стороны, код Хаффмена требует Я, = 3,0675 бит/пара символов. Таким образом, эффективность кодирования увеличилась до 2Н(Х)/Я, = 0,990 (до 99,0 %). Собственная информация Символ Вероятность Код 1 00 01 Х! Х2 ХЗ Итак, мы продемонстрировали, что эффективное кодирование для ДИБП может быть выполнено на посимвольной основе, если использовать неравномерный код, основанный на алгоритме Хаффмена. Кроме того, эффективность процедуры кодирования увеличивается при кодировании блоков из / символов одновременно. Таким образом, выход ДИБП с энтропией Н(Х) может быть закодирован неравномерным кодом со средним числом битов на исходный символ, которое может быть сделано как угодно близким к Н(Х).
89 Таблица 3.3.2. Код Хаффмена для примера 3.3.3 0,45 1,156 0,35 1,520 0,20 2,33 Н(Х)=1,51В бит/символ Я!=1,55 бит/символ Э ективность 97,9 % оо О1О оп 100 1О! по гцо 11!1 Таблица 3.3.3. Код Хаффмена для кодирования пар символов Собственная ин о мация Вероятность Пара символов Код х~ х1 0,2025 2,312 10 Х! Х2 0,1575 2,676 001 Х2 Х1 0,1575 2,676 010 Х2 Х2 0,1225 3,039 011 Х1 Х3 0,09 3,486 111 Х3 Х~ 0,09 3,486 0000 Х2 Хз 0,07 3,850 0001 Х3 Хг 0,07 3,850 1100 Х3 Х3 0,04 4,660 1101 2Н(Х)=3,036 бит/пара символов; А, = 3,0675 бит/пара символов —,' Т = 1,534 бит/символ; Эффективность 99,0 % Сд Н(Х„ Вс котор3 сумме В- что пр Сл Пс возрас могут Та верхне На Поэта~ Н„(Х) =!ппН(Х, ( Х,Х2 ...Х„,). (3.3.17) Этот результат также установлен ниже.
Наше изложение использует подход Галлагера (1968). Во-первых, мы покажем, что что ус.. Те выдаез Н(Х, )Х,Х,...Х,,)<Н(Х„, ~Х,Х2...Х 2) (3.3.18) для й>2. С учетом предыдущего результата, согласно которому наложение условий н случайную переменную не может увеличивать ее энтропию, мы имеем послед удовле преды, 9о 3.3.2.
Дискретные стационарные источники В предыдущем разделе мы описали эффективное кодирование выхода дискретног источника без памяти ЯИБП). В этом разделе мы рассмотрим дискретные источники, д которых последовательность символов выхода является статистически зависимой. Мь ограничим наше исследование источниками, которые являются статистическ стационарными (однородными во времени).
Оценим энтропию некоторой последовательности символов от стационарног источника. Из определения в (3.2.13) и результата, данного в (3.2.15), энтропия блок случайных переменных Х, Х, ... Х„равна Н(ХХ,".Х,) = ХН(Х,|ХХ,".Х,,), (3.3.14) г=! где Н(Х, , 'Х,Х2 ...Х,,) — условная энтропия /-го символа при условии, что источник выд ад предыдущие /-1 символов. Энтропия на символ для /г-символьного блока определяется как НФ (Х) Н(Х1Х2 " Х2 ) ' 1 (3.3.15) Мы определяем количество информации стационарного источника как энтропию н символ в (3.3.15) в пределе при А-+<с, т.е.
Н„(Х) = !ппН„(Х) =1пп — Н(Х,Х2 .Х,). 1 (3.3.16) Й-+а Существование этого предела установлено ниже. В качестве альтернативы мы можем определять энтропию на символ источника ка условную энтропию Н(Х,~Х,Х2" Х„,) в пределе при й-+со. К счастью, этот преде также существует и идентичен пределу в (3.3.16). То есть н(х, ~ х,х, ...х„,) < н(х„!Х,х,...х„,). В силу стационарности источника имеем (3.3.19) = — [(/г-1)н,,(х)+ Н(х„~ Х, Х„,)~ < — Н„,(Х)+ — Н,(Х), 1 й-1 1 то приводит к Н„(Х) ~ Н„,(Х). (3.3.22) Следовательно, Н„(Х) — не возрастающая последовательность (с ростом /с). Поскольку Н„(Х) и условная энтропия Н(х„!Х,Х,...Х„,) не отрицательны и не озрастающие (с ростом /с), оба предела должны существовать. Их предельные выражения агут быть установлены с использованием (3.3.14) и (3.3.15), чтобы выразить Н„„(Х) как На+~(Х) . Н(ХХз -А-~)+ 1 +/ + — [Н(х„~ Х, ...Х,,)+ Н(х„„~ Х, ...
Х„) + ... + Н(Х„„~ Х, ... Х„,, ф 1 х+/' Так как условная энтропия не возрастает, первый член в квадратных скобках является ,рхней границей для других слагаемых. Следовательно, Н„„(Х) < — Н(Х,Х, ...Х,,)+ — Н(Х, ! Х,х« ...Х„,). (3.3.23) 1 /+1 +/ +/ Для фиксированного /~ в пределе для (3.3.23) прн /' -+ со получаем ню(х) — Н(х ! Х$Х2- Х -3) (3.3.24) Но (3.3.24) справедливо для всех /г; следовательно, это справедливо н для й-+ с. >этому н„(х) < 11щн(х„~ х,х, ...х„,), (3.3.25) С другой стороны, с учетом (3.3.21) мы получаем в пределе для /г — э со Н„(Х) > 1пп Н(Х, ~ Х,Х, ... Х,, ), (3.3.26) > устанавливает (3.3.17). Теперь предположим, что мы имеем дискретный стационарный источник, который дает ./ символов с энтропией на символ Н, (Х) . Мы можем кодировать :ледовательность У символов кодом Хаффмена переменной длины, который ~влетворяет префиксному условию при использовании процедуры, описанной в дьп1ущем разделе.
Результирующий код имеет среднее число бит для блока с,/ 9! Н(х„~ Х,Х, ... Х,,) = Н(Х,, ~ Х,Х, ... Х~,) . (3.3.20) Следовательно, (3.3.18) следует немедленно. Этот результат демонстрирует, что Н(Х„~ Х,Х, " Х,,) — не возрастающая последовательность (с ростом /г). Во-вторых, мы имеем результат НМ (х) > Н(хь 1 Х1Х2 ХА ) (3.3.21) соторый следует непосредственно из (3.3.14) и (3.3,15) и того факта, что последний член в :умме (3.3.14) является нижней границей для каждого из остальных /с-1 членов.
В-третьих, по определению Н, (Х) мы можем записать Н,(Х) = 1 [Н(Х,Х, ...Х,,)+Н(Х,! Х, ...Х,,)3= символами, который удовлетворяет условию 1 2 4 5 6 7 8 9 10 11 14 15 16 3.3.3. Алгоритм Лемпела-Зива Из нашего предшествующего обсуждения следует, что алгоритм кодированн Хаффмена приводит к оптимальному кодированию источника в том смысле, что кодовы слова удовлетворяют префиксному условию и средняя длина кодового блока минимальна Конструируя код Хаффмена для ДИБП, мы должны знать вероятности появления все исходных символов.
В случае дискретного источника с памятью мы должны зна совместные вероятности всех блоков длины и > 2. Однако на практике статистика выход источника чаще всего неизвестна. В принципе возможно оценить вероятности выход дискретного источника, наблюдая длинную информационную последовательность выдаваемую источником, и получая требуемые вероятности опытным путем. Такой мето пригоден для оценки вероятностей отдельных символов 1р,~. Однако вычислительн сложность оценки совместных вероятностей чрезвычайно высока. Следовательно использование метода кодирования Хаффмена для многих реальных источников с память вообще непрактично. В отличие от алгоритма кодирования Хаффмена алгоритм кодирования Лемпела — Знв разработан так, чтобы быть независимым от статистики источника.
Следовательно алгоритм Лемпела †Зи принадлежит классу универсальных алгоритмов кодирован источника. Это — алгоритм переменно-фиксированной длины, а кодирование выполняетс так, как описано ниже. В алгоритме Лемпела — Зива последовательность с выхода дискретного источник делится на блоки переменной длины, которые называются фразами. Каждая новая фраз представляет собой последовательность символов источника„отличающуюся от некоторо предыдущей фразы 'в последнем символе. Фразы перечислены в словаре, которь сохраняет расположение существующих фраз.
При кодировании новой фразы мы прост ' определяем адрес существующей фразы в словаре и добавляем в конец новый символ. Как пример рассмотрим бинарную последовательность 10101101001001110101000011001110101100011011. Деление последовательности, как описано выше, производит следующие фразы: 1, О, 10, 11, 01, 00. 100, 111, 010, 1000, 011, 001, 110„ 101, 10001, 1011. Мы видим, что каждая фраза в последовательности — соединение одной из предыдущи ' фраз с новым выходным символом источника. Для кодирования фразы мы конструируе словарь, как показано в табл. 3.3.4. 92 Н(Х,...Х,) < кз <Н(Х,...Х,)+1. (3.3.27) Деля обе части (3.3.27) на,У, мы получаем границы для среднего числа Я = Яз у',У бит и исходный символ как Н,(Х) <Я < Н,(Х)+ —.
(3.3.28) Увеличивая размер блока,У, мы можем приближаться к Н, (Х) сколь угодно близко, и пределе, когда,У -+ о, Р удовлетворяет соотношению Н„(Х) < Я < Н„(Х) + в, (3.3.29) где е стремится к нулю как 1/У. Таким образом, эффективное кодирование стационарны источников может быть выполнено, если кодировать большие блоки символов в кодовы слова. Мы должны подчеркнуть, однако, что конструкция кода Хаффмена требует знан совместных ФПВ для У-символьных блоков. .1 до 11 кажл коне ячей фра ното фр фр соот~ пять вооб след мере Эффе она исто слов; «Сж~ мног разл~ Таблица р.3.4.
Словарь для алгоритма Лемпела — Зива Содержимое слов я Расположение в слова е Кодовое слово Ячейки словаря пронумерованы последовательно, начиная с 1 и далее, в данном случае до 1б, что является числом фраз в последовательности. Различные фразы, соответствующие ' каждой ячейке, также перечислены, как показано в таблице. Кодовые слова , конструируются путем соединения двух частей. Первая часть представляет собой номер ' ячейки словаря (в двоичной форме) предыдущей фразы, которая соответствует новой фразе, кроме последнего символа. Вторая часть — это новый символ, выданный .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
