11.11. Код с исправлением двойных ошибок

Для того чтобы продемонстрировать код с исправлением двойных ошибок, понадобится более длинный, чем раньше, код Хэмминга, имеющий общую длину 15 и четыре проверки на четность. В качестве возможного кандидата на роль многочлена-основания рассмотрим многочлен Ясно, что не является делителем этого многочлена. Если бы многочлен делился на то сумма его коэффициентов была бы равна (см. задачу 11.6.1). Поэтому, чтобы убедиться, что рассматриваемый многочлен является простым, достаточно проверить, что его делителем не является лишь простой квадратичный многочлен

Далее нужно выяснить, удовлетворяет ли многочлен условию примитивности. Начнем последовательно вычислять степени а

Получим, что как и должно быть, и что ни одна меньшая степень а не равна 1. Поэтому а является примитивным корнем, и проверочная матрица имеет вид:

Для того чтобы исправлять большее число ошибок, чем исправляет этот код (т. е. больше одной ошибки), к матрице нужно добавить дополнительные строки. Добавим четыре дополнительных строки. Как это можно сделать?

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

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

Попробуем использовать в качестве второго синдрома куб первого синдрома, т. е. Имеем

так что

Если заданы сумма и произведение двух чисел, то почти автоматически возникает мысль о квадратном уравнении и его корнях:

Эти два корня дают различные синдромы ошибок.

При наличии только одной ошибки синдромы равны: Таким образом, квадратное уравнение приобретает вид

В случае отсутствия ошибок и квадратное уравнение приобретает вид

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

(в обратном порядке). Таким образом, полная матрица имеет вид

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