имеет отличный от нуля определитель тогда и только тогда, когда ф Xj для всех i, у = 1, [л; i Ф /.

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

Для доказательства прямого утверждения воспользуемся индукцией. Утверждение верно при р, = 1. Мы сейчас покажем, что если оно верно для матриц Вандермонда размера (р, - 1) X X (р, - 1), то оно верно и для матриц Вандермонда размера р, X р.. Заменим Ху в матрице на переменную х. Тогда определитель будет функцией от х и запишется в виде

D(x) = det

х ... х1-1

1 X, Х1 ... ХГ

Xfx х

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

D (х) = dijxf-i + ... +dyx +d,

и, таким образом, имеет не более р, - 1 корней. Коэффициент dyi сам по себе равен определителю матрицы Вандермонда и по предположению индукции не равен нулю. Если для любого i, 2 < i < fx, мы положим X = Xj, то два столбца в матрице будут равны и D (Xf) = 0. Таким образом, каждое Xj (i Ф 1) есть корень D (х), и, поскольку все они различны и их число равно р, - 1, легко получить разложение многочлена

W = -in(-Xj).

Отсюда следует, что определитель исходной матрицы Вандермонда равен

(i) = Cin(Xi-Xj).

Последнее выражение отлично от нуля, поскольку d i отлично от нуля, а Ху отличен от остальных Xj. Поэтому определитель матрицы Вандермонда размера .i X ц не равен нулю, и по индукции получаем справедливость теоремы для любого □

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

Теорема 7.2.2. Матрица компонент синдрома

Si $2 ... S„

So Sq ... s

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

Доказательство. Пусть = О для р. > v, и пусть А - матрица Вандермонда

I 1 ... 1

Xi Xg . • • х„

хг хг... х"-

с элементами Aij = XJ- а В - диагональная матрица

YyXi О ... О О F,X, ... О

о ...YX.,

с элементами Btj = YiXitj, где б;; = 1, если i = /, и бг; = О в противном случае. Тогда произведение матриц АВА будет иметь элементы

(АВА),-у = h ХГ S r,X6«Xi- =

1=1 k=\

= £ XrYiXiXr = £ YiX\+>-\ i=\ 1=1

которые совпадают с элементами матрицы М. Таким образом, М = АВА и, следовательно, определитель матрицы М удовлетворяет соотношению

det (М) = det (А) det (В) det (А).

Если [Л больше v, то det (В) = 0. Тогда det (М) = о и М вырождена. Если р, равно V, то det (В) Ф 0. Кроме того, определитель матрицы Вандермонда А не равен нулю, если все столбцы матрицы различны, что выполняется, если р, равно v. Следовательно, det (М) О, и теорема доказана. □

Эта теорема является основной при построении алгоритма декодирования. Прежде всего найдем правильное значение v, поступая следующим образом. В качестве пробного значения возьмем V = и вычислим определитель матрицы М. Если он не равен нулю, то мы получили правильное значение для v; если же определитель равен нулю, то уменьшим значение v на 1 и повторим процедурку. Поступать таким образом необходимо до тех пор, пока не будет получен определитель, отличный от нуля, и тогда мы узнаем число v ошибок, которые произошли на самом деле. Затем обратим матрицу М и вычислим коэффициенты Л (х). Найдя корни Л (х), найдем локаторы ошибок. Если код двоичный, то ошибки известны. В противном случае вернемся к уравнениям, определяющим коппоненты синдрома:

S, = ух\ + ухХ + ... ь ivX;

= KiXf -I- yxi + ... + F,X~

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

Ху Х ... Ху Х] Хт ... X»,

.Л] Лг ... Ау

= (XiX, ... Ху) det

... 1

хг хг... X

По теореме 7.2.1 определитель последней матрицы не равен нулю, если произошло v ошибок, поскольку Xi, Xg, Ху различны и не равны нулю.

Алгоритм декодирования представлен на рис. 7.1. Здесь мы предположили, что /о произвольно, хотя все рассуждения проводились для частного случая /о = I. Рассуждения остаются теми же для произвольного /о.