Изучение кодеров и декодеров Хэмминга

Лабораторная работа

Изучение кодеров и декодеров Хэмминга

Линейные коды Хэмминга

В блочных кодах непрерывная информационная последовательность делится на блоки — сообщения длиной k символов. Кодер преобразует блоки информации в более длинные двоичные последовательности, состоящие из n символов, которые называются кодовыми словами. Символы (n-k), добавляющиеся к каждому блоку информации, называются избыточными.

Код называется линейным, если сумма по модулю 2 двух кодовых комбинаций также является кодовой комбинацией этого кода.

Важным качеством линейных блочных кодов является систематичность. Систематический код содержит неизменную информационную часть длиной k символов и избыточную длиной (n-k) символов. Блочный код, обладающий свойствами линейности и систематичности, называется линейным блочным систематическим кодом и обозначается как (n-k).

Коды Хэмминга относятся к линейным систематическим кодам, в которых проверочные разряды (избыточные символы) формируются линейным преобразованием (суммированием по модулю 2) информационных разрядов (символы сообщения). Данные коды имеют кодовое расстояние d₀=3 и d₀=4.

данного типа связано с кодовым расстоянием следующим выражением:

Таким образом, с учетом кодового расстояния, коды Хэмминга позволяют исправлять только одну ошибку.

В зависимости от количества информационных и проверочных разрядов в кодовых словах выделяют коды Хемминга (7,4), (9,5), (11, 7), (15, 11). Обозначение кода (7, 4) означает, что длина кодового слова равна 7 бит, а длина сообщения 4.

Следовательно, число проверочных разрядов r в коде равно 3. По аналогии рассматриваются другие типы кодов.

«Синдром» определяется как сумма по модулю 2 принятых приемником проверочных разрядов b_i кода Хэмминга и заново вычисленных проверочных разрядов b*_i по принятым информационным элементам кода. При этом проверочные разряды b*_i рассчитываются по тем же самым выражениям, которые использовались при расчете b_i.

Если в результате суммирования по модулю 2 элементов b_i и b*_i «синдром» равен нулю, то ошибки в кодовой комбинации отсутствуют, при наличии ошибки в составе «синдрома» появятся единицы.

Двоичное число «синдрома» представляет собой условный номер (в десятичной системе) разряда в коде, где произошла ошибка. В таблице 1 приведены числа, представляющие синдром, для кода Хэмминга (7,4).

Если ошибка происходит в одном из проверочных элементов, то в составе «синдрома» будет только одна единица, например, при возникновении ошибки в разряде b₁ ей будет соответствовать двоичный код «синдрома» 100 (десятичное число 4). Появление большего числа единиц в «синдроме» будет связано с ошибками в информационной части кода. В таблице условные номера присваиваются информационным элементам в порядке возрастания двоичного числа «синдрома».

Используя приведенную таблицу, определяются выражения для расчёта элементов проверочной группы b_i. Например, в двоичном коде «синдрома» элемента b₁ единица присутствует в разряде C₁, поэтому в выражение для его расчёта будут входить только те информационные элементы кода, у которых в разряде С₁ «синдрома» также находится единица. Такими информационными элементами являются a₂ a₃ и а₄. По аналогии определяются формулы для расчёта b₂ и b₃.

Таким образом, выражения для расчета проверочной группы кода Хэмминга (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 разряде

Эпюры работы декодера. Код без ошибки Эпюры работы декодера. Код с ошибкой Из приведенных эпюров видно, что декодер исправил ошибку.

6. С помощью дешифратора проверим таблицу синдромов для кодов Хэмминга.

7. Соберем в Multisim структуру кодера (11,7). Подадим на вход информационную последовательность из пункта 3.3, сравним полученные данные с расчетными:

Структура кодера Хэмминга (11,7)

Эпюры напряжений на выходе кодера.

Полученный код аналогичен расчетному коду

8. Соберем в Multisim структуру декодера (11,7). Подадим на вход код (11,7) из пункта 3.3, введя ошибку в один из разрядов. Сравним полученные данные с расчетными данными:

Входные слова, содержащие единичные ошибки Эпюры напряжений на входе и выходе декодера.

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