Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
9N-т
1
ность для Дд (Л)
Рис. 6.6.2. Символы g(D), расположенные по кругу.
лишь рт — 1 возможных сочетаний символов; поэтому выходные символы любого m-разрядного регистра с обратной связью и с элементами из GF(p) являются периодическими, причем период не больше рт — 1. Так как при использовании для обратной связи примитивного многочлена достигается именно этот максимальный период, то такие регистры называются регистрами максимальной длины с обратной связью, а коды называются кодами максимальной длины.
Периодические последовательности, выходящие из регистра сдвига максимальной длины с обратной связью, называются псевдошумо-вымм или (р — ^-последовательностями. Если выбрать последовательность i символов (г < т), случайно выбирая ее места в указанной выше последовательности, то вероятность ненулевой последовательности будет равна рт~‘/(рт—1), а вероятность нулевой последовательности будет равна (рт~1 — 1 )/(рт — 1). Поэтому при больших т для широкого круга задач можно рассматривать результирующую по-
Элементы GF(24) Минимальные многочлены
как степени а как многочлены g(t)
8з Si Si go
0 0 0 0 0
1 0 0 0 1 D+ 1
а 0 0 1 0 D4 + Z>+ 1
а2 0 1 0 0 D4 + D +1
а3 1 0 0 0 D* + D3 + D2 + D + 1
а4 0 0 1 1 D4 + D + 1
а6 0 1 1 0 D4D + 1
а0 1 1 0 0 D4 + D3 + D2 + D+ 1
а? 1 0 1 1 D4 + D3+ 1
а8 0 1 0 1 D^ + D + l
а9 1 0 I 0 ?>4+D3 + D2 + D + 1
а10 0 1 1 I D2 + 0 + 1
а11 1 1 1 0 D4 + D3+ 1
а1'2 1 1 1 1 D4 + D3 + D2 + D+ 1
а13 1 1 0 1 ?>4 + Z>3+ 1
а14 1 0 0 1 ?>44-?3+1
Рис. 6.6.3. Элементы GF(24) как многочлены по модулю D*+D+ 1.
следовательность как случайную последовательность независимых равновероятных символов из GF (р). Эти последовательности часто используются для определения дальности целей и синхронизации в радиолокации и связи. Например, путем использования т-разряд-ного регистра сдвига можно в двоичном случае добиться разрешения 2т—1 различных значений дальности, или позиций синхронизации.
Теперь рассмотрим дуальный код для кода максимальной длины. В этом случае примитивный многочлен h (D) является порождающим многочленом для кода, a g (D) — проверочным. При этом столбцы проверочной матрицы можно трактовать как g (D) и (пг — 1) его первые циклические сдвиги. Поэтому множество строк проверочной матрицы является множеством последовательностей т следующих друг за дру-250
гом символов на кольце, представленном на рис. 6.6.2. Следовательно, все эти строки различны и получается циклическое представление кода Хэмминга.
Пример. Теперь обсудим более детально частный случай поля Галуа GF (24) отчасти для того, чтобы сделать теорию чуть менее абстрактной, а отчасти для того, чтобы рассмотреть, как на практике производятся операции е поле Галуа. В качестве представления GF (24) можно рассмотреть поле многочленов над GF (2) по модулю многочлена / (D) = D4 + D + 1. Разделив / (D) на все многочлены первой и второй степени над GF (24), можно убедиться, что / (D) — неприводимый многочлен. На рис. 6.6.3 элементы GF (24) представлены двумя способами, при одном из них
— степенями элемента поля а, соответствующего многочлену t, а при другом — в виде многочленов g(t) = g3ts +
+ git2 + git+go- В § 6.4 было указано, что сложение элементов поля производится путем сложения многочленов, а умножение — путем умножения многочленов по модулю / (t). Умножение на элемент
поля а = t выполняется осо- г, г с л \т -
,, Рис. 6.6.4. Устройство для умножения про-
бенно легко и может быть реа- извольного элемента поля на a=t в поле лизовано устройством, изоб- многочленов по модулю f(D):
раженным на рис. 6.6.4. По- а) /(D)=D4+D+1/(o)6>TeXrTbHbIii многочлен еле того как в регистр подан многочлен g (t), регистр сдвигается на один разряд вправо, что соответствует умножению на t, а затем приводится по модулю f(t) путем использования обратных связей. Читатель может проверить, что при последовательных сдвигах регистра, изображенного на рис. 6.6,4, последовательно генерируются многочлены, приведенные на рис. 6.6-3.
Покажем, что элемент поля а — t на рис. 6.6.3 имеет мультипликативный порядок 15 и потому примитивный . Для любого поля многочленов по модулю многочлена f (D) минимальным многочленом для элемента поля а = t является f (D) [так как вычет f (t) по модулю / (t) равен 0]; поэтому то обстоятельство, что а примитивный, означает, что нам повезло при выборе f (D) в качестве примитивного многочлена.
Минимальные многочлены для всех элементов поля GF (24) представлены на рис. 6.6.3. В задаче 6.29 разрабатывается способ вычисления этих минимальных многочленов, который основан на последующих результатах этого параграфа. Питерсон (1961) затабулировал эти минимальные многочлены для полей с характеристикой 2 вплоть до GF (217); поэтому, как правило, нет необходимости проделывать эти вычисления. В данном случае, однако, можно по крайней мере проверить, что приведенные на рис. 6.6.3 минимальные многочлены правильны. Например, минимальный многочлен для а10 записан в виде
