Лабораторный практикум по теории электросвязи

ХАРЬКОВСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ

Факультет: ТКВТ

Кафедра: ТКС

Лабораторный практикум по теории электросвязи

Лабораторная работа № 12

Тема:   12 ИССЛЕДОВАННИЕ МЕТОДОВ ЭФФЕКТИВНОГО КОДИРОВАНИЯ

 

Цель работы: Изучение основных понятий теории информации, информационных характеристик систем передачи сообщений и методов эффективного статистического кодирования на примере эффективного кода Хаффмана, кода Шеннона-Фано и алгоритма арифметического кодирования.

 

Подготовка к выполнению работы

 

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

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

 

Неравномерное кодирование дискретных источников.

Изучая информационные характеристики дискретных источников информации мы убедились в том, что источники информации, вообще говоря, избыточны в том смысле, что, при эффективном кодировании можно уменьшить затраты на передачу или хранение порождаемой ими информации. Для представления данных потребуется тем меньше бит, чем меньше энтропия. Не нужно долго изучать теорию информации, чтобы догадаться, что для таких источников нужно использовать кодирование, сопоставляющее часто встречающимся сообщениям короткие кодовые комбинации, а редким сообщениям – длинные. Мы начнем с кодирования отдельных букв источника. Оптимальным побуквенным кодом является известный код Хаффмана. Однако, для того, чтобы понять, как правильно кодировать последовательности, нам придется изучить побуквенные код Шеннона - Фано. От него – один шаг к пониманию арифметического кодирования, которое позволяет предельно эффективно кодировать длинные последовательности и обладает при этом относительно невысокой сложностью.

 

Неравенство Крафта

Вернемся к примеру 12.1 и сравним коды C₁ и C₂ объема 4. Код C₁ равномерный, все слова имеют одинаковую длину 2. Нельзя ли выбрать слова короче? Действительно, в коде C₂ есть одно слово длины 1, но чтобы сохранить объем кода и префиксность, пришлось на единицу увеличить длины двух других кодовых слов. Этот пример показывает, что требование префиксности накладывает жесткие ограничения на множество длин кодовых слов и не дает возможности выбирать кодовые слова слишком короткими. Формально эти ограничения записываются в виде изящного неравенства, называемого неравенством Крафта.

Теорема 12.1. Необходимым и достаточным условием существования префиксного кода объема N с длинами кодовых слов m₁,…,m_N является выполнение неравенства

                      (12.1)

Для достижения равенства в (12.1) кодовое дерево должно быть полным, т.е. каждая промежуточная вершина дерева должна иметь ровно 2 потомка и всем концевым вершинам должны быть сопоставлены кодовые слова.

Неравенство Крафта как бы ограничивает снизу длины кодовых слов префиксного кода заданного объема N. В связи с этим важно быть уверенным, что оно имеет место и для любых других однозначно декодируемых кодов. Это утверждение является содержанием следующей теоремы.

Теорема 12.2. Для любого однозначно декодируемого двоичного кода объема N с длинами кодовых слов m₁,…,m_N справедливо неравенство

.                             (12.2)

Избыточность кода Хаффмана

Из теоремы 12.3 следует, что для построенных по алгоритму Хаффмана кодов средняя длина кодовых слов удовлетворяет неравенству

,                                        (12.4)

где H(x) – энтропия ансамбля.

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

Итак, из (12.4) следует, что для кода Хаффмана избыточность r ≤ 1. Хотелось бы получить более точную оценку средней длины кодовых слов. Р. Галлагер, получил гораздо более точную оценку избыточности, наложив ограничение на максимальную из вероятностей сообщений.

 

Теорема 12.5. Пусть P₁ – наибольшая из вероятностей сообщений конечного дискретного ансамбля. Тогда избыточность кода Хаффмана для этого ансамбля удовлетворяет неравенствам

где H(P₁) = –P₁ log P₁ – (1– P₁)log(1– P₁) – энтропия двоичного ансамбля, и

s = 1 – log e – log log e» 0,08607.

Код Шеннона - Фано

Рассмотрим источник, выбирающий буквы из множества X ={1,...,N} с вероятностями {P₁,…,P_N}. Считаем, что буквы упорядочены по убыванию вероятностей, т.е. P₁ ≥ P₂ ≥ … ≥ P_N.

Кодирование Шеннона-Фано имеет большое сходство с кодированием Хаффмана. Рассмотрим алгоритм вычисления кодов Шеннона-Фано (для наглядности возьмём в качестве примера последовательность 'aa bbb cccc ddddd'. Для вычисления кодов, необходимо создать таблицу уникальных символов сообщения x_i и их вероятностей P(x_i), и отсортировать её в порядке невозрастания вероятности символов.

Далее, таблица символов делится на две группы таким образом, чтобы каждая из групп имела приблизительно одинаковую частоту по сумме символов. Первой группе устанавливается начало кода в '0', второй в '1'. Для вычисления следующих бит кодов символов, данная процедура повторяется рекурсивно для каждой группы, в которой больше одного символа. Таким образом для нашего случая получаем следующие коды символов:

Кодирование Шеннона-Фано является достаточно старым методом сжатия, и на сегодняшний день оно не представляет особого практического интереса (разве что как упражнение в учебных целях). В большинстве случаев, длина закодированной последовательности, по данному методу, равна длине закодированной последовательности с использованием кодирования Хаффмана. Но на некоторых последовательностях всё же формируются не оптимальные коды Шеннона-Фано, поэтому сжатие методом Хаффмана принято считать более эффективным. Такие отличии в степени сжатия возникают из-за нестрогого определения способа деления символов на группы.

Прямая теорема кодирования.

Теорема 12.7. Для дискретного стационарного источника с энтропией H(x) и для любого d > 0. существует способ неравномерного FV-кодирования такой, для которого

.

Итак, выбрав достаточно большую длину блоков n и применив к блокам побуквенное кодирование, мы получим кодирование со средней скоростью

,

где o(n) ® 0 при n ® ¥.

К сожалению, этот внешне оптимистический результат оказывается почти бесполезным при решении практических задач. Основное препятствие на пути его применения – это экспоненциальный рост сложности при увеличении длины блоков n. Поясним эту проблему следующим простым примером.

Предположим, что кодированию подлежат файлы, хранящиеся в памяти компьютера. Символы источника – байты и, значит, объем алфавита |X| = 2⁸ = 256. При кодировании последовательностей длины n = 2 объем алфавита вырастает до |X²| = 2¹⁶ = 65536. Далее при n = 3, 4, … объемы алфавита будут 2²⁴ = 16777216, 2³² = 4294967296, …. Понятно, что работать с кодами таких размеров невозможно.

Описываемый в следующем параграфе метод арифметического кодирования позволяет эффективно кодировать блоки длины n с избыточностью порядка 2/n и со сложностью растущей только пропорционально квадрату длины блока n. За счет пренебрежимо малого проигрыша в средней длине кода на сообщение сложность может быть сделана даже линейной по длине кода. Неудивительно, что арифметическое кодирование все шире применяется в разнообразных системах обработки информации.

Арифметическое кодирование

 

При кодировании кодом Шеннона-Фано и Хаффмана оптимальность будет обеспечена только в том случае, если вероятность появления кодируемых символов кратна 2ⁿ, n = -1, -2, … При произвольном значении вероятности появления символа  условие оптимальности  не выполняется.

Арифметическое кодирование обеспечивает более точное выполнение этого равенства при произвольной величине .

Рассмотрим для простоты дискретный постоянный источник, выбирающий сообщения из множества X = {1, …, N}, с вероятностями {P₁, …, P_N}. Наша задача состоит в кодировании последовательностей множества .

Мы хотели бы применить к ансамблю  достаточно простой и эффективной побуквенный код. Упрощение состоит в том, ни кодер ни декодер не хранят и не строят всего множества из |Xⁿ| кодовых слов. Вместо этого при передаче конкретной последовательности   кодером вычисляется кодовое слово  только для данной последовательности . Правило кодирования, конечно, известно декодеру и он восстанавливает   по , не имея полного списка кодовых слов.

Идея арифметического кодирования заключается в следующем. Сообщения буквы в тексте встречаются с определенными вероятностями  при этом справедливо равенство .

Интервал 0…1 разбивается на подинтервалы с длинами, равными вероятностям появления символов в потоке, которые называются диапазонами соответствующих символов. Выбирается диапазон для первого символа (буквы), определяется его начало и конец. Появление следующих символов уменьшает ширину этого диапазона. В конце текста образуется достаточно узкий диапазон и число, выбранное из этого диапазона в двоичном коде будет определять передаваемую кодовую комбинацию.

Например, символы “a”, “b”, “c” в потоке встречаются с вероятностями ; ; . Составим таблицу

 

Допустим, что необходимо закодировать текст “bcbab”. Для первого символа рабочий диапазон выбирается 0,0…0,6. Диапазон следующего символа “c” равен 0,6…0,9. В результате исходный диапазон 0,0…0,6 сужается по следующему правилу: начало нового диапазона  равно началу исходного диапазона  плюс начало диапазона следующей буквы , умноженное на разность конец исходного диапазона  минус начало исходного диапазона

.

Конец нового диапазона определяется по правилу

Здесь - конец диапазона буквы “c”.

С поступлением каждой последующей i-ой буквы начало и конец диапазона определяется по правилу

;

.

В этом выражении  и  соответственно начало и конец диапазона передаваемой буквы “x”.

Для приведенного примера после буквы “c” передается буква “b”.

Начало и конец следующего диапазона будут равны

;

.

При передаче буквы “a” начало и конец диапазона равны

;

.

Последняя буква текста “b” имеет начало и конец диапазона текста равные

;

.

В этом диапазоне выбирается точка, значение которой определяется по формуле

.

Графически процесс кодирования показан на рис. 12.0

        

 

 

Двоичный код этого числа является кодовой комбинацией, обозначающей передаваемый текст.

Дробное число в двоичном коде записывается следующим образом:

.

Количество разрядов определяется необходимой точностью записи числа и чтобы это число попадало в интервал закодированного слова.

Для приведенного примера кодовая комбинация имеет вид 01110110. Этой кодовой комбинации соответствует число 0,4609375.

При таком кодировании длина полученного интервала равна произведению вероятностей всех встретившихся символов, а его начало зависит от порядка следования символов.

Определим алгоритм восстановления текста. При кодировании каждый следующий интервал вложен в предыдущий. Это означает, что если принято число 0,4609375, то первым символом в цепочке текста может быть только буква “b”, так как ее диапазон (0,0…0,6) включает это число. Перебором всех возможных символов по приведенной выше методике расчета определяем, что следующая буква “c” и т.д.

Обсудим кратко вопрос о сложности кодирования.

Из описания алгоритма следует, что на каждом шаге кодирования выполняется одно сложение и 2 умножения. Отсюда легко сделать неправильный вывод о том, что сложность кодирования последовательности из n сообщений пропорциональна n. Это неверно, поскольку на каждом шаге линейно растет сложность выполнения самих операций сложения и умножения, т.к. нарастает число двоичных разрядов, необходимых для записи операндов.

Предположим, что для представления вероятностей P₁, …, P_N использованы числа разрядности d. После первого шага кодирования точное представление Н и K потребует 2d разрядов, после n шагов кодирования кодер и декодер будут работать (в худшем случае) с числами разрядности nd, и, следовательно, суммарная сложность имеет порядок

.

Таким образом, можно говорить о том, что сложность арифметического кодирования пропорциональна n². На самом деле, возможна практическая реализация арифметического кодирования со сложностью пропорциональной n.

Отметим еще одну чрезвычайно важную особенность арифметического кодирования. Его легко адаптировать к случаю источников с памятью. Если, например, в качестве модели источника рассматривается простая цепь Маркова, то алгоритм кодирования остается прежним за тем исключением, что вместо одномерных вероятностей P(x_i) нужно использовать условные вероятности P(x_i|x_i-1).

Порядок выполнения работы

 

1. Перед началом работы задайте программе каталог, в который будут помещаться результаты работы.

2. Задайте в программе таблицу статистики появления символов согласно своему варианту и таблице 12.1. Для этого необходимо произвести пересчет частот появления символов в оценку вероятности их появления.

3. Постройте с помощью программы код Шеннона-Фано. Результат занесите в отчет, заполнив таблицу 12.3 и отразив ход построения кода.

 

4. Постройте с помощью программы код Хаффмана. Результат занесите в отчет (заполнить таблицу 12.3 и зарисовать полученное кодовое дерево).

5. Закодируйте полученными кодами сообщение согласно своему варианту и таблице 12.1. Сравните полученные закодированные сообщения и их длины.

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

7. Для выполнения следующих пунктов заготовьте в отчете таблицу 12.4.

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

9. Постройте с помощью программы код Шеннона-Фано.

10. Определите с помощью программы информационные характеристики полученного кода. Результат занести в отчет (таблица 12.4).

11. Закодируйте полученным кодом заданный преподавателем текстовый файл, определите длину полученного закодированного сообщения, и коэффициент сжатия. Результат занести в таблицу 12.4.

12. Постройте с помощью программы код Хаффмана.

13. Повторите эксперимент с полученным кодом аналогично п.10, 11. Результат занести в таблицу 12.4.

14. Повторите эксперимент п.8-13, приняв длину символов источника равной двум, трем и четырем буквам. Результат занести в таблицу 12.4.

15. Повторите эксперимент п.8-13, приняв длину символов источника равной одному, двум, трем и четырем битам. Результат занести в таблицы 12.3 и 12.4 (таблицу 12.3 заполнять для каждого значения длины символов источника).

16. Задайте в программе таблицу статистики появления символов аналогично п.2. Закодируйте арифметическим алгоритмом сообщение согласно своему варианту и таблице 12.1. Процесс кодирования занесите в отчет. Определите длину сообщения и основные информационные характеристики.

17. Задайте в программе таблицу статистики появления символов аналогично п.8. Закодируйте арифметическим алгоритмом файл, заданный преподавателем, определите его длину и основные информационные характеристики. Результат занести в таблицу 12.4.

 

n_и – количество символов в букве укрупненного алфавита источника (длина кодируемого блока);

N – мощность алфавита источника;

H_max – максимальная энтропия для данного алфавита источника;

H(x) – энтропия источника;

H₁(x) – удельная энтропия на один символ источника;

I(S) – количество информации содержащееся в сообщении;

r_и – избыточность источника;

r_к – избыточность кода;

– средняя длина кодового слова;

 – средняя длина кодового слова на один символ источника;

m(S) – длина закодированного сообщения;

h – коэффициент сжатия.

 

Содержание отчета

 

Отчет должен содержать:

- Цель работы.

- Исходные данные из таблицы 12.1 согласно своему варианту и результаты пересчета частоты появления символов в вероятности их появления.

- Заполненную в результате выполнения п.3 и п.4 таблицу 12.3.

- Рисунки, поясняющие процесс построения кода Шеннона-Фано и кода Хаффмана.

- Закодированные каждым из полученных кодов сообщения, искаженное закодированное сообщение, результат его декодирования и результат расчета трека ошибок.

- Заполненную в результате выполнения п.10, 11, 13, 14, 15, 17 таблицу 12.4.

- Заполненную в результате выполнения п.15 таблицу 12.3, для каждого значения длины символа источника (1, 2, 3, 4 бита).

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

- Анализ полученных результатов и выводы.

 

Контрольные вопросы и задания

 

1. Префиксные коды. Неравенство Крафта.

2. Поясните преимущества блочного кодирования и его особенности.

3. Что такое "неприводимость" кода?

4. Сущность и методы эффективного кодирования.

5. Поясните процедуру кодирования по методу Хаффмана. Назовите достоинства процедуры Хаффмана.

6. Перечислите достоинства эффективных кодов и возможности их применения.

7. Как влияют помехи на декодирование сообщений при эффективном кодировании?

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

9. Сравните пропускные способности двух дискретных каналов без помех, если в первом канале используются сигналы с основанием кода N= 2 при технической скорости передачи В = 100 Бод, а во втором канале основание кода N = 8 и В = 40 Бод.

10. Закодировать двоичным кодом Шеннона - Фано множество из пяти сообщений с вероятностями P₁ = 0,4; P₂ = P₃ = P₄ = P₅ = 0,15. Оценить среднюю длину кодовых слов .

11. Закодировать сообщения этого же источника кодом Хаффмана, определить среднюю длину кодовых слов . Сравнить результаты кодирования по этим двум методам и сделать выводы.

 

 

ХАРЬКОВСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ

Факультет: ТКВТ

Кафедра: ТКС

Лабораторный практикум по теории электросвязи

Лабораторная работа № 12

Тема:   12 ИССЛЕДОВАННИЕ МЕТОДОВ ЭФФЕКТИВНОГО КОДИРОВАНИЯ

 

Цель работы: Изучение основных понятий теории информации, информационных характеристик систем передачи сообщений и методов эффективного статистического кодирования на примере эффективного кода Хаффмана, кода Шеннона-Фано и алгоритма арифметического кодирования.

 

Подготовка к выполнению работы

 

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

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