Размещено на http://www.allbest.ru/

Тема: Кодирование и сжатие информации

В этом разделе будут рассмотрены два метода построения оптимального неравномерного кода: Шеннона-Фено и Хаффмана для дискретного ансамбля {Х,р(х)}, а также будет проведен их сравнительный анализ.

Оба метода Шеннона-Фено и Хаффмана предназначены для получения оптимального (т.е. кода с минимальным значением средней длины кодового слова) префиксного кода для дискретных источников информации со свойством однозначного декодирования.

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

1. Лабораторная работа № 1. Кодирование информации методом Шеннона-Фено

1.1 Теоретическая часть

Обозначим через А некоторое множество, состоящее из D, D>1, элементов: А={а₁,....,а_D}.

Назовём его алфавитом кода источника. Элементы множества А будем называть кодовыми символами. Последовательность кодовых символов называется кодовым словом, а любое семейство кодовых слов -- кодом над алфавитом А.

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

Если длина кода m разрядов, то таким двоичным кодом можно представить максимум 2^m различных слов. Если все разряды слова служат для представления информации, то код называется простым (неизбыточным). Коды, в которых лишь часть кодовых слов используется для представления информации, называются избыточными. Часть слов в избыточных кодах является запрещённой, и появление таких слов при передаче информации свидетельствует о наличии ошибки.

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

Кодовым расстоянием между двумя словами называется число разрядов, в которых символы слов не совпадают. Если длина слова т, то кодовое расстояние может принимать значение от 1 до т.

Минимальным кодовым расстоянием кода называется минимальное расстояние между двумя любыми словами данного кода. Если имеется хотя бы одна пара слов, отличающихся друг от друга только в одном разряде, то минимальное кодовое расстояние данного кода равно 1. Неизбыточный код имеет минимальное расстояние d_min = 1. Для избыточных кодов d_min > 1.

1.2 Метод Шеннона-Фено

Алгоритм Шеннона-Фено состоит из двух следующих этапов:

1) Подразделить множество сообщений на D подмножеств (по числу слов кодового алфавита), так, чтобы вероятности каждого из подмножеств были примерно одинаковыми, произвольным образом пронумеровать подмножества. Для всех сообщений из i -го подмножества, i = 1,2,...,D, положить первый символ кодовых слов равным а_i A, где А={а₁,....,а_D}.

2) Каждое из подмножеств рассматривается как некоторое новое множество сообщений. Выполнить на j-ом шаге j=2,3,..., действия указанные в п.1 для определения j-го символа кодовых слов. Считать, что действия над данным подмножеством закончены, если оно содержит одно сообщение.

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

Рассмотрим этот алгоритм на конкретном примере для ансамбля Х содержащего всего 6 сообщений с вероятностями 0,35 0,2 0,2 0,1 0,08 0,07 соответственно. Будем рассматривать наиболее простой случай, когда кодирующий алфавит состоит всего из двух кодовых символов: 1 и 0.

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

На первом этапе исходное множество разделится на два подмножества с вероятностями 0,55 и 0,45 соответственно, всем элементам из первого множества в качестве первого символа соответствующего им кодового слова будет записана 1, а всем элементам второго подмножества 0. Затем на втором шаге первое подмножество разделится еще на два подмножества, состоящих из одного элемента, для которых будет повторена эта же операция. Второе подмножество, полученное на первом этапе, будет разделено на множество из одного элемента и подмножество из двух элементов. В общей сложности работа алгоритма будет продолжаться 4 шага.

1.3 Задание

Выбрав произвольный текст (русский или латинский) объёмом в 5-6 машинописных страниц, подсчитать для каждого символа его частоту вхождения. Вычисление проводить с точностью до 3-го знака после запятой. Закодировать символы кодом Шеннона-Фено. Для полученного кода подсчитать среднюю длину кодового слова и энтропию, приходящуюся на 1 символ. Сравнив их, сделать вывод.

Закодировать сообщения:

1) теория информации;

2) своё сообщение.

Форма отчёта:

1) задание на лабораторную работу;

2) исходный текст;

3) таблица соответствия кодируемым символам их частот и кодовых слов;

4) закодированные сообщения, энтропия, средняя длина кодового слова.

2. Лабораторная работа №2. Кодирование информации методом Хаффмана

2.1 Теоретическая часть

Второй метод, метод Хаффмана, основан на следующем:

Рассмотрим Х', ансамбль, состоящий из М-1 сообщения (х'₁, ..., х'_M-1) с вероятностями

р(х_i), i=1,2,...,М-2

р (х'_i) =

р(х_M-1)+ р(х_M), i = М -1

Любой однозначно декодируемый префиксный код для ансамбля Х' можно превратить в однозначно декодируемый префиксный код для ансамбля Х приписыванием к кодовому слову, кодирующему сообщение х'_M-1, символы 0, 1 для получения слов, кодирующих сообщения х_M-1, х_M. Следовательно, задача построения оптимального префиксного кода сводится к задаче построения оптимального префиксного кода для ансамбля, содержащего на одно сообщение меньше. В этом ансамбле снова можно выделить два наименее вероятных сообщения и, объединяя их, получить новый ансамбль, содержащий теперь уже на два сообщения меньше, чем исходный. Очевидно, что таким образом рано или поздно возникнет ситуация, когда в ансамбле останется всего два слова, оптимальным кодом, для которого является 0 для одного и 1 для другого.

Рассмотрим пример, приведенный в лабораторной работе №1. Для наглядности метод кодирования Хаффмана изображается в виде бинарного дерева. Дерево получается путем последовательного объединения двух минимальных вероятностей в одну и повторения данного действия до тех пор, пока исходное множество вероятностей не сведется к одному элементу.

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

2.2 Задание

префиксный код хаффман шеннон фено

Закодировать символы текста из лабораторной работы №1 кодом Хаффмана. Подсчитать среднюю длину кодового слова для полученного кода. Сравнить её с энтропией, приходящейся на один символ и со средней длиной кодового слова кода Шеннона-Фена. Сделать вывод. Закодировать те же сообщения, что и в лабораторной работе №1. Сравнив с кодом Шеннона-Фено, сделать вывод.

Форма отчёта:

1) задание на лабораторную работу;

2) кодовое дерево;

3) таблица соответствия кодируемым символам их частот и кодовых слов;

4) закодированные сообщения, энтропия, средняя длина кодового слова.

Размещено на Allbest.ru