3.3.3. Схемы для полиномиальной арифметики в GF(2^r)

На материале этого раздела основана теория кодов, обнаруживающих и исправляющих ошибки, обсуждаемая в гл. 4 [мы придерживаемся книги (Afrati, 1985)]; однако тема довольно технична, и если читатель не знаком с регистрами сдвига, то для хорошего понимания от него могут потребоваться дополнительные усилия [см.-, например, (Taub, 1982)].

Схемы, которые мы будем обсуждать, в основном состоят из элементов, показанных на рис. 3.3.1. Сумматор выводит сумму двух значений, представленных на входе, а умножитель выводит произведение значения, представленного на входе, на константу а. Элемент памяти «сохраняет» значение, представленное на входе, а потом выводит его.

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

Рис. 3.3.1. Строительные блоки схем.

Рис. 3.3.2. Схема для умножения полиномов.

задержки рассматривается как этап регистра сдвига. Более того, поскольку мы имеем дело с элементами поля GF(2), сумматор — это просто схема исключающего ИЛИ, а умножитель — просто соединение, если константа равна 1, или разрыв соединения, если константа равна нулю.

Ввод и вывод в регистре сдвига выполняются последовательно. Когда вводится или выводится полином, то на вход или выход подаются только коэффициенты [которые принадлежат полю GF(2)] по одному элементу за такт. Отметим, что сначала передаются коэффициенты при самых высоких степенях. (Это происходит потому, что при делении мы сначала работаем с коэффициентами при слагаемых наивысшей степени в делимом.) Например, полином

вводится в регистр сдвига или выводится из него как последовательность элементов поля GF(2), в которой первым идет одним тактом позже — и т. д.

Ниже представлены схемы для умножения или деления произвольного полинома на другой данный полином. Схема, представленная на рис. 3.3.2, умножает любой полином

появляющийся на входе, на данный полином

Предполагается, что изначально все элементы задержки содержат «0»; кроме того, за коэффициентами полинома , которые вводятся последовательно, следует раз «0».

Очевидно, что вычисляемое произведение равно

Как видно из рис. 3.3.2, когда первый коэффициент а полинома появляется на входе, первый коэффициент полинома появляется на выходе. В этот момент все элементы задержки содержат . Через такт на входе появляется а содержится в первом элементе памяти, а остальные элементы памяти содержат выход равен что совпадает со вторым коэффициентом произведения Аналогично, после двух тактов появляется на входе, элементы памяти содержат и на выходе появляется третий коэффициент полинома Этот процесс продолжается таким же образом. После тактов регистр сдвига содержит и предпоследний коэффициент полинома появляется на выходе, а именно После к тактов регистр сдвига содержит , и выход - , последний коэффициент произведения

Другая схема для умножения показана на рис. 3.3.3. Коэффициенты произведения формируются в элементах памяти регистра сдвига. Когда первый коэффициент появляется на входе, на выходе появляется и все элементы памяти содержат «0». Через такт регистр сдвига содержит вход — а выход — это что является вторым коэффициентом произведения . В следующем такте регистр сдвига содержит вход есть , а выход — это третий коэффициент полинома . Процесс продолжается таким образом и дальше.

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

Рис. 3.3.3. Другая схема для умножения полиномов.

Рис. 3.3.4. Полиномиальный умножитель с двумя входами.

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

Схема представленного типа может иметь несколько входов. Например, схема на рис. 3.3.4 имеет два входа, и выход равен

где

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

Схема для деления произвольного полинома, скажем, на полином представлена на рис. 3.3.6. Регистр содержит вначале все

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

Рис. 3.3.6. Схема для деления полиномов.

Выход равен для первых тактов. Затем появляется первый ненулевой выход, это — первый коэффициент частного. Для каждого коэффициента частного полином должен вычитаться из делимого [Напомним, что в GF(2) сложение совпадает с вычитанием.] Это достигается с помощью линий обратной связи. После тактов частное полностью появляется на выходе, а остаток находится в элементах памяти регистра. Это легче понять, если рассмотреть схему на рис. 3.3.7, взять в качестве делимого полином и выполнить деление.

Рис. 3.3.7. Схема для деления на

Приведенные выше схемы легко приспособить для полиномиальной арифметики по модулю Регистр, показанный на рис. 3.3.6, может запоминать элементы поля GF(2), которые можно рассматривать как коэффициенты полинома

степени . После сдвига содержимого регистра на единицу вправо (или по истечении одного такта) полином в памяти

становится равным

где последнее слагаемое — результат линии обратной связи. Это можно переписать в виде

что совпадает с

Чтобы сделать изложение яснее, рассмотрим пример. Возьмем и поле GF(2). Полином с-примитивен и его корень а — примитивный корень поля т.е. все элементы поля получаются из первых 16 степеней а. Соответствующий регистр показан на рис. 3.3.8. Если поместить «1» в первый слева элемент памяти и в остальные, то последовательные сдвиги дадут нам представления различных степеней а в том же самом виде, как они даны в табл. 3.3.1. Отметим, например, что выход «1» из последнего элемента памяти соответствует что заменяется на а с помощью линии обратной связи.

Рис. 3.3.8. Схема, которая производит вычисления в

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

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

что и является ответом.