Арифметико-логическое устройство для сложения чисел по модулю Российский патент 2017 года по МПК G06F7/52 

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

Известен сумматор, содержащий 2 логических элемента «Исключающее ИЛИ», 3 двухвходовых логических элемента «И» и 1 трехвходовый логический элемент «И» (Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. – М.: Радио и связь, 1990. Рисунок 3.44а, с. 132).

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

Наиболее близким по технической сущности к заявляемому изобретению является арифметико-логическое устройство для выполнения операции сложения, содержащий три n-разрядных регистра, два электронных ключа, входную и выходную n-разрядные шины, один n-разрядный сумматор, схему дизъюнкторов ИЛИ, модуль управляющего блока, схему выработки признаков переполнения (Бабич Н.П., Жуков И.А. Компьютерная схемотехника. Методы построения и проектирования: Учебное пособие. - К.: «МК-Пресс», 2004, рис. 9.1, стр. 279).

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

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

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

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

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

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

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

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