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

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

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

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

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

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

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

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

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

Москва, 2012

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

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

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

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

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

Таблица

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

Предположим, что в результате первой проверки на четность для младшего разряда опознавателя будет получена единица. Очевидно, это может быть следствием ошибки в одном из разрядов, опознаватели которых в младшем разряде имеют единицу. Следовательно, первое проверочное равенство должно включать символы 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 разрядов.

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

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

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

Рис. 1

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

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

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

Декодер.

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

Рис. 2

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

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

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

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

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

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

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

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

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

Рис. 3

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

Рис. 4

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

Рис. 5

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

Рис. 6

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

Рис. 7

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

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