Кодирование в телекоммуникационных системах.-2
.pdf
71
Теорема К.Шеннона об эффективном кодировании символов ИДИ (основная теорема
К.Шеннона)
Пусть источник дискретной информации (ИДИ) генерирует алфавит
X xi : p(xi ); i 1, n , составленный из n дискретных статистически независимые
n
H ( X ) p(xi ) log2 p(xi ) i 1
символов, характеризующийся энтропией , тогда:
1. существует такой способ кодирования символов, при котором среднее на символ
lср K( X ) |
n |
p(xi )l K(xi ) |
|
|
i 1 |
число двоичных разрядов кода будет сколь угодно близким к энтропии H ( X ) ИДИ; |
|
2. не существует такого способа кодирования, при котором среднее на символ число
двоичных разрядов кода lср K( X ) |
n |
|
p(xi )l K(xi ) будет меньше энтропии |
H(X) |
|
|
i 1 |
|
ИДИ.
Наиболее распространенными алгоритмами эффективного кодирования, основанного на использовании основной теоремы К.Шеннона, являются:
-Алгоритм К.Шеннона - Р.Фано,
-Алгоритм Д. Хаффмэна.
Следует сказать, что содержательный момент этих алгоритмов, несмотря на процедурные различия, позволяющий построить эффективный двоичный код, средняя на символ длина которого максимально приближена к энтропии источника, состоит в том, что символам с большей вероятностью появления на выходе ИДИ ставятся в соответствие коды меньшей длины, а символам с меньшей вероятностью - коды большей длины. Таким образом, эффективное кодирование реализуется в классе неравномерных кодов.
Эффективные коды принято характеризовать двумя показателями кода: избыточность и эффективность
Определение 2.1. Избыточностью эффективного кода называется показатель Dk ,
определяемый выражением |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
n |
|
|
|
|
l |
ср |
K( X ) l |
min |
K( X ) |
|
p(xi ) l K(xi ) H ( X ) |
|
|
||
D |
|
|
|
|
|
i 1 |
|
. |
(2.6) |
||
|
|
lср K( X ) |
|
n |
|||||||
k |
|
|
|
|
|
||||||
|
|
|
p(xi ) l K(xi ) |
|
|
||||||
|
|
|
|
|
|
|
|
|
i 1 |
|
|
Определение 2.2. Эффективностью эффективного кода называется
определяемый выражением |
|
|
|||||
|
l |
K( X ) |
|
|
H ( X ) |
|
|
|
min |
|
|
|
|
. |
|
|
|
|
|
||||
|
|
|
n |
|
|||
lср K( X ) |
p(xi ) l K(xi ) |
|
i 1 |
Нетрудно видеть, что избыточность и эффективность эффективного соотношением
Dk 1 .
72
показатель ,
(2.7)
кода связаны
(2 . 8 )
2.2. Исследование кодирования источника дискретных сообщений методам
Шеннона Фано
Для удобства расположим все имеющиеся п букв в один столбик в порядке убывания вероятностей. Затем все эти буквы следует разбить на две группы – верхнюю и нижнюю – так, чтобы суммарная вероятность первой группы была наиболее близка к суммарной вероятности второй группы. Для букв первой группы в качестве первой цифры кодового обозначения используется цифра 1, а для букв второй группы – цифра 0. Далее, каждую из двух групп подобным образом снова надо разделить на две части и в качестве второй цифры кодового обозначения мы будем использовать цифру 1 или 0 в зависимости от того, принадлежит ли наша группа к первой или ко второй из этих подгрупп. Затем, каждая из содержащих более одной буквы групп снова делится на две части возможно более близкой суммарной вероятности и т.д.; процесс повторяется до тех пор, пока мы не придем к группам, каждая из которых содержит по одной единственной букве.
Например, если наш алфавит содержит всего шесть букв, вероятность которых (в порядке убывания) равны 0,4, 0,2, 0,2, 0,1, 0,05 и 0,05, то на первом этапе деления букв на группы мы отщепим лишь одну первую букву (1-я группа), оставив во второй группе все остальные. Далее, вторая буква составит 1-ю подгруппу 2-й группы; 2-я же подгруппа той же группы, состоящая из оставшихся четырех букв, будет и далее последовательно делиться на части так, что каждый раз 1-я часть будет состоять лишь из одной буквы.
|
|
|
|
|
|
|
|
Таблица 2.1. |
|
|
|
|
|
|
|
|
|
|
|
№ |
|
разбиение на подгруппы |
(римские |
кодовое |
|||||
вероятность |
цифры обозначают номера |
групп и |
|||||||
буквы |
обозначение |
||||||||
|
подгрупп) |
|
|
||||||
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
1 |
0,4 |
} 1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
73
2 |
0,2 |
|
} 1 |
|
|
|
01 |
|
|
|
|
|
|
|
|
|
|
3 |
0,2 |
|
|
} 1 |
|
|
001 |
|
|
|
|
|
|
|
|
|
|
4 |
0,1 |
} 0 |
} 0 |
|
} 1 |
|
0001 |
|
|
|
|
|
|
|
|
||
5 |
0,05 |
} 0 |
} 0 |
} 1 |
00001 |
|||
|
|
|||||||
|
|
|
|
|
|
|
||
6 |
0,05 |
|
|
|
} 0 |
00000 |
||
|
|
|
|
|||||
|
|
|
|
|
|
|
|
Основной принцип, положенный в основу кодирования по методу Шеннона – Фано,
заключается в том, что при выборе каждой цифры кодового обозначения мы стараемся,
чтобы содержащееся в ней количество информации было наибольшим, т. е. чтобы независимо от значений всех предыдущих цифр, эта цифра принимала оба возможных для нее значения 0 и 1 по возможности с одинаковой вероятностью.
Процесс декодирования Теперь рассмотрим алгоритм декодирование кодов Шеннона-Фано. Процесс
усложняется тем, что невозможно, как в случае кодирования, заменять каждые 8 бит входного потока, кодом переменной длины. При восстановлении исходной последовательности необходимо провести обратные операции - заменить код переменной длины символом длиной 8 бит. В данном случае, лучше всего будет использовать бинарное дерево, ячейками которого будут являться символы.
Пример кодирования сообщений Для наглядной иллюстрации алгоритма, сделаем сжатие предложения "Карлсон, который
живет на крыше.". Вычислим, сколько раз встречается каждый символ, и занесем данные в таблицу 2.2.
Таблица 2.2.
Си |
Количество |
мвол |
появлений |
|
|
Пр |
4 |
обел |
3 |
р |
3 |
о |
2 |
к |
2 |
а |
2 |
е |
2 |
т |
2 |
|
|
74
ы2
н1
К1
й1
л1
в1
и1
ш1
ж1
с1
. |
1 |
, |
|
Далее, разделив таблицу на две части, таким образом, чтобы число появлений символов в верхней половине таблицы примерно равнялось общему числу в нижней половине. В
предложении 32 символа, а значит, верхняя часть таблицы должна содержать около 16
появлений. Мы можем получить этот результат, поместив разделительную линию (далее р.л.)
между строками "е" и "т". В итоге верхняя часть будет содержать появление 16 символов, а
нижняя, соответственно, оставшиеся 16.
Далее проделаем то же с каждой из частей таблицы: размесим линии так, чтобы разделить 2 полученные части на приблизительно равные по количеству появлений.
Продолжаем процесс разделения до того момента, пока каждый символ не будет отделен от другого.
Результирующее дерево.
Рис.2.1. Результирующее дерево
75
Если принять, что перемещение влево эквивалентно нулевому биту, а вправо -
единичному, можно создать таблицу кодирования.
Таблица 2.3
Си |
Коди |
мвол |
ровка |
|
|
Пр |
000 |
обел |
001 |
р |
0100 |
о |
0101 |
к |
0110 |
а |
0111 |
е |
1000 |
т |
1001 |
ы |
1010 |
н |
10110 |
К |
10111 |
й |
11000 |
л |
11001 |
в |
11010 |
и |
11011 |
ш |
11100 |
ж |
11101 |
с |
11110 |
. |
11111 |
, |
|
|
|
Таблица содержит 137 бит, а оригинальная фраза "Карлсон, который живет на крыше."
занимает 256 бит, следовательно, у нас получается коэффициент сжатия 53%.
Практическая часть
1. Запустить программный комплекс [6].
76
Рис. 2.2. Панель программного комплекса
2.Выбрали в меню пункт задания «Коды Шеннона-Фано». Изучили предложенную таблицу 16-символьного алфавита. Символы отсортированы в порядке убывания вероятностей их появления.
3.Пользуясь теоретическим материалом, найти двоичные коды для каждого из предложенных символов, записали их в графу Код кодовой таблицы. Следуя правилу приписывания очередного символа, указанному в окне программы над кодовой таблицей.
Рис. 2.3. Кодовая таблица для данного сообщения
77
Рис. 2.4. Процесс проверки кодовой таблицы
Рис. 2.5. Закодированная последовательность
4. Декодировали при помощи составленной таблицы предложенной последовательности символов. Ответ записали в поле результат. По завершении проверили.
78
Рис. 2.6. Декодирование закодированной последовательности Полученную последовательность в соответствии с таблицей символов декодировали
самостоятельно и в результате получили слово: «Видео».
Рис. 2.7. Результат проверки
79
Рис. 2.8. Кодовое дерево Преимуществом данного метода является его простота и, как следствие этого, высокая
скорость кодирования и декодирования. Данный метод является простым в понимании, в
реализации, а как следствие довольно эффективным. В настоящее время не используется, так как был усовершенствован Хаффманом, алгоритм которого в данный момент широко используется в связках с другими алгоритмами при кодировании/декодировании информации.
2.3. Исследование алгоритма Лемпеля - Зива
Основная идея алгоритма Лемпеля-Зива состоит в замене появления фрагмента в данных
(группы байт) ссылкой на предыдущее появление этого фрагмента. Существуют два основных класса методов, названных в честь Якоба Зива (Jakob Ziv) и Абрахама Лемпеля
(Abraham Lempel), впервые предложивших их в 1977 (алгоритм LZ77) и 1978 годах
(алгоритм LZ78).
Алгоритм LZ77
LZ77 использует уже просмотренную часть сообщения как словарь. Чтобы добиться сжатия, он пытается заменить очередной фрагмент сообщения на указатель в содержимое словаря.
80
В качестве модели данных LZ77 использует “скользящее” по сообщению окно,
разделенное на две неравные части. Первая, большая по размеру, включает уже просмотренную часть сообщения. Вторая, намного меньшая, является буфером, содержащим еще не закодированные символы входного потока. Обычно размер окна составляет несколько килобайтов. Буфер намного меньше, обычно не более ста байтов. Алгоритм пытается найти в словаре фрагмент, совпадающий с содержимым буфера.
Алгоритм LZ77 выдает коды, состоящие из трех элементов:
-смещение в словаре относительно его начала подстроки, совпадающей с содержимым буфера;
-длина подстроки;
-первый символ в буфере, следующий за подстрокой.
Пример. Размер окна – 20 символов, словаря – 12 символов, а буфера -8. Кодируется сообщение «ПРОГРАММНЫЕ ПРОДУКТЫ ФИРМЫ MICROSOFT». Пусть словарь уже заполнен. Тогда он содержит строку «ПРОГРАММНЫЕ_», а буфер строку «ПРОДУКТЫ».
Просматривая словарь, алгоритм обнаружит, что совпадающей подстрокой будет «ПРО», в
словаре она расположена со смещением 0 и имеет длину 3 символа, следующим символом в буфере является «Д». Таким образом, выходным кодом будет тройка (0, 3, «Д»). После этого алгоритм сдвигает влево все содержимое окна на длину совпадаю-щей подстроки +1 и
одновременно считывает столько же символов из входного потока в буфер. Получаем в словаре строку «РАММНЫЕ ПРОД», в буфере – «УКТЫ ФИР». В данной ситуации совпадающей подстроки обнаружить не удастся и алгоритм выдаст код (0, 0, «У»), после чего сдвинет окно на один символ. Затем словарь будет содержать «АММНЫЕ ПРОДУ», а
буфер – «КТЫ ФИРМ». и т.д.
Проблемы LZ77
Очевидно, что быстродействие кодера LZ77 сильно зависит от того, каким образом будет осуществляться поиск совпадающей подстроки в словаре. Если искать совпадение полным перебором всех возможных вариантов, то очевидно, что сжатие будет очень медленным.
Причем при увеличении размеров окна для повышения степени сжатия скорость работы будет пропорционально уменьшаться. Для декодера это неважно, так как при декодировании не осуществляется поиск совпадения.
Быстродействие и кодера, и декодера зависит от того, как реализовано “скольжение” окна по содержимому сообщения. Рационально было бы для работы с окном пользоваться кольцевым буфером, организованным на физически сплошном участке памяти, а не реальным сдвигом содержимого окна. Хотя для поддержания кольцевого буфера