Материал: 3 ИССЛЕДОВАНИЕ СИСТЕМ СВЯЗИ С ИСПОЛЬЗОВАНИЕМ КОРРЕКТИРУЮЩЕГО БЛОЧНОГО КОДА ХЭММИНГА

Корректирующие коды Хемминга.

Построение кодов Хемминга базируется на принципе проверки на чётность веса W (числа единичных символов) в информационной группе кодового блока.

Поясним идею проверки на чётность на примере простейшего корректирующего кода, который так и называется кодом с проверкой на чётность или кодом с проверкой по паритету (равенству).

В таком коде к кодовым комбинациям безизбыточного первичного двоичного m - разрядного кода добавляется один дополнительный разряд (символ проверки на чётность, называемый проверочным, или контрольным). Если число символов “1” исходной кодовой комбинации чётное, то в дополнительном разряде формируют контрольный символ 0, а если число символов “1” нечётное, то в дополнительном разряде формируют символ 1. В результате общее число символов “1” в любой передаваемой кодовой комбинации всегда будет чётным.

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

,

где i - соответствующий информационный символ (0 или 1), m - общее их число а под операцией "" здесь и далее понимается сложение по mod2. Очевидно, что добавление дополнительного разряда увеличивает общее число возможных комбинаций вдвое по сравнению с числом комбинаций исходного первичного кода, а условие чётности разделяет все комбинации на разрешённые и неразрешённые. Код с проверкой на чётность позволяет обнаруживать одиночную ошибку при приёме кодовой комбинации, так как такая ошибка нарушает условие чётности, переводя разрешённую комбинацию в запрещённую.

Критерием правильности принятой комбинации является равенство нулю результата S суммирования по mod2 всех n символов кода, включая проверочный символ k₁. При наличии одиночной ошибки S принимает значение 1:

.

Этот код является (m+1, m) - кодом, или (n, n-1) - кодом. Минимальное расстояние кода равно двум (d_min = 2), и, следовательно, никакие ошибки не могут быть исправлены. Простой код с проверкой на чётность может использоваться только для обнаружения (но не исправления) однократных ошибок.

Увеличивая число дополнительных проверочных разрядов и формируя по определённым правилам проверочные символы k, равные 0 или 1, можно усилить корректирующие свойства кода так, чтобы он позволял не только обнаруживать, но и исправлять ошибки. На этом и основано построение кодов Хемминга.

Коды Хемминга. Рассмотрим эти коды, позволяющие исправлять одиночную ошибку, с помощью непосредственного описания. Для каждого числа проверочных символов k = 3,4,5… существует классический код Хемминга с маркировкой

(n,m) = (2^k – 1, 2^k – 1 – k) , (3.19)

т.е. - (7,4), (15,11), (31,26) …

При других значениях числа информационных символов m получаются так называемые усечённые (укороченные) коды Хемминга. Так, для международного телеграфного кода МТК-2 , имеющего 5 информационных символов, потребуется использование корректирующего кода (9,5), являющегося усечённым от классического кода Хемминга (15,11), так как число символов в этом коде уменьшается (укорачивается) на 6. Для примера рассмотрим код Хемминга (7,4), который можно сформировать и описать с помощью кодера, представленного на рис.3.1. В простейшем варианте при заданных четырёх (m = 4) информационных символах (i₁, i₂, i₃, i₄) будем полагать, что они сгруппированы в начале кодового слова, хотя это и не обязательно. Дополним эти информационные символы тремя проверочными символами (k = 3), задавая их следующими равенствами проверки на чётность, которые определяются соответствующими алгоритмами. Известно, что кодовое расстояние равно минимальному числу проверок, в которые входит информационный символ плюс один. В рассматриваемом коде d_min. Следовательно каждый информационный символ должен входить минимум в две проверки. Определим правило формирования проверочных символов следующий образом:

В соответствии с этим алгоритмом определения значений проверочных символов k_i на рис.3.3 приведены все возможные 16 кодовых слов (7,4) - кода Хемминга.

На рис. 3.2 приведена схема декодера для (7,4) - кода Хемминга, на вход которого поступает кодовое слово

.

Апостроф означает, что любой символ слова может быть искажён помехой в канале передачи.

В декодере в режиме исправления ошибок строится последовательность:

Трёхсимвольная последовательность (s₁, s₂, s₃) называется синдромом. Термин "синдром" используется и в медицине, где он обозначает сочетание признаков, характерных для определённого заболевания. В данном случае синдром S = (s₁, s₂, s₃) представляет собой сочетание результатов проверки на чётность соответствующих символов кодовой группы и характеризует определённую конфигурацию ошибок (вектор ошибок).

Рис.3.1. Кодер для простого (7,4) - кода Хемминга

Рис.3.2. Декодер для простого (7,4) - кода Хемминга

Рис.3.3. Кодовые слова код (7,4) – кода Хемминга

Число возможных синдромов определяется выражением

S = 2^k. (3.20)

При числе проверочных символов k = 3 имеется восемь возможных синдромов (2³ = 8). Нулевой синдром (000) указывает на то, что ошибки при приёме отсутствуют или не обнаружены. Всякому ненулевому синдрому соответствует определённая конфигурация ошибок, которая и исправляется. Классические коды Хемминга (3.19) имеют число синдромов, точно равное их необходимому числу, позволяют исправить все однократные ошибки в любом информативном и проверочном символах и включают один нулевой синдром. Такие коды называются плотноупакованными.

Усечённые коды являются неплотноупакованными, так как число синдромов у них превышает необходимое. Так, в коде (9,5) при четырёх проверочных символах число синдромов будет равно 2⁴ =16, в то время как необходимо всего 10. Лишние 6 синдромов свидетельствуют о неполной упаковке кода (9,5).

Для рассматриваемого кода (7,4) в табл.3.1 представлены ненулевые синдромы и соответствующие конфигурации ошибок.

Таблица 3.1

Таким образом, код (7,4) позволяет исправить все одиночные ошибки. Простая проверка показывает, что каждая из ошибок имеет свой единственный синдром. При этом возможно создание такого цифрового корректора ошибок (дешифратора синдрома), который по соответствующему синдрому исправляет соответствующий символ в принятой кодовой группе. После внесения исправления проверочные символы k_i можно на выход декодера (рис.3.2) не выводить. Две или более ошибки превышают возможности корректирующего кода Хемминга, и декодер будет ошибаться. Это означает, что он будет вносить неправильные исправления и выдавать искажённые информационные символы.

Идея построения подобного корректирующего кода, естественно, не меняется при перестановке позиций символов в кодовых словах. Все такие варианты также называются (7,4) - кодами Хемминга.

Расширенные коды Хемминга строятся в результате дополнения кодов с d_min = 3 общей проверкой каждой из кодовых комбинаций на чётность, т.е. ещё одним проверочным символом. Это позволяет увеличить минимальное кодовое расстояние до d_min = 4.

3.3 Описание лабораторной установки

Лабораторный макет представляет собой программную имитационную модель в пакете Simulink. Модель содержит источник информации с возможностью выдачи заданной или случайной кодовой комбинации, кодер, модель двоичного симметричного канала связи, декодер и средства анализа процессов кодирования, декодирования и передачи кодовых комбинаций. Структурная схема модели представлена на рис.3.4. На рис.3.5 представлена структурная схема кодера и декодера для классического кода Хемминга (7,4).

Рис. 3.4. Структурная схема модели

Рис.3.5. Структурная схема кодера и декодера

Структурные схемы кодера и декодера построены на сумматорах по модулю два, мультиплексорах и демультиплексорах. В схеме декодера в качестве решающего устройства применена модель программируемой логической матрицы. Программируемая логическая матрица содержит матрицу, которая определяет кодовую комбинацию выдаваемую на выход по следующему алгоритму: на выход выдается строка матрицы с индексом соответствующем кодовой комбинации поступившей на вход (входная кодовая комбинация рассматривается как двоичное число, первый разряд старший). Так, например, для классического кода Хемминга (7,4), приведенного на рис.3.5, марица имеет вид:

0 0 0 0;

0 0 0 0;

0 0 0 0;

1 0 0 0;

0 0 0 0;

0 1 0 0;

0 0 1 0;

0 0 0 1.

При настройке параметров модели необходимо ввести строку:

«[0 0 0 0, 0 0 0 0, 0 0 0 0, 1 0 0 0, 0 0 0 0, 0 1 0 0, 0 0 1 0, 0 0 0 1,]»

3.4 Порядок выполнения работы и методические указания по ее выполнению

В лабораторной работе исследуется коды Хемминга в том числе и усеченные.

Таблица 3.2

1. Запустите систему моделирования Simulink.

2. Откройте шаблон модели Hemming.mdl.

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

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

5. Повторите проверку для остальных разрядов. Результаты проверки сведите в таблицу (см. табл.3.3)

Таблица 3.3

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

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

Таблица 3.4

8. Внести в канале связи двукратную ошибку. Провести исследование процесса декодирования принятой кодовой комбинации. Повторить эксперимент еще три раза для других вариантов двукратной ошибки. Результаты занести в табл.3.4. Объяснить полученные результаты.

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

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