Циклические коды

Циклическими кодами называют специальную группу линейных кодов, которые имеют полиномиальное представление. Например, кодовая комбинация 101101 имеет следующее полиномиальное представление:

P (x) = 1× x ⁵ + 0× x ⁴ + 1× x ³ + 1× x ² + 0× x ¹ + 1 = x ⁵ + x ³ + x ² + 1.

Циклические коды относятся к систематическим (n, k)-кодам, в которых контрольные n – k и информационные k разряды расположены на строго определенных местах.

Над полиномами, представляющими циклические коды, определены операции умножения, деления, сложения и вычитания. При этом операции сложения и вычитания выполняются по модулю 2.

Циклический код F (x) получают следующим образом:

где h (х) – заданный многочлен, соответствующий исходной кодовой комбинации, g (х) – образующий многочлен, который является неприводимым сомножителем при разложении двучлена хⁿ +1 (таблица 9.6).

При декодировании принятую кодовую комбинацию необходимо разделить на g (x). Если в результате деления остаток не равен нулю, то означает, что в кодовой комбинации имеется ошибка.

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

n – k = log(n + 1),

которое в численном виде показано в таблице 7.4, а затем из таблицы неприводимых полиномов (таблица 7.6) выбирают самый короткий многочлен со степенью, равной числу контрольных символов.

Таблица 7.4

Соотношения между числом информационных и контрольных символов

Пусть, например, требуется закодировать комбинацию вида 1101, что соответствует h (х) = х ³ + х ² + 1. Процесс кодирования последовательно выполняется в виде следующих шагов.

1. Определим число контрольных символов n – k. Оно будет равно 3.

2. Из таблицы 9.6 выберем многочлен g (х) = х ³ + х + 1, т.е. 1011.

3. Умножим h (х) на х^{n – k}: h (x) х^{n – k} = (x ³ + x ² + 1) x ³ = x ⁶ + x ⁵ + x ³, что соответствует 1101000.

4. Разделим полученное произведение на образующий полином g (х):

.

5. Суммируем остаток с h (х) х^{n – k}. В результате получим закодированное сообщение F (x) = x ⁶ + x ⁵ + x ³ + 1 = 1101001.

В полученной кодовой комбинации циклического кода информационные символы h (х) = 1101, а контрольные R (х) = 001. Закодированное сообщение делится на образующий полином без остатка:

1101001 / 1011 = 1111.

Для образования циклических кодов можно воспользоваться образующей (порождающей) матрицей. Образующая матрица G_{k ´ n} составляется на основе единичной матрицы I_k, к которой справа дописывается матрица остатков R_{k ´( n – k )}:

.

Матрица R_{k ´( n – k )} получается из остатков r_i от деления полинома x ^{2( n – k )– i– 1}на образующий многочлен g (x) для всех строк с номерами i = 1, 2, …, k. Например, для (7, 4)-кода и g (x) = х ³ + х + 1 будут получены остатки, представленные в таблице 7.5.

Таблица 7.5

Образование элементов матрицы остатков

Порождающая матрица для (7, 4)-кода с порождающим многочленом g (x) = х ³ + х + 1 имеет вид

.

Для обнаружения ошибок можно использовать проверочную матрицу

.

Например, для (7, 4)-кода проверочная матрица будет следующей

.

Применение порождающей и проверочной матриц точно такое же, как и в случае кодов Хэмминга. Пусть, например, необходимо получить линейный код для 1101. Тогда умножив 1101 на порождающую матрицу, получим искомую кодовую комбинацию 1101001. Теперь, пусть вместо 1101001 была принята комбинация 1101011. Умножив ее на транспонированную проверочную матрицу, получим синдром 010, соответствующий 6 строке этой матрицы, что означает, что необходимо исправить 6 разряд проверяемой кодовой комбинации. Выполнив исправление, получаем 1101001.

Таблица 7.6

Порождающие многочлены

Поиск по сайту: