Исследование кодов хемминга

Цель работы – изучение принципа построения кодов Хемминга, их реализация аппаратурными и программными методами.

Опыт 1. Изучение принципов построения кодов Хемминга

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

Длина кода Хемминга определяется выражением:

, (2.1)

где – количество проверочных символов.

Формулу (2.1) можно привести к следующему виду:

, (2.2)

где – количество информационных разрядов.

Это неравенство позволяет определить длину кода при заданном числе информационных разрядов. В табл. 2.1 приведены параметры кода Хемминга, вычисленные по формулам (2.1) и (2.2).

Таблица 2.1 – Параметры кода Хэмминга

n	k

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

Таблица 2.2 – Двоичная форма записи номеров позиций

Номер позиции кодовой комбинации	Двоичная форма записи номера позиции

В качестве проверочной может быть выбрана следующая матрица, составленная на основании табл. 2.1:

H7,3=	U1	U2	U3	U4	U5	U6	U7

В качестве проверочных разрядов выбираем разряды.

Чтобы закодировать сообщение 1101, нужно определить проверочные разряды в комбинации

U1

U2

U4

Для матрицы имеем

где символ обозначает сложение по модулю два.

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

Следовательно, закодированное сообщение имеет вид:

Предположим, что текстовой символ принят ошибочно и получено сообщение:

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

В результате получили номер разряда 110, где возникла ошибка. Этот код соответствует шестому разряду.

Порядок выполнения опыта

Заданное преподавателем сообщение закодировать по коду Хемминга.

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

Опыт 2. Изучение аппаратурной и программной реализации средств кодирования и декодирования кодов Хемминга

Основным элементом алгоритма кодирования сообщений по коду Хемминга и обнаружения ошибок является операция сложения по модулю два. Ниже приведена таблица истинности для этой операции (табл. 2.3).

Таблица 2.3 – Таблица истинности для операции сложения по модулю два

Q1	Q2	∑

Для построения схемы, реализующей операцию сложения по модулю два двух слагаемых, составим карту Карно (рис. 2.1).

Рисунок 2.1 – Карта Карно для операции сложения по модулю два

Как видно из этой карты, минимизировать функцию сложения по модулю два путем применения операции склеивания не удается.

Составим логическое уравнение, реализующее функцию сложения по модулю два: .

Схема аппаратурной реализации этого уравнения приведена на рис. 2.2.

Рисунок 2.2 – Схема реализующая операцию сложения по модулю два

С использованием сумматоров по модулю два схема кодирующего устройства для сообщений, состоящих из семи разрядов, примет вид, указанный на рис. 2.3, а схема декодирующего устройства будет иметь вид, указанный на рис. 2.4.

Рисунок 2.3 – Схема кодирующего устройства

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

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

В лаборатории микропроцессорных систем для этих целей используются установки МикроДАТ.

Блок-схема алгоритма кодирования приведена на рис. 2.5, а обнаружения ошибок и их исправления – на рис. 2.6. Эти алгоритмы реализованы программным путем на языке Бейсик.

Рисунок 2.4 – Схема декодирующего устройства

Для выполнения данного опыта используются два рабочих места, соединенные между собой линией связи. Одно рабочее место является приемником, а второе – источником сообщения. Рабочее место-источник выполняет операцию кодирования сообщения и искажения заданного разряда, приемник – операцию декодирования сообщения и исправления ошибок.

Порядок выполнения опыта

1 Включить рабочее место поворотом ключа в гнезде "ВКЛ."

2 Привести прибор контроля и отладки в исходное состояние (все клавиши отжаты).

3 Установить адрес Е000Н. Для этого нажать тумблеры "Адрес" 15, 14, 13.

4 Нажать тумблеры "РАБ/ОСТ", "ПУСК", "ВНА".

Рисунок 2.5 – Блок-схема алгоритма кодирования

5 Отпустить тумблер "РАБ/ОСТ".

6 Нажать тумблер "ПРД". На экране должно появиться сообщение о готовности программы "МОНИТОР".

7 На клавиатуре набрать следующий текст:

G8000 BK

NEW BK

8 Заправить перфоленту в фотосчитыватель FS 1501 и включить тумблером, расположенным на задней стенке.

9 Провести считывание программы с перфоленты. Для этого на клавиатуре набрать текст: START BK.

10 Запустить программу на выполнение (набрать на клавиатуре RUN 180 BK).

11 Ввести с клавиатуры заданные руководителем исходные данные. Ввод каждого данного должен заканчиваться нажатием клавиши "ВК." Сообщение вводится побитно, начиная со старшего разряда.

12 Занести в протокол информацию, выводимую на экран.

13 Выполнить пп. 1–10 для рабочего места-приемника сообщения.

14 С клавиатуры рабочего места-источника ввести: "ПЕРЕДАЧА ВК".

15 Определить номер искаженного разряда и декодировать сообщение, полученное приемником.

16 Для выполнения программы декодирования сообщения с клавиатуры рабочего места-приемника ввести: "CONT ВK".

17 Сравнить результаты выполнения программы с результатами ручного декодирования.

Опыт 3. Исследование выигрыша в точности передачи информации при применении кодов Хемминга

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

Рисунок 2.6 – Блок-схема алгоритма обнаружения ошибок и их исправления

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

Вероятность появления ошибки в канале связи, где действуют помехи, определяется соотношением сигнал / шум:

, (2.3)

где – мощность сигнала; – мощность шума.

Ошибки в канале связи делятся на две группы:

типа пропуск цели, возникающие при приеме "0" в то время, когда была послана "1";

типа ложная тревога, возникающие при приеме "1" в то время, когда был послан "0".

Если вероятности ошибок ложной тревоги и пропуска цели равны, то вероятность возникновения полной ошибки будет определяться выражением

. (2.4)

Программа математической модели канала связи искажает символы многократно посылаемого сообщения с вероятностью по биномиальному закону. Использование алгоритмов кодирования и декодирования информации по коду Хемминга дает возможность набрать статистику и определить дисперсию ошибки, возникающей в канале связи. Для сравнения проводится эксперимент с тем же самым каналом связи, но с применением простого кодирования. Блок-схема алгоритма проведения эксперимента с математической моделью канала связи приведена на рис. 2.7.

Порядок выполнения опыта

1 Запустить программу – набрать на клавиатуре RUN 205 BK.

2 Ввести заданные преподавателем исходные данные аналогично тому, как это сделано в опыте 2.

Исходные данные для выполнения опыта следующие:

– число информационных и контрольных разрядов сообщения;

– число многократно посылаемых сообщений;

– соотношение сигнал / шум.

Рисунок 2.7 – Блок-схема алгоритма проведения эксперимента с математической моделью канала связи

3 Результаты вычислений, выведенные на экран, записать в табл. 2.4; в которой – дисперсия ошибки при кодировании сообщений по коду Хемминга; – дисперсия ошибки при простом кодировании.

Таблица 2.4 – Результаты вычислений

				P0

4 Повторить пп. 1 – 3 для других значений .

5 Повторить пп. 1 – 4 для случая простого кодирования.

6 Сделать выводы о целесообразности применения кода Хемминга в каналах связи с различным соотношением сигнал / шум.

Оформление отчёта

В отчете о лабораторной работе следует привести:

схемы и алгоритмы кодирующего и декодирующего устройства (рис. 2.2 – 2.5);

исходные данные опыта 2 и закодированное сообщение;

табл. 2.4 с результатами опыта;

краткие выводы.

Контрольные вопросы

1 Область применения помехоустойчивого кодирования.

2 Принципы кодирования сообщений с использованием кодов Хемминга.

3 Обнаружение и исправление ошибок сообщений, закодированных с использованием кодов Хемминга.

4 Избыточность кодов Хемминга.

5 Влияние соотношения сигнал / шум на точность передачи сообщений по каналу связи.

Список рекомендуемой литературы

1. Березюк Н.Т., Андрущенко А.Г., Мощинский С.С. и др. Кодирование информации (двоичные коды). - Харьков, 1978. – 252 С.

2. Оптимизация систем цифровой передачи измерительных сигналов: Учеб. пособие / Терентьев С.Н., Глухов А.Б., Константинова Л.В. – Харьков НТУ «ХПИ», 2002. – 268 с.

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