Устройство для умножения чисел по модулю Советский патент 1993 года по МПК G06F7/72 

(Л

С

Изобретение относится к области автоматики и вычислительной техники и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Цель изобретения - повышение быстродействия за счет сокращения циклов суммирования при выполнении операции модульного умножения, которое достигается путем реализации в устройстве соотношения А В (mod m) A .(2П - 1) (mod m) - А -В (mod m), (где А, В - операнды, m - модуль операции, n log2m, В - представление операнда в двоичном коде, когда все разряды его инвертированы), в тех случаях, когда количество нулей в двоичном представлении операнда В превышает число единиц. 1 ил., 5 табл.

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

Цель изобретения - повышение быстродействия,

Поставленная цель достигается тем, что в устройство, содержащее группу блоков элементов И, первый и второй кольцевые регистры сдвига, первый блок элементов ИЛИ, счетчик, первый элемент НЕ, с первого по третий элементы И, первый блок элементов И, группу блоков умножения на константу по модулю, первый элемент ИЛИ, шифратор, причем выходы разрядов первого кольцевого регистра соединены с первыми аходами соответствующих блоков элементов И группы, выходы которых соединены с соответствующими входами первого

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

00

о

XI

4Ь.

00

Јь

со входом разрешения сдвига второго кольцевого регистра сдвига, выходы разрядов которого соединены с соответствующими входами шифратора, выход которого соединен с вторым входом первого блока элементов И, выход последнего разряда первого кольцевого регистра сдвига и выход первого элемента НЕ соединены соответственно с первым и вторым входами третьего элемента И, выход второго элемента И соединен со входом разрешения сдвига первого кольцевого регистра сдвига, введены с второго по четвертый блоки элементов И, второй и третий блоки элементов ИЛИ, блок умножения на константу по модулю, четвертый и пятый элементы И, второй элемент НЕ, второй элемент ИЛИ, дешифратор и вычитатель по модулю, причем вход второго сомножителя устройства соединен с первым входом второго блока элементов И и с входом дешифратора, соответствующие выходы которого соединены с соответствующими входами второго элемента ИЛИ, выход которого соединен с вторым входом четвертого элемента И, входом второго элемента НЕ и с вторым входом третьего блока элементов И, с первым входом которого соединен дополнительный вход второго сомножителя устройства, выход второго элемента НЕ соединен с вторым входом второго блока элементов И. и со вторым входом пятого элемента И, выходы второго и третьего блоков элементов И соединены с соответствующими входами второго блока элементов ИЛИ, выходы элементов которого соединены со вторыми входами соответствующих блоков элементов И группы, вход первого сомножителя устройства соединен с входом блока умножения на константу; выход которого соединен со входом уменьшаемого вы- читателя по модулю, вход вычитаемого которого соединен с выходом шифратора, а выход - с первым входом четвертого блока элементов И, выходы четвертого и пятого элементов И соединены со вторыми входами соответственно четвертого и первого блоков элементов И, выходы которых соединены с соответствующими входами третьего блока элементов ИЛИ, выход которого является выходом устройства, выход третьего элемента И соединен с первыми входами четвертого и пятого элементов И.

Сущность изобретения состоит в следующем. Время проведения модульной операции умножения зависит от числа единиц в представ лении второго операнда В при проведении операции А В (modm), Если количество единиц в двоичном представлении операнда В больше числа нулей, то нули меняются на единицы, а единицы на нули в

двоичном представлении операнда В, что соответствует преобразованию § « (2П - 1)- В, п log2m. Тогда А В А (2П - 1) -В А (2 - 1) - А В, откуда А B(mod m) А -(2n-1)(mod m)-A B(modm).

Операция А (2n- 1)(modm) реализуется с помощью блока умножения на константу по модулю, а вычитание в определенных случаях выполняется при помощи вычитате

ля по модулю, вход задания модуля которого

соединен с выходом блока умножения на константу по модулю. Случаи превышения, количества нулей над количеством единиц в представлении операнда В объединяются

элементом ИЛИ на выходе дешифратора. Вычитатель по модулю работает по модулю устройства. Рассмотрим случай m 5. Операнды В и В представлены в табл. 1, а А и А(2П -1) А-7 для работы блока умножения

на константу - в табл. 2.

Т а б л и ц а 1

25

Таблица 2

30

Следует отметить, что если m 2 - 1 (k 2, 3, ...), то блок умножения на константу

не нужен и с входом уменьшаемого вычита- теля по модулю соединен вход задания модуля устройства т.

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

Заявляемое техническое решение соответствует критерию новизна, т.к. введенные новые признаки (три блока элементов И, два блока элементов ИЛИ, блок умножения на константу, два элемента И, элемент НЕ, элемент ИЛИ, дешифратор и вычитатель по модулю и их связи) в совокупности с

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

совокупность признаков способствует достижению поставленной цели - повышению быстродействия.

Заявляемое техническое решение соответствует критерию существенные отличия, т.к. при проведении поиска по

печатным источникам в науке и технике в данной области сходных признаков не обнаружено.

На чертеже представлена структурная схема устройства, где: 1 - вход второго сомножителя устройства; 2 - второй блок элементов И; 3 - дешифратор; 4 - второй элемент ИЛИ; 5 - четвертый элемент И; 6 - второй элемент НЕ; 7 - третий блок элементов И; 8 - дополнительный вход второго сомножителя устройства; 9 - пятый элемент И; 10 - второй блок элементов ИЛИ; 11 - группа блоков элементов И; 12 - вход первого сомножителя устройства; 13 - блок умножения на константу; 14 - вычитатель по модулю; 15 - дешифратор; 16 - четвертый блок элементов И; 17 - первый блок элементов И; 18 - третий блок элементов ИЛИ; 19

- выход устройства; 20 - третий элемент И; 21 - первый кольцевой регистр сдвига; 22 - первый блок элементов ИЛИ; 23 - тактовый вход устройства; 24 - первый элемент И; 25

- второй элемент И; 26 - первый элемент НЕ; 27 - группа блоков умножения на константу по модулю; 28 - счетчик; 29 - первый элемент ИЛИ; 30 - второй кольцевой регистр сдвига.

Вход 1 второго сомножителя устройства соединен с первым входом второго 2 блока элементов И и с входом дешифратора 3, соответствующие входы которого соединены с соответствующими входами второго 4 элемента ИЛИ, выход которого соединен с вторым входом четвертого 5 элемента И, входом второго 6 элемента НЕ и с вторым входом третьего 7 блока элементов И, с первым входом которого соединен дополнительный вход 8 устройства второго сомножителя, выход второго 6 элемента НЕ соединен с вторым входом второго 2 блока элементов И и со вторым входом пятого 9 элемента И, выходы второго 2 и третьего 7 блоков элементов И соединены с соответствующими входами второго 10 блока элементов ИЛИ, выходы элементов которого соединены со вторыми входами соответствующих блоков элементов 11 группы, вход 12 первого сомножителя устройства соединен с входом блока 13 умножения на константу, выход которого соединен с входом уменьшаемого вычитателя 14 по модулю, вход вычитаемого которого соединен с выходом шифратора 15, а выход - с первым входом четвертого 16 блока элементов И, выходы четвертого 5 и пятого 9 элементов И соединены со вторыми входами соответственно четвертого 16 и первого 17 блоков элементов И, выходы которых соединены соответствующими входами третьего 18 блока элементов ИЛИ, выход которого является выходом 19 третьего 18 блока элементов ИЛИ, выход которого является выходом 19 устройства, выход третьего 20 элемента И соединен с первыми входами четвертого 5 5 и пятого 9 элементов И, выходы разрядов первого 21 кольцевого регистра сдвига соединены с первыми входами соответствующих блоков элементов И 11 группы, выходы которых соединены с соответствующими

0 входами первого 22 блока элементов ИЛИ, тактовый вход 23 устройства соединен с первыми входами первого 24 и второго 25 элементов И, выход первого26 элемента НЕ соединен со вторым входом второго 25 эле5 мента И, вход 12 первого сомножителя устройства соединен со входами блоков умножения 27 на константу по модулю группы, выходы которых соединены соответственно с третьими входами блоков

0 элементов И 11, кроме последнего, группы, вход 12 первого сомножителя устройства соединен с третьим входом последнего блока элементов И 11 группы, выход первого 22 блока элементов ИЛИ соединен с устано5 вочным входом счетчика 28, выходы разрядов которого соединены с соответствующими входами первого 29 элемента ИЛИ, выход которого соединен со входом первого 26 элемента НЕ и со вторым

0 входом первого 24 элемента И, выход которого соединен с вычитающим входом счетчика 28 и со входом разрешения сдвига второго 30 кольцевого регистра сдвига, выходы разрядов которого соединены с соот5 ветствующими входами шифратора 15, выход которого соединен с вторым входом первого 17 блока элементов И, выход последнего разряда первого 21 кольцевого регистра сдвига и выход первого 26 элемента

0 НЕ соединены соответственно с первым и вторым входами третьего 20 элемента И, выход второго 25 элемента И соединен со входом разрешения сдвига первого 21 кольцевого регистра сдвига.

5Работу устройства удобно рассматривать в двух режимах:

1) число единиц в двоичном представлении второго операнда В больше числа нулей;

02) число единиц в двоичном представлении операнда В меньше числа нулей. Первый 21 кольцевой регистр сдвига состоит из п двоичных разрядов (с 0-го.по (п - 1)-й). Второй кольцевой регистрсдвига состоитиз

5 m двоичных разрядов (с 0-го по (т - 1)-й). В исходном состоянии в нулевые разряды регистров 21 и 30 записаны единицы, а в остальные разряды - нули по входу начальной установки устройства (на чертеже не показан). Второй сомножитель В подается вдвоичном коде по входу 1, а по входу 8 подается сомножитель В, у которого единицы заменены на нули и, наоборот, нули на единицы.

Рассмотрим работу в первом режиме. Первый сомножитель А поступает на входы блоков 27 умножения на константу по модулю, а также на первый вход последнего блока 11 элементов И группы, на выходах блоков 27 умножения на константу по модулю группы получаем произведения (А -2 )тос1тО п - 1 - 1), а на третьем входе последнего блока 11 элементов И имеем (А 2°)modm А. Второй сомножитель В в двоичном коде поступает на первый вход второго 2 блока элементов И и на вход дешифратора 3, выходы которого, соответствующие превышению числа единиц над нулями в двоичном его представлении соединены с входами второго 4 элемента И. В данном случае сигнал поступит с выхода второго элемента НЕ на второй вход Второго 2 блока элементов И и на второй вход пятого 9 элемента И. Второй сомножитель В в двоичном коде поступает через второй 2 блок элементов И и далее через второй 10 блок элементов ИЛИ на соответствующие вторые входы блоков 11 элементов И группы. На первые входы блоков 11 элементов И группы поступает сигнал с выходов разрядов первого кольцевого регистра 21 сдвига. Первоначально в нулевом разряде регистра 21 записана единица. В соответствующем (п - 1)-м разряде операнда В будет тоже записана единица; тогда через соответствующий блок элементов И и через первый 22 блок элементов ИЛИ число (А 2П 1)modm поступит на импульсный вход установки числа счетчика 28. Сигнал с выхода первого 29 элемента ИЛИ откроет элемент 24 и импульсы с входа 23 устройства поступят на вычитающий вход счетчика 28. Через {А 2n 1)modm импульсов единица из нулевого разряда регистра 30 перейдет в (А 2П 1)modm-u разряд, а содержимое счетчика 28 станет равно нулю. Тогда сигнал будет поступать через первый 26 элемент НЕ на вход элемента И 25. С входа 23 устройства один импульс поступит на вход разрешения сдвига разрядов регистра 21, передвинув единицу из нулевого разряда в первый, Если в (п - 2)-м двоичном разряде операнда В будет ноль, то сигнал с выхода первого 26 элемента Н Е поступит на вход элемента И 25 и единица из первого разряда регистра 21 перейдет во второй. Процесс продолжается до тех пор, пока единица в регистре 21 перейдет в (п - 1)-й разряд. В этом случае, если соответствующий (нулевой) разряд операнда В будет равен

нулю, то на выходе первого 27 элемента НЕ будет сигнал, который поступит с выхода элемента И 20 на первый вход пятого 9 элемента И, сигнал с выхода которого поступит

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

двоичное представление и далее через первый 17 блок элементов И, третий 1& блок элементов ИЛИ на выход 19 устройства, если нулевой двоичный разряд операнда В будет равен единице, то сигнал с выхода

элемента И 20 поступит только тогда, когда содержимое счетчика 28 станет равно нулю, т.е. после проведения последнего суммирования. .

Во втором режиме сигнал с выхода второго 4 элемента ИЛИ поступит на второй вход третьего 3 блока элементов И и второй вход четвертого 5 элемента И. В этом случае второй сомножитель В поступит на вход второго 10 блока элементов ИЛИ, а на вход

уменьшаемого вычитателя 14 по модулю поступит с выхода.блока 13 умножения на константу величина А(2П )modm. Результат операции модульного умножения А B(modm), полученный в унитарном коде

на выходах разрядов регистра 30, поступит через шифратор 15 на вход вычитаемого вычитателя .1.4 по модулю m и А B(modm) и далее через четвертый 16 блок элементов И, третий 18 блок элементов ИЛИ поступит

результат операции модульного умножения А B(modm)Ha выход 19 устройства.

Рассмотрим примеры конкретного выполнения операции для m 5. В этом случае КРС21 имеет п log (m-1)+ 1 3 двоичных

разряда, а КРС 30 - 5 двоичных разряда. Количество необходимых блоков умножения на константу по модулю группы равно двум. В табл. 3 и 4 представлено преобразование первото операнда А, осуществляемое

соответственно первым и вторым блоками умножения на константу по модулю группы.

ТаблицаЗ

50

55

Таблица 4

Пример 1. Пусть необходимо определить результат операции модульного умножения для А 3, В 4 (А и В - операнды).

Первый операнд А 011 поступает на входы второго и первого блоков 27 умножения на константу по модулю группы, а также на первый вход последнего блока элементов И 11 группы. На выходе второго блока 27 умножения на константу будет число 010, на выходе первого блока 27 умножения - 001.

На вход последнего элемента И 11 группы поступает число А 011 (А 2°). На вход 1 поступает второй операнд В 100, который поступает на первый вход второго 2 блока элементов И и вход дешифратора 3, Сигнал с выхода второго 6 элемента НЕ поступает на второй вход второго 2 блока элементов И, разрешая прохождение второго операнда В на вход второго 10 блока элементов ИЛИ и на второй вход пятого 9 элемента И. С выходов второго 10 блока элементов ИЛИ сигнал поступает только на второй вход первого 11 блока элементов И группы, На третий вход первого 11 блока элементов И группы поступает сигнал с нулевого разряда КРС 21 и число 010 поступает через первый 22 блок элементов ИЛИ на вход установки числа счетчика 28. Сигнал с выхода первого 29 элемента ИЛИ откроет первый 24 элемент И и импульсы с тактового входа 23 поступят на вход сдвига разрядов КРС 30 и на вычитающий вход счетчика 28. Через два импульса единица из нулевого разряда КРС 30 перейдет во второй разряд, а содержимое счетчика 28 будет равно нулю. Сигнал через первый 26 элемент НЕ поступит на второй вход элемента И 25. С тактового входа 23 поступит один импульс на вход сдвига разрядов КРС 21. Единица из нулевого разряда перейдет в первый. В первом разряде операнда в записи ноль, поэтому снова сигнал с выхода первого 26 элемента НЕ поступит на вход блока элементов И 11 группы и единица из первого разряда КРС 21 перейдет во второй. В нулевом разряде операнда В в записи ноль, поэтому сигнал с выхода первого 26 элемента НЕ поступит через элемент И 20 на первый вход пятого 10 элемента И, сигнал с его выхода поступит на второй вход первого блока элементов И, и результат операции через шифратор 15 поступит в двоичном коде через первый 17 блок элементов И, третий 18 блок элементов ИЛИ на выход 19 устройства. Первоначальное состояние КРС 30:

с

1-0-0-0-0-1

Заключительное состояние КРС 30:

0-0-1-0-0

Это состояние соответствует унитарному коду числа 2. На выходах шифратора 15 получим число 010. Это и будет результат операции.

Проверка: 3 4 (mod5) 2.

Пример2. Пусть необходимо определить результат операции модульного умножения для А 2, В 3(АиВ- операнды). Первый операнд А -010 поступает на входы второго и первого блоков 27 умножения на константу, а также на первый вход последнего блока элементов И 11 группы, На выходе второго блока 27 будет число 011, на выходе первого блока 27 умножения - 100, на входе последнего блока элементов

И 11 группы - 010. Операнд В 011 поступает по входу 1, а операнд В 100 - по входу 8. В данном случае с выхода второго 4 элемента ИЛ И поступает сигнал на второй вход третьего 7 блока элементов И и на второй

вход четвертого 5 элемента И. Операнд В 100 поступает на вход второго 10 блока элементов ИЛИ. Дальнейшая работа происходит аналогично первому примеру, но в счетчик 28 поступает число 011 и единица из

нулевого разряда КРС 30 перейдет в третий разряд, после чего содержимое счетчика 28 будет равно нулю. Заключительное состояние КРС 30 будет равно:

35

0-0 - 0- 1 -О -Ч

Это состояние соответствует унитарному коду числа 3. На выходах шифрауора 15 получим число 011. Это будет результат опе- рации А В (mod5) 2 4 (mod5) 3. Это число поступает на вход вычитаемого вычи- тателя 14 по модулю 5. На второй вход его (вход уменьшаемого) поступает число А(2П

-1)mod5 2 7 modS 4 (см. табл. 2). На выходе вычитателя 14 по модулю 5 будет (4

-3) mod5 1. Следовательно, число 001 поступит через четвертый 16 блок элементов И, третий 18 блок элементов ИЛИ на выход 19 устройства. Это и будет результат опера- ции.

Проверка: 2-3(mod5) 1(mod5). Отметим, что в прототипе необходимо было провести два цикла суммирования, а в данном устройстве ограничились одним циклом, т.к. число циклов суммирования равно количеству единиц в двои чном представлении операнда В.

Техническое преимущество заявляемого изобретения по сравнению с прототипом

состоит в уменьшении циклов суммирования путем уменьшения количества единиц в двоичном представлении второго операнда В (что определяет число этих циклов). Рассмотрим, какой выигрыш при этом достигается. Обозначим через Тп -. максимальное число циклов суммирования в прототипе; Тз - максимальное число циклов суммирования в заявке; V ТП/ТЭ. Результаты поместим в табл. 5 (т - модуль устройства):

Та блица 5

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

Анализируя содержание табл. 5 можно сделать вывод, что выигрыш VOT внедрения данного изобретения значительный.

Достоверность достижения поставленной цели подтверждается конкретными примерами модульной операции умножения при m 5.

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

регистра сдвига соединен с вторым входом третьего элемента И, выход второго элемента И соединен с входом разрешения сдвига первого кольцевого регистра сдвига, отличающееся тем, что, с целью повышения

быстродействия, содержит с второго по четвертый блоки элементов И, второй и третий блоки элементов ИЛИ, блок умножения на константу по модулю, четвертый и пятый элементы И, второй элемент НЕ, второй элемент ИЛИ, дешифратор и вычитатель по мо- дулю, причем первый вход второго сомножителя устройства соединен с первым входом второго блока элементов И, и входом дешифратора, выходы которого соединены с входами элемента ИЛИ, выход которого соединен с первым входом четвертого элемента И, входом второго элемента НЕ и первым входом третьего блока элементов И, второй вход которого соедипен с вторым входом второго сомножителя устройства, выход второго элемента НЕ соединен с вторым входом второго блока элементов И и первым входом пятого элемента И, выходы второго и третьего блоков элементов И соединены с соответствующими входами второго блока элементов ИЛИ, выходы элементов которого .соединены с третьими входами элементов И, соответствующих блоков группы, вход первого сомножителя устройства соединен с входом бл ока умножения на константу по модулю, выход которого соединен с входом уменьшаемого вычитателя по модулю, вход вычитаемого которого соединен с выходом шифратора, а

выход -- с первым входом четвертого блока элементов И, выходы четвертого и пятого элементов И соединены с вторыми входами соответственно четвертого и первого блоков элементов И, выходы которых соединены с соответствующими входами третьего блока элементов ИЛИ, выход которого является выходом устройства, выход третьего элемента И соединен с вторыми входами четвертого и пятого элементов И.

JT