В информационных системах обмен сообщениями в сетях связи или вычислительных сопровождается возмущающими воздействиями среды или нарушителя, что приводит к появлению искажений сигналов и к ошибкам в символах при цифровой передаче. Борьбу с этим явлением ведут, используя корректирующие коды. Ранее я описывал код Хемминга, и показал как исправляется одиночная ошибка в кодовом слове. Естественно возник вопрос и о ситуациях с большим количеством ошибок. Сегодня рассмотрим случай двух ошибок в кодовом слове (кратную ошибку). С одной стороны, все в теории более менее просто и понятно, но с другой — совершенно не очевидно. Изложение материала выполнено на основе работ Э. Берлекемпа.
Теоретические положения
Идея использования организованной избыточности в сообщениях привела Р. Хемминга к построению корректирующего кода описанного здесь. Линейный корректирующий (n, k)-код характеризуется проверочной (m×n) матрицей H. Требования к матрице просты: число строк совпадает с числом проверочных символов, ее столбцы должны быть отличны от нулевого и все различны. Более того, значения столбцов описывают номера позиций, занимаемых в кодовом слове символами слова, являющимися элементами конечного поля.
Часто для установления ошибочности переданного слова декодер использует вычисление синдрома, вычисляемого для этого слова. Синдром равен сумме столбцов этой матрицы, умноженных на компоненты вектора ошибки. Если в H имеется m строк и код позволяет исправлять одиночные ошибки, то длина блока (кодового слова) не превышает
. Важна также выполнимость требуемой удаленности кодовых слов друг от друга.Коды Хемминга достигают этой границы. Каждая позиция кодового слова кода Хемминга может быть занумерована двоичным вектором, совпадающим с соответствующим столбцом матрицы H. При этом синдром будет совпадать непосредственно с номером позиции, в которой произошла ошибка (если она только одна) или с двоичной суммой номеров (если ошибок несколько).
Идея векторной нумерации весьма плодотворна. Далее будем полагать
и, что i-я позиция слова занумерована числом i.Нумерацию в двоичном виде,(т.е. такое представление) называют локатором позиции. Допустим, что требуется исправлять все двойные и одиночные ошибки. Видимо, для этого потребуется большая избыточность кода, т.е. матрица H должна иметь больше строк (вдвое большое число). Поэтому будем формировать матрицу H с 2m строками и с
столбцами, и эти столбцы разумно выбирать различными. В качестве первых m строк будем брать прежнюю матрицу кода Хемминга. Это базисные векторы-слова пространства слов.Пример 1
Пусть m = 5 и n = 31. Желательно было бы получить (n, k)-код, исправляющий двойные ошибки, с проверочной матрицей Н в виде:
Для обозначенных в матрице функций fj(ξ) желательно иметь функцию, которая отображала бы множество 5-мерных векторов в себя. Последние 5 строк матрицы будут задавать код Хемминга тогда и только тогда, когда функция f является биекцией (перестановкой).
Если первые 5 строк и последние 5 строк в отдельности позволят исправлять одиночные ошибки, то возможно совместно они позволят исправлять две ошибки.
Мы должны научиться складывать, вычитать, умножать и делить двоичные 5-ти мерные векторы, представлять их многочленами степени не выше 4-ой, чтобы находить требуемую функцию fj(ξ).
Пример 2
00000 ←→ 0
00010 ←→ 1
00011 ←→ х
…
Сумма и разность таких многочленов соответствует сумме и разности векторов:
0 ± 0 = 0, 0 ± 1 = 1, 1 ± 0 = 1, 1 ± 1 = 0, знаки ± имеют в двоичном случае совпадающий смысл. Не так с умножением, показатель степени результата умножения может превысить 4.
Пример 3
.Необходим метод понижения степеней больше 4.
Он называется (редукцией) построением вычетов по модулю неприводимого многочлена M(x) степени 5; метод состоит в переходе от многочленов произведений к их остаткам от деления на
Так что
или 
Символ ≡ читается «сравнимо с».
В общем виде A(x) ≡a(x)mod M(x)
Тогда и только тогда, когда существует такой многочлен C(x), что
A(x)= M(x)C(x) +a(x) коэффициенты многочленов приводятся по модулю два:
A(x) ≡ a(x)mod(2,M(x)).
Важные свойства сравнений
Если а(x) ≡А(x)mod M(x) и b(x) ≡ B(x)mod M(x), то
а(x) ± b(x) ≡ А(x) ± B(x)mod M(x) и
а(x)·b(x) ≡ А(x)·B(x)mod M(x).
Более того, если степени многочленов а(х) и А(х) меньше степени М(х), то из формулы
а(x) ≡ А(x)mod(2,M(x)) следует, что а(x) = А(x).
Различных классов вычетов существует 2 в степени degM(x) – т.е. столько, сколько существует различных многочленов степени, меньшей m, т.е. сколько может быть различных остатков при делении. С делением еще больше сложностей.
Алгоритм деления
Для чисел.
Для данных a и M существуют однозначно определенные числа q и A, такие, что а =qM + A, 0 ≤ A ≤ M,
Для многочленов с коэффициентами из данного поля.
Для данных a(x) и M(x) существуют однозначно определенные многочлены q(x) и A(x), такие, что a(x) = q(x)M(x) + A(x), degA(x) <deg M(x).
Возможность деления многочленов обеспечивается алгоритмом Евклида.
Для чисел пример расширенного НОД описан здесь.
Для заданных a и b существуют такие числа A и B, что aA +bB = (a,b), где (a,b) – НОД чисел a и b.
Для многочленов с коэффициентами из данного поля.
Для заданных a(x) и b(x) существуют такие многочлены A(x) и B(x), что
a(x)A(x) + b(x)B(x) = (a(x), b(x)),
где (a(x), b(x)) — нормированный общий делитель a(x) и b(x) наибольшей степени.
Если а(х) и М(х) имеют общий делитель d(x) ≠ 1, то деление на a(x) по mod M(x) не всегда возможно.
Очевидно, что деление на a(x) эквивалентно умножению на A(x).
Так как если (a(x), b(x))= 1 =НОД, то согласно алгоритму Евклида, существуют такие A(x) и B(x), что a(x)A(x) + b(x)B(x) = 1, так, что a(x)A(x) ≡ 1mod b(x). Проверка того, что двоичный многочлен является неприводимым над полем GF (
), выполняется непосредственным делением на всевозможные делители со степенями, меньшими, чем deg M(x).Пример 4.
делим на х и на (х + 1)на линейные делители. Результат деления не нуль. Делим на квадратные делители
. Они выдают остатки, не равные нулю. Делителей степени ≥ 3 не существует, так как их произведение дает степень ≥ 6.Таким образом, многочлены можно складывать, вычитать, умножать и делить по модулю
.Переходим к поиску функции для проверочной матрицы H, задающей код с исправлением двойных ошибок с блоковой длиной 31 и скоростью 21/31; 31-21=10 =2t – проверочных символов = 10. Такая функция должна иметь своими корнями номера ошибочных позиций в кодовом слове, т.е. при подстановке в эту функцию номеров позиций, обращает ее в нуль.
Поиск функции
Предположим, что β1 и β2 — номера искаженных символов (позиций) слова. Используя двоичную запись чисел β1 и β2 можно представить эти номера в виде классов вычетов по модулю M(x) т.е. установить соответствие βi → β(i)(x) — двоичные многочлены степени < 5.
Первые 5 проверочных условий определяют β1 + β2; второе множество проверочных уравнений должны определять f(β1) + f(β2).
Декодер должен определить β1 и β2 по заданной системе:
Какой же должна быть функция f(x)?
Простейшая функция – это умножение на константу f(β)≡ αβ(х)modM(x).
Но тогда ξ2 = αξ1, т.е. уравнения системы зависимы. Новая пятерка проверочных условий декодеру не даст ничего нового.
Аналогично и функция f(β) = β + α не изменяет ситуацию, так как ξ2 = ξ1.
Пробуем степенные функции: сначала возьмем
. При этом 
Эти уравнения также зависимы, так как
Таким образом, второе уравнение является квадратом первого.
Пробуем
. Уравнения декодера меняют вид: 
Откуда
Так что при ξ1≠0 имеем
Значит, β1 и β2 удовлетворяют уравнению
Таким образом, если произошло точно две ошибки, то их локаторы удовлетворяют этому уравнению.
Так как в поле двоичных многочленов по модулю M(x) данное уравнение имеет точно 2 корня, то декодер всегда сможет найти два нужных локатора.
Если произошла только одна ошибка, то β1=ξ1 и
. Следовательно, в этом случае единственная ошибка удовлетворяет уравнению β + ξ1 = 0 или 1+ ξ1β-1= 0.Наконец, декодер всегда производит декодирование, если ошибок не произошло, то в этом случае ξ1 + ξ2 = 0 .
Более удобно (на практике) оперировать не непосредственно с многочленом, корнями которого являются локаторы ошибок, а с многочленом, корни которого взаимны к локаторам; т.е. являются к ним мультипликативным обратными величинами.
Ясно, что при не более чем двух ошибках декодер может определить номера ошибок. Если же искажаются три или более символов, то произойдет ошибка декодирования или отказ от декодирования.
Таким образом, функция
подходит для построения нижних пяти строк проверочной матрицы Н двоичного кода с длиной кодовых слов 31 и 10-ю проверочными символами, исправляющего все двойные ошибки.Первые пять проверок задают сумму номеров ошибок (S1); вторые пять проверок задают сумму кубов номеров ошибок (S3).
Процедура декодирования состоит из трех основных шагов:
- каждое полученное кодовое слово проверяется и вычисляются S1 и S3;
- находится многочлен локаторов ошибок от σ(z);
- вычисляются взаимные величины для корней σ(z) и изменяются символы в соответствующих позициях полученного слова.
