Матричное представление циклических кодов

Для формирования строк производящей матрицы по первому способу образования циклического кода берут комбинации простого k-разрядного кода G(х), содержащие единицу в одном разряде. Эти комбинации умножаются на х^m-k, определяется остаток R(х) от деления полученного произведения
х^m-kG(х) на образующий полином и записывается соответствующая строка матрицы в виде суммы произведения х^m-kG(х) и остатка R(х). При этом производящая матрица P_m,k представляется двумя подматрицами – информационной U_k и дополнительной Н_p : P_m,k =|U_k , H_p |.

Информационная подматрица U_k представляет собой квадратную единичную матрицу с количеством строк и столбцов, равным k. Дополнительная подматрица H_p содержит p = m - k столбцов и k строк и образована остатками R(х).

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

Пример 2.6.

Пусть, например, необходимо построить производящую матрицу (7,4) циклического кода. Образующий полином Р(х) = х³ + х² + 1.

Информационная подматрица имеет вид

_{Дискретная математика – пособие (Часть 3 из 5). Кодирование сигналов"/>}.

Для получения первой строки дополнительной подматрицы первая строка информационной подматрицы умножается на х³ и делится на образующий полином. Это соответствует выполнению операций [(0001 · 1000)/ 1000]. Остаток этих операций (101) и составит первую строку дополнительной подматрицы. Аналогично определяются остальные строки дополнительной подматрицы. Окончательно производящая матрица имеет вид

.

При втором способе образования циклического кода производящая матрица P_m,k формируется путем умножения образующего полинома Р(х) степени р = m – k на одночлен х^m-k и последующих k – 1 сдвигов полученной комбинации.

Выбор образующего полинома

При построении циклического кода вначале определяется число информационных разрядов k по заданному объему кода. Затем находится наименьшая длина кодовых комбинаций m, обеспечивающая обнаружение или исправление ошибок заданной кратности. Эта проблема сводится к нахождению нужного образующего полинома Р(х). Степень образующего полинома должна быть равна числу проверочных разрядов р.

Поскольку в циклическом коде опознавателями ошибок являются остатки от деления многочлена принятой комбинации на образующий многочлен, корректирующая способность кода будет тем выше, чем больше остатков может быть образовано в результате этого деления. Наибольшее число остатков, равное 2^p - 1 (исключая нулевой), может обеспечить только неприводимый многочлен степени р (т.е. не делящийся ни на какой другой многочлен).

Двучлен типа (x ^m + 1) = (x ^t-1 + 1), где t = 2 ^z, в разложение которого в качестве сомножителя должен входить образующий многочлен, обладает тем свойством, что является общим кратным для всех без исключения неприводимых полиномов степени z и разлагается на множители из всех неприводимых полиномов, степени z_i которых делят без остатка число z.

Простейшим циклическим кодом является код, обеспечивающий обнаружение однократных ошибок. Вектору однократной ошибки соответствует одночлен хⁱ, степень которого i может принимать значения от 1 до m. Для того чтобы могла быть обнаружена ошибка, одночлен xⁱ не должен делиться на образующий полином Р(х). Среди неприводимых многочленов, входящих в разложение двучлена х ^m + 1, является многочлен наименьшей степени х + 1. Таким образом, образующим полиномом данного кода является двучлен
Р(х) = х + 1. Остаток от деления любого многочлена на х + 1 может принимать только два значения 0 и 1. Следовательно, при любом числе информационных разрядов необходим только один проверочный разряд. Значение символа этого разряда обеспечивает четность числа единиц в кодовой комбинации.

Данный циклический код с проверкой на четность обеспечивает обнаружение не только однократных ошибок, но и всех ошибок нечетной кратности.

Например, для кода с k = 4 информационная подматрица будет иметь вид

.

Дополнительную матрицу можно построить по остаткам деления последней строки информационной подматрицы, дополненной р нулями, на образующий полином:

Таким образом, дополнительная матрица имеет вид

.

Следовательно, производящая матрица

.

Для построения циклического кода, исправляющего однократные или обнаруживающего двукратные ошибки, необходимо, чтобы каждой одиночной ошибке соответствовал свой опознаватель, т. е. остаток от деления многочлена принятой комбинации на образующий многочлен. Поскольку количество возможных однократных ошибок равно m, а неприводимый многочлен степени р может дать 2 ^p – 1 ненулевых остатков, то необходимым условием исправления любой одиночной ошибки является выполнение неравенства

Отсюда находятся степень образующего полинома

и общая длина m кодовой комбинации.

В табл. 2.13 приведены наибольшие значения k и m для различных р. Поскольку образующий многочлен Р(х) должен входить в качестве сомножителя в разложение двучлена (х^m + 1) = (x ^t-1 + 1), где t = 2 ^z, то, используя указанные ранее свойства этого двучлена, а также условие (2.22), можно выбрать образующий полином.

Таблица 2.13

Однако не всякий многочлен степени р, входящий в разложение двучлена х^m + 1, может быть использован в качестве образующего полинома. Необходимо, чтобы для каждой из m однократных ошибок обеспечивался свой, отличный от других, остаток от деления принятой кодовой комбинации на образующий полином. Это будет иметь место при условии, если выбранный неприводимый многочлен степени р, являясь делителем двучлена х^m + 1, не входит в разложение никакого другого двучлена х^l + 1, степень которого
l < m.

Пример 2.7.

Рассмотрим в качестве примера способ выбора образующего полинома для построения циклического кода, содержащего k = 4 информационных символа и обеспечивающего устранение однократных ошибок и обнаружение двукратных ошибок.

В соответствии с (2.22) и табл. 2.13 определяем общее количество символов m = 7 и количество проверочных символов p = 3. Образующий полином Р(х) должен быть степени р = 3 и входить в качестве сомножителя в разложение двучлена (x ^m + 1) = (x ^t-1 + 1), где t = 2 ^z. Так как m = 7, то составляющие сомножители двучлена должны быть неприводимыми полиномами, степени которых являются делителями числа z = 3. К числам, на которые z = 3 делится без остатка, относятся 1 и 3. Следовательно, сомножителями двучлена (х ⁷ + 1) должны быть неприводимые полиномы первой и третьей степеней. Пользуясь таблицами неприводимых полиномов, получим

Ни один из сомножителей степени 3 не входит в разложение другого двучлена х ^m + 1 степени m < 7. Поэтому каждый из этих сомножителей может быть выбран в качестве образующего полинома.

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

1. По заданному числу информационных разрядов k определяется число проверочных разрядов r, необходимое для исправления однократных ошибок, и находится образующий полином.

2. Рассматривая полученный (m, k)-код как некорректирующий m-разрядный код, определяют дополнительные разряды для обеспечения исправления одной ошибки в этом коде и находят соответствующий образующий полином.

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

Однако код, построенный таким образом, является неоптимальным с точки зрения числа избыточных символов. В этом отношении более совершенен код Боуза – Чоудхури, обеспечивающий минимальное число проверочных символов при заданном k. Математическая структура этого кода несколько отлична от рассмотренной ранее и характеризуется более сложными устройствами для обнаружения и исправления ошибок. Особенностью этого кода является то, что для любых целых положительных чисел z и t существует циклический код значности m = 2 ^z – 1 с кодовым расстоянием d_мин = 2t + 1. При этом число проверочных символов r не превышает величины zt, т. е.
r £ zt. Такой код исправляет ошибки кратности не более t или обнаруживает ошибки кратности не более 2t. Кроме того, код обнаруживает все пачки ошибок, длина которых равна или меньше r.

К числу циклических кодов, предназначенных для исправления пачек ошибок, относятся коды Файра, Абрамсона и Миласа – Абрамсона, обеспечивающие исправление одной пачки ошибок, и код Рида – Соломона, рассчитанный на исправление нескольких пачек ошибок.