Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Теорема 6.6.5. Все поля Галуа с рп элементами изоморфны данному полю многочленов над GF(p) по модулю неприводимого многочлена п-й степени.
247
Коды максимальной длины и коды Хэмминга
Допустим, что /г (D) — минимальный многочлен некоторого примитивного элемента а из GF(pm). Из теоремы 6.6.5 следует, что h (D) остается I минимальным многочленом примитивного элемента при любом представлении GF{pm)\ такой многочлен называется примитивным многочленом степени т. Циклический код с длиной блока N--рт — 1, для которого примитивный многочлен h(D) является проверочным многочленом, называется кодом максимальной длины. Кодовые слова такого кода можно порождать с помощью устройства, имеющего регистр сдвига и представленного на рис. 6.5.4 и вновь воспроизведенного на рис. 6.6.1.
Одно из кодовых слов в этом коде соответствует порождающему многочлену g (D) = [Dpm~l — 1 ]/h (D). Покажем, что множество кодовых слов состоит из чисто нулевой последовательности и множества циклических сдвигов g (D). Так как число информационных символов в коде равно т, то число кодовых слов равно рт. Так как число циклических сдвигов многочлена g (D)! равно рт — 1 [включая сам g (D)], то достаточно показать, что все циклические сдвиги g (D) различны. Для этого предположим, что i-й и й циклические сдвиги дают одинаковые многочлены; 0 scC i < j < рт — 1. Тогда получим
RDpm- 1 _i
Это означает, что при некоторых a (D) и b (D)
Dl g(D) — a(D) [Dp’n~l— 1] =
= D>g(D) — b(D)[DPm~'- 1].
Разделив обе части равенства на g (D) и преобразовав выражение, получим
[b(D)—a(D)]h (D) = D> — Dl = Dl [ZV— 1J.
Наконец, в силу того, что j — i < рт — 1, получим, что примитивный элемент а не может быть корнем D>-1 — 1 и, следовательно [согласно теореме 6.6.3], h (D) не является делителем Di~l — 1. Полученное противоречие показывает, что все циклические сдвиги g (D) различны.
Так как каждое кодовое слово определяется своими т информационными символами, из приведенных выше рассуждений следует, что
248
всем циклическим сдвигам g (D) соответствуют различные начальные множества т символов и что они исчерпывают все рт — 1 ненулевые комбинации т символов из GF (q). Наглядно это интерпретируется на рис. 6.6.2, где представлено кодовое слово g (D), соединенное своими концами в кольцо, так что циклические сдвиги g (D) могут считываться с кольца, если начинать считывание с различных его точек.
Каждая последовательность без пропусков в кольце, состоящая из пг символов, является информационной последовательностью одно-го-единственного циклического сдвига g (D). Кроме того, можно'пока-зать, что информационная последовательность t-ro циклического'сдви-га g (D) совпадает с последовательностью, хранящейся в регистре сдвига на рис. 6.6.1 (причем наиболее «продвинутый» по ходу часовой стрел ки символ кольца соответствует символу левого разряда регистра), после i сдвигов регистра при генерировании g (D).
Теперь заметим, что ровно pm—1 из рт — 1 ненулевых последовательностей длины т начинаются каждым из р — 1 ненулевых элементов поля GF (р) и ровно рт~1 — 1 начинаются нулевым элементом. Поскольку каждый символ кодового слова, соответствующего g (D), является начальным символом для одной из указанных выше последовательностей длины т, то каждый ненулевой символ встречается в любом ненулевом кодовом слове точно рт~1 раз, а 0 встречается рт~1 — 1 раз. Поскольку разность двух кодовых слов является другим кодовым словом, то отсюда следует, что каждая пара различных кодовых слов совпадает в рт~1 — 1 позициях и отличается во всех остальных позициях. Можно показать (см. задачу 6.24), что рассматриваемый код обладает максимальным числом позиций, в которых могут отличаться все пары кодовых слов с данной длиной блока; поэтому такие коды весьма эффективны при исправлении ошибок.
Нетрудно убедиться, что если регистр сдвига на рис. 6.6.1 генерирует бесконечную последовательность символов, не останавливаясь после получения рт — 1 символов, то получится периодическая последовательность с периодом рт — 1; последовательные символы последовательности можно найти путем считывания по часовой стрелке символов с кольца, представленного на рис. 6.6.2. Так как будущий выход регистра сдвига с обратной связью зависит лишь от того, что хранится в нем в настоящий момент, то нетрудно убедиться, что после того как хранящиеся в нем символы совпадут с символами, хранящимися в какой-либо предыдущий момент времени, выходные символы регистра должны повторяться периодически. Если не считать нулевой последовательности, в /л-разрядном регистре могут храниться
249
Инсрорнаи, ионнаь последователь -ность для ^
n I n Информационная
Уо V Q {^-^последователь-
V иПГ'ГГИ-
О
