Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
241
Рис. 6.5.3. Проверочная матрица циклического кода.
В случае двоичных циклических~кодов техническая реализация этого устройства довольно проста; устройство включает в себя лишь L-разрядный двоичный регистр сдвига и сумматоры по модулю 2. Умножение на ht производится просто путем размыкания цепи при/ij = О и замыкания — при h г = 1. В случае циклических кодов в произвольном поле цепь немного более сложная, поскольку требуются устройства, выполняющие сложение и умножение элементов в этом поле.
Рис. 6.5.4, L-разрядный кодер циклического кода.
Теперь обсудим другую реализацию циклического кодера, для которой требуется регистр сдвига на N — L разрядов. Ясно, что выбор той или иной реализации зависит от того, велико или мало отношение числа информационных символов к длине блока. Информацион-
-*>{+)* xi 4+)* xl/-z —
Рис. 6.5.5, (N — L) -разрядный кодер циклического кода.
ные символы в кодовом слове могут быть представлены в виде многочлена 1 + ... + Xiv-LDn-1. Согласно алгоритму Евклида,
XN-1 DN-1 + ... + xN-L DN~L = a(D)g (D) + r (D), (6.5.17)
где степень r (D) не превышает N — L — 1.
Из (6.5.17) следует, что xN^DN~l + ... + xN_LDN~L — г (D) является кодовым словом, а —г (D) — многочлен, соответствующий проверочным символам. Любое устройство, совершающее деление xN^DN~l + ... + xn^lDn-l на g (D), позволяет найти г (D); такое устройство представлено на рис. 6.5.5.
Первоначально в регистре сдвига этого устройства хранятся первые N — L информационных символов, причем правые разряды оста-
242
ются свободными, если число информационных символов меньше чем N — L. Первая операция состоит в вычитании из xL_1+j произведений g)XN_i при — L — 1, после чего регистр сдвигается
на одну позицию вправо, и, если возможно, добавляется новый информационный символ. Символ xN^x больше не требуется для вычисления г (D) и поэтому сбрасывается. Можно показать, что хранящиеся в этот момент в разрядах регистра сдвига числа точно совпадают с теми числами, которые получились бы после первого вычитания, если бы деление многочленов производилось на бумаге. Этот цикл повторяется L раз; рассуждая, как в предыдущем случае, можно убедиться, что после этого в регистре останется многочлен г (D); при этом слагаемые более высокого порядка хранятся в правых разрядах. После этого ключ в правом углу на рис. 6.5.5 переводится в вертикальное положение и — г (D) считывается и передается в канал.
Из свойства линейности рассмотренной цепи следует, что аналогичный результат может быть получен и в том случае, когда первоначально регистр пуст; при этом информационные символы поступают в устройство в точке А через сумматор, который прибавляет поступающие информационные символы к выходным символам самого правого разряда регистра.
6.6. ПОЛЯ ГАЛУА
В настоящем параграфе будет изучена несколько подробнее, чем в § 6.4, структура полей Галуа. Полученные результаты потребуются нам в следующем параграфе, посвященном кодам Боуза—Чоудхури — Хоквингема (БЧХ); они играют главенствующую роль во многих проводящихся в настоящее время исследованиях по технике алгебраического кодирования.
Начнем с изучения мультипликативного порядка различных ненулевых элементов поля Галуа GF (q), состоящего из q элементов. Так как ненулевые элементы поля, обозначенные, допустим, символами аь а2, ..., а9_1( образуют абелеву группу по умножению в рассматриваемом поле, то из теоремы 6.3.2 следует, что каждый из этих элементов имеет мультипликативный порядок, на который делится число <7 — 1. Поэтому а?-1 — 1 = 0 при всех г, 1 ^ i ^ q — 1. Отсюда следует, что каждый элемент at является корнем многочлена D4—1 — 1 [рассматриваемого здесь в качестве многочлена над GF (<7)]. Так как степень этого многочлена равна q — 1 и известны ровно q — 1 его различных корней, т. е. аь ..., а?_1( то получим
ч— 1
Оч-1-1 = П (D — аг). (6.6.1)
1= 1
Например, в поле целых чисел по модулю 3 это равенство будет D2 — 1 = (D — 1) (D — 2),
которое, очевидно, удовлетворяется, если производить сложение и ум ножение целых чисел по модулю 3.
243
Выше было показано, что все ненулевые элементы поля, состоящего из q элементов, имеют мультипликативный порядок, на который делится число q — 1. Примитивным элементом поля из q элементов называется элемент, у которого мультипликативный порядок точно равен q— 1. Если можно найти некоторый примитивный элемент поля, допустим а, то последовательность а, а2, ..., а1?-1 содержит все ненулевые элементы поля, а мультипликативная группа ненулевых элементов поля является циклической. При этом ясно, что не представляет труда нахождение мультипликативного порядка любого элемента, являющегося степенью элемента а (см. задачу 6.26).
