Главная страница  Алгебраическая теория кодирования 

[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]

2 -

= а

представить в виде многочлена от а над GF (4), степень которого < 2. Соответствующие результаты приведены в столбце 3.

Соответствующие строчки столбца 3 могут быть получены с помощью представленного на рис. 4.1 регистра с обратной связью, если позаботиться о том, чтобы правильно выполнялись все арифметические операции поля GF (4). Для этого необходимо использовать равенства = + 1= аи5 = 5 + 1 = .

Используя столбец 3, можно отождествить остальные элементы поля GF (16). Ясно, что совпадает с элементом я, сопряженным с а относительно GF (4); равно и а" равно д, а? и а* сопряжены

с а относительно GF (2), но не относите ль-, но GF (4). Следовательно, они - корни одного и того же неприводимого двоичного-; многочлена четвертой степени и разных; неприводимых квадратных многочленов над! GF(4). Эти элементы обозначены через ф1 и р (в произвольно выбранном порядке).

Так как а и я - корни квадратного урав- нения х -f а; + = О, то они являютс»; также корнями многочлена 5а;~ (х + а; + ) = = -\- дх~ + 5 и, следовательно, а~ я~1 = а~*- корни квадратного уравнений + 5а; + 5 = 0. Такими элементами являются Я и . Аналогична и а" - корни многочлена х + gx -- , и они совпадают с р и v Наконец, нам осталось определить, с какими из пар (а, а} или (а, а} сопряжены корни многочленов х + х + 1 и л: + йх + i относительно поля GF (4). Так как [(а) -Ь 1]/а = 5, то заключаем что а* и - это Y и 9, а а® и - это б и х. Таким образом, полз чаются 16 элементов, список которых приведен в столбце 5. Ов являются корнями соответствующих неприводимых многочлене над GF (4), записанных в столбце 4. Отметим, что, не мен столбца 4, можно переименовать любую пару сопряженных othoci тельно GF (4) элементов.

В столбце 6 для каждого из 16 элементов выписаны минимальны! двоичные многочлены. Они получаются непосредственно из разложе ния неприводимых двоичных многочленов четвертой степени нЯ неприводимые квадратные многочлены над GF (4). Заметим, чт произвольный элемент, его квадрат, его четвертая степень и ei восьмая степень являются корнями одного и того же неприводимох двоичного многочлена.

Так как а является корнем неприводимого двоичного многочлен! четвертой степени х* -- х + 1, то можно пренебречь подполем GF (4 и выразить каждый элемент поля как двоичный многочлен от а степе ни < 4. Такое представление приведено в столбце 7. Соответствующи1 степени а найдены как подходящие состояния регистра сдви! с обратной связью для умножения на а; см. рис. 4.2.

Рис. 4.1. Регистр сдвига с обратной связью над OF (4).

4 S

Рис 4.2. Регистр сдвига с обратной связью для умножения на а.

в большинстве случаев наиболее удобными являются представления, приведенные в столбцах 1 и 7. В машинной обработке исполь-;)уется почти исключительно представление, записанное в столбце 7. Однако при ручных вычислениях полезными оказываются оба представления. Умножение,.деление, возведение в степень и извлечение корня более удобно выполнять в терминах представления, заданного и столбце 7.

В столбце 8 приведена двоичная запись логарифмов ненулевых элементов по основанию а. Такая запись имеет несколько преимуществ. Например, двоичный ) логарифм мультипликативного обратного к элементу поля получается путем поэлементного дополнения двоичного логарифма самого элемента. Единственной особенностью является появление последовательности единиц в качестве дополнения к нулевой последовательности, представляющей двоичный логарифм единицы. Такая единичная последовательность должна также пониматься как двоичный логарифм единицы. Нулевая и единичная последовательности являются эквивалентными представле-1П1ЯМИ одного и того же числа, подобно Тому как --0 и -О являются в действительности одним и тем же числом. По существу арифметикой двоичных логарифмов является так называемая арифметика «дополнения до единиц», которая повсеместно используется в определенных тинах вычислительных программ и арифметических блоках.

Другим более важным преимуществом двоичной записи логарифмов является то, что двоичный логарифм каждого из двоично сопря-/ненных элементов может быть получен с помощью циклического сдвига двоичного логарифма самого элемента. Например, двоичные логарифмы сопряженных элементов а", а = а, а* и = а равны векторам 1011, 0111, 1110, 1101, каждый из которых является левым циклическим сдвигом своего предшественника. Аналогично двоичные логарифмы GF (4) -сопряженных элементов являются двукратными циклическими сдвигами друг друга.

В полях характеристики р р-ичные ) логарифмы обладают такими же преимуществами, какими обладают двоичные логарифмы в полях характеристики 2.

Выбор примитивного элемента а, через который выражаются все остальные элементы поля, является несколько произвольным.

М Не путать с логарифмом по основанию два!- Прим. перев. 2) Опять имеется в виду р-ичная запись логарифмов, а не их основание.-

/Ч.ч. перев.



В столбце 9 приведена реализация, связанная с выбором другого корня р неприводимого примитивного двоичного многочлена х* + + 1 четвертой степени. В столбце 10 выписано представление элементов поля в виде двоичных многочленов от р степени < 4. В столбце 11 дается иное представление элементов поля в виде линейных комбинаций элементов р, р, р* и Р*. Аналогичным образом все элементы поля могут быть представлены в виде линейных комбина-ций.любых четырех линейно независимых элементов поля, т. е. четырех элементов, для которых все 16 двоичных комбинаций различны, или, иначе, элементов, для которых ни одна ненулевая линейная! комбинация не равна нулю. Некоторые множества из четырех эле-J ментов, как, например, {а, а, а*, а*}, удовлетворяющие уравне-, нию а + + а* + а* = О, не являются независимыми. Множество из четырех линейно зависимых элементов поля нельзя выбират1г в качестве базиса для представления поля.

Четыре элемента поля, используемые в качестве базиса представь ления, выписанного в столбце И, а именно Я = р*, v = Р*, = И и р, представляют собой полное множество двоично сопряженными элементов. Поэтому, используя этот базис, можно возводить в квад- рат и извлекать квадратные корни из элементов поля, использ} только перестановку позиций в представлении. Возведение в квадра выполняется с помощью левых циклических сдвигов, а извлечеь квадратного корня - с помощью правых циклических сдвиге! В отношении этих операций столбец 11 подобен столбцу 8. Одна» на этом аналогия кончается. Представление, выписанное в столбце II и представления в столбцах 7, 10 и 15, являются линейными: сло ние элементов может быть выполнено покомпонентно. Представ ние, приведенное в столбце 8, этим свойством не обладает; сложев двух элементов поля, заданных только представлением столбца составляет существенную проблему. В терминах представлеь столбцов 7, 10, И и 15 сложение является тривиальным, одна умножение значительно сложнее. Возведение в квадрат наибол просто выполнимо в терминах представления, выписанного в сто це И, но умножение двух произвольных элементов является бол сложным. Поэтому практически наиболее часто используется щ ставление элементов поля в виде двоичных многочленов от неко1 рого корня неприводимого двоичного многочлена.

В столбце 12 сделана попытка представления элементов не в виде степеней непримитивного элемента у, являющегося Kopi многочлена () и не являющегося корнем (). Представление oi бочно, так как у* = 1 и имеется только пять различных степене! Однако в столбцах 13 и 14 выписаны допустимые представлей поля через степени у и смежные классы. Различный выбор лиде смежных классов по подгруппе этих степеней в столбцах 13 и 14 ил1 стрирует тот факт, что два смежных класса либо не пересекав либо полностью совпадают.

В столбце 15 выписано представление элементов поля в виде двоичных многочленов от у степени < 4. Так как у - корень неприводимого двоичного многочлена четвертой степени, то это представ-юние допустимо несмотря на то, что этот многочлен не примитивен.

Интересно остановиться на изображенном на рис. 4.3 регистре сдвигов с обратной связью, предназначенном для умножения элементов поля на Y в данном представлении. При любом начальном


7*=73 + 72 + J

Р и с. 4.3. Регистр сдвига с обратной связью для умножения на у.

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

В столбцах 16 и 17 выписаны следы элементов поля GF (16) относительно подполей GF (2) и GF (4). След в GF {q") относительно GF {q), часто обозначаемый через Тг, определяется соотношением

Тг(х)= 2

Так как [Тг (х)]« = Тг (х) = Тг (х), то Тг (х) g GF q).

Как будет видно из теоремы 6.69, след дает информацию о решении в данном поле некоторых квадратных и кубических уравнений.

4.6. Алгебраическое замыкание

Так как к\ делит /! при к < /, то

GF (р) CZ GF (/>2!) с: GF {р) с: GF (р) сг ... .

Онределим GF{p) следующим образом: IqGFip"") тогда и только югда, когда I £GF (pi!) ддя всех достаточно больших п. Каждый элемент поля GF {р°°) имеет конечный порядок, хотя порядок самого ноля равен оо.

Как показывает теорема 4.61, поле GF {pj является алгебраически замкнутым.

4.61. Теорема. Каждый многочлен степени d над GF (р") имеет в GF {р°°) точно d корней.

Доказательство. Если / (х) - многочлен над GF {р"-), то найдется такое к, что все коэффициенты / (х) лежат в GF (/?").



Если g {х) - неприводимый делитель / {х) над GF (р) и степень g (х) равна i, то все корни g (х) лежат в поле GF (/)), являющемся при достаточно большом п подполем поля GF (р")- Следовательно, корни / (х) лежат в GF (р-). щ

*4.7. Определение минимальных многочленов

Если W - корень в GF (д") неприводимого многочлена степени тп над GF (q), то каждый элемент поля GF (д") может быть представлен в виде многочлена от w степени < т. Каждый элемент из GF (д™) является корнем некоторого минимального многочлена над GF (q), степень которого делит т. Часто бывает необходимо определить этот минимальный многочлен.

Например, предположим, что U7 - корень в GF [1) кругового многочлена (х) = х" + + 1. Так как мультипликативный

порядок числа 2 по модулю 9 равен 6, то w имеет в поле GF {2) 6 различных сопряженных элементов и (х) неприводим над GF (2). Предположим, что и = -\- w -\- \. Каков минимальный многочлен элемента и?

Наиболее простое решение этой задачи состоит в представлении элементов и, и, . . ., в виде многочленов от и; и нахождении их линейной комбинации, равной 0. Для настоящего примера имеем

1 = 1

и- i-\-w

U=r.l

u* = l и = u =

+ w + w + w + w, 4- + w*,

-\--\-, w + w-i- -t- w* + w.

Решая уравнение

[Mo, Ml, Мз, Ms, M„ Ms, Мб]

1 0 0 0 0 0

110 1 0 0 11 10 11 10 0 1 0 0 0 1 LO 1 1 1

1 1 1 1

= [0, 0, 0, 0, 0, 0],

получаем, что М = [1, 1, 1, О, О, 1, 1]. Таким образом, минимальный многочлен и равен 1 + х + х -f х + х**.

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

Если известно, что М (х) - минимальный многочлен элемента w, то минимальный многочлен элемента w - к, который мы будем обозначать через G (х), очевидно, задается равенством G (х) = М {х -\- к). Если к - целое число, то G (х) может быть вычислен по формуле бинома

{х+Ъ) = 2 Мп (х+кГ=. 2 " S ( " )

В поле характеристики р эти вычисления упрощаются, если для биномиальных коэффициентов известны сравнения по модулю р. Эти сравнения впервые были исследованы Лукасом в 1878 г.

4.71. Теорема Лукаса. Если р простое и N==j]Nip\ 0<Ni<p,

K=-.j\Ktp\ 0<Kt<p,

Доказательство. Согласно теореме 4.404,

(l-f-x) = 2 (l)x> = iAxPmodp.

ft=0

Продолжая вычисления, получаем

(1 -L x)"+ = (14 xr (1 + xf mod p.

np+A

m=0 i=0

Сравним коэффициенты при xP+.

если 0<Л<5<р. если 0<5<4<р.




[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.0133