9.5. Другой способ исправления ошибок для двоичных кодов

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

В случае двоичного кода величины которые не могут обращаться в нуль, должны быть равны 1. Следовательно,

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

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

Уравнение (9.7) может быть эффективно решено просто последовательной подстановкой в него каждого из элементов поля. Для каждого символа вектора, полученного после передачи, в уравнение подставляется соответствующий элемент из Если

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

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

Теорема 9.4. Матрица размерности

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

Для доказательства потребуются следующие две леммы.

Лемма 9.5. Если симметрические функции являются суммами степеней — 2 различных элементов поля, то матрица является вырожденной.

Доказательство. В соответствии с тождествами Ньютона (9.23;

таким образом, матрица должна быть вырожденной. Ч. т. д.

Лемма 9.6. Если симметрические функции являются суммами степеней переменных то определитель матрицы равен

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

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

Тогда

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

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

Теперь утверждение теоремы 9.4 следует из того факта, что если определитель равен нулю, то необходимо, чтобы некоторое Так как все ненулевые элементы различны, то следовательно, в этом случае имеется меньше, чем ошибок. Ч. т. д.

Если в действительности произошло ошибок, то из тождеств Ньютона (9.23), правила Крамера и теоремы 9.4 можно вывести, что решение системы относительно неизвестных а приводит к результату о, — 0. Среди корней соответствующего многочленного уравнения обязательно должен содержаться нуль.

Рассмотрим теперь процесс исправления ошибок. Код Боуза — Чоудхури, исправляющий ошибок, дает в качестве результатов проверок на четность на основе полученного вектора все симметрические функции, являющиеся суммами нечетных степеней» вплоть до а промежуточные функции, являющиеся суммами четных степеней, можно просто вычислить с помощью этих функций. Если предполагается, что появилось не более чем ошибок, то в соответствии с теоремой 9.4 либо можно найти как решение системы номера положений ошибок, либо на самом деле появилось или меньше ошибок. В этом последнем случае и два уравнения можно отбросить, получив при этом уравнений с неизвестными, к которым снова применима теорема 9.4. В конечном счете, если ошибки вообще были, будет найдена совокупность уравнений, которые допускают решение относительно элементарных симметрических функций, определяющих номера положений ошибок.

Процесс исправления ошибок можно разбить на три этапа:

1) проведение проверок на четность и вычисление значений для четных у;

2) вычисление по ним элементарных симметрических функций

3) и, наконец, подстановка каждого элемента поля в уравнение

Те элементы поля, которые удовлетворяют этому уравнению, соответствуют положению ошибки.

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

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

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

Пример. Рассмотрим двоичный -код, исправляющий тройные ошибки, который обсуждался на стр. 188. Соответствующие уравнения записываются как

Проверки на четность для получаемых векторов позволяют найти значения Далее, Разрешая уравнения относительно значений , получаем

при условии, что Если произошла только одна ошибка, то Далее, если из тождеств Ньютона следует, что уравнение

имеет два одинаковых корня, которые необходимо равны нулю, и, следовательно, имеется только одна ошибка.

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

Обращаясь к табл. 6.1, находим

Тогда

Аналогично

Теперь легко проверить, что уравнение

удовлетворяется при трех значениях X: и только при них. Эти значения являются номерами положения ошибок в векторе