Лекционная часть к лабораторной работе 11
“Кодер и декодер Хэмминга”
Техническое задание.
Спроектировать в пакете MAX+PLUS 2 схему четырехразрядного двунаправленного кодировщика - декодировщика двоичных данных в код Хэмминга.
Краткие теоретические сведения.
Код Хэмминга позволяет обнаружить и исправить возможные одиночные ошибки.
В рассматриваемом коде из N позиций M используется для информации, а K в качестве контроля. Все информационные разряды разбиваются на контрольные группы, при этом за каждой группой закрепляется контрольный разряд.
Контрольные разряды в коде Хэмминга формируются как «исключающее или» информационных разрядов т.е. дополнение до четного числа единиц.
В приемном устройстве производится K проверок на четность всех контрольных групп. После каждой проверки в регистр ошибок записывается:
0 – если результат проверки четный, нет ошибок;
1 – если нечетность, наличие ошибки в группе;
Полученная последовательность единиц и нулей в регистре ошибок образует двоичное слово, которое называют «синдромом ошибки»; оно указывает номер позиции в слове, в котором искажен символ.
Далее приведена таблица выбора числа контрольных разрядов по числу информационных.
М |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
N |
3 |
5 |
6 |
7 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
17 |
18 |
K |
2 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
5 |
5 |
M - число информационных разрядов;
N - общее число разрядов;
K - число контрольных разрядов
Пример четырехразрядного кодирования.
Методика разбиения числа на контрольные группы:
-
Первая контрольная группа охватывает все разряды кода, номер
которого в двоичной системе имеет единицу первом разряде, т.е. 1,3,5,7.
-
Вторая группа - с единицей во втором разряде, т.е. 2,3,6,7.
-
Третья группа - с единицей в третьем разряде, т.е. 4,5,6,7.
-
Разряды, имеющие степень двойки - контрольные, т.е. 1,2,4.
Номер разряда |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
Номер разряда в двоичной форме |
1000 |
111 |
110 |
101 |
100 |
011 |
010 |
001 |
Обозначение разрядов |
K |
D3 |
D2 |
D1 |
K3 |
D0 |
K2 |
K1 |
Пример кодирования |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
Кодирование: (1)
K1=D0 + D1 + D3
K2=D0 + D2 + D3
K3=D1 + D2 + D3
K =K1 + K2 + D0 + K3 + D1 + D2 + D3
Примечание 1: в данном случае знак “+” не является знаком сложения арифметического, а обозначает операцию “исключающее или” или сложение по модулю 2.
Примечание 2: контрольный разряд K проверяет четность всего закодированного слова и позволяет определить наличие двойной ошибки совместно с контрольными разрядами кода Хэмминга. Код с таким контрольным разрядом называют “модифицированный код Хэмминга”.
Декодирование: (2)
P1=K1 + D0 + D1 + D3
P2=K2 + D0 + D2 + D3
P3=K3 + D1 + D2 + D3
KP=K1 + K2 + D0 + K3 + D1 + D2 + D3 + K
Если P1=P2=P3=0 ошибок нет
Если :
P3 |
P2 |
P1 |
Пояснение |
1 |
0 |
1 |
ошибка в 5 разряде (по предыдущей таблице) |
Таблица поясняет возможные состояния системы декодирования:
KP |
P3 |
P2 |
P1 |
Пояснение |
0 |
0 |
0 |
0 |
нет ошибок |
0 |
0 |
1 |
1 |
двойная ошибка, разряды неизвестны |
1 |
0 |
0 |
0 |
ошибка в главном контрольном разряде |
1 |
0 |
1 |
1 |
одиночная ошибка в 3 разряде, исправляется |
Выбор технического решения.
Первая особенность связана с тем, что мы имеем в своем распоряжении регистр ошибок, который хранит номер ошибочного разряда. Это позволяет нам сделать аппаратную коррекцию одиночной ошибки.
Вторая особенность состоит в том, что данная задача хорошо структурируется, т.е. схему можно разбить на несколько законченных модулей:
-
Модуль кодирования.
Осуществляет формирование четырех контрольных разрядов. Модуль является полностью комбинационным, т.е. используются только логические элементы (без триггеров и регистров и пр.), и к тому же однонаправленным.
-
Модуль декодирования.
Выполняет более сложную задачу: формирует три разряда регистра ошибок, сигналы которого поступают на дешифратор, соответствующий выход которого показывает ошибочный разряд.
Автоматической коррекции подвергаются только разряды данных; при этом, если ошибка появляется в контрольных разрядах, то они просто игнорируются.
Модуль имеет два выхода для обозначения ошибок:
-
ONE_ERR - Одиночная ошибка, исправлена.
-
DBL_ERR - Двойная ошибка, сбой в декодировании.
Данный узел имеет в своем составе еще один модуль: комбинационный двоично - десятичный дешифратор (3 входа, 8 выходов).
Рассмотренные два главных модуля объединяются в итоговой схеме с помощью буферов с тремя состояниями на выходе для обеспечения двунаправленного обмена.