Определение двойной ошибки по синдрому для Реверсивного кода

Синдром ошибок в принятом сообщении х вычисляется по формуле гдеН проверочная матрица кода. Если Следовательно, сообщениесодержит ошибки.

В соответствии со структурой матрицы двоичные координаты вектора-синдрома произвольной ошибки в реверсивном коде сгруппируем последовательно в две группы по m координат в каждой. Тогда вектор можно записать в виде где s₁ и s₂ – элементы поля GF(2^m). Следовательно, s₁=aⁱ, s₂=a^j для подходящих i, j из множества Т={-¥, 0, 1, 2, ..., n-1}. Код имеет конструктивное расстояние 5 и, следовательно, исправляет двойные ошибки. Для определения координат двойной ошибки нужно решить систему уравнений

Левую часть второго уравнения приведём к общему знаменателю, то есть к виду: Легко видеть, что здесь синдром любой двойной ошибки имеет ненулевые компонентыПоэтому с учётом первого уравнения имеем:Становится ясным, что компоненты решения системыпо теореме Виета совпадают с корнями квадратного уравнения

Подбором, то есть методом Чэня находим корни этого уравнения и определяем на каких позиция принятое сообщение содержит двойную ошибку

Бчх-коды, исправляющие тройные ошибки

Примитивный двоичный БЧХ-код исправляющийслучайных ошибок, задается над полем Галуапроверочной матрицей

где фиксированный примитивный элемент поля, параметрпринимает целые значения в пределах от 0 додля. Предполагается, что каждый элемент матрицыесть двоичный столбец изэлементов 0 или 1 – координат соответствующей степеникак вектора пространстванад полемв базисеПоскольку ядром матрицыявляется весь кодненулевоемерное подпространство в двоичноммерном пространстве, то ранг матрицыпо построению равныйдолжен быть существенно меньшеТаким образом, при задании кода автоматически должно выполняться строгое неравенствоКонструктивное кодовое расстояние такого БЧХ-кодаотсюда следует мотивация обозначения данного кода через

Предположим, что мы применяем БЧХ-код , исправляющий тройные ошибки, то есть код с параметромТогда для исправления тройных ошибок необходимо решить систему

(2.7)

Для степенных сумм Ньютоном установлены рекуррентные формулы. Так для БЧХ-кода данная система линейных уравнений будет иметь вид:

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

Теорему Виета будем применять следующим образом, составим уравнение локаторов ошибок.

Алгебраические уравнения над полями Галуа , проще всего решать методом Чэня, то есть последовательной подстановкой в уравнение элементов данного поля. Найдя корни мы однозначно определяем вектор и, следовательно, исправляем принятое сообщение.

Орбиты ошибок и их свойства

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

Г-орбиты имеют четкую структуру, которую описывает

Теорема Для произвольного фиксированного вектора из пространства ошибок его Г-орбита состоит из λ элементов, гдеилиделитПри этомнаименьшее натуральное число с условиеми Г-орбитаимеет следующую структуру:. Для любых двух векторов-ошибокииз их Г-орбиты <ē> и <> либо совпадают, либо не имеют одинаковых элементов.

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

Теорема Пусть – вектор ошибок в БЧХ-коде С. Пусть - синдром ошибок вектораТогда

а для произвольного целого l синдром

.

Если же БЧХ-код задан проверочной матрицей , то

S (s())=.(3.3)

Пусть реверсивный с проверочной матрицей Тогда