Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

8. Циклические коды, исправляющие две ошибки

Пусть m ≥ 2, n = 2m - 1, и a - примитивный элемент поля GF(2m). Построим циклический код, состоящий из всех многочленов степени меньше n, корнями которых являются элементы a и a3 (в расширении GF(2m)). Покажем, что такой код исправляет любую комбинацию из двух или менее ошибок.

Пусть v(x) - многочлен, соответствующий кодовому слову v, т. е. a и  a3 суть корни многочлена v(x). Пусть, кроме того, при передаче слова произошли ошибки (не более двух), и принят вектор u, которому соответствует многочлен u(x). Как обычно, обозначим через e(x) = v(x) + u(x) вектор ошибок. Поскольку могли произойти две или менее ошибок, то многочлен e(x) имеет не более двух слагаемых с ненулевыми коэффициентами, т. е. e(x) = xi + xj. Таким образом, для того, чтобы исправить ошибки достаточно найти значения i и j.

Так как a - примитивный  элемент поля GF(2m), то различные степени элемента a можно использовать для маркировки n = 2m - 1 разрядов в принятом слове. Обозначим x1 = ai и x2 = aj. Наша задача заключается в нахождении значений неизвестных x1 и x2 по принятому вектору u. По определению, u(a) = v(a) + e(a), и так как v(a) = 0, то u(a) = e(a) = x1 + x2. Обозначив u(a) через s1, мы получаем первое уравнение системы:

x1 + x2 = s1.

Аналогично, можно вычислить значение полинома u(x) в точке a3: u(a3) = e(a3) = (a3)i + (a3)j = (ai)3 + (aj)3 = x13 + x23. Обозначив u(a3) через s3, мы получаем второе уравнение системы:

x13 + x23 = s3.

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

По теореме Виета, сумма корней квадратного трехчлена равна коэффициенту при переменной x, а произведение корней равно свободному члену. Иными словами, если X1 и X2 - корни квадратного трехчлена, то сам трехчлен имеет вид: x2 + (X1 + X2) x + X1X2. Согласно первому уравнению системы, X1 + X2 = s1. Вычислим значение s13 + s3:

s12 = (X1 + X2)2 = X12 + X22,

так  как в двоичной математике (a + b) 2 = a2 + b2. Следовательно,

s13 = X13 + X2 3 + X12 X2 + X1 X22 = X13 + X2 3 + X1 X2 (X1 + X2) =

s3 + X1 X2 s1.

Поэтому X1 × X2 = (s13 + s3) s1-1. Как следствие мы получаем, что корни системы

совпадают с корнями квадратного трехчлена s(x) = x2 + s1 x + (s13 + s3) s1-1.

Пример: Рассмотрим (7, 1)-код, порожденный многочленом x6 + x5 + x4 + x3 + x2+ x + 1. Представим элементы поля числами 0, 1, ..., 7, где позиционный код каждого числа представляет коэффициенты соответствующего многочлена, т. е., например, элемент 3 соответствует классу вычетов с представителем [x+1] и т. п. Непосредственной проверкой можно убедиться, что a = 2 (класс вычетов [x] по модулю неприводимого многочлена x3 + x + 1 с представителем x) является примитивным элементом поля Галуа GF(23), и элементы a = 2 ([x]) и a3 = 3 ([x+1]) суть корни многочлена x6 + x5 + x4 + x3 + x2+ x + 1 в данном поле. Таким образом, данный код исправляет любую комбинацию из двух или менее ошибок. Пусть в переданном слове 1111111 произошли две ошибки и принято слово 1011011, т. е. ошибки произошли во втором и пятом разрядах и принятому слову соответствует многочлен u(x) = x6 + x4 + x3 + x + 1. Находим значения данного многочлена в точках a = 2 и a3  = 3, используя таблицу умножения и сложения в поле GF(23). Напомним, что данное поле построено как множество классов вычетов по модулю неприводимого многочлена x3 + x + 1, т. е.   21 = 2; 22 = 4; 23 = 3; 24 = 6; 25 = 7; 26 = 5; 27 = 1. Таким образом, s1  = u(2) = 26 + 24 + 23 + 2 + 1 = 5 + 6 + 3 + 2 + 1 = 3, s3  = u(3) = 36 + 34 + 33 + 3 + 1 = 218 + 212 + 29 + 3 + 1 = 24 + 25 + 22 + 2 + 1 = 6 + 7 + 4 + 3 + 1 = 7. Соответственно, мы получаем квадратный трехчлен s(x) = x2 + s1 x + (s13 + s3) s1-1 = x2 + 3x + (33 + 7)3-1 = x2 + 3x + (22 + 7)24 = x2 + 3x + 23×24 = x2 + 3x + 1. Непосредственной проверкой можно убедиться, что 42 + 3×4 + 1 = 24 + 23×22 + 1 = 6 + 7 + 1 = 0 и 72 + 3×7 + 1 = 210 + 23×25 + 1 = 23 + 2 + 1 = 3 + 2 + 1 = 0. Таким образом, x1 = 4 и x2 = 7. Так как 4 = 22 и 7 = 25, то ошибки произошли во втором и пятом разрядах.