В.Н. Васюков - Теория электрической связи (1266498), страница 38
Текст из файла (страница 38)
Затем все буквы делятся на две(неравные в общем случае) группы так, что сумма вероятностейбукв для обеих групп одинакова или примерно одинакова, и в качестве первого символа кодового слова каждой букве первой группы присваивается кодовый символ 0, а каждой букве второй группы – символ 1 (или наоборот). Далее первая и вторая группыделятся на подгруппы в соответствии с принципом равной вероятности, и эта процедура продолжается до тех пор, пока алфавит источника не будет исчерпан.
Пример построения кода Шеннона –Фано приведен в табл. 8.1.Построение кода Шеннона – ФаноСимвол и еговероятностьp( i )iДлинакомбинацииКомбинация кодовых символов1-й2-й3-й4-й5-йТ а б л и ц а 8.16-йi11/400221/401231/410241/811051/16111061/321111071/64111110681/641111116345На первом шаге процедуры все символы алфавита источникаделятся на две группы, причем в первую группу входят символы2 , которым соответствует суммарная вероятность 1/2, а во1 ивторую – все остальные символы. Символам 1 и 2 приписывается в качестве первого кодового символа символ 0, а всем осталь-2388. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИным символам источника – кодовый символ 1. На втором шагепервая и вторая группы рассматриваются по отдельности, при этомв первой группе содержатся всего два символа, которые получаютв качестве второго кодового символа 0 и 1 соответственно.
Такимобразом, символу источника 1 ставится в соответствие кодовоеслово 00, а символу 2 – слово 01. Вторая группа символов источника, включающая символы 3 , 4 , 5 и 6 , делится на две части в соответствии с их вероятностями, при этом символ 3 , которому соответствует вероятность 1/4, получает в качестве второгосимвола кодового слова символ 0, а остальные символы источника – символ 1. Далее процесс продолжается до тех пор, пока не останется группа из двух символов – в данном примере это символы 7 и 8 , – которым присваиваются кодовые символы 0 и 1.Необходимо обратить внимание на следующее свойство полученного кода: ни одна кодовая комбинация не является началом какой-либо другой кодовой комбинации (так называемое префиксноеправило).
Такие коды называются неперекрываемыми (неприводимыми). Декодирование неприводимого кода может быть осуществлено на основе дерева декодирования105 (рис. 8.1), отвечающегонекоторому конечному автомату, который переходит из начального состояния в другие состояния в соответствии с очередным символом кодовой последовательности.Перед декодированием конечный автомат устанавливается вначальное состояние НС, а дальнейшие переходы зависят только11111801НС13000100145671111121011Рис. 8.1. Дерево декодирования для кода Шеннона– Фано(табл. 8.1)105Деревом называется граф, не содержащий циклов (замкнутых путей).2398.4.
Кодирование источникаот поступающих символов кода, при этом все концевые состояния(«листья» дерева) соответствуют декодированным символам алфавита источника; по достижении листа автомат переходит вновь вначальное состояние. Поскольку с поступлением последнего кодового символа декодирование кодового слова всегда заканчивается,префиксные коды называют также мгновенными [16]. Существуютоднозначно декодируемые коды, не обладающие префикснымсвойством и не являющиеся мгновенными, однако их декодирование требует больших объемов памяти декодера и приводит кбольшим задержкам результата.Средняя длина кодовой комбинации для построенного кода8 p(i 1i) i 0,75 2 0,125 3 0,0625 4 0,03125 5 0,03125 6 2,469 .Согласно теореме Шеннона при оптимальном кодированииможно достичь средней длины8min H ( ) / log 2 p(i 1i )logp(i) 2.469 .Таким образом, построенный код является оптимальным.
Такполучилось вследствие того, что на каждом шаге процедуры построения кода удавалось разделить символы на группы с равнымивероятностями. Заметим, что восемь различных символов источника можно представить восемью комбинациями равномерного двоичного кода (Бодо), при этом длина каждой кодовой комбинацииравняется, очевидно, трем.
Уменьшение средней длины кодовойкомбинации (и, следовательно, увеличение скорости передачи информации) составляет в данном примере около 22 %. Если при делении символов на группы их суммарные вероятности оказываются неравными, выигрыш может быть не столь значительным.Определим вероятность появления определенного символа вкодовой комбинации (пусть это будет символ 1).
Очевидно, ееможно найти следующим образом: а) подсчитать количества единиц во всех кодовых словах; б) умножить эти количества на вероятности соответствующих кодовых слов; в) просуммировать полученные величины; г) отнести результат к средней длине кодовогослова. Таким образом,p(1) 0, 25 0, 25 20,125 30,0625 40,03125 (5 6)0,0156252, 4690,5 .2408. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИИтак, при оптимальном кодировании источника кодовые символы равновероятны; такое кодирование является безызбыточным.Источник вместе с кодером можно рассматривать как новый источник с алфавитом, состоящим из кодовых символов; энтропия иизбыточность этого источника – это энтропия и избыточность кода. Оптимальный код имеет максимальную энтропию и нулевуюизбыточность.Кодирование источника по методу Хаффмена.Другим широко известным методом кодирования источникаявляется метод Хаффмена106.
Процедура кодирования состоит изследующих шагов.1. Все символы алфавита записываются в порядке убываниявероятностей.2. Два нижних символа соединяются скобкой, из них верхнемуприписывается символ 0, нижнему 1 (или наоборот).3. Вычисляется сумма вероятностей, соответствующих этимсимволам алфавита.4. Все символы алфавита снова записываются в порядке убывания вероятностей, при этом только что рассмотренные символы«склеиваются», т.е. учитываются как единый символ с суммарнойвероятностью.5.
Повторяются шаги 2, 3 и 4 до тех пор, пока не останется ниодного символа алфавита, не охваченного скобкой.Скобки в совокупности образуют дерево. Код Хаффмена длянекоторого символа алфавита находится путем последовательнойзаписи нулей и единиц, встречающихся на пути от корня дерева(корню соответствует суммарная вероятность 1) до листа, соответствующего данному символу.
Полученное дерево, очевидно, является деревом декодирования.Для примера, показанного на рис. 8.2, получаются следующиекодовые комбинации:11;01;101:100;2341001; 6 0000; 7 00011; 8 00010.5Энтропия алфавита H ( ) 2,628 . Средняя длина кодовогословаn pii 1i 0,3 2 + 0,2 2 + 0,15 3 + 0,15 3 + 0,1 3 ++ 0,04 4 + 0,03 5 + 0,03 5 = 2,66.106Доказана оптимальность кода Хаффмена в смысле наименьшей средней длины кодовых слов [16].2418.4. Кодирование источникаСледовательно, код не оптимален, но очевидно, что он довольно близок к оптимальному.
Для сравнения: равномерный код дляэтого случая имеет среднюю длину кодового слова 3 (совпадающую для равномерного кода с длиной каждого кодового слова).1:10,32:110,23:НС110,1504:000,155:10,16:7:0,03000,04018:10,030Рис. 8.2. Дерево декодирования для кода ХаффменаВероятность символа 1 в последовательности кодовых комбинаций находится как среднее количество единиц, отнесенное ксредней длине кодового словаp(1) 2 0,3 0,2 2 0,15 0,15 0,1 2 0,03 0,03 0,541 .2,66Неоптимальность кода проявляется в неравенстве вероятностейкодовых символов (0,541 для 1 и 0,459 для 0).
Избыточность кода,как легко видеть, равна 0.005.2428. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИЗАМЕЧАНИЯ1. Из рассмотренных примеров не должно составиться ложное впечатление, будто код Шеннона – Фано оптимален, а кодХаффмена – нет. Оптимальность кода Шеннона – Фано в рассмотренном примере объясняется специально подобранными вероятностями символов, так, что на каждом шаге вероятностиделятся ровно пополам.2.
В приведенных примерах предполагалось, что символы в сообщении являются независимыми (т. е. вероятность появления всообщении любых двух символов рядом равна произведению вероятностей появления каждого из символов в отдельности). В реальных сообщениях на естественных языках символы не являютсянезависимыми; в таких случаях следует кодировать не отдельныесимволы (буквы), а группы букв или слова. Это уменьшает зависимость и повышает эффективность кода.3.
Кодирование групп символов вместо отдельных символовтакже повышает эффективность кодирования в случае независимого источника с сильно различающимися вероятностями символов, как это видно из следующего примера.Пример 8.6. Рассмотрим источник, вырабатывающий два независимых символа с вероятностями 0,1 и 0,9. В этом тривиальномслучае методы кодирования Хаффмена и Шеннона – Фано приводят к одинаковому коду: символы алфавита кодируются символами0 и 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
