Средняя длина кода из таблицы 1 будет равна
Лабораторная работа № 2
Оптимальное кодирование
Основные сведения об оптимальном кодировании
Кодированием информации называется операция преобразования сообщений, состоящих из символов первичного алфавита, в определенную последовательность символов вторичного алфавита (элементарных символов). Обратная операция, восстанавливающая исходное сообщение по элементарным символам называется декодированием. Любому дискретному сообщению можно приписать некоторое число – его код. Тогда передача сообщений сводится к передаче кодов. Очевидно, что для восстановления по кодам сообщений они должны быть однозначно декодируемыми (разделимыми). Таким свойством обладают префиксные коды.
Префиксные коды – это такие коды, в которых ни одна более короткая комбинация не является началом более длинной комбинации, что позволяет производить однозначное декодирование, даже если последовательность кодов не содержит разделителей между кодами.
Для существования двоичного разделимого кода, содержащего N кодовых слов, состоящих из символов 0 и 1, с длинами n1, n2, …, nN, необходимо и достаточно, чтобы выполнялось неравенство Крафта:
.
Дискретный источник сообщений, который описывается моделью с независимыми символами сообщений, называется дискретным источником без памяти. Для любого дискретного источника без памяти X с конечным алфавитом и энтропией H(X) существует двоичный код, в котором средняя длина кодового слова 
удовлетворяет неравенству
|
|
|
,
т.е. средняя длина кодового слова не может быть меньше энтропии источника сообщений. Кроме того, доказано, что для блока длины L существует двоичный префиксный код, в котором средняя длина кодового слова на один символ удовлетворяет неравенству
,
где 
. Последнее неравенство позволяет утверждать, что существуют такие способы кодирования для достаточно длинного сообщения, что средняя длина кодового слова может быть сделана сколь угодно близкой к величине H(X).
Так как минимально достижимой длиной кодового слова на символ является величина, равная значению энтропии H, то избыточность кода можно определить по формуле 
.
Одно и то же сообщение можно закодировать различными способами. Оптимальным считается такой код, при котором на передачу сообщений затрачивается минимальное время. Если при этом на передачу каждого элементарного символа кода тратиться одно и то же время, то оптимальным будет код, имеющий минимально возможную длину.
Принципы построения оптимальных кодов:
1. каждый элементарный символ должен переносить максимальное количество информации, для этого необходимо, чтобы элементарные символы в закодированном тексте встречались в среднем одинаково часто, т.к. энтропия в этом случае будет максимальной;
|
|
|
2. необходимо кодируемым символам, имеющим большую вероятность, присваивать более короткие кодовые слова.
При равномерном распределении вероятностей символов в сообщении оптимальным будет равномерный код. При равномерном кодировании каждому символу алфавита сообщений присваивается код, состоящий из ]log2n[ двоичных значений, где n – число различных кодируемых символов, а ]log2n[ – ближайшее целое, не меньшее n. Это можно сделать, например, сопоставив каждому символу число от 0 до n – 1 в двоичной системе счисления.
Одним из способов оптимального кодирования является метод Шеннона-Фано. Для построения кода Шеннона-Фано все символы алфавита сообщений записывают в порядке убывания вероятностей их появления. Полученную ранжированную (упорядоченную) последовательность символов разбивают на две группы так, чтобы суммы вероятностей групп были примерно одинаковыми. Для символов первой группы в качестве первого кодового символа присваивают 0, а для символов второй группы – 1. Полученные группы символов сообщений опять разбивают таким же образом на две подгруппы и опять кодируют. Это продолжается до тех пор, пока в последних подгруппах не останется по одному символу сообщений. Пусть, например, имеется алфавит сообщений
|
|
|
X = (x1, x2, x3, x4, x5, x6, x7, x8)
с распределением вероятностей появления символов
.
В результате кодирования по методу Шеннона-Фано символов алфавита X будут получены коды из таблицы 1.
Таблица 1
Кодирование Шеннона-Фано
| X | P | Шаг | Коды | |||
| 1 | 2 | 3 | 4 | |||
| x1 | 1/4 | 0 | 0 | ¾ | ¾ | 00 |
| x2 | 1/4 | 1 | ¾ | ¾ | 01 | |
| x3, | 1/8 | 0 | 0 | ¾ | 100 | |
| x4 | 1/8 | 1 | ¾ | 101 | ||
| x5 | 1/16 | 1 | 0 | 0 | 1100 | |
| x6 | 1/16 | 1 | 1 | 1101 | ||
| x7 | 1/16 | 1 | 0 | 1110 | ||
| x8 | 1/16 | 1 | 1111 | |||
Средняя длина кода из таблицы 1 будет равна
бит,
что совпадает со значением энтропии:
бит.
Еще одним способом построения оптимальных кодов является метод Хаффмана. Код Хаффмана строится следующим образом:
1) располагают символы в порядке убывания их вероятностей;
2) складывают вероятности двух последних символов и из них образуют новый составной символ с вероятностью, равной получившейся сумме;
|
|
|
3) повторяют шаги 1 и 2, пока не останется только один символ с вероятностью 1;
4) приписывают компонентам составных символов 0 и 1 – первой компоненте приписывают 0, а второй – 1.
Покажем процесс построения кодов Хаффмена для алфавита сообщений
X = (x1, x2, x3, x4, x5, x6, x7, x8)
с распределением вероятностей появления символов
.
1. Исходный список букв X = {x1, x2, x3, x4, x5, x6, x7, x8} уже упорядочен, так как 
.
2. Объединим буквы x7 и x8 в одну букву x1 с вероятностью 
и переупорядочим список:
, X1 = {x1, x2, x3, x4, x1, x5, x6}.
3. Повторим шаг 2 до тех пор, пока не останется одна буква в списке:
, X2 = {x1, x2, x3, x4, x1, x2};
, X3 = {x1, x2, x3, x3, x4};
, X4 = {x1, x2, x3, x4};
, X5 = {x5, x1, x2};
, X6 = {x5, x6};
, X7 = {x7}.
4. Присвоим двоичные коды символам:
x7: x5 = 0, x6 = 1;
x6: x1 = 10, x2 = 11;
x5: x3 = 00, x4 = 01;
x4: x3 = 010, x4 = 011;
x3: x1 = 000, x2 = 001;
x2: x5 = 0010, x6 = 0011;
x1: x7 = 0000, x8 = 0001.
Таким образом, получены следующие коды исходных символов:
x1 = 10, x2 = 11, x3 = 010, x4 = 011, x5 = 0010, x6 = 0011, x7 = 0000, x8 = 0001.
Средняя длина кода равна
бит,
что совпадает со средней длиной кода Шеннона-Фано и с энтропией.
Способом добиться наименьшей средней длины кода на один символ является блочное кодирование. При блочном кодировании коды присваиваются не отдельным символам сообщений, а их сочетаниям. При увеличении числа символов в сочетании средняя длина кода на один символ приближается к энтропии. Например, пусть имеются две буквы алфавита – A и B, с вероятностями появления 0.9 и 0.1 соответственно. Закодировать их можно, присвоив 0 одному символу и 1 – другому:
A = 0, B = 1.
Средняя длина кода в этом случае будет равна 1 биту:
,
тогда как энтропия равна
бит.
Избыточность составляет около 53%. Если же закодировать двухбуквенные сочетания XiXj, Xi, Xj Î {A, B} с вероятностями p(XiXj) =pipj, то по методу Шеннона-Фано можно получить коды, представленные в таблице 2.
Таблица 2
Блочное кодирование Шеннона-Фано
| XiXj | pipj | Шаг | Код | ||
| 1 | 2 | 3 | |||
| AA | 0.81 | 0 | ¾ | ¾ | 0 |
| AB | 0.09 | 0 | ¾ | 10 | |
| BA | 0.09 | 1 | 1 | 0 | 110 |
| BB | 0.01 | 1 | 111 | ||
Тогда средняя длина кода двухбуквенного блока будет равна 
бит, а на одну букву будет приходиться 
бит. Избыточность в этом случае будет составлять уже только около 17%. Если мы возьмем сочетания из трех букв, то получим еще лучший результат и т.д. Увеличивая длину блоков можно как угодно близко приблизиться к оптимальному значению энтропии.
Дата добавления: 2020-04-25; просмотров: 167; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!