![]() |
Главная страница Алгебраическая теория кодирования [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] 100000000000 010000000000 001000000000 eooioooooooo 000010000000 000001000000 000000100000 000000010000 000000001000 000000000100 000000000010 000000000001 111000111000 1 0 0 0 1 1 1 0 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 10 110 1 1 о 1 о о 1 10000000 0 000 001000000000 000010000000 00000010000О 00000000100 0 „ 000000000010 111000111000 00111000111О 1110 110 1 о 1 1 0 о 1 1 1 1 1 о о 10 10 1 0 10 10 110 0 1 о 1 о о 0 10 1 0 0 10 1 0 0 1 0 0 1 0 0 1110 0 10 0 1110 10101001001О 110010011100 001100100111 000000000000 011000000000 001010000000 000100100000 000010001000 000001000010 111000011000 1 0 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1110 110 10 0 10 10 10 0 10 1 1 1 0 0 1 0 0 1 1 1 0 0 1 1 0 0 1 0 0 1 1 о 1 о Если перенумеровать столбцы матрицы @ - J числами от О до 11 и прибавить третий столбец к шестому, первый, второй и четверты! столбцы к восьмому, а пятый столбец к десятому, то верхний правы! восьмимерный квадрат матрицы й - 3 можно сделать нулевыз* Нижний правый квадрат при этом примет вид О 1 1 О .0 О 111110 О 1 1 О О 1 0 10 110 0 11110 0 0 1110 Решениями уравнения [е, т, g] М = являютс [6, 8ъ , gii) = U, О, О, Л, О, А], где Л = О или 1. Перв1 шесть координат g легко находятся из уравнения g (б - J) = решения которого имеют вид g = [В, А, О, А, А, О, А, О, О, А, О, А\ где А, В GF (2). Наконец, применим алгоритм Евклида к / (ж) J = 1110001110001 и g{x)-s = si 0 110 10 0 10 Выбирая S независимой переменной и t - s + l, можно с помош;ью одних и тех же вычислений найти н. о. д. многочленов 1110001110001и010110100101ин. о. д. многочленов 111000111000 IHIIOIIOIOOIOI: 1110001110001 slOllOlOOlOl liOOlllOlOl slOllOlOOlOl sOflUOl UOOlllOlOl ItOsisOl somm mm Если f = 0, TO H. o. Д. равен 10011101, если s = О, н. о. д. многочленов lllOOOlllOOOlnOlOllOlOOlOl равен н. о. д. многочленов 111101и11001001и совпадает с 1 1 1 1 О 1. Оба многочлена 111101и10011101 неприводимы над полем GF (2) и разложение является полным: 1 4- х + + а;б + ж + х» + х = (1 + х + х + з? + x) X X (1 + аг* + X* + -f- х). в общем случае предположим, что/(а;) = [] [р() (x)f, где каждый многочлен p<> (х) неприводим над GF (q). Многочлен / (х) делит и Ig {х) - s] тогда и только тогда, когда каждый многочлен (х) делит g (х) - Si для некоторого s,- g GF (q). С другой стороны, для произвольного заданного множества скаляров s, sj, s3, . . ., 6 GF (q) китайская теорема об остатках 2.17 гарантирует существование единственного по mod / (х) многочлена g (х), такого, что g (х) = Si mod [p> {x)Vi для всех i. Так как существует точно gr" векторов {si, s2, . . ., Sn), то существует точно решений уравнения [g (х)]ч - g (х) ~0 mod / (х). Это доказывает 6.13. Теорема. Число различных неприводимых делителей f {х) равно размерности нуль-пространства матрицы й - J. В частности, многочлен / (х) является степенью неприводимого многочлена тогда и только тогда, когда нуль-пространство матрицы g J имеет размерность 1. В этом случае решениями сравнения [g (х)]9 - g (х) = 0 mod / (х) являются только скаляры поля iq) и нуль-пространство матрицы й - 0 содержит единственный вектор вида [s. О, О, . . ., 0]. Если размерность нуль-пространства матрицы @ - J равна п, то оно имеет базис, состоящий из п нормированных многочленов g<i) (х), g-l (х), . . ., (х). Без потери общности можно считать, что g(> (ж) = 1 и что степени остальных {п - 1) многочленов положительны. Применяя алгоритм Евклида к / (ж) и g() {х) - s, мы получим разложение / (ж). Если это разложение содержит менее п множителей, то вычисляем п. о. д. g{x) - s и каждого уже известного множителя многочлена /(х) и т. д. Следующие соображения показывают, что этот процесс приводит в конце концов к разложению / (х) в произведение степеней п неприводимых многочленов. Пусть - некоторая {п X ?г)-матрица над GF [q), где (х) = S eij mod {x)f. Тогда ё невырожденна, так как если Ajei,j = О для всех i, то Ajg (х) =0 mod [р<> {х)Р для всех i и, следовательно, () = 0 mod / (х), что нротиворе- чит линейной независимости g() (х), (х), . . ., g() (х). Так как в ;-м столбце матрицы ё стоят различные элементы, то, применяя к / (х) и (х) - S алгоритм Евклида, получим разложение / (х) на различные множители. Степени неприводимых многочленов [р()(х)] и (х)]"выделяются тогда и только тогда, когда Так как IS невырожденна, то для каждых i и к существует некоторое /, такое, что ei,j "ek.j- Следовательно, некоторый многочлен: g< (х) выделяет степени любых дэух неприводимых делителей / (х). Степень произвольного неприводимого делителя может быть; определена путем применения алгоритма Евклида к многочлензг / (х) и его производной. Если д достаточно велико, то к этому алгоритму может быть применено несколько остроумных приемов, некоторые из которых обсуж даются во втором томе книги Кнута [1968]. *6.2. Определение периода многочлена Часто нужно знать период многочлена / (х), т. е. наименьшее число /, для которого многочлен / (х) делит х - 1. Если / (х)-I неприводимый многочлен степени т над GF (q), то период / (х) равещ наименьшему общему кратному мультипликативных порядков ег( корней (оно делит число q™ - 1). Найдем связь между периодом многочлена и периодами era неприводимых делителей. Предположим сначала, что /(х) - ненриво! димый многочлен с периодом п, и найдем период многочлена,[/ (х)]" Так как п - делитель числа qs.f - 1, то пфО mod р, где р характеристика поля GF {q). Так как период / (х) равен п, то / (а делит многочлен х - 1 тогда и только тогда, когда А; = О (mod га 6.2. Определение периода многочлена 161 Если к = р/> где 7 не делится на р, то х - i - (х - 1)". Многочлен х - 1 не имеет кратных корней, так как он делит xfl~ - 1, где т - мультипликативный порядок числа q по модулю /. Следовательно, каждый неприводимый делитель многочлена х - \ имеет кратность р\ Отсюда заключаем, что если неприводимый многочлен. / (х) имеет период п, то период многочлена [/ (х)]™ равен пр, где p - наименьшая степень числа р, такая, что р т. Предположим теперь, что / (х) = [/<i) (х)]"Ч/() (х)]"" . . ., где /() (х) - различные неприводимые многочлены. Так как х - 1 делит х - 1 тогда и только тогда, когда к делит N, то период / (х) равен наименьшему обш;ему кратному периодов многочленов [/" (х)]™, [/() (х)]™, .... Это число в свою очередь равно произведению наименьшего обш;его кратного периодов многочленов (х) на наименьшую степень числа р, такую, что р m,i для всех i. Итак, имеет место 6.21. Т е о р е м а. Если / (х) = [][/*(х)]™*, где /<*() - неприводимые многочлены с периодами Hi над полем GF (q) характеристики р, то период f (х) равен произведению наименьшего общего кратного чисел ni на такую наименьшую степень p числа р, что р т,-для всех i. Таким образом, задача определения периода многочлена сводится к задаче определения периодов каждого из его неприводимых множителей. Каков наилучший метод определения периода п неприводимого многочлена / (х)? Если степень / (х) равна т, то п должно быть делителем числа д"* - 1, так что первый шаг сводится к разложению д"* - 1 =nii Д Pi - различные простые числа. Опре- делив классы вычетов х""". mod / (х), можно узнать, входит ли в период пчисло pp. Эти вычисления могут быть выполнены путем перемножения подходящих комбинаций классов вычетов х, х, Х9-, . . ., x«"~*mod / (х). Если х" 1 mod/(х), то период / (х) кратен числу рр, если же х = 1 mod / (х), то число рр не входит в период / (х). В последнем случае надо проверить, кратен ли период / (х) числам рр", рр~, .... Эти выкладки надо провести для всех простых делителей числа д*" - 1. Результаты этих вычислений сразу позволяют определить период п многочленов /(х). 6.22. Пример. Чему равна блоковая длина укороченного циклического двоичного кода с порождающим многочленом g (х) = = х» + ж 4- 1? 11-658 [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] 0.0145 |