Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
^ (?-1)г ( Л'') <qN~L. t = 0 ' 1 /
Подставляя вместо е величину (dm[n—1) J/2, получаем требуемую границу.
II. Рассуждая, как и в задаче 6.3(b), нетрудно убедиться, что самое большее {q — 1 )lq доля кодовых слов содержит в любой данной позиции ненулевые
символы. Так как число кодовых слов равно qL и в блоке имеется N символов,
то общее число ненулевых символов во всех кодовых словах не превышат NqL(q —
— 1 )Iq. Поскольку число ненулевых кодовых слов равно qL —1, то вес по меньшей мере одного из них меньше среднего веса, или
, 'N (д— 1) qL
&min ^ г
Я qL — 1
Рассматривая совокупность q1 кодовых слов, у которых первые L — / символов нулевые, с помощью тех же рассуждений получаем
(N— L-\-j)(q—1) qj
dmin <---------------------------- при любом /, 1 < / < L.
q qJ— 1
Преобразуя это выражение, получаем
. т . qdmin .
N — L > ------- 1 —q-J)—i.
q—l
Положив /= |_ log, (qdmin) J, получим
N — L > q-^~ — —+ * — log, (qdmin), (1)
q—l q—l
где
* = logq (qdmin) |_ log, {qdmin) _I- (2)
Отсюда видно, что x принадлежит интеовалу (0,1). В этом интервале функ-
qx
ция — q_________j "Ь х выпукла ^ по х и принимает при х = 0 и при х = I значение
— 1 /(q — 1); поэтому она ограничена снизу величиной —11{q — 1). Используя
эту оценку, из (I) будем иметь
,, . qdmin 1 , .
N — L >---------- --—log, (qdmin)-
q—l
646
111 v Воспользуемся процедурой построения, отличающейся от процедуры построения в задаче 6.8. лишь тем, что элементы строк являются теперь элементами GF(q). Общее число линейных комбинаций из d — 2 или меньшего числа строк, выбираемых из N строк, равно
d~2 / д?
;= о V f
В момент окончания процедуры построения эта сумма должна превысить qN~~L, и для построенного таким образом кода dmtn > d, давая требуемую границу.
6.25. Нужно показать, что
D* — 1 = (D — 1 )(D - t)[D - (t + 1)], где обе части равенства являются многочленами по D над полем GF(4) из элементов {0,1, t, t + 1} со сложением и умножением, определяемыми на рис. 6.4.1. Производя умножение в правой части, получаем
D3 + L>2[-1 - t - (t + 1)] + D[t + (/ + 1) + t(t + 1)] - t(t + 1). Выполнив операции в данном поле, получим, например, что t(t + 1) = 1, и приведенное выше выражение сводится к D3 — 1, что и требовалось установить.
6.26 (а) Так как элемент а примитивный, то ап = 1 тогда и только тогда, когда п кратно q ¦— 1, и следовательно, а,п = 1 тогда и только тогда, когда in кратно q — 1. Порядок элемента а1 равен наименьшему п > 0, при котором а1П = 1 или, другими словами, наименьшему п > 0, такому, что in кратно q — 1. Определим j равенством q—1=[НОД(9— 1, /)]/.
Заметим, что / и i взаимно просты, так что п (порядок а1) должен быть кратен j и, следовательно, п > /. Вместе с тем ij кратно q — 1, так что п = / = (q — 1) /НОД (q — 1, /)• Из того, что i (q — 1) = [НОД (г, q —
— 1)] [НОК ((, <7— 1)], следует, что порядок аг также равен [HOK(t, q — 1)]/(.
(б) Если q — 1 делится на п, то порядки следующих п элементов а^— а2(? —1)/«( ^ an(q — i)/n _ j являются делителями п и эти элементы, как
нетрудно понять, образуют циклическую группу по умножению. Вместе с тем эти элементы являются единственными элементами, порядки которых являются делителями п, поскольку из пункта (а) следует, что если порядок а‘ делит п, то НОД (q — 1, () = m(q ¦— 1)/я при некотором гп, которое является делителем п. Это означает, однако, что i кратно m(q — 1)/я; следовательно, а1 является одним из элементов, рассмотренных выше.
6.27. (а) Пусть f(D) — минимальный многочлен элемента а над GF(p). Рассмотрим множество элементов
P = ... -Wo a0, (1)
где г0, гх.г'т-i — произвольные целые элементы поля. Число таких элементов
равно рт и они все различны [аналогично (6.6.7)]. Вместе с тем, так как ат = ш— 1
= 2 fioс', то рассмотренное выше множество замкнуто по умножению и сложению.
г=0
Кроме того, (р — 1) Р = — Р и Рр —2 Р = 1, так что р-1 = ~2; отсюда
следует, что обратные элементы по сложению и умножению принадлежат множеству. Таким образом, рассмотренное выше множество образует подполе из рт элементов. Оно является минимальным подполем, содержащим а, так как включает лишь а, целые элементы поля и комбинации этих элементов.
