Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

2.4. Алгебраические системы на базе групп

Примеры корректирующих кодов

Для задания циклического кода достаточно указать всего лишь один порождающий многочлен g(x), а для задания линейного кода C нужно задать список базисных кодовых векторов, в роли которых, как мы убедились, могут выступать кодовые многочлены f(x). Линейный код C является циклическим только тогда, когда C — идеал в кольце многочленов P_n(x) (понятие идеала мы ввели в предыдущем подразделе). Во всяком идеале C существует порождающий многочлен g(x), которому кратен всякий многочлен идеала C. Если C — идеал, то для всякого кодового многочлена f(x) можно получить циклические сдвиги xf (x), x²f (x), x³f (x) ... ∈ C, т.е. сдвиги снова являются кодовыми многочленами. И обратно, если C — циклический код, то для всякого кодового многочлена f (x) его сдвиги будут кодовыми многочленами.

Рассмотренные кодовые слова суть векторы линейного пространства G над полем Галуа GF(q). Если выразиться точнее, то G является лишь подпространством пространства E, поскольку у него имеется ортогональное дополнение H:

E = ,

здесь символ «звездочка» означает транспонирование.

Если f есть n-мерный кодовый вектор, полученный из информационного слова a с помощью порождающей матрицы G, то произведение fH* = aGH* = 0, т.е. H* переводит любой вектор f из линейного пространства G в нулевой вектор; если же попадется такой вектор f ', который не будет принадлежать линейному пространству G, то матрица H* уже не сможет перевести его в нулевой вектор, сигнализируя нам об этом соответствующим синдромом s.

Примером классического линейного кода является код Хэмминга (n, k), для которого выполняется условие: n = 2^m – 1. Согласно этому условию, будем иметь следующие коды Хэмминга —

в поле GF(2): (7, 4), (15, 11), (31, 26), (63, 57), (127, 120) ... ;

в поле GF(2²): (5, 3), (21, 18), (85, 81), (341, 336), ... ;

в поле GF(2³): (9, 7), (73, 70), (585, 581), ... ;

в поле GF(2⁴): (17, 15), (273, 270) ... .

Существует код Хэмминга (13, 10) над полем GF(3) с проверочной матрицей

H = ,

по которой нетрудно найти порождающую матрицу G. Существуют различные модификации кодов Хэмминга, в частности, из кода (n, k) можно получить код (n + 1, k), который способен исправлять одинарную ошибку и обнаруживать двойную. Так, для модифицированного кода Хэмминга (8, 4) проверочной матрицей служит

H = .

Тогда к трем вышеприведенным проверочным соотношениям добавится еще одно:

s₄ = h₇ + h₆ + h₅ + h₄ + h₃ + h₂ + h₁ + h₀ = 0.

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

Код Хэмминга (7, 4) уже рассматривался; было показано, что он может быть преобразован в циклический код с ленточной матрицей G, образованной порождающим многочленом g(x) = 1 + x2 + x³. Для кодирования информации и исправления сразу нескольких ошибок Боуз, Чоудхури и Хиквингем (сокращенно БЧХ) предложили использовать сразу несколько порождающих многочленов g_i(x). Порождающий многочлен БЧХ-кода можно представить в виде

g(x) = НОК[g₁(x), g₂(x), g₃(x), ... , g_2t (x)],

где g_i(x) — неприводимые многочлены, t — число исправленных ошибок. Так, для исправления двух ошибок (t = 2) с длиной кодового слова n = 2⁴ – 1 = 15 получим следующий многочлен:

g(x) = НОК[g₁(x), g₂(x), g₃(x), g₄(x)] =

= НОК[x⁴ + x + 1, x⁴ + x + 1, x⁴ + x³ + x² + x + 1, x⁴ + x + 1] =

= (x⁴ + x + 1)( x⁴ + x³ + x² + x + 1) = x⁸ + x⁷ + x⁶ + x⁴ + 1,

здесь m = 8, k = 7, т.е. мы получили корректирующий БЧХ-код (15, 7), одновременно исправляющий два любых сбоя в канале связи при передаче N = 2^k = 128 сообщений. Неприводимые многочлены g₁(x), g₂(x), g₃(x) и g₄(x) предварительно были нами найдены и теперь только взяты из табл. 2.82.

Для исправления трех ошибок (t = 3) имеем:

g(x) = НОК[g₁(x), g₂(x), g₃(x), g₄(x), g₅(x), g₆(x)] =

= (x⁴ + x + 1)( x⁴ + x³ + x² + x + 1)( x² + x + 1) =

= x¹⁰ + x⁸ + x⁵ + x⁴ + x² + x + 1,

который дает (15, 5) БЧХ-код. При t = 4, 5, 6, 7 будем иметь одинаковые порождающие многочлены g(x), отличающиеся от x¹⁵ + 1 на множитель x + 1, а от предыдущего случая на множитель x⁴ + x³ + 1:

x¹⁴ + x¹³ + x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1.

Этот БЧХ-код (15, 1) способен нести лишь один бит информации.

Таблица 2.89

Аналогичным образом мы можем найти порождающие многочлены для других БЧХ-кодов. Воспользовавшись полными таблицами неприводимых многочленов (табл. 2.83 – табл. 2.86), можно исправить до 32 одновременно произошедших ошибок (табл. 2.86). Любопытно сравнить помехозащищенность БЧХ-кода над полем многочленов GF(2⁴) (табл. 2.82) и GF(4²) (табл. 2.89). Порождающий многочлен для исправления одиночной ошибки в поле GF(4²), кажется, принципиально ничем не отличается от порождающего многочлена в поле GF(2⁴):

g(x) = НОК[g₁(x), g₂(x)] =

= (x² + x + 2)( x² + x + 3) = x⁴ + 2x³ + 2x² + x + 3,

который тоже дает код (15, 11). Порождающий многочлен для исправления двух ошибок для GF(2⁴) был g(x) = x⁸ + x⁷ + x⁶ + x⁴ + 1, что давал код (15, 7); для GF(4²) будем иметь уже код (15, 9):

g(x) = НОК[g₁(x), g₂(x), g₃(x), g₄(x)] =

= (x² + x + 2)( x² + x + 3)( x² + 3x + 1) =

= x⁶ + 3x⁵ + x⁴ + x³ + 2x² + 2x + 1.

Степень многочлена g(x) получилась на два порядка ниже, а это значит, что данный код при той же помехозащищенности имеет преимущество: из 15 символов, отведенных на каждое кодовое слово, у него, вместо 7, будет уже 9 информационных символов, причем каждый символ принимает значения не 0 и 1, а 0, 1, 2 и 3.