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

Российский Государственный университет  нефти и газа

им. И.М.Губкина

 

Кафедра информационно-измерительных  систем

 

 

 

 

Курсовая работа:

 

«Обнаружение одиночных  ошибок в коде Хэмминга»

 

по дисциплине

«Преобразование измерительных сигналов»

 

 

 

Выполнила:

           Душейко Анна, студентка группы: АИ-09-7

Принял:

 Дадаян Ю.А.

 

 

 

 

 

Москва, 2012

 

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

Построение корректирующего  кода Хэмминга производится исходя из требуемого объема информационных сообщений  и статистических данных о наиболее вероятных векторах ошибок в используемом канале связи. Вектором ошибки будем  называть кодовую комбинацию, имеющую  единицы в разрядах, подвергшихся искажению, и нули во всех остальных  разрядах. Любую искаженную кодовую  комбинацию можно рассматривать  как сумму по модулю 2 разрешенной  кодовой комбинации и вектора  ошибки.

В коде Хэмминга необходимое  число проверочных разрядов определяется из известного соотношения

 

Значения символов в проверочных  разрядах устанавливаются в результате суммирования по модулю 2 значений символов в определенных информационных разрядах.

В коде Хэмминга сопоставляются подлежащие исправлению номера разрядов с ошибками в разрядах, начиная  с младшего, в порядке возрастания  двоичных чисел. В этом случае каждому  вектору ошибки соответствует своя кодовая комбинация, называемая опознавателем. Каждый опознаватель представляет собой  двоичное число, в котором произошла  ошибка.

 

 

 

 

 

Векторы ошибок	Опознаватели
0000001 0000010 0000100 0001000 0010000 1000000	001 010 011 100 110 111

 

 

 

 

 

 

 

 

 

Сущность кода Хэмминга состоит  в том, что производятся многократные проверки на четность различных вариантов  сумм разрядов полученного кода, в  результате которых получается двоичный код номера искаженного разряда.

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

Предположим, что в результате первой проверки на четность для младшего разряда опознавателя будет получена единица. Очевидно, это может быть следствием ошибки в одном из разрядов, опознаватели которых в младшем  разряде имеют единицу. Следовательно, первое проверочное равенство должно включать символы 1-го, 3-го, 5-го, 7-го и  т.д. разрядов:

                                         

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

                                               

Аналогично находим и  третье равенство:

                                      

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

Таким образом, для кода, например, (7,4), исправляющего одиночные  ошибки, искомые соотношения принимают  вид:

                                        

В принципе, место расположения контрольных разрядов в коде Хэмминга безразлично, но определенные удобства создает такое размещение, при  котором контрольные разряды  входили бы в возможно меньшее  число сумм, получаемых при проверке кода. Это будет, если контрольные  размещать в разрядах, номера которых  равны целой степени числа 2, т.е. в разрядах: 1,2,4,8,16,32 и т.д.

Проверка на приемной стороне  принятой кодовой комбинации осуществляется следующим образом: создаются контрольные  суммы S₁, S₂, S₃ и S₄.

 

Правило построения контрольных  сумм:

S₁ - все нечетные разряды

S₂ - начиная со второго разряда по два разряда подряд через два разряда

S₃ – начиная с 4^го разряда по 4 разряда через 4

S₄ – начиная с 8^го разряда по 8 разрядов через 8 разрядов.

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

 

 

 

 

 

 

 

 

 

Кодер и декодер  кода Хэмминга

Кодер. Схема кодирующего  устройства на четыре информационных разряда представлена на рис. 16

 

 

 

 

 

 

 

 

 

 

 

Рис.16

Со схемы управления поступает  сигнал на кодирование k разрядной информации. Эта комбинация неизбыточного кода переписывается в информационные разряды n-разрядного регистра (триггеры Т3, Т5, Т6 и Т7).

Выходные импульсы сумматоров 1, 2, 4 устанавливают триггеры проверочных  разрядов в положение 0 или 1 в соответствии с  вышеприведенными равенствами.

Сформированная таким  образом в регистре Т1-Т7 комбинация кода Хэмминга импульсом, поступающим  с блока управления, считывается  в линию связи.

Декодер.

Схема декодера представлена на рис.17

 

 

 

 

 

 

 

Рис.17

Схема строится на основе совокупности проверочных равенств.

Кодовая комбинация, возможно содержащая ошибку, поступает на n-разрядный приемный регистр (триггеры Т1-Тn, в нашем случае всего семь разрядов кода Хэмминга). По окончании переходного процесса в триггерах с блока управления на каждый из сумматоров (∑1-∑3) поступает импульс опроса.

Если проверочные равенства  выполняются, на выходах всех сумматоров будет “0”. При наличии ошибки в регистр опознавателей запишется опознаватель этого вектора ошибки. Дешифратор ошибки ДО ставит в соответствие множеству опознавателей множество векторов ошибок. Сигналы с дешифратора поступают только на те разряды, в которых вектор ошибки имеет единицы. Сигналы коррекции воздействуют на счетные входы триггеров. Последние изменяют свое состояние, и таким образом ошибка исправляется. На триггеры поверочных разрядов регистра импульсы коррекции не посылаются, так как после коррекции информация списывается только с информационных разрядов.

 

Практическая  часть

Задание. Построить код Хэмминга с исправлением одиночной ошибки при 10 информационных разрядах, т.е. m=10. Определим число контрольных разрядов.

 

Число контрольных разрядов – 4.

Предположим, необходимо закодировать сообщение:

1011010110

Представим это информационное сообщение в виде кода Хэмминга, установив контрольные разряды  на 1, 2, 4, 8 позициях.

Они вычисляются следующим  образом:

 

 

 

 

 

Разберем схему кодера.

Подаем входной сигнал на регистр сдвига с формирователя. Формирователь исходного кода представляет собой набор из 10 булевых констант, т.е. принимающих значение 0 или 1. С формирователя подаем код 1011010110.

Для вывода и перекодирования  сигнала из параллельного в последовательный код используем два последовательно  подключенных мультиплексора, управляемые  формирователем кода с той же частотой как и у входного сигнала. К  мультиплексорам подключаем триггеры и получившиеся контрольные суммы, которые ставятся на определенные места.

Получаем на выходе код  (на осциллографе код в обратном порядке)

10110100110011

 

 

 

 

Разберем схему декодера

 

 

Используемая литература.

1. Ю.А.Дадаян  «Помехоустойчивое кодирование»