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

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

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

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

Задание

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

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

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

,

Задача № 1

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

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

Вариант m

Задача № 2

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

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

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

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

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

Вариант r q p1, p2, …pr
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 =Ai1,Ai2 ,Ai3,…Ain, и имеет единственное такое разложение. Если ограничиться бинарным кодированием, то Ai = a1 a2 a3…..am номера слов в словаре, записанные в двоичной системе (ai принимает значения 0 или1). Необходимо отметить, что каждый двоичный номер слова может быть однозначно записан и десятеричным числом.

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

A1® B1

A2® B2

A3® B3 (1)

….

As® Bs ,

где Bi = b1 b2 b3 …bl – элементарные двоичные коды, имеющие одинаковую длину l = m + k , при этом такие, чтобы по коду, полученному на выходе канала связи (помеха может изменить 0 на 1 или наоборот, но не может добавить или убрать элементbi) однозначно восстановить код на входе канала и из него получить исходное сообщение.

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

2m ? 2l / (l + 1) (2)

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

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

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

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

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

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

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

. . . . . . . . . .

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

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

4 = 22;…., причем 2k–1 ? l , а 2k+1 ³ l+1.

Члены bi набора b1 b2 b3 …bl , у которых индекс i принадлежит множеству {1, 2, 4,… 2k–1}, называются контрольными членами, остальные – информационными. Таким образом, контрольных членов будет k, а информационных l – k = m. Сформулируем правило построения набора …bl по набору a1 a2 a3…..am.

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

b3 = a1

b5 = a2

b6 = a3

. . . . .

Таким образом, набор информационных членов, расположенных в естественном порядке, совпадает с набором a1 a2 a3…..am . Затем определяются контрольные члены,

b1 = b3+ b5 + b7 + …(mod 2),

b2 = b3+ b6 + b7 + …(mod 2), (3)

b4= b3+ b6 + b7 + …(mod 2),

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

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

b1 + b3+ b5 + b7 + …= 0,

b2 + b3+ b6 + b7 + …= 0, (4)

b4 + b3+ b6 + b7 + …= 0,

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

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

Рандомно подобранные статьи с сайта:

Лекция 218. Код Хемминга


Похожие статьи:

admin