Циклические коды и их применение

ЦИКЛИЧЕСКИЕ КОДЫ

Основные свойства циклического кода и способы построения

Циклические коды получили довольно широкое применение благодаря их эффективности при обнаружении и исправлении ошибок. Схемы кодирующие и декодирующих устройств для этих кодов чрезвычайно просты и строятся на основе обычных регистров сдвига.

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

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

(1)

где - цифры данной системы счисления (в двоичной системе 0 и 1).

Так, например, двоичное семиразрядное число 1010101 может быть записано в виде полинома

(2)

Наибольшая степень х в слагаемом с нулевым коэффициентом называется степенью полинома.

Представление кодовых комбинаций в форме (2) позволяет свести действия над комбинациями к действию над многочленами. При этом сложении многочленов сводится к сложению по модулю два коэффициентов при равных степенях переменной х, умножение производится по обычному правилу перемножение степенных функций, однако полученные при этом коэффициенты при равных степенях переменной х складывается по модулю два; деление осуществляется по правилам деления степенных функций, при этом операции вычитания заменяются операциями суммирования по модулю два.

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

.

Однако в последнем члене надо заменить на 1.

Следовательно навоя комбинация будет

.

Например, циклический сдвиг кодовой комбинации 1010101 может быть получен путем умножения полинома (2) на х

Заменив на 1, получим полином

Соответствующей кодовой комбинации 0101011.

Согласно определению циклического кода для построения производящей матрицы достаточно выбрать только одну исходную n- разрядную комбинацию циклическим сдвигом можно получить (n - 1) различных комбинаций, из которых любые k комбинаций могут быть взяты в качестве исходных. Суммируя строки производящей матрице во всех возможных комбинациях, можно получить остальные кодовые комбинации. Можно показать0, что кодовые комбинации, получаемые из некоторых комбинаций циклическим сдвигом, удовлетворяют условиям, представляемым к совокупности исходных комбинаций.

Циклический сдвиг комбинации с единицей в старшем n-м разряде равносилен умножению соответствующего многочлена на х с одновременным вычитанием из результата многочлена или ,

Так как операции осуществляются по модулю два. Следовательно, если в качестве исходного взять некоторый полином Р(х), то процесс получения базовых полиномов можно представить в следующем виде;

(3),

где - коэффициенты, принимающие значения 1 при и значение 0 при

При таком способе построения базовых полиномов полином Р(х) называют образующим.

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

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

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

Циклический (n, k)- код может быть получен путем умножения простого к значного кода, выраженного в виде полинома степени (n - 1), на некоторый образующий полином Р(х) степени (n - k).

Возможна и другая процедура получения циклического кода. Для этого кодовая комбинация простого k- значного кода G(x) умножается на одночлен , а затем делится на образующий полином Р(х) степени (n - k). В результате умножения G(x) на степени каждого одночлена, входящего в G(x), повысится на (n - k). При делении произведения G(x) на образующий полином Р(х) получится частное Q(x) такой же степени, как и G(x).

Результат умножения и деления можно представить в следующем виде:

(4),

где R(x)- остаток от деления G(x) на Р(х).

Так как частное Q(x) имеет такую же степень, как и кодовая комбинация G(x), то Q(x) также является комбинацией простого к- значного кода.

Умножая обе части равенства (4) на Р(х) и произведения некоторые перестановки, получим

(5)

В правой части (5) знак минус перед R(x) заменен знаком плюс, так как вычитание по модулю два сводится к сложению.

Таким образом, кодовая комбинация циклического (n, k)- кода может быть получен двумя способами:

1) путем умножения простой кодовой комбинации степени (k - 1) на одночлен и добавления к этому произведению остаток, полученного от деления произведения на образующий полином Р(х) степени (n - k);

2) путем умножения простой кодовой комбинации степени (k - 1) на образующий полином Р(х) степени (n - k).

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

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

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

Для формирования строк производящей матрицы по первому способу образование циклического кода берут комбинации простого К-разрядного кода G(x), содержащие единицу в одном разряде. Эти комбинации умножаются на , определяется остаток R(x) от деления получено произведения G(x) на образующий полином и записывается соответствующая строка матрицы в виде суммы произведения G(x) и остаток R(x). При этом производящая матрица представляется двумя подматрицами - информационной и дополнительной :

.

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

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

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

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

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

Окончательно производящая подматрица имеет вид

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

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

Как уже отмечалось раннее, степень образующего полинома должна быть равна числу проверочных разрядов р.

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

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

Известно, что двучлен типа , в разложении которого в качестве сомножителя должен входить образующий многочлен, обладает тем свойством, что он является общим кратным для всех без исключения неприводимых полиномов степени z и разлагается на множители из всех неприводимых полиномов, степени которых делится без остатка число z.

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

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

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

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

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

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

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

(6)

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

(7)

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

В таблице приведены наибольшие значение К и n для различных р.

Поскольку образующий многочлен Р(х) должен входить в качестве сомножителя в разложении двучлена , то, используется отмеченные ранее свойства этого двучлена, а также условие (7), можно выбрать образующий полином.

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

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

В соответствии с таблицей определяем общее количество символов n = 7 и количество проверочных символов р =3.

Образующий полином Р(х) должен быть степени р = 3 и входить в качестве сомножителя в разложении двучлена Так как n = 7, то составляющие сомножители двучлена должны быть неприводимыми полиномами, степени которых являются делителями числа z = 3. К числам, на которые z = 3 делится без остатка, относятся 1 и 3. Следовательно, сомножителями двучлена должны быть неприводимые полиномы первой и третьей степеней.

Пользуясь таблицами неприводимых полиномов.

.

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

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

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

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

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

Однако код, построенный таким образом, является неоптимальным с точки зрения числа избыточных символов. В этом отношении более совершен код Боуза - Чоудхури, обеспечивающий минимальное число проверочных символов при заданном К. математическая структура этого кода несколько отлична от рассмотренной ранее и характеризуется более сложными устройствами для обнаружения и исправления ошибок. Особенностью этого кода является то, что для любых положительных чисел z и существует циклический код знатности с кодовым расстоянием .

При этом число проверочных символов р не превышает величины , т. е. . Такой код гарантийно исправляет ошибки кратности не более . Кроме того, код обнаруживает все пачки ошибок, длина которых равна или меньше р.

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

Наиболее известным из этой группы кодов является код Файра.

Образующий полином данного кода имеет вид

 , (8)

где q(х)- неприводимый многочлен степени t, принадлежащий показателю степени

(9)

А число с есть некоторое постоянное число, которое не должно делится на m.

Число проверочных символов равно с +t., а общее число символов в кодовой комбинации равно наименьшему общему кратному чисел с и m.

С помощью кодов Файра можно исправить одиночную пачку ошибок длины b или меньше и одновременно обнаружить пачку ошибок длинны t b или меньше, если

b + l - 1 c;

b m. (10)

Если применить эти коды только для обнаружения ошибок, то они позволяют обнаружить любую комбинацию из двух пачек не превосходит с+1, а также любую одиночную пачку ошибок с длинной , не превосходящей числа проверочных символов р = с + t.