Тема: Алгоритм эффективного кодирования Шеннона-Фано.
План лекции.
1. Описание алгоритма Шеннона-Фано.
2. Граф кодирования по алгоритму Шеннона-Фано.
3. Сравнение эффективного кодирования равномерным кодом и
неравномерным кодом по алгоритму Шеннона-Фано.
4. Блочное кодирование по алгоритму Шеннона-Фано.
Описание алгоритма Шеннона-Фано
Суть этого алгоритма при использовании двоичного кода (объем алфавита элементов символов кода равен 2), заключается в следующем.
Все символы алфавита источника сообщений ранжируют, т. е. располага-ют в порядке убывания вероятностей их появления. Затем символы алфавита делятся на две группы приблизительно равной суммарной вероятности их появления. Все символы первой группы получают «0» в качестве первого элемента кодового символа, а все символы второй группы – «1». Далее группы делятся на подгруппы, по тому же правилу примерно равных суммарных вероятностей, и в каждой подгруппе присваивается вторая позиция кодовых символов. Процесс повторяется до закодирования всех символов алфавита кодируемого источника сообщений. В кодовый символ, соответствующий последней группе, добавляется в качестве последнего элемента «0» для того, чтобы начальный элемент символов кода не совпадал с конечным, что позволяет исключить разделительные элементы между символами кода.
Таблица 11.1 иллюстрирует процесс построения кода Шеннона-Фено на примере источника сообщений, алфавит которого состоит из восьми символов.
|
|
|
Таблица 11.1
| Номер | Символы | Вероятности | Номера | Кодовые |
| символа (i) | алфавита (mi) | (Рi) | разбиений | символы |
| 1 | m1 | 1/2 |
I
II
III
IV
V
VI
VII | 0 |
| 2 | m2 | 1/4 | 10 | |
| 3 | m3 | 1/8 | 110 | |
| 4 | m4 | 1/16 | 1110 | |
| 5 | m5 | 1/32 | 11110 | |
| 6 | m6 | 1/64 | 111110 | |
| 7 | m7 | 1/128 | 1111110 | |
| 8 | m8 | 1/256 | 11111110 |
Граф кодирования по алгоритму Шеннона-Фано
На рис. 11.1 представлен граф кодирования (кодовое дерево), который показывает, как «расщепляется» ранжированная последовательность символов кодируемого источника сообщений на группы и отдельные символы и какие кодовые символы присваиваются группам и отдельным символам алфавита источника сообщений на каждом шаге разбиения.
Рис 11.1. Граф кодирования по алгоритму Шеннона-Фано.
Алгоритм Шеннона-Фано применим и при иных числовых основаниях кода (k > 2). В этом случае алгоритм получения кода аналогичен рассмот-ренному примеру, только алфавит кодируемого источника сообщений разбивается на k групп и подгрупп примерно одинаковой суммарной вероятности.
Сравнение эффективного кодирования равномерным кодом и
Неравномерным кодом по алгоритму Шеннона-Фано
|
|
|
Представляет интерес сравнение эффективного кодирования равномер-ным кодом и неравномерным кодом по алгоритму Шеннона-Фано.
В качестве примера рассмотрим предложенный выше (табл. 11.1) источник сообщений с объемом алфавита равным 8 и соответствующими вероятностями появления отдельных символов (Pi). Для кодирования используем двоичный код (k = 2).
Энтропия рассмотренного источника сообщений (Hи) определяется по формуле Шеннона:
(бит/символ).
Максимально же возможное значение энтропии источника сообщений (Hu.max), при условии равновероятного и взаимно независимого появления символов, находится по формуле Хартли:
.
Следовательно, избыточность рассматриваемого источника сообщений (Rи) может быть найдена из соотношения:
Используя формулу для эффективного равномерного кода (6.1) при k = 2, получим значность равномерного двоичного кода (пр):
и избыточность равномерного кода (Rрк):
Энтропия элементов символов равномерного кода ( 
), т.е. количество информации, приходящееся на один элемент символа кода, будет равна:
(бит / элемент символа кода). (11.1)
При использовании эффективного кодирования по алгоритму Шеннона-Фано соответствующие информационные параметры кода будут следующие.
|
|
|
Средняя длина неравномерного кода (пН)определяется выражением:
, (11.2)
где пi – значность i-го кодового символа, соответствующего символу алфавита mi.
Избыточность неравномерного кода (RНК)определим из соотношения:
.
Энтропия элементов символов эффективного неравномерного кода 
может быть легко найдена:
(бит/элемент символа кода). (11.3)
Из сравнения выражений (11.1) и (11.3) видно, что, при использовании эффективного кодирования по алгоритму Шеннона-Фано, энтропия элементов символов такого неравномерного кода на 50% выше, чем энтропия элементов символов в случае использования равномерного кода. Если предположить, что скорость передачи по каналу элементов символов кода (W) одинакова для равномерного и неравномерного кода, то скорость передачи информации (V), определяемая выражением
,
где Н – энтропия элементов символа кода, также будет на 50% выше при использовании эффективного кодирования по алгоритму Шеннона-Фано по сравнению с равномерным кодированием.
|
|
|
Дата добавления: 2018-05-12; просмотров: 855; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!