Кодирование и шифрование информации в радиоэлектронных системах передачи информации. Часть 1. Кодирование

р3

о2

к2

а2

е2

т2

ы2

н1

К1

й1

л1

в1

и1

ш1

ж1

с1

Далее, разделив таблицу на две части, таким образом, чтобы число появлений символов в верхней половине таблицы примерно равнялось общему числу в нижней половине. В

предложении 32 символа, а значит, верхняя часть таблицы должна содержать около 16

появлений. Мы можем получить этот результат, поместив разделительную линию (далее р.л.)

между строками "е" и "т". В итоге верхняя часть будет содержать появление 16 символов, а

нижняя, соответственно, оставшиеся 16.

Далее проделаем то же с каждой из частей таблицы: размесим линии так, чтобы разделить 2 полученные части на приблизительно равные по количеству появлений.

Продолжаем процесс разделения до того момента, пока каждый символ не будет отделен от другого.

Результирующее дерево.

71

Рис.2.1. Результирующее дерево

Если принять, что перемещение влево эквивалентно нулевому биту, а вправо -

единичному, можно создать таблицу кодирования.

Таблица 2.3

р0100

о0101

к0110

а0111

е1000

т1001

ы1010

н10110

К10111

й11000

л11001

в11010

и11011

ш11100

ж11101

с11110

72

Таблица содержит 137 бит, а оригинальная фраза "Карлсон, который живет на крыше."

занимает 256 бит, следовательно, у нас получается коэффициент сжатия 53%.

Практическая часть

1. Запустить программный комплекс [6].

Рис. 2.2. Панель программного комплекса

2.Выбрали в меню пункт задания «Коды Шеннона-Фано». Изучили предложенную таблицу 16-символьного алфавита. Символы отсортированы в порядке убывания вероятностей их появления.

3.Пользуясь теоретическим материалом, найти двоичные коды для каждого из предложенных символов, записали их в графу Код кодовой таблицы. Следуя правилу приписывания очередного символа, указанному в окне программы над кодовой таблицей.

Рис. 2.3. Кодовая таблица для данного сообщения

73

Рис. 2.4. Процесс проверки кодовой таблицы

Рис. 2.5. Закодированная последовательность

4. Декодировали при помощи составленной таблицы предложенной последовательности символов. Ответ записали в поле результат. По завершении проверили.

74

Рис. 2.6. Декодирование закодированной последовательности Полученную последовательность в соответствии с таблицей символов декодировали

самостоятельно и в результате получили слово: «Видео».

Рис. 2.7. Результат проверки

75

Рис. 2.8. Кодовое дерево Преимуществом данного метода является его простота и, как следствие этого, высокая

скорость кодирования и декодирования. Данный метод является простым в понимании, в

реализации, а как следствие довольно эффективным. В настоящее время не используется, так как был усовершенствован Хаффманом, алгоритм которого в данный момент широко используется в связках с другими алгоритмами при кодировании/декодировании информации.

2.3. Исследование алгоритма Лемпеля - Зива

Основная идея алгоритма Лемпеля-Зива состоит в замене появления фрагмента в данных

(группы байт) ссылкой на предыдущее появление этого фрагмента. Существуют два основных класса методов, названных в честь Якоба Зива (Jakob Ziv) и Абрахама Лемпеля

(Abraham Lempel), впервые предложивших их в 1977 (алгоритм LZ77) и 1978 годах

(алгоритм LZ78).

Алгоритм LZ77

LZ77 использует уже просмотренную часть сообщения как словарь. Чтобы добиться сжатия, он пытается заменить очередной фрагмент сообщения на указатель в содержимое словаря.

В качестве модели данных LZ77 использует “скользящее” по сообщению окно,

разделенное на две неравные части. Первая, большая по размеру, включает уже

76

просмотренную часть сообщения. Вторая, намного меньшая, является буфером, содержащим еще не закодированные символы входного потока. Обычно размер окна составляет несколько килобайтов. Буфер намного меньше, обычно не более ста байтов. Алгоритм пытается найти в словаре фрагмент, совпадающий с содержимым буфера.

Алгоритм LZ77 выдает коды, состоящие из трех элементов:

-смещение в словаре относительно его начала подстроки, совпадающей с содержимым буфера;

-длина подстроки;

-первый символ в буфере, следующий за подстрокой.

Пример. Размер окна – 20 символов, словаря – 12 символов, а буфера -8. Кодируется сообщение «ПРОГРАММНЫЕ ПРОДУКТЫ ФИРМЫ MICROSOFT». Пусть словарь уже заполнен. Тогда он содержит строку «ПРОГРАММНЫЕ_», а буфер строку «ПРОДУКТЫ».

Просматривая словарь, алгоритм обнаружит, что совпадающей подстрокой будет «ПРО», в

словаре она расположена со смещением 0 и имеет длину 3 символа, следующим символом в буфере является «Д». Таким образом, выходным кодом будет тройка (0, 3, «Д»). После этого алгоритм сдвигает влево все содержимое окна на длину совпадаю-щей подстроки +1 и

одновременно считывает столько же символов из входного потока в буфер. Получаем в словаре строку «РАММНЫЕ ПРОД», в буфере – «УКТЫ ФИР». В данной ситуации совпадающей подстроки обнаружить не удастся и алгоритм выдаст код (0, 0, «У»), после чего сдвинет окно на один символ. Затем словарь будет содержать «АММНЫЕ ПРОДУ», а

буфер – «КТЫ ФИРМ». и т.д.

Проблемы LZ77

Очевидно, что быстродействие кодера LZ77 сильно зависит от того, каким образом будет осуществляться поиск совпадающей подстроки в словаре. Если искать совпадение полным перебором всех возможных вариантов, то очевидно, что сжатие будет очень медленным.

Причем при увеличении размеров окна для повышения степени сжатия скорость работы будет пропорционально уменьшаться. Для декодера это неважно, так как при декодировании не осуществляется поиск совпадения.

Быстродействие и кодера, и декодера зависит от того, как реализовано “скольжение” окна по содержимому сообщения. Рационально было бы для работы с окном пользоваться кольцевым буфером, организованным на физически сплошном участке памяти, а не реальным сдвигом содержимого окна. Хотя для поддержания кольцевого буфера необходимы дополнительные затраты на сохранение целостности индексов в нем, в целом это дает очень существенный выигрыш потому, что отсутствует постоянное сдвигание большого блока памяти. Если размер кольцевого буфера равен степени двойки, то

77

стандартная для кольцевого буфера операция “смещение по модулю размер”, может быть заменена побитовой логической операцией, что еще больше повышает эффективность.

Помимо проблем с быстродействием, у алгоритма LZ77 возникают проблемы с самим сжатием. Они появляются, когда кодер не может найти совпадающую подстроку в словаре и выдает стандартный 3-компонентный код, пытаясь закодировать один символ. Если словарь имеет длину 4К, а буфер — 16 байтов, то код <0, 0, символ> будет занимать 3 байта.

Кодирование одного байта в три имеет мало общего со сжатием и существенно понижает производительность алгоритма.

Упрощенный алгоритм LZ77

пока (буфер_предпросмотра не пуст) найти наиболее длинное соответствие

(позиция_начала, длина) в буфере_предыстории и в буфере_предпросмотра; если

(длина>минимальной_длины), то вывести в кодированные данные пару (позиция_начала,

длина); иначе вывести в кодированные данные первый символ буфера_предпросмотра;

изменить указатель на начало буфера_предпросмотра и продолжить.

Алгоритм LZ78

Этот алгоритм генерирует на основе входных данных словарь фрагментов, внося туда фрагменты данных (последовательности байт) по определенным правилам и присваивает фрагментам коды (номера). При сжатии данных (поступлении на вход программы очередной порции) программа на основе LZ78 пытается найти в словаре фрагмент максимальной

длины, совпадающий с данными, заменяет найденную в словаре порцию данных кодом

фрагмента и дополняет словарь новым фрагментом. При заполнении всего словаря

(размер словаря ограничен по определению) программа очищает словарь и начинает процесс заполнения словаря снова. Реализации этого метода различаются конструкцией словаря,

алгоритмами его заполнения и очистки при переполнении.

Обычно, при инициализации словарь заполняется исходными (элементарными)

фрагментами всеми возможными значениями байта от 0 до 255.

Это гарантирует, что при поступлении на вход очередной порции данных будет найден в словаре хотя бы однобайтовый фрагмент.

Алгоритм LZ78 резервирует специальный код, назовем его «Reset», который вставляется в упакованные данные, отмечая момент сброса словаря. Значение кода Reset обычно принимают равным 256.

Таким образом при начале кодирования минимальная длина кода составляет 9 бит.

Максимальная длина кода зависит от объема словаря – количества различных фрагментов,

которые туда можно поместить. Если объем словаря измерять в байтах (символах), то очевидно, что максимальное количество фрагментов равно числу символов, а,

78

следовательно, максимальная длина кода равна log2 (объем словаря в байтах).

Проведение эксперимента и обработка результатов

Кодирование фразы алгоритмом LZ77 со следующими размерами СЛОВАРЬ/БУФЕР Таблица 2.3. Варианты расчетных заданий

Используем ввод фразы с клавиатуры в программе LZ77.EXE для разных размеров словаря/буфера:

Рис. 2.9. Ввод фразы с клавиатуры для размеров 8/5

79

Рис. 2.10. Ввод фразы с клавиатуры для размеров 12/5

Рис. 2.11. Ввод фразы с клавиатуры для размеров 12/8

Рис. 2.12. Ввод фразы с клавиатуры для размеров 16/8

Используем ввод текста из файла для разных размеров словаря/буфера:

Текст: «Полуадаптированное моделирование pешает эту проблему, используя для каждо-

го текста свою модель, котоpая строится еще до самого сжатия на основании результатов предварительного просмотра текста (или его образца). Перед тем, как окончено формиро-

вание сжатого текста, модель должна быть пеpедана pаскодиpовщику. Несмотря на до-

полнительные затpаты по передаче модели, эта стpатегия в общем случае окупается бла-

годаря лучшему соответствию модели тексту.

Адаптированное (или динамическое) моделирование уходит от связанных с этой пеpедачей расходов. Первоначально и кодировщик, и раскодировщик присваивают себе некоторую пустую модель, как если бы символы все были равновероятными. Кодировщик

80