“Работа в системе остаточных классов” (стр. 2 из 3)

Приведённые факторы, наряду с преимуществами модулярных

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

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

Существует достаточно большое количество подходов к реализации сумматоров по модулю m. Далее будут рассмотрены наиболее типичные и простые схемы модулярного суммирования (рис. 2).

Первая из них вычисляет модульную сумму

с помощью таблицы размером Для двух соответствующих элементов просто выбирается ответ из большой таблицы. Это решение очень хорошо подходит для случаев, когда длина слова мала, например, n 4 .

Для больших модулей, память LUT была бы значительного размера и другие схемы для суммирования оказываются в этом случае более предпочтительными. Следующее предложение основывается на обычном суммировании x + y и одной таблицы, содержащей все возможные значения для

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

Третья схема суммирования является самой распространённой и наиболее предпочтительной в большинстве случаев. В этой схеме используется два сумматора и мультиплексор для выбора результата в соответствии с выражением:

(9)

Умножители на основе закона квадратов (рис. 3) вычисляют модулярное произведение

с помощью следующего равенства (закон квадратов):

(10),

где 0

x, y < m . Модулярное умножение на основе (10) можно записать следующим образом:

, , (11)

и произведение

(12)

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

, гарантируется только в случае, если 2 не делит m (т.е. m – нечётно). Тэйлор в своей работе привёл доказательство теоремы, показав, что даже если при вычислении (11) будут промежуточные дроби, они взаимно уничтожатся. Умножители, основанный на арифметике указателей является сравнимой альтернативой по сложности и скорости умножителям, основанным на законе квадратов. Их использование ограничено простыми модулями и основывается на осуществлении преобразования в степенную форму (так называемое степенное исчисление), в котором умножение может более быстро осуществляться посредством операции суммирования.

Метод работы этого умножителя связан с математическими свойствами полей Галуа обозначаемых GF(p), где p – простое число. Все ненулевые элементы поля Галуа могут быть получены путём многократного возведения в степень примитивного элемента – порождающёго /?/ поле GF(p) элемента g

.

Это свойство полей Галуа можно использовать для умножения в GF(m

) благодаря использованию изоморфизма между мультипликативной по модулю m группой Q = {1, 2,…, m -1}, и аддитивной по модулю (m - 1) группой I = {0, 1,…, m - 2}. Этот изоморфизм может быть установлен следующим образом: : (13) и умножение над полем GF(m) может производиться по формуле: (14). Таким образом, умножение двух чисел q и q можно производить, вычисляя модулярную сумму соответствующих указателей i и i а затем проводя обратное преобразование из степенного пространства в исходный вид. Необходимо специально

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

Степени i

и i для q и q , соответственно, могут быть заранее вычислены и помещены в LUT. Сложение степеней выполняет сумматор по модулю m - 1. Обратное преобразование из степенного представления i и i в исходное q и q , также может быть выполнено с помощью предварительно вычисленных LUT.

Рассмотрим в качестве примера работу этого умножителя на примере умножения двух чисел 14 и 28 по модулю 31. Так как 31 – простое число, существует порождающий элемент g, дающий возможность ассоциировать каждый элемент мультипликативной группы Q = {1, 2,…, 31} с элементом

аддитивной группы I = {0, 1,…, 30} . Соответствие задаётся выражением

, где , и , . Эта таблица в сущности и представляет собой содержание LUT размером прямого и обратного преобразования в умножителе, изображенном на рис. 4.

Рассмотрим работу умножителя Галуа (рис. 4, рис. 5, табл. 1) на

примере умножения

. Итак, и , а произведение получается посредством суммирования соответствующих им элементов i и i , выбранных из табл. 1. Таким образом, указатели оказываются i = 22 и i = 16 и

= 8. Элементу в табл. 1 соответствуют , следовательно

Таблица 1. Содержание LUT-таблицы для умножителя Галуа по модулю 31

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	0	24	1	18	20	25	28	12	2	14	23	19	11	22	21
	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
	6	7	26	4	8	29	17	27	13	10	5	3	16	9	15