Работа №3. Помехоустойчивое кодирование сообщений

Теоретические сведения

Помехоустойчивыми (корректирующими) называются коды, позволяющие обнаружить и при необходимости исправить ошибки в принятом сообщении. Наибольшее распространение получили блочные систематические коды, в которых существует четкое разделение разрядов на информационные и проверочные. Такие коды обозначаются как (п, к)-коды, где п — количество разрядов в блоке, к — количество информационных разрядов в блоке.

К блочным систематическим кодам относятся матричный код и циклический код.

Матричный код Получение кодовых комбинаций производится с помощью порождающих матриц, состоящих из к строк и п столбцов:

В классической (канонической) форме кода элементы первых к столбцов служат для информационных целей, а оставшихся — для проверочных. Соответственно, порождающую матрицу G можно представить в виде двух подматриц — информационной 4 и проверочной Р:

где

Информационную подматрицу обычно берут в виде квадратной единичной матрицы размерностью к х к, а проверочная подматрица Р строится с соблюдением следующих условий:

• 1) вес (количество единиц) каждой строки подматрицы должен быть не менее d_min — 1, где d_min — минимальное кодовое расстояние кода;
• 2) все строки должны быть различны.

Кодовое слово помехоустойчивого кода образуется умножением исходной комбинации на порождающую матрицу: и = т? G .

В отличие от канонического представления, в коде Хемминга информационные и проверочные биты не разнесены в отдельные подматрицы, а чередуются. Если биты кодовой комбинации пронумеровать, начиная с 1, слева направо, то контрольными (проверочными) оказываются биты с номерами 1, 2, 4, 8 и т. д., а все остальные являются информационными. Таким образом, для получения порождающей матрицы кода Хемминга нужно в порождающей матрице канонической формы переставить столбцы, поставив столбцы проверочной подматрицы на 1, 2, 4, 8 и т. д. места.

Циклический код Циклические коды используют полиномиальное представление двоичных последовательностей. Для составления (п, /с)-кода применяется так называемый порождающий полином степени п — к. Кодовое слово циклического кода состоит из неизменной информационной части т и (п — к) проверочных символов. Проверочные символы являются коэффициентами полинома р (х), являющегося остатком от деления т (х) • х^п-^к на порождающий полином g (x). То есть, при поступлении на вход кодера комбинации т кодовое слово и получается так:

что соответствует бинарной комбинации Задание к работе Задание, А А.1. Для заданного в лабораторной работе № 2 варианта системы передачи информации определить:

• 1) количество информационных разрядов в кодовом слове;
• 2) минимальное кодовое расстояние для однократных и двукратных ошибок;
• 3) минимально необходимое количество контрольных разрядов для кодов, исправляющих однократные и двукратные ошибки.

А.2. Составить порождающие матрицы для кода Хемминга, исправляющего однократные ошибки, и канонического матричного кода, исправляющего двукратные ошибки.

А.З. Составить проверочные матрицы для матричных кодов из п. А.2.

А.4. Для канонического матричного кода, исправляющего двукратные ошибки, составить таблицу соответствия синдрома и локализации ошибок (для уменьшения трудоемкости задания в таблицу можно включить только ошибки в информационных разрядах).

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

А.6. Получить помехоустойчивые коды для каждого символа первичного алфавита.

А. 7. Составить порождающий полином g (x) для исправления однократных и двукратных ошибок.

Задание Б Б.1. Составить программу кодирования, декодирования и локализации однократных ошибок с использованием циклического кода.

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

• 1. Как классифицируются помехоустойчивые коды?
• 2. Что такое корректирующая способность кода?
• 3. Что такое кодовое расстояние и как оно влияет на корректирующую способность кода?
• 4. Что такое избыточность кода и от чего она зависит? Как уменьшить избыточность кода?
• 5. Как определяется длина кодового слова?
• 6. Как вычисляется синдром ошибки?
• 7. Каковы правила сложения по модулю два?
• 8. Каковы арифметические правила для полиномов?
• 9. В чем состоят правила кодирования с использованием порождающей матрицы?
• 10. В чем состоят правила декодирования с использованием проверочной матрицы?
• 11. Что такое вектор ошибки?
• 12. Каковы правила кодирования с помощью порождающих полиномов?
• 13. Как определить соответствие вектора ошибки и синдрома ошибки для циклических кодов?
• 14. Как определить соответствие вектора ошибки и синдрома ошибки для матричных кодов?