2.2.2. Построение полиномиальных кодов

Ранее в этом режиме полиномиальный -код был определен как множество всех многочленов степени или меньше, делящихся на Степень равна Например, если

то множество многочленов вида

образует -код. Заметим, что существует ровно восемь различных многочленов в соответствии с восемью различными способами выбора коэффициентов в поле GF (2). Один из способов применения этого кода состоит в том, чтобы взять в качестве информационных символов и выполнить соответствующие умножения. Результат будет

Устройство, производящее это умножение, показано на рис. 2.2. Хотя такой метод кодирования вполне пригоден, его недостаток состоит в том, что полученный код обычно оказывается несистематическим. (В данном примере код является систематическим в позициях 1, 5, 6; однако в общем случае это не так.)

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

Решив систему уравнений относительно и подставив результат в (2.9), получим кодовый многочлен вида

Этот кодовый многочлен имеет обычный вид кода с проверками на четность, и читатель может заметить, что если поменять местами первый и второй проверочные символы, то полученный код

Рис. 2.2. Схема для умножения произвольного многочлена на

будет совпадать с -кодом с проверками на четность, описанным в (2.1). С тем же успехом можно выбрать и другие множество информационных символов. Например, выбрав последние три символа, получим

Такой выбор обычно оказывается более предпочтительным по причинам, которые скоро станут ясными.

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

Второй метод, который, по существу, является объединением этих двух шагов, состоит в следующем. Предположим, что умножаем многочлен на получая Разделив полученный многочлен на найдем частное и остаток Заметим, что, прибавив остаток к делимому, получим кодовое слово (2.11) в систематическом виде. Эта процедура состоит в применении алгоритма Евклида, согласно которому делимое (частное) (делитель) остаток.

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

Рис. 2.3. Схема для одновременного умножения на и деления на

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

Схема, показанная на рис. 2.3, очень проста, поскольку все арифметические операции выполняются в поле GF (2). В общем случае кода над полем GF (q) следует выполнять также операции умножения. Предположим, что порождающий многочлен кода имеет вид где коэффициенты лежат в Тогда схема на рис. 2.3 должна быть изменена следующим образом. Прежде всего, все операции сложения должны быть заменены на сложение в GF (q) и каждая ячейка регистра сдвига должна содержать элемент из Далее, результат на выходе сумматора, формирующего член обратной связи, нужно умножить на Наконец, для каждого ненулевого член обратной связи должен быть умножен на Сумма полученного произведения с результатом выхода предыдущей ячейки является входным значением ячейки регистра меняется от О до Полученная обобщенная схема кодирования показана на рис. 2.4. Производя деление, легко показать, что эта схема дает требуемый остаток.

Полезной может оказаться еще одна точка зрения. Сделаем, чтобы схема, изображенная на рис. 2.3, начала работать таким образом, чтобы в самой левой ячейке появился символ 1. Производя в схеме несколько сдвигов и не подавая ничего на ее вход, будем получать содержимое регистров, показанное на рис. 2.5. Можно заметить, что полученные тройки совпадают со столбцами проверочной матрицы, и если остановиться после семи шагов, то полученная матрица будет совпадать с проверочной матрицей -кода Хемминга. Сделав меньше семи шагов, получим проверочную матрицу укорочения этого кода. Заметим также, что,

Рис. 2.4. Схема для умножения на к и деления на

Рис. 2.5. Регистр обратной связи и соответствующая последовательность состояний при поступлении на вход одного символа 1

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

Если подать на вход символ 1 и сделать один сдвиг, то в соответствующих ячейках появится набор После второго сдвига появится - набор после третьего и после четвертого 10 1. Эти четыре тройки совпадают с четырьмя строками проверочной части порождающей матрицы. При вводе в регистр последовательности 1000 (начиная с самого правого символа) получим проверочную последовательность Аналогично при вводе в регистр последовательности появятся проверочные символы 101. Кроме того, рассматриваемое устройство является линейным, так что при вводе в регистр последовательности 1001 результатом будет 011. Эти проверочные символы возникают при сложении первой и четвертой строк порождающей матрицы.

На практике схема,

Рис. 2.6. Кодер для кода, порожденного многочленом с использованием регистра сдвига с ячейками

изображенная на рис. 2.3, используется так, как показано на рис. 2.6. Кодируемая последовательность подается одновременно в канал и в кодер с включенной цепью обратной связи. Затем цепь обратной связи отключается и содержимое регистра подается в канал.