Методическое пособие 640

Из последнего примера следует, что при циклическом сдвиге вправо на один разряд необходимо исходную кодовую комбинацию поделить на X, а умножение на X эквивалентно сдвигу влево наодин символ.

Установив операции сложения полиномов и умножения полинома на скаляр, можно сказать, что множество полиномов U(z) кодовых слов обладает структурой векторного пространства и для него справедливы утверждения:

–если u(z), v(z) U(z), то u(z) v(z) U(z);

–если u(z) U(z), GF(q), то u(z) U(z).

Рассмотрим некоторые определения, связанные с полиномиальным представлением кодовых слов. Пусть имеется многочлен a(z) am 1zm 1 am 2zm 2 a1z a0 .

Приведенным (или нормированным) полиномом называ-

ется полином, старший коэффициент которого am 1 1.

Нулевым многочленом называется многочлен a(z) 0. Степенью ненулевого полинома a(z) называется

наибольшая степень формальной переменной z при ненулевом коэффициенте ai и обозначается как deg a(z).

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

211

a qd r, 0 r d ,

где неотрицательное целое r, меньшее d , называется остатком (от деления a на d ), q называется частным от деления, a

– делимым, а d – делителем. Поскольку в кольце полиномов определена операция умножения, то, поступая аналогично,

можно ввести операцию деления полиномов с остатком. Одна-

ко, для полиномов сравнение в терминах «больше–меньше» невозможно, поэтому для получения остатка сравниваются степени полиномов. Возьмем полином d(z) и представим произвольный полином a(z) как

a(z) q(z)d(z) r(z), degr(z) degd(z). (7.21)

Всоотношении (7.21), возможном для любых a(z) и d(z)

,назовем полиномы a(z), d(z), q(z) и r(z) делимым, делите-

лем, частным и остатком соответственно. Операция деления полиномов в соответствие с (7.21) известна под названием ал-

горитма Евклида.

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

a(z) r(z)mod d(z),

которая символизирует, что полиномы a(z) и r(z) имеют один и тот же остаток от деления на d(z). Действительно, согласно (7.21), r(z) является остатком от деления a(z) на d(z). С другой стороны, поскольку degr(z) degd(z), то r(z) сразу же является остатком от деления на d(z).

Если в (7.21) r(z) 0, т.е. a(z) d(z)q(z) 0modd(z), то говорят, что a(z) делится на d(z), или d(z) делит a(z), или d(z) является множителем a(z). Используется также выражение, что a(z) раскладывается на множители меньшей степени.

212

Полином, который не может быть разложен на множители меньшей степени, называется неприводимым.

Наибольшим общим делителем двух полиномов a(z) и b(z), обозначаемым как НОД[a(z),b(z)], называется приведенный полином наибольшей степени, делящий одновременно оба из них.

Наименьшим общим кратным двух полиномов a(z) и b(z), обозначаемым как НОК[a(z),b(z)], называется приведенный полином наименьшей степени, делящийся на оба из них.

Если наибольший общий делитель двух полиномов равен единицы, т.е. НОД[a(z),b(z)] 1, то они называются взаимно простыми.

7.15.2. Порождающие полиномы циклических кодов

Циклические коды привлекательны по двум причинам. Во-первых, операции кодирования и вычисления синдро-

ма для них выполняются очень просто с использованием сдвиговых регистров.

Во-вторых, этим кодам присуща алгебраическая структура, и существуют простые и эффективные способы их декодирования.

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

Формирование разрешённых кодовых комбинаций ЦК Вi (X) основано на предварительном выборе так называемого порождающего (образующего) полинома G(X), который обладает важным отличительным признаком: все комбинации Вi (X) делятся на порождающий полином G(X) без остатка, т. е.

В (Х)

( )

= ( ) (при остатке ( ) = 0),

213

где Ai (X) – информативный полином (кодовая комбинация первичного кода, преобразуемого в корректирующий ЦК).

Поскольку ЦК относятся к классу блочных разделимых кодов, у которых при общем числе символов n число информационных символов в Ai (X) равно k, то степень порождающего полинома определяет число проверочных символов r = n - k.

Из этого свойства следует сравнительно простой способ формирования разрешённых кодовых комбинаций ЦК — умножение комбинаций информационного кода Ai (X) на порождающий полином G(X):

( ) = ( ) ∙ ( ).

В теории циклических кодов доказывается, что порождающими могут быть только такие полиномы, которые являются делителями двучлена (бинома) Хn+1:

+1 ( ) = ( ) (при остатке ( ) = 0). (7.22)

Некоторые из порождающих полиномов приведены в таблице 7.4.

Следует отметить, что с увеличением максимальной степени порождающих полиномов r резко увеличивается их количество. Так, при r = 3 имеется всего два полинома, а при r = 10 их уже несколько десятков.

Первый порождающий полином минимальной степени r = 1, удовлетворяющий условию (7.22), формирует код с проверкой на чётность при двух информативных символах и одном проверочном, обеспечивающем обнаружение однократной ошибки, поскольку минимальное кодовое расстояние dmin = 2. В общем случае коэффициент избыточности минимален:

== 1 ,

аотносительная скорость кода - максимальна и равна

== − 1 .

214

В связи с этим коэффициент избыточности иногда называют быстрым кодом.

Второй порождающий полином степени r=2, являющийся "партнёром" первого G(X) = Х+1 при разложении бинома с n=3, определяет код с повторением единственного информативного символа k = 1 ("0" или "1").

Отметим, что ЦК принадлежат к классу линейных кодов,

215

у которых кодовые комбинации "000...00" и "111...11" являются разрешёнными.

У кода с повторением возможности обнаружения и исправления ошибок безграничны, поскольку число повторений l определяет минимальное кодовое расстояние:

dmin = l .

В общем случае коэффициент избыточности кодов с повторением кодовых комбинаций является максимально воз-

и при увеличении l приближается к 1, а скорость - минимальна

= 1 − = 1 .

Таким образом, коды с проверкой на четность и коды с повторением – коды антиподы. Первый код очень быстр (всего один дополнительный символ), но у него низкая степень защиты. Возможности второго кода с повторением по исправлению ошибок теоретически безграничны, но он «медлителен».

Следующие полиномы в таблице 7.4 со степень r = 3 позволяют оформить набор классических кодов Хэмминга (7,4). Коды Хэмминга также принадлежат к классу ЦК, одна при этом группа проверочных символов кода получается сразу "в целом" при делении информативной кодовой группы на порождающий полином, а не "поэлементно". Отметим, что два варианта порождающих полиномов кода Хэмминга (7,4), с записью по модулю 2 в виде 1101 и 1011, представляют собой так называемые двойственные многочлены (полиномы).

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

( ) = + ∙ + ∙ + + ∙ ,

то двойственным к нему полиномом является

216

то есть весовые коэффициенты исходного полинома, зачитываемые слева направо, становятся весовыми коэффициентами двойственного полинома при считывании их справа налево. Говоря образно, набор весовых коэффициентов "вывёртывается наизнанку".

Обратим внимание на то, что в полных таблицах порождающих ЦК полиномов двойственные полиномы, как правило, не приводятся [6].

Наряду с тем, что порождающие полиномы кода Хемминга (7,4) являются двойственными друг другу, они также являются неприводимыми.

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

Далее в таблице 7.4 при значениях r = 4 и 5 попадают следующие классические коды Хэмминга (15, 11) и (31, 26). Порождающие их полиномы также являются двойственными друг к другу и неприводимыми. Напомним, что к классическим кодам Хэмминга относятся коды, у которых

n = 2 r - 1, k = 2 r - 1 - r ,

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

При значениях r = 4 в таблице 7.4 попадают двойственные порождающие многочлены кода Абрамсона (7, 3), являющиеся частным случаем кодов Файра, порождающие полиномы для которых имеют вид

где р(Х) – неприводимый полином.

Коды Абрамсона совпадают с кодами Файра, если положить с = 1. Число проверочных символов r = 4 определяет общее число символов в коде (значность кода), поскольку для этих кодов n = 2 r-1 - 1. Эти коды исправляют все одиночные и смежные двойныеошибки (т.е. серии длиной 2). Помещённые в

217

таблице 7.4 коды Абрамсона (7,3) являются первыми циклическими кодами, исправляющими серийные ошибки (пакеты ошибок). В этом применении ЦК оказываются особенно эффективными. Обратим внимание на то, что при с = 1 в (7.23) порождающими полиномами р(Х) являются двойственные полиномы X3 + Х2 + 1 и X3 + X + 1, образующие код Хэмминга

(7,4) при r = 3.

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

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

Порождающий полином G(X) бином X7 + 1 можно разложить на три неприводимых полинома

каждый из которых является порождающим для следующих кодов:

G1(X) = X + 1 - код с проверкой на чётность, КПЧ (7,6); G2(X) = X3 + Х2 + 1 - первый вариант кода Хэмминга (7,4);

G3(X) = X3 + Х + 1 - двойственный G2(X), второй вариант кода Хэмминга.

Кроме того, различные вариации произведений G1,2,3(Х) дают возможность получить остальные порождающие полино-

мы:

G4(X) = G1(X)·G2 (X) = (X + 1)·(Х3 + Х2 + 1) = X4 + Х2 + X + 1 -

код Абрамсона (7,3);

G5(X) = G1(X)·G3(X) = (X + 1)·(Х3 + Х + 1) = X4 + Х3+ X2 + 1 -

двойственный G4(X);

G6(X) = G2(X)·G3(X) = (X3 + Х2 + 1)·(Х3 + Х + 1) =

= X6 + X5 +Х4 + X3 + Х2 + X + 1 - код с повторением (7,1).

218

Таким образом, для постоянного заданного значения n все возможные порождающие полиномы ЦК размещаются между кодами с проверкой на чётность (n, n - 1) (r = 1) и кодами с повторением (n, 1) (r = n - 1), которые правомерно и называют "кодами антиподами".

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

7.15.3. Принципы формирования и обработки разрешённых кодовых комбинаций циклических кодов

Таким образом, циклические коды (ЦК) составляют множество многочленов Bi(X) степени n-1 и менее (до r = n - k, где r - число проверочных символов), кратных порождающему (образующему) полиному G(X) степени r, который, в свою очередь, должен быть делителем бинома Xn + 1, т. е. остаток после деления бинома на G(X) должен равняться нулю.

Учитывая, что ЦК принадлежат к классу линейных, групповых кодов, сформулируем ряд основных свойств, им присущих:

1. Сумма разрешённых кодовых комбинаций ЦК образует разрешённую кодовую комбинацию

2. Поскольку к числу разрешённых кодовых комбинаций ЦК относится нулевая комбинация 000...00, то минимальное кодовое расстояние dmin для ЦК определяется минимальным весом разрешённой кодовой комбинации:

3. Циклический код не обнаруживает только такие искажённые помехами кодовые комбинации, которые приводят к

219

появлению на стороне приёма других разрешённых комбинаций этого кода из набора N0.

4. Значения проверочных элементов r = n - k для ЦК могут определяться путём суммирования по mod 2 ряда определённых информационных символов кодовой комбинации Ai(X). Например, для кода Хэмминга (7,4) с порождающим полиномом G(X) = X3+X+1 алгоритм получения проверочных символов будет следующим [3]:

r1 = i1 i2 i3;

r2 = i2 i3 i4; (7.27) r3 = i1 i2 i4;

Эта процедура свидетельствует о возможности "поэлементного" получения проверочной группы для каждой кодовой комбинации Ai(X). В соответствии с (7.27) могут строиться кодирующие устройства для ЦК [3].

5.Умножение полинома на X приводит к сдвигу членов полинома на один разряд влево, а при умножении на Хr, соответственно, на r разрядов влево, с заменой r младших разрядов полинома "нулями". Умножение полинома на X свидетельствует о том, что при этой процедуре X является "оператором сдвига". Деление полинома на X приводит к соответствующему

сдвигу членов полинома исходной кодовой комбинации Ai(X), после домножения её на Хr, дописать справа r проверочных символов.

6.Поскольку разрешённые кодовые слова ЦК Bj(X) без остатка делятся на порождающий полином G(X) с получением итога в виде информационной комбинации Ai(X) (7.22), то имеется возможность формировать Bj(X) на стороне передачи (кодирующее устройство) простым методом умножения (7.22).

Два последних свойства ЦК позволяют осуществить построение кодеров ЦК двумя методами: методом умножения и методом деления полиномов. Рассмотрим достоинства и недостатки этих методов с учётом вариантов построения декодеров ЦК, соответствующих этим методам.

Метод умножения позволяет при формировании разре-

220