ЗНАЕТЕ ЛИ ВЫ?

Самокорректирующиеся коды. Коды Хемминга.



Цель работы: изучение общих методов формирования кодов, получение практических навыков по формированию корректирующих кодов на примере построения и декодирования систематического кода и изучение его свойств.

Задание.

Обнаружить и исправить ошибку в представленном коде, декодировать сообщение.

Вариант Закодированное сообщение
1 1 1 0 1 0- 0 1 0 1 0 0 0 0 0-0 1 0 0 1 1 1-1 1 0 1 0 1 1 1 1- 0 0 0 0 0 1
1 0 1 0 0 1 1-0 0 0 1 1 1 0-1 1 1 0 1 0-1 0 0 0 0 0 1-1 1 0 0 1 0 0 0 0-1 1 0 0 1 1 0 0 1- -0 1 0 1 1 0 0 0 1 0-1 1 0 1 0 1 1 1 1-0 0 1 0 0 0
1 1 1 1 1 1 1 0 1-1 0 0 0 1 0 1-0 1 0 0 1 0 0 1 1-1 1 1 0 0 1 1 1 1 1-0 0 1 0 0 0 0 1 1 0 1 1 1 0 0-1 1 1 0 0 1-0 1 1 0 1 0 1-0 0 0 0 0 1
0 1 0 0 0 1 0 1 1-0 1 1 0 0 1 1 0 1-0 1 0 1 1 1 1 1 1-1 0 1 0 0 0 1 0 1 1-0 0 1 0 0 1 0 1 1 1 0 1 0-0 0 0 0 0 1-0 1 1 1 0 1 0 0 0-0 0 0 0 1 0-1 0 1 1 0 1 1-0 1 1 0 1 1 0 1 1- 1 1 1 0 0 1-1 0 1 0 0 1 1-0 0 1 0 0 0
1 0 1 1 1 1 0-1 0 1 0 1 0 0-0 0 1 0 1 1 1-1 0 1 1 0 0 0-1 0 1 1 1 0 0 0 0-1 1 0 0 0 0- 0 0 0 1 1 1 0-1 1 1 0 0 1-0 1 0 1 0 1 1 0 0 -1 0 0 0 1 1 1-1 0 0 1 1 0 1 0 0-0 0 0 0 1 0
0 1 0 1 0 1 0 0 1-0 0 0 1 0 1 1-0 0 1 0 1 1 1-0 0 1 0 0 0-1 0 0 0 0 0 1-0 0 0 0 1 0
1 0 0 1 0 1 0-0 1 0 0 0 0 1-0 1 1 1 1 0 0 0 0 1-0 1 0 0 1 1 1-1 0 1 0 0 1 1 0 0 1- 0 0 1 0 1 1 1-1 1 1 0 1 0-0 0 0 0 0 1
1 0 1 1 0 1 1-1 0 1 0 1 1 1-0 1 1 0 1 0 1-1 1 0 1 0 1 0 1 0-1 1 1 0 0 1-1 0 0 0 1 1 1- 0 0 0 0 0 1
0 0 1 1 1 1 0 1 0 1-0 0 0 1 1 0 0 1 0 0-0 0 1 1 1 1 1-1 1 1 0 1 0-0 0 1 0 0 1 0 1 0 1 1 1 0 0 0 1 1 1-0 1 0 0 1 1 1-0 1 0 1 0 1 0 0 1-0 0 0 0 1 0
1 0 0 1 0 1 0-1 0 1 0 0 0 1-1 0 0 0 0 0 1-1 1 1 1 1 0 0 1 1 1-1 0 1 0 0 1 1- 0 0 0 1 0 1 1-0 0 1 1 1 0 0 1 1 1-1 0 0 1 0 0 0 0 0-1 1 1 0 0 1-0 0 0 1 1 0 1 1 1 0- 0 0 1 0 0 0
0 1 1 0 1 0 1-1 0 1 1 0 0 0-0 1 1 1 1 1 0 1 1-0 0 0 1 1 1 0-0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1-0 0 1 1 1 1 1-1 0 0 1 1 1 0 0 0-0 0 1 0 0 0
0 1 1 0 1 1 1 0 0-0 0 1 0 0 0-1 1 1 1 0 1 1 0 0-1 0 1 0 1 1 1-0 1 0 0 0 1 0 1 1- 0 1 1 1 1 0 0 1 1 1 0-0 0 1 1 1 0 0 1 1 0-1 0 0 1 1 0 1 0 0-0 1 1 1 1 1 0 0 0 0- 0 0 0 0 0 1
1 1 0 0 0 0-0 1 1 0 1 0 1-1 1 1 0 1 0-0 0 0 0 1 0
1 0 0 0 0 1 0-0 0 0 1 1 1 0-1 1 1 0 1 0-1 0 0 0 0 0 1-1 1 0 0 1 0 0 0 0-1 1 0 0 1 1 0 0 1- -0 1 0 1 1 0 0 0 1 0-1 1 0 1 0 1 1 1 1-0 0 1 0 0 0
1 1 1 1 1 1 1 0 1-1 0 0 0 1 0 1-0 1 0 0 1 0 0 1 1-1 1 1 0 0 1 1 1 1 1-0 0 1 0 0 0- 1 1 1 0 1 0- 0 1 0 1 0 0 0 0 0-0 1 0 0 1 1 1-1 1 0 1 0 1 1 1 1- 0 0 0 0 0 1
0 1 1 0 0 0 1 0 0-1 1 1 0 0 1-0 1 0 0 1 1 1-0 0 0 0 0 1-1 1 1 1 1 0 1 1 1 0-0 0 1 0 1 0 0
0 0 0 1 1 1 0-1 1 1 0 1 0-0 0 1 0 1 1 1-1 1 0 0 1 1 1 0 0-0 0 0 0 1 0
1 0 1 0 0 1 1-0 0 1 0 0 0-1 0 1 1 0 1 1-1 0 1 0 1 0 0-1 0 0 1 1 0 0 0 1-0 1 1 1 1 0 1 0 0 0- 0 0 0 0 1 0

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

Каждое слово сообщения A при равномерном кодировании допускает разложение вида A =Ai1,Ai2 ,Ai3,…Ain, и имеет единственное такое разложение. Если ограничиться бинарным кодированием, то Ai = a1 a2 a3…..am номера слов в словаре, записанные в двоичной системе (ai принимает значения 0 или1). Необходимо отметить, что каждый двоичный номер слова может быть однозначно записан и десятеричным числом.

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

A1® B1

A2® B2

A3® B3 (2.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.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), (2.3)

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

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

 

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

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

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

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

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

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

 

Обнаружение ошибок в кодах Хемминга

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

S = Sk… S2 S1 ,

где Si определяется по формулам (4) для элементарного кода, полученного на выходе канала связи. Если ошибки нет, то Si = 0 и общий результат S = 0.

 

Пример 1: Пусть на вход канала связи поступил элементарный код 0110011 (т.е закодировано **1*011 (поз. 3,5,6,7– информационные, а контрольные члены заменены * )). На выходе получено 0110001 (искажен 6–й член элементарного кода). Вычислим S.

S1 = b1 + b3+ b5 + b7 = 0 + 1 + 0 + 1 = 0 (mod 2),

S2= b2 + b3+ b6 + b7 = 1 + 1 + 0 + 1 = 1 (mod 2),

S3= b4 + b5 + b6 + b7 = 0 + 0 + 0 + 1 = 1 (mod 2).

S= 1 1 0 = 6 (в десятичной системе).

Пример 2:Пусть на выходе получено 0111011 (искажен 4–й (контрольный) член элементарного кода).

S1 = b1 + b3+ b5 + b7 = 0 + 1 + 0 + 1 = 0 (mod 2),

S2= b2 + b3+ b6 + b7 = 1 + 1 + 1 + 1 = 0 (mod 2),

S3= b4+ b5 + b6 + b7 = 1 + 0 + 1 + 1 = 1 (mod 2).

S= S3 S2 S1=1 0 0 = 4 (в десятичной системе).

Тогда восстановленное сообщение имеет вид: 0110011, а исходное сообщение – 1011(удалены контрольные члены, выделенные цветом)

Декодирование

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

 

Примечание: Рассмотрено построение кодов Хемминга для бинарного кодирования и допустимом числе ошибок в элементарных кодах не более одной. Существует теория для построения таких кодов для равномерного кодирования любой арности и числе ошибок не более 2, 3,… и. д.


Лабораторная работа №3

Формальные грамматики и языки|речь|.

(Цепочки. Классификация грамматик по Хомскому).

 

Цель работы: закрепить понятия «алфавит», «цепочка», «формальная грамматика» и «формальный язык», «выводимость цепочек», «эквивалентная грамматика»;сформировать умения и навыки распознавания типов формальных языков и грамматик по классификации Хомского, построения эквивалентных грамматик.

 

Задание.

1.Определить к какому типу по Хомскому относится данная грамматика, какой язык она порождает, каков тип языка.

2.Указать максимально возможный номер типа грамматики и языка.

 

Вариант Задание
 

 





Последнее изменение этой страницы: 2016-04-26; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.239.109.55 (0.009 с.)