Расчеты показывают, что для поля GF(2*) уравнения четвертой и более высоких степеней вьподнее (по числу операций) решать с помощью БПФ, а ниже четвертой степени - с помощью обычного ДПФ.

По существу классический вариант ДПФ (без факторизации матрицы) эквивалентен последовательно упорядоченному перебору корней, т. е. является одной из форм процедуры Ченя [22,40].

В последнем случае, организуя вычисления по схеме Горнера (1.31) - см. § 1.2, можно для каждого испытываемого корня ограничиться умножением на одну и ту же константу.

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

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

5.6. СИСТЕМЫ УРАВНЕНИЙ НАД ПОЛЯМИ ГАЛУА

Системы линейных уравнений с произвольной матрицей. Некоторые задачи в теории помехоустойчивого кодирования, например по восстановлению стираний, вызьшают необходимость решать системы линейных уравнений над тем или иным алгебраическим полем. Наибольшее распространение получили следующие методы решения системы линейных уравнений [32, 33]: метод Гаусса последовательного исключения неизвестных и приведения матрицы системы уравнений к треугольному или диагональному виду; метод Крамера, основанный на составлении определителей. Мы рассмотрим одну из разновидностей первого метода - приведение матрицы системы к так назьюаемой треугольной идемпотентной форме L, удовлетворяющей свойству i Эта форма характеризуется следующими особенностями: каждый элемент, расположенный ниже главной диагонали (как и в любой 1реугольной форме), равен нулю; на главной диагонали расположены нули или единицы; всякий элемент столбца, имеющего нуль на главной диагонали, равен нулю; всякий элемент строки, имеющий единицу на главной диагонали, равен нулю.

Процедура приведения квадратной матрицы порядка v к форме L основана

на следующем алгоритме [§].

1. Если верхняя строка матрицы является нулевой или ее левый элемент

отличен от нуля, то перейти к п. 3.

2. Если левый элемент первой строки равен нулю, то переставить первый столбец с самым левым столбцом, в котором верхний элемент отличен от нуля и на главной диагонали стоит нуль; если же подходящего столбца нет, то поменять местами первый столбец с самым левым столбцом, в котором отличны от нуля оба элемента (верхний н на главной диагонали).

3. Разделить все члены первого столбца на его самый верхний элемент.

4. Обратить в нуль верхние элементы во всех столбцах, кроме первого, добавляя к ним первый столбец, умноженный на -а-.

5.Циклически сдвинуть строки вверх, а столбцы влево. Если полученная матрица не имеет форму L, то вернуться к п. 1.

Проиллюстрируем данный алгоритм на используемом далее примере матрицы с двоичными элементами:

1 о о

а О О О О

а 1 1 О

1 1 О О

а О О О О

О О О О

п. 5

а О О О О

О О О О

О О О О

1 О О 1

(5.89)

Решениями уравнения XL = О являются линейные комбинации (ненулевых) строк матрицы L - Е, где Е - единичная матрица порядка v.

Система неоднородных линейных уравнений. Пусть система v линейных уравнений с V неизвестными задается неоднородным уравнением ХМ = Q или эквивалентным однородным

м - Р J

= 0,

где j3 - ненулевой вектор (строка).

Приводя матрицу М к треугольной идемпотентной форме L (с соответствующей трансформацией вектора Q в вектор р), составим матрицу - к которой присоединим снизу строку Если хотя бы одно произведение компоненты q иа соответствующий диагональный элемент отлично от нуля, то уравнение ХМ = 0 решений не имеет. Если же все v произведений равны нулю, то х = 0 является одним из решений. Другие решения равны сумме строки /з с линейными комбинациями ненулевых строк матрицы L Е.

Рассмотрим пример решения системы уравнений

(5.90) Неизвестный

где Q = [1101]; М - первая матрица в соотношении (5.89); X -четырехкомпонеитный вектор.

В процессе приведения матрицы М (5.89) в уравнении (5.90) к форме L строка/?= (1101) преобразуется к виду/3 = (0001);

Вычитая из матрицы L (5.89) единичную матрицу Е и располагая столбцы в естественном порядке (а, а. а\а**), получим

Таким образом, одно из решений заданной системы суть =/?" = (1000),

(1010); (0101);

а остальные 7 решений равны: Х2 ~ & " у\ = (0100); Хз = 3" +32 = х0"+Уз = (1001); Xs = 0" -Ух +32 = (ОНО); х = 0 -у +33 = 7 = "+32+33= (1011); х0" +уу +У2-Уз- (0111).

Решение уравнений с помощью аффинного кратиого« Линеаризованным полиномом/, (х) над полем GF( = р ) назьшается полином вида

£(x) =Z,oX + Z,iJc+l2x* + ... + IwX = £ Lx , (5.91)

i = О

коэффициенты которого принадлежат полю GF(p). Аффинным полиномом над полем GF( - р) называется полином! (х) -/3, гдеZ, (х) - линеаризованный полином.

Для того чтобы найти корни полинома L{x) - 0, поступаем следующим образом.

1. Вычисляем значения полинома L (л) (5.91) в следующих точках: х е ( а**, а, а, а, ..., а*" *} , где а - примитивный элемент поля GF(p*), а в фигурных скобках представлен канонический базис этого поля; для GF(2) всегда можно принять а = 2.

2. По полученным значениям L{Oi), Ь{<Х), L{a~) составляем матрицу М (с присоединенной строкой разложения 0 по тому же базису), которую приводим к треугольной идемпотентной форме L .

3. Вычисляем корни заданного полинома как линейные комбинации последней и остальных ненулевых строк матрицы из п. 2.

Пример 5 Л 8. Пусть над полем GF (2 ) задан полином

(5.92)

L{x~0),

тт1{х) =х® + 15х* + 7х+3х; 0= 14= (1101).

Находим: Z, (1) = О = (0000); 1 (2) = О = (0000); I (3) = 14 (1101); I (4) = = 14 = (1101). Таким образом, получаем систему (5.90): ХМ= . Заменяя полученные там двоичные векторы на соответствующие элементы поля GF(2), найдем: Xi =4; х2 = 3; х3 = 10; х4 = 15; х5 = 6; х = 9; х7 = 8; xg = 11.

Оказывается, для произвольного полинома /(х) степени v можно составить аффинный полином Z-(х) - 0, кратный /(х) над полем GF(p*). Тогда корни полинома/(х) будут среди корней полинома Z. (х) - 0.

Метод составления аффинного кратного полинома £ (х) - 0 по заданному полиному fix) следующий [8]:

1. Находим значения x по модулю/(х) для1 = v,v + I,,. ., iv - l)p.

2. Вычисляемх* по модулю/(х) для / =0, 1, 2, . . ., - 1.

3. Образуем линейную комбинацию