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

Акимов О.Е.

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

Корректирующие коды

Рассмотрим вопрос, как используется теория полей многочленов для защиты информации от помех в канале связи. Считается, что помехи в канале связи действуют независимо и мы не в состоянии повлиять на случайное изменение нуля на единицу, и наоборот; мы можем лишь на выходе канала связи исправить кодовое слово, восстановив его первоначальную форму. С этой целью и используются специальные корректирующие коды, которые основываются на введении информационной избыточности. При корректирующем кодировании в каждое кодовое слово, помимо информационных символов, вводят проверочные, или корректирующие. Например, можно ввести лишь один корректирующий символ в конце информационного слова, для которого определить: 0 — число единиц в кодовом слове четно и 1 — число единиц в кодовом слове нечетно. Если принятое кодовое число имеет четное число единиц, а корректирующий символ равен 1, то в канале связи произошел сбой.

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

Информационное сообщение a = a₀a₁ ... a_k–1 будем записывать с помощью многочлена:

a(x) = a₀ + a₁x + a₂x² + ... + a_{k – 1} x^k–1.

Если многочлен a(x) умножить на x^m, то символы, составляющие сообщение, будут коэффициентами при более высоких степеях. Далее, a(x)x^m разделим на примитивный многочлен g(x), тем самым, найдя частное от деления p(x) и остаток r(x). Зашифрованное информационное слово определится многочленом:

f (x) = a(x)x^m – r(x) = g(x)p(x),

степень которого равна n = k + m. Кодовое слово f будет состоять из k информационных и m проверочных символов. В случае, когда полученное слово f ' совпадает с переданным словом f, то при делении многочлена f ' (x) на g(x) получается нулевой остаток r(x). Но если остаток отличен от нуля, то в канале связи произошел сбой:

f ' (x) = g(x)p(x) + r(x),     где r(x) ≠ 0.

Пусть a = 1001, k = 4, m = 3, n = 7, g(x) = 1 + x + x³ — примитивный многочлен. Найдем многочлен f (x), отвечающий коду a: 

a(x) = 1 + x³;     x³a(x) = g(x)p(x) + r(x) = 

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

f (x) = x + x² + x³ + x⁶;     f = 011 1001.

В кодовом слове f первые три символа 011 являются проверочными, последние четыре 1001 — информационными. Пусть при передаче f произошел сбой, и мы приняли слово f ' = 011 1011. При делении многочлена f ' (x) на g(x) получаем остаток r(x) = 1 + x + x², что соответствует коду ошибки r = 111. Если сбой произойдет не в шестом символе, а в любом другом месте, то код ошибки изменится.

Существует несколько иной способ кодирования и декодирования информации, а именно, при шифровке многочлен информационного слова a(x) умножается на порождающий многочлен g(x); так получается многочлен f (x). При дешифровке кодовый многочлен f (x) умножается на проверочный h(x), в результате получим:

A(x) = f (x)h(x) = a(x)g(x)h(x) = a(x)(xⁿ + 1) = a(x)s(x)a(x),

где s(x) — синдром ошибки, исполняющий роль кода ошибки: s = r. При такой форме кодирования при том же информационном слове и порождающем многочлене, что и в предыдущем случае, сформируется другой кодовый многочлен:

f (x) = (1 + x³)(1 + x + x³) = 1 + x + x⁴ + x⁶,    f = 1100101.

В процессе декодирования получим нулевой синдром:

A(x) = f (x)h(x) = (1 + x + x⁴ + x⁶)( 1 + x + x² + x⁴) = 

= 1 + x³ + x⁷ + x¹⁰;

A = asa = 1001 000 1001;     s = 000.

Пусть произошел сбой и было получено слово f ' = 1100001; тогда в результате декодирования возникнет набор: A' = 1001 111 1101 с синдромом ошибки s = 111.

Вместо многочленов можно использовать матрицы. Чтобы получить кодовое слово f, нужно информационное слово a умножить на порождающую матрицу G, т.е. f = aG. Так, если a = 011 — информационное слово из k = 3 символов и задана порождающая матрица G размерности 3 · 5, то кодовое слово f будет состоять из n = 5 символов, из которых два последних (m = 2) являются проверочными:

f = aG = (011) = 01110.