Векторы
ошибок
|
Опознаватели
|
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 и т.д.
Проверка на приемной стороне
принятой кодовой комбинации осуществляется следующим образом: создаются
контрольные суммы S1, S2, S3 и S4.
Правило построения контрольных сумм:
S1 - все
нечетные разряды
S2 - начиная
со второго разряда по два разряда подряд через два разряда
S3 - начиная с
4го разряда по 4 разряда через 4
S4 - начиная с
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. Ю.А.
Дадаян «Помехоустойчивое кодирование»