Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
а.р1П — а = 0. (6.6.17)
Используя (6.6.17) и (6.6.12), получаем
Р = В (а) = В (аРт) = {В (а)]пт = ^т. (6.6.18)
Из (6.6.18) следует, что рт — 1 делится на порядок элемента р. Вместе с тем, так как р — примитивный элемент, его порядок равен рп — 1, и число рп — 1 должно быть делителем рт — 1. Выполнив это деление, получим
рт — 1 ^(рп—\)(рт~п + рт~2п + ...), (6.6.19)
откуда следует, что рт — 1 делится на рп — 1 тогда и только тогда, когда т делится на п. Таким образом, если Dрш~ 1 — 1 делится на / (D), то т должно делиться на п. Обратно, если т. делится на п, то рт — 1 делится на порядок элемента а, поскольку рп — 1 делится на порядок элемента а. Следовательно, а — корень Dpm-1 — 1 и DPm~l — 1 делится на минимальный многочлен / (D) элемента а. |
Из этой теоремы следует, что при любых т ^ 1 все неприводимые делители DPm~l — 1 над GF (р) имеют степени, равные т или делителям т.
254
Теорема 6.6.8. Для любого положительного целого числа т и любого простого числа р существуют неприводимые многочлены в GF (р) степени т и, следовательно, поля с р"‘ элементами.
Доказательство этой теоремы основывается на том факте, что не существует достаточного числа многочленов степени т!2 или меньше, составляющих все делители многочлена Dpm~l — 1. Прежде чем использовать это соображение, нужно доказать следующую лемму.
Лемма. Многочлен Dpm~i — 1, рассматриваемый как многочлен над GF (р), не имеет кратных нормированных неприводимых делителей положительной степени.
Доказательство. Предположим, что / (D) — нормированный неприводимый делитель п-й степени в разложении Dp"1-1 — 1. Так как т делится на п, то рт — 1 делится на рп — 1 [см. (6.6.19)]. Поэтому
Dpm~l — 1 = (Dpn~l-l) A (D), (6.6.20)
где
A (D) = D(pm- 0-(рп- О -f_ фт- 0-2 (р»- 0 _j_ _ + 1 _ (6.6.21)
Существование /(D) предполагает существование поля Галуа GF (рп) и поэтому / (D) не может быть кратным делителем (DPn~1 — 1). Кроме того,/(D)—минимальный многочлен некоторого элемента а из GF (рп), поэтому если A (D) делится на / (D), то а — корень A (D). Вместе с тем, так как рт — 1 делится на порядок элемента а, то а(рт-\)-црп-\) _ j = о.
Следовательно,
А (а) ¦-= 1 4~ 1 + ...-}-1, (6.6.22)
где число слагаемых в правой части (6.6.22) равно
(рт —\)1(рп—\) = рт-п + рт~2п + ... + \.
Так как А (а) равно остатку от деления этого числа слагаемых на р, то А (а) — 1. Поэтому а не может быть корнем A (D) и A (D) не может делиться на / (D), что завершает доказательство. | Доказательство теоремы. Пусть at равно числу нормированных неприводимых делителей многочлена Dpт~1 — 1, степень которых равна m/i. Так как сумма степеней этих делителей равна рт— 1, то получим
pm~l =-_aLm + a2-j + as^-\-... +ат. (6.6.23)
Так как все неприводимые делители степени m!i являются делителями многочлена DPmlt~l — 1, то
рт—l<axm-f- S [pmIi— 1 ] -
/ = 2
i : —r — целое
(6.6.25)
Заменяя в (6.6.25) m/г на / и строя границу сверху с помощью суммирования по всем /, 1 ^ ^ т/2, получаем
1 < ах т -f-
plm/2J+ 1 —р р— 1
т
Т-Г
Ясно, что это неравенство удовлетворяется при ах > 0, что завершает доказательство. I
6.7. БЧХ-КОДЫ
Коды Боуза, Чоудхури и Хоквингема (БЧХ), открытые Хоквинге-мом(1959) и независимо от него Боузе и Чоудхури (1960), представляют собой класс циклических кодов, которые обладают весьма мощной способностью исправлять ошибки и одновременно допускают простые алгоритмы декодирования. Наиболее простым примером БЧХ-кодов являются двоичные коды, но совершенно аналогично можно в качестве алфавита выбирать элементы произвольного поля Галуа GF (q). Порождающий многочлен для этих кодов определяется в терминах некоторого расширения GF (q,n) поля GF (q). Пусть а — элемент GF (qm), мультипликативный порядок которого равен N) числа г ^ 0 и d,
2 ^ d ^ N — произвольные целые числа; пусть далее /г (D), fr + 1 (D), ..., fr+d-2 (D) — минимальные многочлены для о/, аг+1, аг+а~2.
Для каждого набора определенных выше параметров (т. е. для q, т, а, г и d) существует БЧХ-код; его порождающий многочлен определяется равенством
S (D) = НО К [/г (D), fr+1(D), .... fr+d-2m, (6.7.1)
где НОК означает наименьшее общее кратное.
Длина блока в коде по определению равна N, мультипликативному порядку элемента а. Так как каждый из элементов аг, ..., ar+d~2 является корнем DN — 1, то многочлен DN— 1 делится на каждый из многочленов fr (D), ..., fr+d-2 (D) (см. теорему 6.6.3) и, следовательно, на g (D), что необходимо для циклических кодов. В неинтересном случае, когда g (D) = DN — 1, последовательность, целиком состоящая из нулей, по определению, выбирается в качестве единого кодового слова.
