Главная Помехоустойчивое кодирование



заданного полинома fi {z), совпадаюпше с корнями его орбитальных полиномов.

Ясно, что такое совпадение всегда произойдет, если корни полинома fx (z) лежат в одном и том же циклоклассе (подразумевается,

что они некратные).

Предположим, что корни исходного полинома fx (z) лежат в циклоклассах разной длины; тогда корень из более короткого циклокласса также обязательно совпадает с корнем одного из орбитальных полиномов и,следовательно, может бьтгь выявлен.

Другими словами, орбитальный метод позволяет выявлять такие некратные корни полинома fx (z) , которые не являются единственными представителями в циклоклассах одинаковой длины. Если же корни этого полинома лежат в разных циклоклассах, имеющих одинаковую длину (и являются единственными корнями в этих циклоклассах), то указанный метод не позволяет провести факторизацию. Например, составим полином над полем GF (2):

Fx iz) = (7 + 2) (7 + 4) (z + 6) (2 + 8) (z + 12) (z + 16) , (5.83)

имеющий строго по одному корню, взятому из каждого циклокласса длины 5 - см. табл. 3.14. Полиному (5.83) соответствуют такие орбитальные полиномы:

р2 (z) = (2 + 3) (2 + 7) (z + 11) (z + 15) (2 + 23) (2 + 31); (5.84а)

F4 (2) = (2 + 5) (2 + 13) (2 + 21) (2 + 29) (2 + 14) (2 + 30) ; (5.846)

Fg (z) = (z + 9) (z + 25) (z + 10) (2 + 26) (z + 27) (z + 28); (5,84в)

(2) = (z + 17) (2 + 18) (2 + 19) (2 + 20) (2 + 22) (z + 24). (5.84r)

Ясно, что у полиномов (5.83), (5.84) нет общих корней. Однако рассмотренный метод можно усовершенствовать, если эти полиномы использовать в качестве испытательных, вычисляя НОД [/(2), F\iz)] при различных X.

В принципе нет необходимости составлять вспомогательный полином Fx (2) высокого порядка, а можно ограничиться формированием нескольких полиномов, выбирая их корни из небольшого числа разных циклоклассов, В пределе, при линейных полиномах, решение сведется, по существу, к упорядоченному неким образом перебору корней. Другой метод упорядоченного перебора приведен ниже.

Решение уравнений с помощью ФМС-преобраэования (ДПФ и БПФ над полями Галуа). Как отмечалось в § 4,3, элемент является корнем полинома V (х) = Vq + ViX + ... + Vj. х тогда и только тогда, когда равен нулю коэффициент в полиноме F(x) = Vq + Fiх + . .. + ,

представляющем собой ФМС-преобразование От полинома v (х).

Таким образом, еще один универсальный метод решения уравнений основан на ФМС-преобразовании. Последовательность действий сле-



дующая- Пусть задано уравнение v(x) = О, где v(x) - полином f-й степени. Без потери общности можно считать, что = 1. Подвергнем v(x) ФМС-преобразованию (в форме ДПФ или БПФ), Индексы / у коэффициентов Vj-у равных нулю, соответствуют корню а заданного уравнения [3, 20].

Пример 5,17. В § 5.4 рассматривалось уравнение пятой степени, имеющее множество корней (З, 7, 10, 12, 15} е GF(2) и вектор коэффициентов v = (Vq, Vi, ... , Vs) = (13, 7, 15, 5, 9, 1). Так как q - 1 = 15, то для ФМС-преобразования длины « = 15 вектор v должен быть дополнен девятью нулевыми компонентами.

Если пля поеобоазования использовать матоипу Ф1с. то можно

по-д ру г о му

номерами

скомпонуем матрицу, на которую слева умножим ате получим

V= iVo, Fl, Fj, Кз, F4, Fs, Рб, V,, Vs, f9, Fio, Кц, Vn, 13, F14) = = (14,3, 0, 15,14,2, 0, 2, 10,0, 5, 0, 10, 1, 0). (5.85)

Таким образом,

v2=Ve=V9= Vn = Fi4 = 0, (5.86)

a потому корнями заданного уравнения являются а = 3, а* = 7, = = 10,а" = 12,а* = 15.

Воспользуемся теперь быстрым алгоритмом, основанным на факторизации матрицы преобразования (рис. 4,14). Заданный вектор v (формально удлиненный до « = - 1 = 15) нужно перекомпоновать в вектор V согласно последовательности (4,9а), т. е-

= (Vo,V3,V6, V9,Vi2,V5, Vg, Vii, Vi4, V2, Vio, Vi3, V] , V4,V) =

= (13,5, 0, 0, 0, 1, 0, 0, 0, 15,0, 0, 7, 9, 0).

Умножая вектор v на матрицу 5, найдем промежуточные величины: Zo = Vq + Vs + Vio = 12; 2i = V3 -h Vg + Vi3 = 5; 72 = V6 + Vn + Vi = 7; 73 = V9 H- Vi4 + V4 = 9; Z4 = V12 + V2 + V7 = 15; Z5 = Vq + 6vs + llvio = 15; 7б = V3 4- 68 + llvi3 = 5; 77 = V6 + 6vn + Hvj = 2; Zg = V9 -h 6vi4 -h 11V4 = 4; 79 = V12 + 6V2 + IIV7 = 5; Zto = Vq + llvs + 6vio = 4; 7ii = V3 + llvs + 6vi3 = 5; Z12 = V6+ lliii + 6vi = 12; 7i3 = V9 -h llvi4 + 6V4 = 14; 14 = V12 + IIV2 + 6V7= 10, GF(2*). (5.87)



Далее вектор г - (zq, , . .. , 714) умножим на матрицу А. В результате получим

21 + 22 + 3 + 24

= 14;

42i + 722 + IO23

+ 1324

72i + 1З22 + 423

+ IO24

102i + 422 + 132

3 + 724

132i + IO22 + 72

3 + 4Z4

2б + 27 + Zg + 29

= 5;

4Z6 + 7Z7 + lOzg

+ 1З29

726 + 1З27 + 428

+ IO29

102б + 427 + 132

8 + 7Z9

132б + IO27 + 72

8 + 4Z9

Ухо = Zio + 2ц + Zi2 + Zi3 + 2i4 =2;

Уп = Zw + 4zn + 72i2 + 10213 + 1324 = 0;

L

12 = Zio + 72ii + 13212 + 42i3 + 10214 = 0; У1Э = Zio + 10211 + 42,2 + 13zi3 + 72i4 = 10;

У1Л = Zio + 132ii + 102i2 + 72i3 + 42i4 = 0. (5.88)

Остается переупорядочить вектор = (уоУх, - • • 9 Уы) в вектор У = (о> 1» . • • , Via) согласно правилу (4,96), Таким образом, вновь получаем соотношения (5.86).

В заключение сравним по числу операций классический и быстрый алгоритмы в зависимости от степени f решаемого над полем GF( = 2 ) уравнения. В классическом, первом, варианте (при использовании нефакторизованной матрицы Ф) требуется (q - 2)f умножений и (q - 2) (f + 1) сложений. Пусть « = ni«2 = Q - 1, НОД («i, «2) = 1 и матрица Фп факторизована. Тогда во втором варианте требуется на

первой итерации: («j - 1) (f - 1) умножений и («i - l)(f+ 1) сложений, а на второй итерации: («2 - умножений и «2 («2 - cJo-жений. Итак, для вычисления ФМС-преобразования необходимо выполнить:

Вариант.......... Первый Второй

Число операций:

умножений..... («1«2 - l)f ii - 1) (f - 1) + («2 - 1)«1

сложений...... («12 - 1) (f + 1) («1 - 1) (f + 1) + «2 i2 - 1)1

Всего ...........(2rtirt2 - 2)*»+«12 - 1 (2f + 2rt-3rt2 + l)rti



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 [75] 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94


0.0143