Построение кодов Хемминга (описание алгоритма кодирования)

Лабораторная работа № 4 (7)

Тема: Изучение различных видов кодирования

Цель: Изучить алгоритмы, применяемые в различных видах кодирования.

Задание

1 Изучить теоретический материал по теме лабораторной работы.

2 Решить 2 задачи в соответствии с индивидуальным вариантом.

Выбор варианта: студент выбирает № варианта задачи, определив значение t, где t = [N/ 10] – остаток от деления нацело числа N (порядковый номер в списке преподавателя).

Задача № 1

Разработать самокорректирующийся код (код Хэмминга) в соответствии с вариантом для бинарных слов длины m и привести примеры декодирования искаженных элементарных кодов (для всех вариантов – источник помех может исказить не более одной позиции элементарного кода).

Таблица вариантов к задаче 1

Вариант	m

Задача № 2

Разработать схемы алфавитного кодирования с минимальной избыточностью (коды Хаффмана) для случаев (а) и (б):

а) появление букв в сообщении равновероятно;

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

Построить кодовые деревья. Получить схемы кодирования, определить l_* (увеличение длины закодированного сообщения над исходным)

Таблица вариантов к задаче 2

Вариант	r	q	p₁, p₂, …p_r
			0,3; 0,22; 0,14 ….
			0,35; 0,21; 0,13 ….
			0,25; 0,24; 0,16…
			0,26; 0,22; 0,14…
			0,34; 0,18; 0,15…
			0,25; 0,22; 0,18…
			0,25; 0,24; 0,16
			0,3; 0,22; 0,14
			0,26; 0,22; 0,14
			0,34; 0,18; 0,15…

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

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

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

2 Способы описания источников сообщений.

3 Виды кодирования их особенности и характеристики.

4 Критерии однозначности декодирования при алфавитном кодировании.

5 Алгоритм распознания однозначности декодирования при алфавитном кодировании.

6 Свойства взаимно однозначных кодов.

7 Алгоритм построение кодов с минимальной избыточностью (кодов Хаффмана) при равновероятностном появлении букв входного алфавита.

8 Алгоритм построение кодов с минимальной избыточностью (кодов Хаффмана) при заданных вероятностях появлении букв входного алфавита.

9 Самокорректирующиеся коды (коды Хемминга). Принципы их построения.

Краткие теоретические сведения

Самокорректирующиеся коды

Каждое слово сообщения A при равномерном кодировании допускает разложение вида A =A_i₁,A_i₂,A_i₃,…A_in, и имеет единственное такое разложение. Если ограничиться бинарным кодированием, то A_i = a₁a₂a₃…..a_m номера слов в словаре, записанные в двоичной системе (a_i принимает значения 0 или1). Необходимо отметить, что каждый двоичный номер слова может быть однозначно записан и десятеричным числом.

Пусть S”(I) – подмножество всех слов, допускающих разложение указанного вида. Рассмотрим следующую схему кодирования:

A₁® B₁

A₂® B₂

A₃® B₃ (1)

….

A_s® B_s,

где B_i = b₁b₂ b₃ …b_l – элементарные двоичные коды, имеющие одинаковую длину l = m + k, при этом такие, чтобы по коду, полученному на выходе канала связи (помеха может изменить 0 на 1 или наоборот, но не может добавить или убрать элемент b_i) однозначно восстановить код на входе канала и из него получить исходное сообщение.

Построение самокорректирующихся кодов было осуществлено Хеммингом. Рассмотрим случай, когда источник помех может внести не более одного инвертирования в элементарный код B_i (р =1). Вариантов получения элементарного кода B_i будет l +1 (правильный и l штук с инвертированием b_i на каждой позиции). Для того, чтобы дополнительных разрядов в коде B_i хватило для кодирования l +1 случаев, необходимо выполнение следующего условия:

2 ^m≤ 2 ^l / (l + 1) (2)

Из этих соображений выбираем l как наименьшее целое число, удовлетворяющее неравенству (2).

Дальнейшее построение будет состоять из трех этапов:

Построение кодов Хемминга (описание алгоритма кодирования).
Обнаружение ошибок в кодах Хемминга.
Декодирование.

Построение кодов Хемминга (описание алгоритма кодирования)

В множестве натуральных чисел {1,2,3,…, l }выделим следующие подмножества:

1, 3, 5, 7, 9 ….(содержатся все числа, у которых при переводе в двоичную запись в последнем разряде 1);

2, 3, 6, 7, 10 ….(содержатся все числа, у которых при переводе в двоичную запись в предпоследнем разряде 1);

..........

2^k–1, 2^k–1+1, ….(содержатся все числа, у которых при переводе в двоичную запись в k –ом, считая справа, разряде 1).

Наименьшие члены этих подмножеств являются степенями 2: 1 = 2⁰; 2 = 2¹;

4 = 2²;…., причем 2^k^–1≤ l, а 2^k⁺¹³ l +1.

Члены b_i набора b₁b₂ b₃ …b_l, у которых индекс i принадлежит множеству {1, 2, 4,… 2^k–1}, называются контрольными членами, остальные – информационными. Таким образом, контрольных членов будет k, а информационных l – k = m. Сформулируем правило построения набора …b_l по набору a₁a₂a₃…..a_m.

Сначала определяются информационные члены:

b₃ = a₁

b₅ = a₂

b₆ = a₃

.....

Таким образом, набор информационных членов, расположенных в естественном порядке, совпадает с набором a₁a₂a₃…..a_m. Затем определяются контрольные члены,

b₁= b₃+ b₅+ b₇ + … (mod 2),

b₂ = b₃+ b₆+ b₇ + … (mod 2), (3)

b₄= b₃+ b₆+ b₇ + … (mod 2),

.............

значения которых 0 или 1 и помещаются на соответствующих местах в элементарных кодах B_i. По сути, создается кодовый словарь для схемы кодирования (1), в котором для каждого элементарного кода выполняются следующие условия (суммирование по mod 2):

b₁+ b₃+ b₅+ b₇ + …= 0,

b₂ + b₃+ b₆+ b₇ + … = 0, (4)

b₄+ b₃+ b₆+ b₇ + … = 0,

.............

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