Лекции.Орг


Поиск:




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




Лабораторная работа № 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 случаев, необходимо выполнение следующего условия:

2 m 2 l / (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, а информационных lk = 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,

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

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

 





Поделиться с друзьями:


Дата добавления: 2016-09-03; Мы поможем в написании ваших работ!; просмотров: 1918 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Надо любить жизнь больше, чем смысл жизни. © Федор Достоевский
==> читать все изречения...

824 - | 665 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.