Расчетно-графическая работа №3

Тема: «Кодирование информации (код Шеннона-Фано и код Хаффмана)».

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

1.1 Кодирование

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

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

Символ (или комбинация символов) исходного алфавита, которому соответствует кодовая комбинация, называется исходным символом.

Совокупность кодовых комбинаций называется кодом.

Взаимосвязь символов (или комбинаций символов, если кодируются не отдельные символы исходного алфавита) исходного алфавита с их кодовыми комбинациями составляет таблицу соответствия (или таблицу кодов).

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

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

В зависимости от целей кодирования, различают следующие его виды:

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

2) криптографическое кодирование, или шифрование, – используется, когда нужно защитить информацию от несанкционированного доступа;

3) эффективное, или оптимальное, кодирование – для устранения избыточности данных путем снижения среднего числа символов кодового алфавита для представления одного исходного символа. Активно используется в архиваторах;

4) помехозащитное или помехоустойчивое кодирование – для обеспечения заданной достоверности в случае, когда на сигнал накладывается помеха. Используется для защиты от помех при передаче информации по каналам связи.

1.2 Эффективное кодирование

(3.1)

Для кодирования символов исходного алфавита используют двоичные коды переменной длины: чем больше частота символа, тем короче его код. Эффективность кода определяется средним числом двоичных разрядов для кодирования одного символа – l _ср по формуле (3.1):

где k – число символов исходного алфавита;

n_s – число двоичных разрядов для кодирования символа s;

f_s – частота символа s; причем

При этом Частоты f_s появления каждого символа в исходном:

где m_s – число появлений символа s в исходном тексте.

Существуют два классических метода эффективного кодирования: методы Шеннона-Фано и Хаффмана. Входными данными для обоих методов является заданное множество исходных символов для кодирования с частотами; результат - эффективные коды.

 

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

Этот метод требует упорядочения исходного множества символов по не возрастанию их частот. Затем выполняются следующие шаги:

а) список символов делится на две части (назовем их первой и второй частями) так, чтобы суммы частот обеих частей (назовем их S₁ и S₂) были точно или примерно равны. В случае, когда точного равенства достичь не удается, разница между суммами должна быть минимальна;

б) кодовым комбинациям первой части дописывается 1, кодовым комбинациям второй части дописывается 0;

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

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

д) анализируется оставшийся список: если он пуст – код построен, работа заканчивается. Если нет, – выполняется шаг а).

 

Пример 1. Даны символы a, b, c, d с частотами f_a = 0,5; f_b = 0,25; f_c = 0,125; f_d = 0,125. Построить эффективный код методом Шеннона-Фано.

Сведем все построение в таблицу (табл. 1), где разместим исходные данные, упорядочив их, как требует метод.

Первая линия деления проходит под символом a: соответствующие суммы S₁ и S₂ равны между собой и равны 0,5. Тогда формируемым кодовым комбинациям дописывается 1 для верхней (первой) части и 0 для нижней (второй) части. Поскольку это первый шаг формирования кода, двоичные цифры не дописываются, а только начинают формировать код. В силу того, что верхняя часть списка содержит только один элемент (символ а), работа с ней заканчивается, а эффективный код для этого символа считается сформированным.

Второе деление выполняется под символом b: суммы частот S₁ и S₂ вновь равны между собой и равны 0,25. Тогда кодовой комбинации символов верхней части дописывается 1, а нижней части – 0. Таким образом, к полученным на первом шаге фрагментам кода, равным 0, добавляются новые символы. Поскольку верхняя часть нового списка содержит только один символ (b), формирование кода для него закончено.

Третье деление проходит между символами c и d: к кодовой комбинации символа c приписывается 1, коду символа d приписывается 0.

Таким образом, получили коды:

a - 1,

b - 01,

c - 001,

d - 000.

Определим эффективность построенного кода по формуле (2.1):

l_ср = 0,5*1 + 0,25*01 + 0,125*3 + 0,125*3 = 1,75.

 

Таблица 3.1

Исх. сим- волы	Час- тоты симво-лов	Этапы построения кода	Форми-руемый код
первое деление	второе деление	третье деление
a	0,5	S1 = 0,5	код для символа a сформирован		-	-
линия деления линия деления b	0,25		S1 = 0,25	код для символа b сформирован			-
линия деления c	0,125	S2=0,25+0,125+	S2 = 0,125+0,125 = 0,25	S1 = 0,125   S2 = 0,125
d	0,125	+0,125=0,5

1.4 Метод Хаффмана

Этот метод имеет два преимущества по сравнению с методом Шеннона-Фано: он устраняет неоднозначность кодирования, возникающую из-за примерного равенства сумм частот при разделении списка на две части (линия деления проводится неоднозначно), и имеет, в общем случае, большую эффективность кода.

Исходное множество символов упорядочивается по не возрастанию частоты и выполняются следующие шаги:

1) объединение частот:

- две последние частоты складываются, а соответствующие символы исключаются из списка;

- оставшийся после исключения символов список пополняется суммой частот и вновь упорядочивается;

- предыдущие шаги повторяются до тех пор, пока ни получится единица в результате суммирования и список ни уменьшится до одного символа;

2) построение кодового дерева:

- строится двоичное кодовое дерево: корнем его является вершина, полученная в результате объединения частот, равная 1; листьями – исходные вершины; остальные вершины соответствуют либо суммарным, либо исходным частотам, причем для каждой вершины левая подчиненная вершина соответствует большему слагаемому, а правая – меньшему; ребра дерева связывают вершины-суммы с вершинами-слагаемыми. Структура дерева показывает, как происходило объединение частот;

- ребра дерева кодируются: каждое левое кодируется единицей, каждое правое – нулем;

3) формирование кода: для получения кодов листьев (исходных кодируемых символов) продвигаются от корня к нужной вершине и «собирают» веса проходимых ребер.

Пример 2. Даны символы a, b, c, d с частотами f_a = 0,5; f_b = 0,25; f_c = 0,125; f_d = 0,125. Построить эффективный код методом Хаффмана.

1) объединение частот:

 

Таблица 3.2

Исходные символы s	Частоты fs	Этапы объединения
первый	второй	третий
a	0,5	0,5	0,5
b	0,25	0,25	0,5
c	0,125	0,25
d	0,125

 

 

2) построение кодового дерева:

1

1 0

0,5 a 0,5

1 0

0,25 b 0,25

1 0

0,125 c 0,125 d

 

3) формирование кода:

a - 1;

b - 01;

c - 001;

d - 000.

Как видно, полученные коды совпадают с теми, что были сформированы методом Шеннона-Фано, следовательно, они имеют одинаковую эффективность.

2 Примеры решения задач

Закодировать фамилию преподавателя методами Шеннона-Фано и Хаффмана.

 

3 Задание

Для выбранной в соответствии с вариантом задания задачи:

1) Закодировать сигнал методом Шеннона-Фано.

2) Закодировать сигнал методом Хаффмана.

3) Выполнить сравнительный анализ результатов кодирования.

4) Сделать выводы.

 

 

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

1) Подробное кодирование сигнала методом Шеннона-Фано, а именно:

- таблица:

 

Символ алфавита А

Число появлений mi

Частота символа fi

 

- таблица:

 

Символ алфавита А

Частота символа fi

Этапы деления списка символов

Результирующие коды

 

- двоичное дерево, изображающее деление списка частот символов;

- коды фамилии, имени и отчества.

2) Подробное кодирование сигнала методом Хаффмана, а именно:

- таблица:

Символ алфавита А

Частота символа fi

Этапы объединения частот

 

- кодовое бинарное дерево для метода Хаффмана,

Символ алфавита

Код

- таблица

 

- коды фамилии, имени и отчества.

Столбцы таблиц и таблицы должны быть пронумерованы.

3) Анализ результатов и выводы.

 

5 Варианты задания

Вариант задания формируется каждым студентом индивидуально следующим образом. От источника к приемнику передается следующее сообщение: «фамилия имя отчество». Каждый студент использует в качестве варианта задания свои фамилию, имя и отчество. Например: «иванов семен петрович».

 

Список литературы

1. Афанасьев В.В. Теория вероятностей в вопросах и задачах: http://cito-web.yspu.org/link1/metod/theory/theory.html

2. Топоркова О.М. Информатика: Учебн. пособ. – Калининград: КГТУ, 2001.

3. Яглом А. М., Яглом И. М. Вероятность и информация. — М.: «Наука», 1973.