Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
235
Так как степень (D — а) равна 1, то степень г (D) равна 0 и потому г (D) является просто элементом поля г0. Подставляя а вместо D, получаем f (а) = г0. Поэтому, если f (а) = 0, то г„ = 0 и (D — а) является делителем f (D). Обратно, если (D — а) является делителем f (D), то имеем / (D) = (D — a)h (D) и / (а) = 0.
Теперь представим / (D) в виде произведения элемента поля и неприводимых множителей степени не меньше 1. Так как степень / (D) равна сумме степеней множителей, то существует не более п сомножителей. Это разложение единственно и, следовательно, f (D) имеет не более п корней в рассматриваемом поле. |
0 1 t ^+1 0 1 i t + 1
0 0 1 t t+1 0 0 0 0 0
1 1 0 t +1 t 1 0 1 t t+1
t t t +1 0 1 t 0 t t+1 1
t+1 t+1 t 1 0 14-1 0 t +1 1 t
Сложение * Умножение
Рис. 6.4.1. Поле многочленов в GF(2) по модулю D2+D+ 1.
Используем эти результаты, касающиеся многочленов, для конструирования нового примера конечного поля. Этот пример более важен, чем может показаться на первый взгляд; как будет показано в дальнейшем, он дает конкретное представление для любого конечного поля.
Пусть / (D) — неприводимый многочлен степени п над конечным полем GF (q)\ рассмотрим множество всех многочленов степени, не большей (л — 1) над GF(q). Пусть * означает специальную операцию над этими многочленами, которая дает вычет произведения многочленов по модулю f(D),
gl(D) *g2(D) = Rf(D) [&(?)&(?)]. (6.4.21)
Теперь покажем, что множество многочленов g(t) над GF(q), степени которых не превышают п — 1, образует поле с операциями обычного сложения многочленов и умножения * (неопределенная будет обозначаться в этом случае через t для напоминания о том, что рассматривается частное множество многочленов, степени которых не превышают п — 1, и со специальной операцией * умножения, в отличие от обычной операции умножения многочленов). Чтобы доказать, что получается поле, заметим, что аксиомы 1 и 3 непосредственно следуют из свойств сложения многочленов и умножения. Далее отметим, что при gi (0*ё2 (0 = 0 имеем
g1(D)g2(D)=f(D)h(D). (6.4.22)
Однако, так как многочлен f (D) неприводим и каждый из многочленов gi (D) и g2 (D) имеет степень, меньшую чем / (D), то из теоремы о единственности разложения следует, что либо gx (D) = 0, либо g2 (D) = 0. Отсюда следует, что аксиома 2'в теореме 6.4.1 справедлива и мы имеем поле. Так как каждый из коэффициентов g0, glt ..., gn_i
236
может быть любым из q элементов первоначального поля, то вновь полученное поле содержит qn элементов. Назовем это новое поле полем многочленов над GF (q) по модулю f (D). В рассматриваемом случае необходимо, чтобы многочлен f (D) был неприводимым, так как в противном случае f (D) = gy (D)g2 (D) для некоторых ненулевых и g2
и, следовательно, gx (t) *g2 (t) = 0, что противоречит (6.4.3).
Например, пусть f(D) = D2 + D + 1 является многочленом над GF (2). Тогда элементами поля по модулю f (D) служат многочлены О, 1, t, t + 1. На рис. 6.4.1 приведены таблицы сложения и * умножения. Например, чтобы найти t * t, воспользуемся алгоритмом Евклида; получим D2 — (D2 + D + 1)1 + (D + 1). Отсюда Rf (D) [D2] = = D + 1h^*^ = ^+1.
6.5. ЦИКЛИЧЕСКИЕ КОДЫ
В этом параграфе будет рассмотрен специальный класс кодов с проверкой на четность, известных под названием циклических кодов. Такие коды имеют два преимущества над обычными кодами с проверкой на четность: во-первых, операция кодирования для них легче в реализации и, во-вторых, математическая регулярность структуры кода делает возможным нахождение различных простых алгоритмов декодирования.
Прежде чем определить циклический код, обобщим коды с проверкой на четность на недвоичные алфавиты. Эти обобщенные коды будем называть линейными или групповыми, поскольку слово четность мало подходит для недвоичных алфавитов. Пусть и = (иъ и2, ..., Ul) — произвольная последовательность информационных символов, причем и; является элементом некоторого конечного поля GF(q). Линейным (N, Ь)-кодом называется такой код, в котором кодовое слово х = (хг, ..., xN), соответствующее и, является последовательностью N > L букв из GF (q) и образуется по правилу
L
хп= 3Zi“igi,n’> Kn<N, (6.5.1)
i= i
где элементы gi n произвольно выбираются среди элементов GF (q), а сложение и умножение являются операциями в GF (q).^ Как и раньше, элементы gh п будем представлять с помощью производящей матрицы G, как это показано на рис. 6.1.2, а, а образование кодовых слов будем описывать соотношением
х = u G. (6.5.2)
