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

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

2 Исходное сообщение.

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

4 Таблица кода.

5 Расчет параметров полученного кода.

6 Декодированное сообщение при определенной вероятности одиночной ошибки в канале.

7 Подсчитанное количество ошибочных разрядов, а также их доля от общего числа бит сообщения.

8 Подсчитанное количество ошибочных символов, их доля от общего числа символов сообщения, а также число и доля (от общего числа ошибочных символов) обнаруживаемых ошибок (символ «#») и исправленных и неверно исправленных ошибок.

9 Подсчитанное количество ошибочных символов, а также число и доля обнаруживаемых ошибок и исправленных и неверно исправленных ошибок при различных значениях кратности ошибки и вероятности ошибок (не менее 5 различных значений).

10 График зависимости числа ошибочных символов от вероятности одиночной ошибки в канале связи.

11 Вывод.

5 Конрольные вопросы

1 Какие коды называются циклическими?

2 Как производится построение циклических кодов?

3 С учетом каких характеристик осуществляется выбор образующего полинома?

4 Как получить порождающую матрицу циклического кода?

5 Как происходит обнаружение ошибки при декодировании циклического кода?

6 Как осуществляется исправление ошибки в циклическом коде?

7 В чем отличие обычных циклических кодов от кодов Файра?

Лабораторная работа №6 Динамическое кодирование неравномерными кодами. Динамические коды Хаффмена

1 Цель работы

Приобретение практических навыков кодирования информации динамическими кодами.

2 Основные теоретические положения

2.1 Динамическое кодирование Хаффмена

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

Этот метод обладает двумя существенными недостатками. Первый заключается в том, что для его реализации требуется два прохода кодируемого массива. При первом просмотре вычисляются вероятности появления каждого знака в сообщении, и составляется таблица кода Хаффмена. На следующем этапе осуществляется кодирование на основании статической структуры дерева Хаффмена и передача символов в сжатом виде. Таким образом, выигрыш, полученный за счет сжатия данных, может заметно снижаться, особенно при передаче относительно коротких сообщений, в связи с необходимостью передавать декодеру дополнительную информацию о кодовом дереве. Второй недостаток – наличие задержки от момента поступления данных от источника до выдачи соответствующих кодовых комбинаций, что ограничивает использование неравномерного кодирования в синхронных сетях передачи информации, а также в системах, функционирующих в реальном времени.

В начале 70-х годов были разработаны однопроходные методы сжатия информации, основанные на классической процедуре кодирования Хаффмена. Все эти методы незначительно отличаются друг от друга, и их суть заключается в том, что передатчик строит дерево Хаффмена в темпе поступления данных от источника, т.е. «на лету». В процессе кодирования происходит «обучение» кодера на основе статистических характеристик источника сообщений, в ходе которого вычисляются оценки исходных вероятностей сообщения, и производится соответствующая модификация кодового дерева Хаффмена. В связи с непрерывным изменением кодового дерева этот процесс получил название динамического кодирования Хаффмена. Очевидно, что для правильного восстановления сжатых данных декодер также должен непрерывно «учиться» наряду с кодером, осуществляя синхронное изменение кодовой таблицы на приемной стороне. Для обеспечения синхронности процессов кодирования и декодирования кодер выдает символ в несжатом виде, если он впервые появился на выходе источника, и отмечает его на кодовом дереве. При повторном появлении символа на входе кодера он передается неравномерной кодовой комбинацией, определяемой позицией символа на текущем кодовом дереве. Кодер корректирует дерево Хаффмена увеличением частоты передачи символов, которые уже введены в дерево, или наращивает дерево, добавляя в него новые узлы.

Важнейшим условием, которое должно соблюдаться при модификации кодового дерева, является сохранение свойств Хаффменовского дерева. Для формулирования этих свойств обратимся еще раз к алгоритму построения оптимального кода Хаффмена. При статическом кодировании символы размещаются в списке в невозрастающем порядке весов (вероятностей). Затем производится объединение двух узлов наименьшего веса W_i, W_j и замена их внутренним узлом с весом, равным сумме исходных весов W_i + W_j. Вновь образованный узел размещается в списке таким образом, чтобы не нарушался порядок расположения узлов по весам. Этот процесс повторяется до тех пор, пока в списке не останется один, так называемый корневой узел.

Вспомним процесс построения деревьев оптимального кода Хаффмена (см. л. р. №2) и проанализируем их свойства. Узлы дерева расположены в неубывающем порядке их весов при обходе дерева от крайнего нижнего узла к корню слева направо и снизу вверх. В связи с тем, что узлы с весами W_i и W_j объединяются попарно, то на одном уровне не может быть меньше двух узлов, причем пара узлов является дочерней, т.к. имеет общий родительский узел, вес которого равен сумме весов дочерних узлов. Нетрудно убедиться, что если при построении дерева предположить, что дочерний узел с небольшим весом соединен нулевой ветвью, а с меньшим – единичной, то Хаффменовское дерево остается упорядоченным по возрастанию весов при движении от нижнего узла к корню по уровням справа налево.

При построении кодовых деревьев и их модификации осуществляется нумерация узлов с первого до (2m–1)-го в порядке увеличения их весов. Первый номер присваивается узлу с минимальным весом. Здесь m – число символов алфавита источника. На рисунке 6.1 показано дерево Хаффмена для предыдущего сообщения, имеющего следующую статистику: 18А, 10В, 2С, 2D, 1E, 1F, 1G и 1H.

0

1

18 А

0

1

10 В

0

1

0

0

1

1

2 С

2 D

0

0

1

1

1 F

1 E

1 H

1 G

Рисунок 6.1 – Исходное дерево Хаффмена

Очередной поступивший символ – символ С, т.е. вес символа С увеличился на 1 и стал равным 3. При построении дерева Хаффмена в этом случае получим дерево, представленное на рисунке 6.2.

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

При динамическом кодировании Хаффмена после получения от источника следующего символа (например С) должен увеличиться на 1 вес соответствующего листа и, как следствие, инкрементироваться веса всех узлов на пути от листа С к корню. Но это приведет к нарушению порядка расположения узлов по весам, присущего оптимальному кодовому дереву. Поэтому при получении очередного символа от источника необходимо осуществить модификацию кодового дерева, чтобы оно оставалось оптимальным, так называемым хаффменовским деревом.

Рисунок 6.2 – Модифицированное дерево Хаффмена

Таким образом, на основании анализа свойств оптимальных кодовых деревьев можно сделать вывод, что кодовое дерево, имеющее m внешних узлов, является хаффменовским, если оно обладает следующими свойствами:

а) внешние узлы (листья) хаффменовского кодового дерева имеют неотрицательный вес (W>0); каждый внутренний (родительский) узел имеет подчиненные (дочерние) узлы, а его вес равен сумме весов подчиненных (дочерних);

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

в) все узлы нумеруются в возрастающем порядке таким образом, что узлы с номерами (2j - 1) и 2j являются узлами одного уровня для 1  j m-1, а их общий родительский узел имеет более высокий уровень;

г) нумерация узлов соответствует тому порядку, в котором узлы объединяются в соответствии со статическим алгоритмом Хаффмена.

Ниже рассматриваются формальные методы построения динамического кода Хаффмена.