9.4. Метод исправления ошибок

Здесь описывается метод исправления ошибок для произвольного кода Боуза — Чоудхури, определенного в разд. 9.1. Применение этого метода позволяет исправлять любую комбинацию из или меньшего числа ошибок, если

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

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

Вектор ошибок полностью задается перечислением значений его ненулевых компонент и указанием мест, на которых эти компоненты находятся. Положение ненулевой компоненты будет задаваться с помощью так называемого номера положения ошибки, который для -госимвола равен просто Таким образом, каждая ненулевая компонента вектора описывается парой элементов поля: - (значение компоненты) и (номер положения ошибки); элемент элемент Если появляется ошибок, компонент вектора отличны от нуля, и, следовательно, для полного описания ошибок требуется пар

Используя вновь введенные величины можем записать

Значения для получаются в результате проведения проверок на четность. Заметим, что в соответствии с теоремами 6.14 и 6.18

В случае двоичного кода приведенное описание может быть несколько упрощено. Так как заведомо отличны от нуля, то . Положение ошибки — это все, что нужно знать для того, чтобы ее исправить. Итак, в этом случае вектор ошибок полностью описывается перечислением номеров положения ошибок.

Полученный на выходе вектор позволяет вычислить 21 величин при —1, а для того, чтобы исправить ошибки, необходимо найти пары для каждой из (или меньше) ошибок. Известные и искомые величины связаны 21 уравнениями:

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

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

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

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

Пусть величины определяются уравнением

Эти коэффициенты называются элементарными симметрическими функциями. Если вместо X в уравнение (9.7) подставить значение то обе части уравнения обратятся в нуль. Это будет так и в том случае, если обе части уравнения предварительно умножить на Поэтому для любых значений и I

Суммируя эти уравнения по всем значениям и подставляя выражения (9.5), получаем соотношение

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

Теперь можно дать предварительное описание метода декодирования, основанного на опробовании разных решений. (На самом деле он должен быть несколько видоизменен — не всегда нужно делать точно так, как описано здесь.) 1) Решим систему уравнений относительно величин Подставим эти решения в правую часть уравнения (9.7) и затем подставим в уравнение (9,7) все ненулевые элементы из Те из элементов, которые окажутся корнями уравнения, определяют значения для ошибок. Очевидно, их порядок несуществен. 3) Подставим ненулевых значений найденных на этапе 2), в первые уравнений (9.5) и найдем решение этих уравнений относительно соответствующих величин (Этот шаг оказывается ненужным в случае двоичного кода.) Зная все пары можно исправить ошибки. Остается показать, что уравнения (9.9) и (9.5) разрешимы.

Уравнения (9.5) имеют вид

Определитель системы относительно неизвестных К равен

так что в правой части стоит определитель Вандермонда (9.3). Поэтому определитель в правой части равенства отличен от нуля, если все величины различны и отличны от нуля, что, очевидно, справедливо в данном случае. Следовательно, уравнений (9.10) линейно независимы и могут быть разрешены относительно неизвестных после того, как найдены значения

Ответ на вопрос о разрешимости уравнений (9.9) содержится в следующем утверждении.

Теорема 9.3. Матрица

является невырожденной, если величины образованы в точности из различных ненулевых пар Матрица М является вырожденной, если они образованы меньше, чем из ненулевых пар

Доказательство. Используя систему уравнений (9.5), можно проверить, что

Матрица М является невырожденной тогда и только тогда, когда невырожденной является каждая из матриц, стоящих в правой части равенства (9.13). Первая и последняя из этих матриц — это матрицы Вандермонда, и равенство (9.3) показывает, что эти матрицы являются невырожденными тогда и только тогда, когда все величины различны. Матрица, стоящая между ними, есть диагональная матрица, являющаяся невырожденной тогда и только тогда, когда каждая из величин отлична от нуля. (Заметим, что вследствие метода, которым были введены эти величины, тогда и только тогда, когда так что случай не исключается.) Итак, матрица является невырожденной тогда и только тогда, когда все пары отличны от нуля и различны. Ч. т. д.

Если в качестве неизвестных в уравнениях (9.9) рассматривать величины то матрица коэффициентов этой системы совпадает с матрицей М, задаваемой равенством (9.12). Поэтому из теоремы 9.3 вытеьает, что эти уравнения невырождены и могут быть решены, если произошло точно ошибок, и что уравнения линейно зависимы, если произошло меньше, чем ошибок. Однако в этом последнем случае и либо первое, либо последнее уравнение можно отбросить и применить теорему 9.3 к системе уравнений, в которой число неизвестных на единицу меньше. Этот процесс можно повторять до тех пор, пока не будет найдена разрешимая система уравнений.

Процесс исправления ошибок описывается кратко следующим образом:

1. Вычисляются значения при по полученному на выходе вектору. Эта операция сводится к проведению проверок на четность.

2. Определяется наибольшее число последовательных уравнений, которые линейно независимы. Оно равно числу ошибок которые в действительности произошли.

3. Величины полагаются равными нулю и затем первые уравнений решаются относительно

4. Каждый ненулевой элемент из подставляется в многочлен

Корни этого многочлена задают номера положения произошедших ошибок

5. (Этап ненужный в случае двоичного кода.) Номера положения ошибок, найденные на предыдущем этапе, подставляются в первые уравнений (9,5), и эти уравнения решаются относительно соответствующих величин Определитель матрицы коэффициентов выглядит так же, как определитель (9.3), и, следовательно, отличен от нуля; поэтому уравнения линейно независимы. Зная значения и У можно исправить ошибки.

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

и

Уравнения (9.9) принимают вид

Умножая первое уравнение на второе — на а третье — на получаем

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

Эти уравнения отличаются одно от другого только множителем значит, второе уравнение зависит от первого. Поэтому последнее из первоначальных уравнений (9.16) должно зависеть от первых двух уравнений, и, следовательно, должны были появиться только две ошибки. Полагая из уравнений (9.18) получаем, что или Используя любое из уравнений (9.17), находим, что Итак, номера положений ошибок должны быть корнями многочлена

Легко проверить, что уравнению (9.19) удовлетворяют элементы и только они. Поскольку рассматривается случай двоичного кода, то знаний положения ошибок вполне достаточно для того, чтобы эти ошибки исправить — ошибочные символы следует просто изменить на обратные.

В качестве второго примера рассмотрим код типа кода Рида — Соломона над используя представление элементов поля в табл. 6.1. Предположим, что ошибка, равная произошла на месте, соответствующем положению и ошибка, равная произошла на месте, соответствующем Тогда

и уравнения (9.9) записываются в виде

Умножая первое уравнение на второе — на а третье — на получим

Прибавляя к каждому из двух последних уравнений первое уравнение, находим, что

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

легко найти, что Номера положений ошибок удовлетворяют, как и прежде, уравнению

и, следовательно, положение ошибок определяется корнями, равными Значения ошибок определяются из уравнений (9.5):

Эти уравнения легко решить. Получается, что