Синдром ошибки в циклическом коде

6. Исправление ошибок с помощью циклических кодов

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

Поскольку циклические коды являются линейными, то процесс обнаружения и исправления ошибок связан с нахождением синдрома принятого вектора. Напомним, что синдром вектора uвычисляется как произведение вектора на транспонированную проверочную матрицу кода, т. е. su= uHT. В случае циклического кода синдром равен остатку от деления соответствующего многочлена на порождающий многочлен кода, если проверочная матрица строится определенным образом. Иными словами, если g(x) – порождающий многочлен кода, то синдром вектора u равен остатку от деления u(x) на g(x). Если ошибок не было, то остаток, а следовательно, и синдром принятого вектора, равен 0.

Для того чтобы произвести исправление ошибок нам необходимо построить таблицу, в которой в одном столбце будут все возможные векторы ошибок, которые данный код может исправить, а во втором столбце – соответствующие им синдромы. Исправление ошибок, общее для всех линейных кодов, будет следующим:

1.   Для принятого слова находим синдром многочлена, соответствующего принятому слову.

2.   Если синдром не равен 0, то по полученному синдрому (остатку от деления) находим в таблице соответствующий ему вектор ошибок.

3.   Исправляем принятое слово путем сложения по модулю 2 с вычисленным вектором ошибок.

Первый шаг, который выполняется умножением принятого слова на транспонированную проверочную матрицу, для циклических кодов очень простой, если матрица H является проверочной матрицей систематического кода. В этом случае, j-я строка транспонированной матрицы HT соответствует остатку от деления многочлена xn-1-j на порождающий многочлен кода, и синдром равен остатку от деления многочлена, соответствующего принятому слову, на порождающий многочлен кода.

Пример: Рассмотрим циклический (7,1)-код, порожденный многочленом g(x) = x6 +x5 +x4 +x3 + x2 +x +1. Код состоит из двух слов 0000000 и 1111111 и исправляет все комбинации из 3 или менее ошибок. Образующими являются все булевы векторы длины 7 веса 0, 1, 2 и 3. Проверочная матрица строится по частному (x +1) от деления x7 +1 на x6 +x5 +x4 +x3 + x2 +x +1 и имеет вид

Пусть принято слово 11101101, которое соответствует многочлену x6 +x5 +x4 + x2 + 1. Остаток от деления этого многочлена на порождающий многочлен кода равен x3 + x. Непосредственной проверкой можно убедиться, что при умножении вектора u = 1110101 на транспонированную матрицу HT, так же как и при умножении вектора 0001010 на HT получается вектор 0001010, который соответствует многочлену x3 + x. Вектор, соответствующий многочлену x3 + x, имеет вес 2, т. е. является образующим смежного класса. Сложив принятый вектор 11101101 с образующим 0001010, мы получим кодовое слово 1111111, т. е. ошибка будет исправлена.

Для линейных кодов число различных синдромов равно 2n–k, где n–k – число проверочных символов. Поэтому для кодов с большой длиной кодового слова, т. е. с достаточно большим числом проверочных символов, таблица синдромов получается очень большая, и потребуется много времени на поиск вектора ошибок. Для уменьшения количества строк в этой таблице для циклических кодов можно воспользоваться строгой математической структурой таких кодов. Основной теоремой является теорема Мегитта, которая устанавливает связь между циклическими сдвигами вектора и их остатками от деления на порождающий многочлен кода.

Теорема 6.1. (Меггит). Пусть s – синдром вектора u длины n. Синдром циклического сдвига вектора u совпадает с синдромом вектора, соответствующего полиному xs(x).

Пример: Рассмотрим (7,4)-код Хэмминга, который является циклическим кодом, порожденным многочленом g(x) = x3 + x+ 1. двоичный вектор 1011000 является кодовым словом, так  как соответствующий многочлен x6 + x4 + x3 делится на g(x). Предположим, что при передаче этого кодового слова произошла одна ошибка в разряде, соответствующем x4, и принято слово           u = 1001000. Синдром s принятого вектора равен 110, что соответствует многочлену x2 + x.

Рассмотрим циклический сдвиг 0010001 вектора u. Ему соответствует многочлен x4 + 1. Непосредственной проверкой можно убедиться, что остаток от деления многочленаx4 + 1 на многочлен x3 + x+ 1 равен x2 + x+ 1, т. е. синдром вектора 0010001 равен 111. Остаток от деления полинома xs(x) = x3 + x2  на   x3 + x+ 1 также равен x2 + x+ 1.

Используя теорему Мегитта, в таблице синдромов можно хранить только синдромы векторов ошибок, соответствующие ошибкам в старшем разряде. Процедура исправления ошибок содержит следующие шаги:

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

2.     Если остаток совпал с одним из синдромов таблицы, то прибавляем соответствующий вектор ошибок к принятому слову, делим полученное слово на порождающий многочлен кода; частное от деления есть искомое информационное слово. Если остаток xs(x) не совпадает ни с одним из синдромов таблицы, умножаем s(x) наx и делим многочлен xs(x) на порождающий многочлен кода.

3.     Выполняем Шаг 2 до тех пор, пока после p шагов остаток не совпадет с одним из синдромов таблицы. После этого циклически сдвигаем соответствующий вектор ошибок p раз, прибавляем полученный вектор к принятому слову, делим полученное слово на порождающий многочлен кода; частное от деления есть искомое информационное слово.

Пример: Рассмотрим циклический (7,4)-код Хэмминга, порожденным многочленом g(x) = x3 + x+ 1. Соответствующая таблица декодирования с синдромами имеет следующий вид.

Данный код исправляет одну ошибку. Чтобы проиллюстрировать работу декодера Мегитта, оставим в таблице один класс

и предположим, что в переданном кодовом слове 0001011 произошла одна ошибка, т. е. принято, например, слово 0101011, которому соответствует многочлен x5 + x3 + x+ 1. Остаток от деления многочлена x5 + x3 + x+ 1 на порождающий многочлен кода g(x) = x3 + x+ 1 равен x2 + x+ 1, т. е. синдром принятого вектора отличен от 0 и равен 111. Такого синдрома в таблице нет, и следовательно, в старшем разряде ошибок нет. Умножаем многочлен x2 + x + 1, соответствующий синдрому 111, на x и делим полученный многочлен x3 + x2 + xна g(x). Остаток от деления многочлена x3 + x2 + x на x3 + x+ 1 равен x2 + 1, т. е. синдром 101, соответствующий остатку, совпадает с синдромом в сокращенной таблице декодирования. Соответственно, образующий 100000 смежного класса сдвигается на один разряд влево, и полученный вектор 0100000 складывается с принятым вектором 0101011. В результате получается слово 0001011, которое и является переданным кодовым словом, т. е. ошибка будет исправлена.

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