Блочное кодирование по алгоритму Шеннона-Фано
Алгоритм Шеннона-Фано часто применяют и для блочного кодирования. При этом также существенно повышается эффективность кодирования. Для иллюстрации такого кодирования рассмотрим процедуру эффективного кодирования двоичным числовым кодом сообщений, генерируемых источником сообщений с объемом алфавита, равным 2 (m = 2), т.е. с алфавитом, состоящим только из двух символов m1и m2 с вероятностями появления P(m1) = 0,9 и P(m2) = 0,1 и, следовательно, с энтропией Н = 0,47.
При посимвольном кодировании по алгоритму Шеннона-Фано эффект отсутствует, так как на каждый символ сообщения будет приходиться один символ кода, состоящий из одного элемента.
Произведем теперь кодирование по алгоритму Шеннона-Фано блоков, состоящих из комбинаций двух символов источника сообщений, считая символы взаимно независимыми. Результат приведен в табл. 11.2.
Таблица 11.2
| Блоки | Вероятности | Номера разбиений | Кодовые комбинации |
| m1m1 m1m2 m2m1 m2m2 | 0,81 0,09 0,09 0,01 | I II III | 1 01 001 0001 |
Среднее число элементов символов кода на один символ исходного сообщения, вычисленное по формуле (11.2), равно 0,645, что значительно ниже, чем при посимвольном кодировании.
Кодирование блоков, соответствующих комбинациям из трех символов источника сообщений, дает еще больший эффект. Результат приведен в табл. 11.3.
Таблица 11.3
| Блоки | Вероятности | Номера разбиений | Кодовые комбинации |
| m1 m1 m1 | 0,729 | I | 1 |
| m2 m1 m1 | 0,081 | III | 011 |
| m1 m2 m1 | 0,081 | II | 010 |
| m1 m1 m2 | 0,081 | IV | 001 |
| m2 m2 m1 | 0,009 | VI | 00011 |
| m2 m1 m2 | 0,009 | V | 00010 |
| m1 m2 m2 | 0,009 | VII | 00001 |
| m2 m2 m2 | 0,001 | 00000 |
|
|
|
В этом случае среднее число элементов символов кода на один символ исходного источника сообщений равно 0,53.
Теоретический минимум Н = 0,47 может быть достигнут при кодировании блоков неограниченной длины.
Алгоритм Шеннона-Фано не всегда приводит к однозначному построению кода, так как при разбиении на подгруппы можно сделать большей по суммарной вероятности как верхнюю, так и нижнюю подгруппу. Этого недостатка лишен алгоритм Хаффмена, который гарантирует однозначное построение эффективного кода.
Лекция 7.
Тема: Алгоритм эффективного кодирования Хаффмена.
План лекции.
1. Описание алгоритма Хаффмена.
2. Граф кодирования по алгоритму Хаффмена.
Описание алгоритма Хаффмена
Суть этого алгоритма, при использовании двоичного кода, состоит в следующем. Все символы алфавита источника сообщений ранжируют, т.е. выписывают в столбец в порядке убывания вероятностей их появления. Два последних символа объединяют в один вспомогательный символ, которому приписывают суммарную вероятность.
|
|
|
Вероятности символов, не участвовавших в объединении, и вероятность вспомогательного символа вновь ранжируют, т.е. располагают в порядке убывания вероятностей в дополнительном столбце и два последних символа объединяются. Процесс продолжается до тех пор, пока не получим единственный вспомогательный символ с вероятностью, равной единице. Пример кодирования по алгоритму Хаффмена приведен в табл. 12.1.
Таблица 12.1
Граф кодирования по алгоритму Хаффмена
На рис. 12.1 показан граф кодирования (кодовое дерево), который иллюстрирует ранжирование символов на группы и отдельные символы, причем из точки, соответствующей вероятности 1, направляем две ветви: одной из них (с большей вероятностью) присваиваем символ 1, а второй – символ 0.
Такое последовательное ветвление продолжим до тех пор, пока не дойдем до вероятности каждого символа. Двигаясь по кодовому дереву сверху вниз, можно записать для каждого символа источника сообщений соответствующую ему комбинацию (кодовый символ).
Различные символы, генерируемые источником сообщения, и соответствующие им кодовые символы представлены в табл. 12.2.
|
|
|
Таблица 12.2
| m1 | m2 | m3 | m4 | m5 | m6 | m7 | m8 |
| 01 | 00 | 111 | 110 | 100 | 1011 | 10101 | 10100 |
Этот алгоритм можно использовать и при ином числовом основании кода, а также использовать блоки, как это рассмотрено в алгоритме Шеннона-Фано.
Рис 12.1. Граф кодирования по алгоритму Хаффмена
Эффективность рассмотренных алгоритмов достигается благодаря присвоению более коротких кодовых комбинаций (кодовых символов) символам источника сообщений, вероятность которых более высока, и более длинных кодовых комбинаций – символам источника сообщений с малой вероятностью. Это ведет к различиям в длине кодовых символов и, как следствие, к трудностям при их декодировании. Для разделения отдельных кодовых символов можно использовать специальный разделительный элемент, но при этом существенно снижается эффективность кода, так как средняя длина кодового символа фактически увеличивается на один элемент символа кода.
Целесообразнее обеспечить декодирование без введения дополнительных элементов символов. Этого можно добиться, если в эффективном коде ни одна кодовая комбинация не будет совпадать с началом более длинной кодовой комбинации. Коды, удовлетворяющие этому условию, называют префиксными кодами (префиксом или началом называют первый элемент в кодовом символе, а последний элемент – окончанием или постфиксом).
|
|
|
Легко заметить, что коды, построенные по алгоритмам Шеннона-Фано или Хаффмена, являются префиксными.
Лекция 8.
Дата добавления: 2018-05-12; просмотров: 2221; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!