5.6. ЦИКЛИЧЕСКИЕ КОДЫ, ИСПРАВЛЯЮЩИЕ ДВЕ ОШИБКИ

В предыдущем параграфе было дано описание кодов Хэмминга как циклических кодов, порождающие многочлены которых имеют корень в соответствующем расширении основного поля. Описанные коды исправляют одну ошибку. Сейчас мы возвращаемся к исправляющим две ошибки кодам над полем GF (2). Пусть длина кода имеет вид для некоторого и пусть а — примитивный элемент поля Мы рассмотрим те даоичиые коды, для которых а и а? являются корнями порождающих многочленов, и покажем, что такие коды позволяют исправлять две ошибки.

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

Принятое слово записывается многочленом степени вида

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

Пусть Эти элементы, известные также под названием компонент синдрома, вычисляются непосредственно по принятому слову Так как являются корнями то Предположим, что произошли две ошибки: Но это в точности дает систему двух уравнений относительно двух неизвестных в поле

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

Прямого очевидного способа решения такой системы нет. Один из методов состоит во введении нового многочлена, определяемого так, чтобы локаторы ошибок были его корнями:

Если мы сумеем найти коэффициенты этого многочлена, то, разложив его на линейные множители, мы сможем найти Но над расширением поля

Таким образом,

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

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

Рассмотренные в настоящем параграфе коды, исправляющие две ошибки, служат иллюстрацией того, как построить

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