Коды максимальной длины и коды Хэмминга

Допустим, что минимальный многочлен некоторого примитивного элемента а из Из теоремы 6.6.5 следует, что остается минимальным многочленом примитивного элемента при любом представлении такой многочлен называется примитивным многочленом степени Циклический код с длиной блока для которого примитивный многочлен является проверочным многочленом, называется кодом максимальной длины. Кодовые слова такого кода можно порождать с помощью устройства, имеющего регистр сдвига и представленного на рис. 6.5.4 и вновь воспроизведенного на рис. 6.6.1.

Рис. 6.6.1. Кодер для кода максимальной длины.

Одно из кодовых слов в этом коде соответствует порождающему многочлену Покажем, что множество кодовых слов состоит из чисто нулевой последовательности и множества циклических сдвигов Так как число информационных символов в коде равно то число кодовых слов равно Так как число циклических сдвигов многочлена равно [включая сам то достаточно показать, что все циклические сдвиги различны. Для этого предположим, что циклические сдвиги дают одинаковые многочлены; Тогда получим

Это означает, что при некоторых

Разделив обе части равенства на и преобразовав выражение, получим

Наконец, в силу того, что получим, что примитивный элемент а не может быть корнем следовательно [согласно теореме 6.6.3], не является делителем Полученное противоречие показывает, что все циклические сдвиги различны.

Так как каждое кодовое слово определяется своими информационными символами, из приведенных выше рассуждений следует, что

всем циклическим сдвигам соответствуют различные начальные множества символов и что они исчерпывают все ненулевые комбинации символов из Наглядно это интерпретируется на рис. 6.6.2, где представлено кодовое слово соединенное своими концами в кольцо, так что циклические сдвиги могут считываться с кольца, если начинать считывание с различных его точек.

Каждая последовательность без пропусков в кольце, состоящая из символов, является информационной последовательностью одного-единственного циклического сдвига Кроме того, можно показать, что информационная последовательность циклического сдвига совпадает с последовательностью, хранящейся в регистре сдвига на рис. 6.6.1 (причем наиболее «продвинутый» по ходу часовой стрелки символ кольца соответствует символу левого разряда регистра), после сдвигов регистра при генерировании

Рис. 6.6.2. Символы расположенные по кругу.

Теперь заметим, что ровно из ненулевых последовательностей длины начинаются каждым из ненулевых элементов поля и ровно начинаются нулевым элементом. Поскольку каждый символ кодового слова, соответствующего является начальным символом для одной из указанных выше последовательностей длины то каждый ненулевой символ встречается в любом ненулевом кодовом слоге точно раз, а 0 встречается раз. Поскольку разность двух кодовых слов является другим кодовым словом, то отсюда следует, что каждая пара различных кодовых слов совпадает в позициях и отличается во всех остальных позициях. Можно показать (см. задачу 6.24), что рассматриваемый код обладает максимальным числом позиций, в которых могут отличаться все пары кодовых слов с данной длиной блока; поэтому такие коды весьма эффективны при исправлении ошибок.

Нетрудно убедиться, что если регистр сдвига на рис. 6.6.1 генерирует бесконечную последовательность символов, не останавливаясь после получения символов, то получится периодическая последовательность с периодом ; последовательные символы последовательности можно найти путем считывания по часовой стрелке символов с кольца, представленного на рис. 6.6.2. Так как будущий выход регистра сдвига с обратной связью зависит лишь от того, что хранится в нем в настоящий момент, то нетрудно убедиться, что после того как хранящиеся в нем символы совпадут с символами, хранящимися в какой-либо предыдущий момент времени, выходные символы регистра должны повторяться периодически. Если не считать нулевой последовательности, в -разрядном регистре могут храниться

лишь возможных сочетаний символов; поэтому выходные символы любого -разрядного регистра с обратной связью и с элементами из являются периодическими, причем период не больше как использовании для обратной связи примитивного многочлена достигается именно этот максимальный период, то такие регистры называются регистрами максимальной длины с обратной связью, а коды называются кодами максимальной длины.

Периодические последовательности, выходящие из регистра сдвига максимальной длины с обратной связью, называются псевдошумовыми или -последовательностями. Если выбрать последовательность символов случайно выбирая ее места в указанной выше последовательности, то вероятность ненулевой последовательности будет равна а вероятность нулевой последовательности будет равна Поэтому при больших для широкого круга задач можно рассматривать результирующую последовательность как случайную последовательность независимых равновероятных символов из

Рис. 6.6.3. Элементы как многочлены по модулю

Эти последовательности часто используются для определения дальности целей и синхронизации в радиолокации и связи. Например, путем использования -разрядного регистра сдвига можно в двоичном случае добиться разрешения различных значений дальности, или позиций синхронизации.

Теперь рассмотрим дуальный код для кода максимальной длины. В этом случае примитивный многочлен является порождающим многочленом для кода, проверочным. При этом столбцы проверочной матрицы можно трактовать как его первые циклические сдвиги. Поэтому множество строк проверочной матрицы является множеством последовательностей следующих друг за

другом символов на кольце, представленном на рис. 6.6.2. Следовательно, все эти строки различны и получается циклическое представление кода Хэмминга.

Пример. Теперь обсудим более детально частный случай поля Галуа отчасти для того, чтобы сделать теорию чуть менее абстрактной, а отчасти для того, чтобы рассмотреть, как на практике производятся операции в поле Галуа. В качестве представления можно рассмотреть поле многочленов над по модулю многочлена Разделив на все многочлены первой и второй степени над можно убедиться, что неприводимый многочлен. На рис. 6.6.3 элементы представлены двумя способами, при одном из них — степенями элемента поля а, соответствующего многочлену а при другом — в виде многочленов В § 6.4 было указано, что сложение элементов поля производится путем сложения многочленов, а умножение — путем умножения многочленов по модулю Умножение на элемент поля выполняется особенно легко и может быть реализовано устройством, изображенным на рис. 6.6.4. После того как в регистр подан многочлен регистр сдвигается на один разряд вправо, что соответствует умножению на а затем приводится по модулю путем использования обратных связей. Читатель может проверить, что при последовательных сдвигах регистра, изображенного на рис. 6.6.4, последовательно генерируются многочлены, приведенные на рис. 6.6.3.

Рис. 6.6.4. Устройство для умножения произвольного элемента поля на в поле многочленов по модулю б) произвольный многочлен степени

Покажем, что элемент поля на рис. 6.6.3 имеет мультипликативный порядок 15 и потому примитивный Для любого поля многочленов по модулю многочлена минимальным многочленом для элемента поля является [так как вычет по модулю равен 0]; поэтому то обстоятельство, что а примитивный, означает, что нам повезло при выборе в качестве примитивного многочлена.

Минимальные многочлены для всех элементов поля представлены на рис. 6.6.3. В задаче 6.29 разрабатывается способ вычисления этих минимальных многочленов, который основан на последующих результатах этого параграфа. Питерсон (1961) затабулировал эти минимальные многочлены для полей с характеристикой 2 вплоть до ; поэтому, как правило, нет необходимости проделывать эти вычисления. В данном случае, однако, можно по крайней мере проверить, что приведенные на рис. 6.6.3 минимальные многочлены правильны. Например, минимальный многочлен для записан в виде

Для того чтобы было корнем должно выполняться Так как то что приводит к соотношению складывая многочленные представления и 1, получаем, что утверждение действительно верно.

Для практического выполнения операций в произвольном поле Галуа обычно удобно представлять элементы поля как многочлены по модулю примитивного многочлена степени над с точки зрения реализации это означает представление каждого элемента в виде последовательности элементов в Как было показано, сложение в при этом соответствует сложению соответствующих последовательностей в

Рис. 6.6.5. Умножение элементов поля в поле многочленов по модулю

Умножение на специально выбранный элемент также. выполняется устройством, представленным на рис. 6.6.4. И, наконец, умножение двух произвольных элементов поля может производиться устройством, изображенным на рис. 6.6.5.

Вначале при выполнении умножения этим устройством регистр пуст, и находятся в регистрах соответственно. Затем регистры сдвигаются на одну позицию вправо таким образом, что в регистре будет многочлен Затем регистры вновь сдвигаются вправо. После этого в регистре будет храниться . После сдвигов регистров в регистре убудет или элемент поля Следует заметить, что для выполнения этим устройством умножения в необходимые время и сложность оборудования прямо пропорциональны