Арифметико-логическое устройство для вычитания чисел по модулю

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в криптографических приложениях. Технический результат заключается в расширении арсенала средств за счет обеспечения вычитания чисел именно по модулю. Устройство содержит n-разрядные регистры, электронные ключи, инвертор, n-разрядные сумматоры, схему дизъюнкторов ИЛИ, модуль управляющего блока, входную и выходную n-разрядные шины. В способе обеспечивается вычитание числа В из А по модулю Р. Операндами являются числа А и В, которые находятся в диапазоне от 0 до (Р-1) включительно. Уменьшаемое, вычитаемое и модуль с входной шины записываются в регистры. Операция вычитания выполняется путем суммирования уменьшаемого в прямом коде с вычитаемым в дополнительном коде. В случае если разность чисел S=(A-B) является неотрицательной, то операция приведения по модулю не выполняется и результатом вычитания (А-В) по модулю Р является разность (А-В). Если (А-В)<0, то к этой разности прибавляется значение модуля Р и результат является результатом работы устройства. 2 ил.

 

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

Известно устройство для сложения и вычитания чисел по модулю (патент РФ N2023289, МКИ G06F 7/49, Б.И. N21, 1994 г.), содержащее четыре счетчика, два элемента запрета, девять блоков элементов И, четыре блока элементов ИЛИ, шифратор, дешифратор, четыре элемента ИЛИ-НЕ, два элемента ИЛИ, элемент И, два блока определения дополнительного кода остатка по первому частному модулю, два блока определения дополнительного кода остатка по второму частному модулю, два блока определения кода остатка по первому частному модулю и два блока определения кода остатка по второму частному модулю. Устройство позволяет выполнять арифметические операции по модулю.

Недостатками данного устройства являются сложность и большое количество оборудования.

Наиболее близким по технической сущности к заявляемому изобретению является арифметико-логическое устройство для выполнения операции вычитания, содержащее три n-разрядных регистра, два электронных ключа, инвертор, входную и выходную n-разрядные шины, один n-разрядный сумматор, модуль управляющего блока, схему выработки признаков переполнения (Бабич Н.П., Жуков И.А. Основы цифровой схемотехники: Учебное пособие. - М.: Издательский дом «Додэка-XXI», К.: «МК-Пресс», 2007. - 480 с. рис. 9.6, стр. 281-287).

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

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

Для достижения технического результата в арифметико-логическое устройство для выполнения операции вычитания, содержащее три n-разрядных регистра, два электронных ключа, входную и выходную n-разрядные шины, один n-разрядный сумматор, инвертор, модуль управляющего блока, причем информационные входы первого и второго n-разрядных регистров соединены со входной n-разрядной шиной, управляющий вход первого n-разрядного регистра соединен с первым выходом модуля управляющего блока, управляющий вход второго n-разрядного регистра соединен со вторым выходом модуля управляющего блока, выход первого n-разрядного регистра соединен с информационным входом первого электронного ключа, выход второго n-разрядного регистра соединен с информационным входом инвертора, выход которого соединен с информационным входом второго электронного ключа, управляющие входы первого и второго электронных ключей соединены с четвертым выходом модуля управляющего блока, выход первого электронного ключа соединен с первым информационным входом первого n-разрядного сумматора, второй информационный вход которого соединен с выходом второго электронного ключа, на вход переноса первого n-разрядного сумматора подается сигнал логической 1, выход третьего n-разрядного регистра соединен с выходной n-разрядной шиной, его первый управляющий вход соединен с седьмым выходом модуля управляющего блока, а второй управляющий вход соединен с восьмым выходом модуля управляющего блока, на первый вход модуля управляющего блока подается одноразрядный код команды вычитания, на второй вход модуля управляющего блока подаются тактовые импульсы, введены четвертый n-разрядный регистр, три электронных ключа, второй n-разрядный сумматор, схема дизъюнкторов ИЛИ, причем информационный вход четвертого n-разрядного регистра соединен с входной n-разрядной шиной, управляющий вход соединен с третьим выходом модуля управляющего блока, а выход соединен с информационным входом третьего электронного ключа, управляющий вход которого соединен с четвертым выходом модуля управляющего блока, а выход соединен со вторым информационным входом второго n-разрядного сумматора, выход переноса первого n-разрядного сумматора соединен с третьим входом модуля управляющего блока, информационный выход первого n-разрядного сумматора соединен с информационным входом четвертого электронного ключа, а также с первым информационным входом второго n-разрядного сумматора, информационный выход которого соединен с информационным входом пятого электронного ключа, управляющий вход которого соединен с шестым выходом модуля управляющего блока, а выход соединен со вторым информационным входом схемы дизъюнкторов ИЛИ, первый информационный вход которого соединен с выходом четвертого электронного ключа, управляющий вход которого соединен с пятым выходом модуля управляющего блока, выход схемы дизъюнкторов ИЛИ соединен с информационным входом третьего n-разрядного регистра, причем модуль управляющего блока арифметико-логического устройства для вычитания чисел по модулю содержит три двухвходовых элемента И, трехразрядный счетчик, трехвходовый дешифратор, два RS-триггера и инвертор, при этом первый вход первого двухвходового элемента И является первым входом модуля управляющего блока, второй вход является вторым входом модуля управляющего блока, а выход соединен со счетным входом трехразрядного счетчика, выходы которого соединены с соответствующими информационными входами трехвходового дешифратора, первый выход которого является первым выходом модуля управляющего блока, второй выход является вторым выходом модуля управляющего блока, третий выход является третьим выходом модуля управляющего блока, шестой выход является седьмым выходом модуля управляющего блока, четвертый выход соединен с S-входом первого RS-триггера, пятый выход соединен с S-входом второго RS-триггера, седьмой выход соединен с R-входами первого и второго RS-триггеров и является восьмым выходом модуля управляющего блока, выход первого RS-триггера является четвертым выходом модуля управляющего блока, выход второго RS-триггера соединен с первыми входами второго и третьего двухвходовых элементов И, третий вход модуля управляющего блока соединен со входом инвертора и вторым входом третьего двухвходового элемента И, выход которого является пятым выходом модуля управляющего блока, выход инвертора соединен со вторым входом второго двухвходового элемента И, выход которого является шестым выходом модуля управляющего блока.

Сущность изобретения заключается в реализации следующего способа вычитания числа В из А по модулю Р. Операндами являются числа А и В, которые находятся в диапазоне от 0 до (Р-1) включительно. Уменьшаемое, вычитаемое и модуль с входной n-разрядной шины записываются в регистры. Операция вычитания выполняется путем суммирования уменьшаемого в прямом коде с вычитаемым в дополнительном коде. В случае если разность чисел S=(A-B) является неотрицательной, то операция приведения по модулю не выполняется и результатом вычитания (А-В) по модулю Р является разность (А-В). Если (А-В)<0, то к этой разности прибавляется значение модуля Р и результат является результатом работы устройства.

На фиг. 1 представлена схема арифметико-логического устройства для вычитания чисел по модулю.

Арифметико-логическое устройство для вычитания чисел по модулю содержит четыре n-разрядных регистра 1, 2, 3, 13, пять электронных ключей 5, 6, 7, 10, 11, инвертор 4, два n-разрядных сумматора 8, 9, схему дизъюнкторов ИЛИ 12, модуль управляющего блока 14, входную n-разрядную шину 15 и выходную n-разрядную шину 16. На первый вход 17 модуля управляющего блока 14 подается одноразрядный код команды вычитания по модулю, на второй вход 18 модуля управляющего блока 14 подаются тактовые импульсы. Информационные входы первого, второго и четвертого n-разрядных регистров 1, 2, 3 соединены со входной n-разрядной шиной 15, управляющий вход Y1 первого n-разрядного регистра 1 соединен с первым выходом Y1 модуля управляющего блока 14, а его выход соединен с информационным входом первого электронного ключа 5, управляющий вход Y2 второго n-разрядного регистра 2 соединен со вторым выходом Y2 модуля управляющего блока 14, а его выход соединен с информационным входом инвертора 4, выход которого соединен с информационным входом второго электронного ключа 6, управляющий вход Y3 четвертого n-разрядного регистра 3 соединен с третьим выходом Y3 модуля управляющего блока 14, а его выход соединен с информационным входом третьего электронного ключа 7, управляющие входы Y4 первого-третьего электронных ключей 5, 6, 7 соединены с четвертым выходом Y4 модуля управляющего блока 14. Выход первого электронного ключа 5 соединен с первым информационным входом первого n-разрядного сумматора 8, второй информационный вход которого соединен с выходом второго электронного ключа 6, на вход переноса постоянно подается сигнал логической 1, выход переноса соединен с третьим входом модуля управляющего блока 14, а информационный выход соединен с информационным входом четвертого электронного ключа 10 и с первым информационным входом второго n-разрядного сумматора 9, второй информационный вход которого соединен с выходом третьего электронного ключа 7. Информационный выход второго n-разрядного сумматора 9 соединен с информационным входом пятого электронного ключа 11. Управляющий вход Y5 четвертого электронного ключа 10 соединен с пятым выходом Y5 модуля управляющего блока 14, а его выход соединен с первым информационным входом схемы дизъюнкторов ИЛИ 12, управляющий вход Y6 пятого электронного ключа 11 соединен с шестым выходом Y6 модуля управляющего блока 14, а его выход соединен со вторым информационным входом схемы дизъюнкторов ИЛИ 12, выход которой соединен с информационным входом третьего n-разрядного регистра 13, первый управляющий вход Y7 которого соединен с седьмым выходом Y7 модуля управляющего блока 14, второй управляющий вход Y8 соединен с восьмым выходом Y8 модуля управляющего блока 14, а выход соединен с выходной n-разрядной шиной 16.

На фиг. 2 представлена схема модуля управляющего блока 14 арифметико-логического устройства для вычитания чисел по модулю.

Модуль управляющего блока 14 арифметико-логического устройства для вычитания чисел по модулю содержит три двухвходовых элемента И 14.1, 14.7, 14.8, трехразрядный счетчик 14.2, трехвходовой дешифратор 14.3, два RS-триггера 14.4, 14.5, инвертор 14.6. Первый вход первого двухвходового элемента И 14.1 является первым входом 17 модуля управляющего блока 14, второй вход является вторым входом 18 модуля управляющего блока 14. Выход первого двухвходового элемента И 14.1 соединен со счетным входом трехразрядного счетчика 14.2, выходы которого соединены с соответствующими информационными входами трехвходового дешифратора 14.3, первый выход которого является первым выходом Y1 модуля управляющего блока 14, второй выход является вторым выходом Y2 модуля управляющего блока 14, третий выход является третьим выходом Y3 модуля управляющего блока 14, шестой выход является седьмым выходом Y7 модуля управляющего блока 14, четвертый выход соединен с S-входом первого RS-триггера 14.4, пятый выход соединен с S-входом второго RS-триггера 14.5, седьмой выход соединен с R-входами первого и второго RS-триггеров 14.4, 14.5 и является восьмым выходом Y8 модуля управляющего блока 14. Выход первого RS-триггера 14.4 является четвертым выходом Y4 модуля управляющего блока 14, выход второго RS-триггера 14.5 соединен с первыми входами второго и третьего двухвходовых элементов И 14.7, 14.8, третий вход модуля управляющего блока 14 соединен со входом инвертора 14.6 и вторым входом третьего двухвходового элемента И 14.8, выход которого является пятым выходом Y5 модуля управляющего блока 14, выход инвертора 14.6 соединен со вторым входом второго двухвходового элемента И 14.7, выход которого является шестым выходом Y6 модуля управляющего блока 14.

Арифметико-логическое устройство для вычитания чисел по модулю работает следующим образом.

В исходном состоянии n-разрядные регистры 1, 2, 3, 13 арифметико-логического устройства обнулены, на первый вход 17 модуля управляющего блока 14 подается логический 0, трехразрядный счетчик 14.2, RS-триггеры 14.4 и 14.5 обнулены. Для начала работы устройства и на протяжении всего цикла вычитания на первый вход 17 модуля управляющего блока 14 подается сигнал логической 1. При этом тактовые импульсы, поступающие на второй вход 18 модуля управляющего блока 14, начинают подсчитываться трехразрядным счетчиком 14.2 и последовательно появляются на выходах Y1-Y8 модуля управляющего блока 14. С приходом первого тактового импульса на второй вход 18 модуля управляющего блока 14 состояние трехразрядного счетчика 14.2 изменяется с 000 на 001 и на первом выходе трехвходового дешифратора 14.3 появляется импульс. Этот импульс с выхода Y1 модуля управляющего блока 14 поступает на управляющий вход Y1 первого n-разрядного регистра 1, в результате чего происходит считывание с входной n-разрядной шины 15 кода уменьшаемого А и запись его в первый n-разрядный регистр 1. С приходом второго тактового импульса состояние трехразрядного счетчика 14.2 изменяется на 010. Управляющий импульс появляется на втором выходе трехвходового дешифратора 14.3 и поступает на выход Y2 модуля управляющего блока 14, поступая на управляющий вход Y2 второго n-разрядного регистра 2, в результате чего происходит считывание со входной n-разрядной шины 15 кода вычитаемого В и запись его во второй n-разрядный регистр 2. С приходом третьего тактового импульса состояние трехразрядного счетчика 14.2 изменяется на 011, управляющий импульс появляется на третьем выходе трехвходового дешифратора 14.3 и поступает на выход Y3 модуля управляющего блока 14. С выхода модуля управляющего блока 14 импульс поступает на управляющий вход Y3 третьего n-разрядного регистра 3, осуществляя запись в него с входной n-разрядной шины 15 кода модуля Р. С приходом четвертого тактового импульса, управляющий импульс появляется на четвертом выходе трехвходового дешифратора 14.3 и поступает на S-вход первого RS-триггера 14.4, переводя его в единичное состояние. В результате на выходе Y4 модуля управляющего блока 14 появляется логическая 1, которая открывает первый-третий электронные ключи 5, 6, 7. С выхода первого электронного ключа 5 код уменьшаемого А поступает на первый информационный вход первого n-разрядного сумматора 8, с выхода второго электронного ключа 6 код вычитаемого В поступает в инверсном виде на второй информационный вход первого n-разрядного сумматора 8, а с выхода третьего электронного ключа 7 код модуля поступает на второй информационный вход второго n-разрядного сумматора 9. Первый n-разрядный сумматор 8 выполняет операцию вычитания числа В из числа А, так как код вычитаемого В поступает на второй информационный вход первого n-разрядного сумматора 8 в инверсном виде и на вход переноса первого n-разрядного сумматора 8 постоянно подается сигнал логической 1, что в целом идентично дополнительному коду вычитаемого В. С выхода первого n-разрядного сумматора 8 код разности чисел А и В поступает на первый информационный вход второго n-разрядного сумматора 9 и на информационный вход четвертого электронного ключа 10. В случае если значение (А-В) является неотрицательным, то на выходе переноса первого n-разрядного сумматора 8 появится логическая 1, в противном случае появится логический 0. С приходом пятого тактового импульса на второй вход 18 модуля управляющего блока 14 управляющий импульс появится на пятом выходе трехвходового дешифратора 14.3, переводя второй RS-триггер 14.5 в единичное состояние. В результате на первые входы первого и второго двухвходовых элементов И 14.7 и 14.8 подается логическая 1 с выхода второго RS-триггера 14.5. Если разность чисел (А-В) окажется неотрицательной, то на третий вход модуля управляющего блока поступит логическая 1 и распределительный импульс окажется на выходе Y5 модуля управляющего блока 14, открывая четвертый электронный ключ 10 и пропуская на вход схемы дизъюнкторов ИЛИ 12 значение разности (А-В). Если разность (А-В) отрицательна, то логический 0 на третьем входе модуля управляющего блока 14 откроет второй двухвходовый элемент И 14.7 и управляющий импульс окажется на выходе Y6 модуля управляющего блока 14, открывая пятый электронный ключ 11 и пропуская на вход схемы дизъюнкторов ИЛИ 12 сумму (А-В)+Р. Таким образом, на выходе схемы дизъюнкторов ИЛИ 12 образуется разность (А-В) по модулю Р. С приходом шестого тактового импульса управляющий импульс появляется на выходе Y7 модуля управляющего блока 14, воздействуя на первый управляющий вход Y7 третьего n-разрядного регистра 13, записывая в него разность чисел по модулю. С приходом седьмого тактового импульса управляющий импульс с седьмого выхода трехвходового дешифратора 14.3 обнуляет RS-триггеры 14.4, 14.5 и поступает на выход Y8 модуля управляющего блока 14, поступая затем на второй управляющий вход Y8 третьего n-разрядного регистра 13, в результате чего информация с выхода третьего n-разрядного регистра 13 считывается в выходную n-разрядную шину 16.

Рассмотрим работу арифметико-логического устройства для вычитания чисел по модулю на конкретном примере. Пусть разрядность регистров и сумматоров n составляет 4 бита, пусть А=12, В=7, Р=14. Тогда прямые двоичные коды уменьшаемого, вычитаемого и модуля имеют вид: А₂=1100, B₂=0111, Р₂=1110. Обратный код вычитаемого B_обр=1000. Результат работы первого n-разрядного сумматора 8: А₂+В_обр+1=1100+1000+0001=10101. Старший разряд является признаком переполнения. Поскольку переполнение произошло, результатом вычитания по модулю являются четыре младших разряда полученной суммы, т.е. 0101₂, или 5₁₀. Вычитание выполнено корректно, поскольку 12-7 (mod 14)=5.

Для случая n=4, А=7, В=12, Р=14 имеем: А₂=0111, В₂=1100, Р₂=1110. Обратный код вычитаемого В_обр=0011. Тогда А₂+В_обр+1=0111+0011+0001=1011. Поскольку в данном случае переполнения не произошло, результатом вычитания по модулю является сумма полученного значения 1011 с модулем: А₂+В_обр+1+Р₂=1011+1110=11001. Старший разряд является признаком переполнения и в ответе не учитывается. Окончательный результат операции вычитания по модулю равен 1001₂, или 9₁₀. Вычитание выполнено корректно, поскольку 7-12 (mod 14)=9.

Арифметико-логическое устройство для вычитания чисел по модулю, содержащее три n-разрядных регистра, два электронных ключа, входную и выходную n-разрядные шины, один n-разрядный сумматор, инвертор, модуль управляющего блока, причем информационные входы первого и второго n-разрядных регистров соединены со входной n-разрядной шиной, управляющий вход первого n-разрядного регистра соединен с первым выходом модуля управляющего блока, управляющий вход второго n-разрядного регистра соединен со вторым выходом модуля управляющего блока, выход первого n-разрядного регистра соединен с информационным входом первого электронного ключа, выход второго n-разрядного регистра соединен с информационным входом инвертора, выход которого соединен с информационным входом второго электронного ключа, управляющие входы первого и второго электронных ключей соединены с четвертым выходом модуля управляющего блока, выход первого электронного ключа соединен с первым информационным входом первого n-разрядного сумматора, на вход переноса которого подается сигнал логической 1, а его второй информационный вход соединен с выходом второго электронного ключа, выход третьего n-разрядного регистра соединен с выходной шиной, его первый управляющий вход соединен с седьмым выходом модуля управляющего блока, а второй управляющий вход соединен с восьмым выходом модуля управляющего блока, на первый вход модуля управляющего блока подается одноразрядный код команды вычитания, на второй вход модуля управляющего блока подаются тактовые импульсы, отличающееся тем, что в него введены четвертый n-разрядный регистр, три электронных ключа, второй n-разрядный сумматор, схема дизъюнкторов ИЛИ, причем информационный вход четвертого n-разрядного регистра соединен с входной n-разрядной шиной, управляющий вход соединен с третьим выходом модуля управляющего блока, а выход соединен с информационным входом третьего электронного ключа, управляющий вход которого соединен с четвертым выходом модуля управляющего блока, а выход соединен со вторым информационным входом второго n-разрядного сумматора, выход переноса первого n-разрядного сумматора соединен с третьим входом модуля управляющего блока, информационный выход первого n-разрядного сумматора соединен с информационным входом четвертого электронного ключа, а также с первым информационным входом второго n-разрядного сумматора, информационный выход которого соединен с информационным входом пятого электронного ключа, управляющий вход которого соединен с шестым выходом модуля управляющего блока, а выход соединен со вторым информационным входом схемы дизъюнкторов ИЛИ, первый информационный вход которой соединен с выходом четвертого электронного ключа, управляющий вход которого соединен с пятым выходом модуля управляющего блока, выход схемы дизъюнкторов ИЛИ соединен с информационным входом третьего n-разрядного регистра, причем модуль управляющего блока арифметико-логического устройства для вычитания чисел по модулю содержит три двухвходовых элемента И, трехразрядный счетчик, трехвходовый дешифратор, два RS-триггера и инвертор, при этом первый вход первого двухвходового элемента И является первым входом модуля управляющего блока, второй вход является вторым входом модуля управляющего блока, а выход соединен со счетным входом трехразрядного счетчика, выходы которого соединены с соответствующими информационными входами трехвходового дешифратора, первый выход которого является первым выходом модуля управляющего блока, второй выход является вторым выходом модуля управляющего блока, третий выход является третьим выходом модуля управляющего блока, шестой выход является седьмым выходом модуля управляющего блока, четвертый выход соединен с S-входом первого RS-триггера, пятый выход соединен с S-входом второго RS-триггера, седьмой выход соединен с R-входами первого и второго RS-триггеров и является восьмым выходом модуля управляющего блока, выход первого RS-триггера является четвертым выходом модуля управляющего блока, выход второго RS-триггера соединен с первыми входами второго и третьего двухвходовых элементов И, третий вход модуля управляющего блока соединен со входом инвертора и вторым входом третьего двухвходового элемента И, выход которого является пятым выходом модуля управляющего блока, выход инвертора соединен со вторым входом второго двухвходового элемента И, выход которого является шестым выходом модуля управляющего блока.