Изучение кодеров и декодеров Хэмминга
Лабораторная работа
Изучение
кодеров и декодеров Хэмминга
Линейные коды Хэмминга
В блочных кодах непрерывная
информационная последовательность делится на блоки - сообщения длиной k символов. Кодер преобразует блоки
информации в более длинные двоичные последовательности, состоящие из n символов, которые называются
кодовыми словами. Символы (n-k), добавляющиеся к каждому блоку информации, называются
избыточными.
Код называется линейным, если сумма
по модулю 2 двух кодовых комбинаций также является кодовой комбинацией этого
кода.
Важным качеством линейных блочных
кодов является систематичность. Систематический код содержит неизменную
информационную часть длиной k символов и избыточную длиной (n-k) символов.
Блочный код, обладающий свойствами линейности и систематичности, называется
линейным блочным систематическим кодом и обозначается как (n-k).
Коды Хэмминга относятся к линейным
систематическим кодам, в которых проверочные разряды (избыточные символы)
формируются линейным преобразованием (суммированием по модулю 2) информационных
разрядов (символы сообщения). Данные коды имеют кодовое расстояние d0=3 и d0=4.
данного типа связано с кодовым
расстоянием следующим выражением:
Таким образом, с учетом кодового
расстояния, коды Хэмминга позволяют исправлять только одну ошибку.
В зависимости от количества
информационных и проверочных разрядов в кодовых словах выделяют коды Хемминга
(7,4), (9,5), (11, 7), (15, 11). Обозначение кода (7, 4) означает, что длина
кодового слова равна 7 бит, а длина сообщения 4.
Следовательно, число проверочных
разрядов r в коде равно 3. По аналогии рассматриваются другие типы кодов.
«Синдром» определяется как сумма по
модулю 2 принятых приемником проверочных разрядов bi кода Хэмминга и
заново вычисленных проверочных разрядов b*i по принятым
информационным элементам кода. При этом проверочные разряды b*i
рассчитываются по тем же самым выражениям, которые использовались при расчете bi.
Если в результате суммирования по
модулю 2 элементов bi и b*i «синдром» равен нулю, то
ошибки в кодовой комбинации отсутствуют, при наличии ошибки в составе
«синдрома» появятся единицы.
Двоичное число «синдрома»
представляет собой условный номер (в десятичной системе) разряда в коде, где
произошла ошибка. В таблице 1 приведены числа, представляющие синдром, для кода
Хэмминга (7,4).
Если ошибка происходит в одном из
проверочных элементов, то в составе «синдрома» будет только одна единица,
например, при возникновении ошибки в разряде b1 ей будет соответствовать двоичный код «синдрома» 100 (десятичное
число 4). Появление большего числа единиц в «синдроме» будет связано с ошибками
в информационной части кода. В таблице условные номера присваиваются
информационным элементам в порядке возрастания двоичного числа «синдрома».
Используя приведенную таблицу,
определяются выражения для расчёта элементов проверочной группы bi. Например, в
двоичном коде «синдрома» элемента b1 единица присутствует в
разряде C1, поэтому в выражение для его расчёта будут входить только
те информационные элементы кода, у которых в разряде С1 «синдрома»
также находится единица. Такими информационными элементами являются a2 a3 и а4. По
аналогии определяются формулы для расчёта b2 и b3.
Таким образом, выражения для расчета
проверочной группы кода Хэмминга (7, 4) имеют вид:
Приведенные соотношения можно
компактно отобразить в виде проверочной матрицы Н:
По аналогии строится таблица,
проверочная матрица и выводятся выражения для расчета проверочной группы кодов
Хэмминга (9, 5), (11,7), (15,11).
Аппаратная реализация кодера
Хэмминга может быть представлена в соответствии со структурной схемой,
приведённой на рис. 2.
Кодер включает в себя входной и
выходной регистры, логическую схему и систему управления. На вход устройства
поступает информационная последовательность от источника сообщения, которая
записывается во входной регистр. В логической схеме рассчитываются элементы
проверочной группы, согласно выражениям, полученным на основе анализа
«синдрома». После этого информационная и проверочная кодовые группы
записываются в выходной регистр. Система управления реализует заданный алгоритм
кодирования информации.
Структура декодера Хэмминга приведена
на рис. 3. Она включает в себя входной и выходной регистры, логическую схему и
схему сравнения, дешифратор и схему исправления ошибок. Код Хэмминга поступает
во входной регистр, где выполняется его преобразование из последовательной
формы в параллельную. Логическая схема рассчитывает элементы проверочной группы
b*i по принятым
информационным элементам. Схема сравнения вычисляет «синдром». В случае
ненулевого «синдрома» дешифратор выполняет преобразование его двоичного кода в
десятичный, соответствующий номеру разряда кода в котором произошла ошибка, а
схема исправления ошибок инвертирует данный разряд. В выходной регистр
записывается декодированная кодовая последовательность. Система управления
реализует заданный алгоритм декодирования информации.
Выполнение работы
1. Составим таблицы синдромов для кодов Хэмминга (7,4), (9,5),
(11,7), (15,11):
2. Получим выражения для расчета элементов проверочных групп для
кодов Хэмминга (7,4), (9,5), (11,7), (15,11):
3. На элементах ИСКЛ-ИЛИ построим структуры кодеров и проверим
прохождение сигналов:
4. На стенде подадим на вход кодера (7,4) построенный код, проверим
эпюры работы декодера в контрольных точках.
Введем ошибку в код (7,4), и подадим
полученный код на вход декодера, приведем эпюры. Убедимся, что декодер исправил
ошибку.
Код без ошибки Код
с ошибкой во 2 разряде
Вход
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
|
Вход
|
1
|
0
|
0
|
1
|
0
|
0
|
1
|
a1
|
1
|
|
|
1
|
|
1
|
1
|
|
a1
|
1
|
|
|
1
|
|
|
1
|
a2
|
|
1
|
|
|
1
|
|
1
|
|
a2
|
|
1
|
|
|
1
|
|
|
a3
|
|
|
1
|
|
|
1
|
|
|
1
|
|
|
1
|
|
a4
|
|
|
|
1
|
|
|
1
|
|
a4
|
|
|
|
1
|
|
|
1
|
b1
|
|
|
|
|
1
|
|
|
|
b1
|
|
|
|
|
1
|
|
|
b2
|
|
|
|
|
|
1
|
|
|
b2
|
|
|
|
|
|
1
|
|
b3
|
|
|
|
|
|
|
1
|
|
b3
|
|
|
|
|
|
|
1
|
C1
|
|
1
|
1
|
1
|
|
1
|
|
|
C1
|
|
1
|
1
|
1
|
|
1
|
1
|
C2
|
1
|
|
1
|
|
|
1
|
|
|
C2
|
1
|
|
1
|
|
|
|
|
C3
|
1
|
1
|
|
|
1
|
1
|
|
|
C3
|
1
|
1
|
|
|
1
|
|
1
|
A1
|
|
|
|
1
|
|
1
|
1
|
|
A1
|
|
|
|
1
|
|
|
1
|
A2
|
|
|
|
|
1
|
|
1
|
|
A2
|
|
|
|
|
1
|
|
1
|
A3
|
|
|
|
|
|
1
|
|
|
A3
|
|
|
|
|
|
1
|
|
A4
|
|
|
|
1
|
|
1
|
1
|
|
A4
|
|
|
1
|
B1
|
|
|
|
1
|
1
|
|
|
|
B1
|
|
|
|
1
|
1
|
1
|
|
B2
|
|
|
|
|
|
1
|
|
|
B2
|
|
|
|
|
|
1
|
|
B3
|
|
|
|
|
|
|
1
|
|
B3
|
|
|
|
|
1
|
|
1
|
Эпюры работы декодера. Код без
ошибки
Эпюры работы декодера. Код с ошибкой
Из приведенных эпюров видно, что
декодер исправил ошибку.
6. С помощью дешифратора проверим таблицу синдромов для кодов
Хэмминга.
7. Соберем в Multisim структуру кодера (11,7). Подадим на вход информационную
последовательность из пункта 3.3, сравним полученные данные с расчетными:
Структура кодера Хэмминга (11,7)
Эпюры напряжений на выходе кодера.
Полученный код аналогичен расчетному
коду
8. Соберем в Multisim структуру декодера (11,7). Подадим на вход код (11,7) из пункта
3.3, введя ошибку в один из разрядов. Сравним полученные данные с расчетными
данными:
Входные слова, содержащие единичные
ошибки
Эпюры напряжений на входе и выходе
декодера.
линейный код хэмминг преобразование
Можно убедиться, что декодер
исправил ошибки в каждом из разрядов.