Теория передачи сигналов (2 часть)
.pdf
Декодирование сообщения с равномерным двоичным кодом
0001011011010001 |
Двоичное сообщение |
|
|
Группирование |
|
|
||
00 01 01 10 11 01 00 01 |
||
символов |
||
|
||
|
Таблица соответствия |
|
00→А; 01→Т; 10→Е; 11→С |
||
символов буквам |
||
|
||
|
Буквенное сообщение |
|
АТТЕСТАТ |
||
|
|
11
Декодирование сообщения с равномерным двоичным кодом
А |
Т |
Т |
Е |
С |
Т |
А |
Т |
Исходное буквенное |
|
сообщение |
|||||||||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
00 |
01 |
01 |
10 |
11 |
01 |
00 |
01 |
Двоичный код |
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
10 |
01 |
01 |
10 |
11 |
01 |
00 |
01 |
Двоичный код с ошибкой при |
|
декодировании |
|||||||||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
Е |
Т |
Т |
Е |
С |
Т |
А |
Т |
Декодированное сообщение |
|
|
|||||||||
|
|
|
|
|
|
|
|
|
Ошибка в одном разряде приводит к неправильному приёму одной буквы.
12
Алгоритм статистического кодирования Шеннона - Фано
1.Элементы сообщений располагают в первом столбце таблицы в порядке убывания их вероятностей.
2.Элементы сообщений разбивают на две группы с примерно равными суммарными вероятностями. Элементам первой группы в качестве первого знака кодовой комбинации присваивают символ «0», а элементам второй группы — «1».
3.Элементы, входящие в каждую из групп, вновь разбивают на две группы с примерно равными суммарными вероятностями. Элементам вновь полученных первых групп в качестве второго знака кодовой комбинации присваивают «0», а элементам вторых групп — «1».
4.Этот процесс продолжают, пока в каждой из групп не останется по одному элементу.
13
Алгоритм статистического кодирования Шеннона - Фано
|
Рассмотрим |
на |
предыдущем |
примере. |
Сообщение: |
|||||
«аттестат». |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ai |
p(ai) |
|
Разбиения |
|
Код |
qi |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
т |
4/8 |
0 |
|
|
|
|
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
а |
2/8 |
1 |
|
0 |
|
|
10 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
е |
1/8 |
1 |
|
1 |
|
0 |
110 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
с |
1/8 |
1 |
|
1 |
|
1 |
111 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
14
Алгоритм статистического кодирования Шеннона - Фано
Сообщение будет иметь вид:
А |
Т |
Т |
Е |
С |
Т |
А |
Т |
|
|
|
|
|
|
|
|
10 |
0 |
0 |
110 |
111 |
0 |
10 |
0 |
|
|
|
|
|
|
|
|
Длина двоичного сообщения с |
шф=14 бит. |
|
неравномерным кодом Шеннона-Фано: |
||
|
Сообщение стало на 12.5 % короче, чем при кодировании равномерным кодом.
рав − шф = 16 − 14 = 0.125 → 12.5%рав 16
Ранее вычисленная избыточность =0.125 устранена.
15
Алгоритм статистического кодирования Шеннона - Фано
Средняя длина одной буквы исходного сообщения после кодирования неравномерным кодом:
|
= |
бит/букву |
ср |
|
|
=1
qi – количество разрядов использованных для кодирования i-го символа (т→0→qт=1; а→10→qа=2; е→110→qе=3; с→111→qс=3).
ср = т т + а а + е е + с сср = 48 1 + 28 2 + 18 3 + 18 3 = 1.75 бит/букву
На одну букву алфавита источника, после кодирования неравномерным кодом Шеннона-Фано, приходится в среднем
1,75 двоичных символа. |
16 |
|
Алгоритм статистического кодирования Шеннона - Фано
Остаточная избыточность после кодирования:
|
= |
ср − |
= |
1.75 − 1.75 |
= 0. |
|
|
||||
ост |
|
ср |
1.75 |
|
|
|
|
|
|||
С помощью кода Шеннона-Фано удалось полностью устранить избыточность исходного буквенного сообщения.
Таким образом, часто встречающиеся буквы в сообщении должны составлять короткие кодовые комбинации, а реже встречающиеся - более длинные кодовые комбинации.
Коды, полученные по этому правилу, называют
статистическими или эффективными.
17
Алгоритм статистического кодирования Шеннона - Фано
Рассмотренная методика эффективного кодирования
Шеннона-Фано не всегда приводит к однозначному построению
оптимального кода. Т. к. при разбиении на подгруппы можно
сделать большей по вероятности как верхнюю, так и нижнюю
подгруппы.
18
Алгоритм статистического кодирования Хаффмана
Гарантирует однозначное построение кода с наименьшем числом символов на букву. Кодирование по Хаффману выполняется в следующем порядке:
1)Размещают символы алфавита источника в первом столбце таблицы в порядке убывания их вероятностей.
2)Суммируют в полученном столбце две последние (наименьшие) вероятности и размещают в новом столбце.
3)Располагают все вероятности в новом столбце в порядке убывания.
4)Повторяют шаги 2) и 3) до тех пор, пока не получим столбец, состоящий из одной вероятности, равной 1.
19
Алгоритм статистического кодирования Хаффмана
5)По полученным столбцам строится двоичное дерево-граф, начальным узлом которого является последний столбец (вероятность = 1), а выходящие из каждого узла по две ветви отражают процесс объединения вероятностей, выполненный в пунктах 2) и 3).
6)Затем каждой выходящей из любого узла ветви присваивается символ «1», если она обладает большей вероятностью и «0», если её вероятность меньше или равна.
7)Искомые двоичные кодовые комбинации, соответствующие каждому из символов алфавита источника, можно прочесть из графа, двигаясь по ветвям дерева из начального узла к конечным.
20