Код Голея

Коды Рида-Соломона.

Коды Хэмминга.

Определение проверочных равенств.

Составление таблиц опознавателей.

Лекция 13. Помехоустойчивые корректирующие коды.

Цель лекции: ознакомление cпомехоустойчивыми корректирующими кодами.

Содержание:

а) cоставление таблиц опознавателей;

б) определение проверочных равенств;

в) Коды Хэмминга;

г) Коды Рида-Соломона;

д) Код Голея;

е) коды Финка-Хагельбаргера

Рассмотрим случай обнаружения одиночных ошибок. Допустим Q=15 тогда, с другой стороны:

Из этого выражения можно получить следующую таблицу:

Инф. K		2..4	5..11	12..26	27..57
Контр. m

Составим таблицу соответствия вектора ошибки и опознавателей КК n=7:

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

Тогда проверка №1:

.

Проверка №2 – аналогично, во втором разряде опознавателя:

.

Проверка №3 – аналогично в третьем разряде определителя:

.

Теперь нужно определить NN проверочных и информационных разрядов в КК. Нужно чтобы контрольные символы входили во все проверки только один раз. Это обеспечит независимость декодирования, т.е. значения контрольных разрядов может быть определено решением одного из проверочных равенств:

то получим размещение:

a1	a2	a3	a4	a5	a6	a7
m1	m2	k1	m3	k2	k3	k4

Пример. Код Хэмминга d=3, n=7, k=4, m=3 KK = 1011

a1	a2	a3	a4	a5	a6	a7

то выходная КК:

				1

Проверка:

Опознаватель = 101 > ошибка в разряде №5

Вектор ошибки: 0000100

Исправление ошибки: 0110111

0000100

Исправленная КК: 0110011

Эти коды являются примером линейных кодов, исправляющих одну единственную ошибку. Длина блока кодов удовлетворяет соотношению n=2^(n-k)-1, где n-k количество проверочных символов. Например, при n-k=3 получаем код (7,4).

Коды РС относятся к классу недвоичных кодов БЧХ. В кодере сообщение, состоящее из k q-ичных символов, выбираемых из алфавита, содержащего q=2^m символов, преобразуется в кодовое слово РС- кода, содержащее n двоичных символов. Поскольку обычно входные и выходные алфавиты равны степени 2, то входные и выходные символы могут быть представлены m- разрядными двоичными словами. Таким образом, входное сообщение можно рассматривать как km- разрядное слово, а выходное кодовое слово – как nm- разрядное двоичное слово. Длина кода РС равна n=q-1. Если исправляющая способность кода равна t ошибочным символам, то имеет место соотношение n-k=2t. Коды РС существуют при, а их расширение имеют длины блока: n= q и n= q+1.

Этот код относится к числу наиболее интересных. Он позволяет исправить ошибки высокой кратности (t>1) и является также совершенным кодом. Код Голея (23,12) является циклическим и исправляет все конфигурации ошибок, кратность которых не превышает трех. С кодом Голея (23,12) связан код (24,12), который образуется добавлением к кодовым словам кода дополнительного проверочного символа. Коды (23,12) и (24,12) имеют минимальное кодовое расстояние, равное соответственно 7 и 8. Поэтому код (24,12), кроме исправления ошибок кратности 4 при незначительном изменении кода обнаруживает ошибки выше кратности 4. Код (24,12) относится к числу наиболее распространенных.