Технологическая автоматизация

Методы цифровых технологий

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

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

(2.1)

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

(2.2)

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

(2.3)

Рисунок 2.2 (а) - Схема модулярного умножителя по модулю m на основе закона квадратов

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

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

Метод работы этого умножителя связан с математическими свойствами полей Галуа , обозначаемых 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)

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

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

Рисунок 2.2 (б) - Схема модулярного умножителя, основанного на исчислении степеней (умножитель Галуа)

Рассмотрим в качестве примера работу этого умножителя на примере умножения двух чисел 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 и | ij + ik |30 = 8. Элементу in = 8 в табл. 1 соответствует qn = 20, следовательно, |14 × 28|31 = 20 . Перейти на страницу: 1 2

Другие статьи по теме:

Моделирование и оценка производительности работы защищенных каналов в корпоративных сетях В первое поколение (1945-1954) развития компьютерной техники, Клод Шеннон (создатель теории информации), Алан Тьюринг (математик, разработавший теорию программ и алгоритмов) и Джон фон Н ...

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

Анализ прохождения периодического сигнала через LC-фильтр с потерями Дисциплина "Основы теории цепей" является важнейшей дисциплиной в подготовке специалиста направления "Радиотехника". Данный курс лекций помогает студентам приобретать ...