Проектирование модулярного сумматора и умножителя

курсовая работа

2.2 Выбор модели умножителя по модулю m

Умножители на основе закона квадратов (рис. 2.2 (а)) вычисляют модулярное произведение|x*y|mс помощью следующегоравенства (закон квадратов):

(2.1)

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

(2.2)

и произведение|x*y|mможно вычислять по формуле:

(2.3)

Существование операции деления на 2 ставит под угрозу целочисленность промежуточных вычислений и, соответственно, правильность результата после использования таблиц подстановок. Более того, существование обратного по умножению по модулю mдля 2 элемента,, гарантируется только в случае, если 2 не делит m (т.е. m - нечётно). Тэйлор в работе [11] привёл доказательство теоремы, показав, что даже если при вычислении (2.2) будут промежуточные дроби, они взаимно уничтожатся.

Умножители, основанный на арифметике указателей [12, 13] является сравнимой альтернативой по сложности и скорости умножителям, основанным на законе квадратов. Их использование ограничено простыми модулями и основывается на осуществлении преобразования в степенную форму (так называемое степенное исчисление), в котором умножение может более быстро осуществляться посредством операции суммирования.

Метод работы этого умножителя связан с математическими свойствами полей Галуа [14, 15], обозначаемых GF(p), где p -простое число. Все ненулевые элементы поля Галуа могут быть получены путём многократного возведения в степень примитивного элемента - порождающего поле GF(p) элемента gj. Это свойство полей Галуа можно использовать для умножения в GF(mj)благодаря использованию изоморфизма между мультипликативной по модулю mj группой Q = {1,2,…,m -1}, и аддитивной по модулю (mj-1)- группой I ={0,1,…,m - 2}. Этот изоморфизм может быть установлен следующим образом:

(2.4)

и умножение над полем GF(m) может производиться по формуле:

(2.5)

Рассмотрим в качестве примера работу этого умножителя на примере умножения двух чисел 14 и 28 по модулю 31.

Так как 31 - простое число, существует порождающий элемент g, дающий возможность ассоциировать каждый элемент мультипликативной группы

Q = {1,2,…,31} с элементом аддитивной группы I ={0,1,…,30}. Соответствие задаётся выражением В табл.1 рассчитано соответствие между элементами группы Q и соответствующей степенью из аддитивной группы I. Эта таблица в сущности и представляет собой содержание LUT размером 25?5прямого и обратного преобразования в умножителе, изображенном на рис. 2.2 (б).

Рассмотрим работу умножителя Галуа (рис. 2.2 (б), рис. 2.2 (в), табл. 1) на примере умножения |14 ? 28 |31. Итак, qj= 14 и qk= 28, а произведение |qj ? qk |31получается посредством суммирования соответствующих им элементов ijи ik, выбранных из табл. 1.Таким образом, указатели оказываются ij= 22 и ik= 16 и

На рис. 2.2 (в) показано, каким образом происходит умножение чисел 14и 28 по модулю 31 по схеме, изображённой на рис. 2.2 (б). Для простоты две таблицы LUT1 и LUT2 объединены в одну и представляют собой таблицы, переводящие умножаемые числа в степенное представление по табл. 1, а в качестве сумматора выступает простой модулярный сумматор, изображённый на рис. 2.1 (а). LUT3выполняет сложение по модулю 30, а LUT4 переводит результат из степенного представления обратно в первоначальный. LUT4представляет собой табл. 1, только отсортированную по in. На рис. 2.2 (и) ADDR на входе таблицы и [ADDR] на выходе показывают, что значение, поступившее на вход таблицы, рассматривается в качестве линейного адреса элемента, который будет выдан на выход таблицы, т.е. [ADDR] - это содержимое ячейки таблицы по адресу ADDR.

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

Так же, нельзя исключать использования стандартных схем умножения чисел с фиксированной запятой. Их применение целесообразно при малой разрядности операндов. На рис. 2.2 (г) приведена схема умножения чисел I способом с ФЗ в ПК. Главным недостатком данной схемы является после то, что после перемножения чисел, результат, выходящий за пределы основания, нуждается в корректировке, т.е. выделении остатка от деления.

Пример: А = 120 = (59), В = 104 = (43), p = 61.

А*В= (59*43) mod61 = 2537 mod61 = (36).

В данном примере для получения произведения необходимо было бы 41 раз вычесть основание 61 из 2537 или разделить 2537 на 61, что впоследствии привело бы к значительному усложнению схемы.

Исходя из недостатков первой и третьей схем, в данном курсовом проекте используется вторая - схема умножителя Галуа.

Делись добром ;)