Результат интеллектуальной деятельности: АРИФМЕТИКО-ЛОГИЧЕСКОЕ УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ, ВЫЧИТАНИЯ И УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ

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

Известно устройство для выполнения операций по заданному модулю (патент РФ №2310223, МПК G06F 7/72, Бюл. №31, 2007 г.), содержащее полные сумматоры, элементы И, элементы ИЛИ, управляющие входы. Недостатком устройства является квадратичная зависимость количества оборудования от разрядности операндов.

Наиболее близким по технической сущности к заявляемому изобретению является арифметико-логическое устройство для умножения чисел по модулю (патент РФ №2653263, МПК G06F 7/523, G06F 7/72, Бюл. №13, 2018 г.), содержащее три n-разрядных регистра, два n-разрядных накапливающих сумматора по модулю, n-разрядный двухвходовый мультиплексор, n-разрядный электронный ключ, входную и выходную n-разрядные шины, где n – количество разрядов в двоичном коде операндов, а также модуль управляющего блока. Недостатком устройства является невозможность выполнения операций сложения и вычитания чисел по модулю.

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

Для достижения технического результата в арифметико-логическое устройство для сложения, вычитания и умножения чисел по модулю, содержащее три n-разрядных регистра, два n-разрядных накапливающих сумматора по модулю, n-разрядный двухвходовый мультиплексор, n-разрядный электронный ключ, входную и выходную n-разрядные шины, где n – количество разрядов в двоичном коде операндов, а также модуль управляющего блока, причем информационные входы первого и второго n-разрядных регистров соединены со входной n-разрядной шиной, первый информационный вход n-разрядного двухвходового мультиплексора соединен со входной n-разрядной шиной, второй информационный вход соединен с информационным выходом первого n-разрядного накапливающего сумматора по модулю, управляющий вход соединен со вторым выходом модуля управляющего блока, информационный выход соединен с информационным входом третьего n-разрядного регистра, управляющий вход которого соединен с четвертым выходом модуля управляющего блока, а информационный выход соединен со вторым информационным входом первого n-разрядного накапливающего сумматора по модулю, второй управляющий вход которого соединен с пятым выходом модуля управляющего блока, второй управляющий вход второго n-разрядного накапливающего сумматора по модулю соединен с шестым выходом модуля управляющего блока, информационный выход соединен с информационным входом n-разрядного электронного ключа, информационный выход которого соединен с выходной n-разрядной шиной, а управляющий вход соединен с восьмым выходом модуля управляющего блока, первый выход которого соединен с первыми управляющими входами n-разрядных накапливающих сумматоров по модулю и управляющим входом первого n-разрядного регистра, третий выход соединен с первым управляющим входом второго n-разрядного регистра, седьмой выход соединен со вторым управляющим входом второго n-разрядного регистра, на первый вход подается одноразрядный код команды умножения по модулю, введены два n-разрядных инвертора, n-разрядный сумматор, n-разрядный трехвходовый мультиплексор, причем информационный выход первого n-разрядного инвертора соединен с n младшими разрядами первых информационных входов n-разрядных накапливающих сумматоров по модулю, на (n+1)-й разряд которых подается уровень логической «1», выход первого n-разрядного регистра соединен со входом первого n-разрядного инвертора и с первым информационным входом n-разрядного сумматора, на вход переноса которого подается уровень логической «1», информационный выход третьего n-разрядного регистра соединен также с первым информационным входом n-разрядного трехвходового мультиплексора, младший разряд адресного входа которого соединен с девятым выходом модуля управляющего блока, старший разряд соединен с десятым выходом модуля управляющего блока, информационный выход соединен со вторым информационным входом второго n-разрядного накапливающего сумматора по модулю, третий информационный вход соединен с выходом n-разрядного сумматора, второй информационный вход которого соединен с выходом второго n-разрядного инвертора, информационный выход второго n-разрядного регистра соединен со вторым информационным входом n-разрядного трехвходового мультиплексора и входом второго n-разрядного инвертора, младший разряд соединен с пятым входом модуля управляющего блока, на второй вход которого подается одноразрядный код команды сложения по модулю, на третий вход подается одноразрядный код команды вычитания по модулю, на четвертый вход подаются тактовые импульсы, причем модуль управляющего блока содержит два трехвходовых элемента ИЛИ, два двухвходовых элемента И, r-разрядный счетчик, r-входовый дешифратор, где r = ⌈log₂ (2n+4)⌉, трехразрядный демультиплексор, блок ПЗУ, два (n-1)-входовых элемента ИЛИ, девятиразрядный электронный ключ, два элемента задержки, инвертор, двухвходовый элемент ИЛИ, три RS-триггера, одноразрядный демультиплексор, причем первый вход первого трехвходового элемента ИЛИ, соединенный с адресным входом трехразрядного демультиплексора, является первым входом модуля управляющего блока, второй вход, соединенный с первым входом второго трехвходового элемента ИЛИ, является вторым входом модуля управляющего блока, третий вход, соединенный со вторым входом второго трехвходового элемента ИЛИ и адресным входом одноразрядного демультиплексора, является третьим входом модуля управляющего блока, выход первого трехвходового элемента ИЛИ соединен со входом инвертора и с первым входом первого двухвходового элемента И, второй вход которого является четвертым входом модуля управляющего блока, выход соединен со входом первого элемента задержки и со счетным входом r-разрядного счетчика, выходы которого соединены с соответствующими информационными входами r-входового дешифратора, первый и второй выходы которого соединены с первым и вторым адресными входами блока ПЗУ соответственно, третий, четвертый и пятый выходы соединены с первым, вторым и третьим разрядами информационного входа трехразрядного демультиплексора соответственно, каждый 2k-й выход соединен с (k-1)-м входом первого (n-1)-входового элемента ИЛИ, каждый (2k+1)-й выход соединен с (k-1)-м входом второго (n-1)-входового элемента ИЛИ, где k = 3, 4, …, n, (2n+2)-й выход соединен с девятым адресным входом блока ПЗУ, (2n+3)-й выход соединен с десятым адресным входом блока ПЗУ, первый, второй и третий разряды первого выхода трехразрядного демультиплексора соединены с третьим, четвертым и пятым адресными входами блока ПЗУ соответственно, первый разряд второго выхода соединен с шестым адресным входом блока ПЗУ, второй разряд второго выхода соединен с первым входом первого (n-1)-входового элемента ИЛИ, третий разряд второго выхода соединен с первым входом второго (n-1)-входового элемента ИЛИ, выход первого (n-1)-входового элемента ИЛИ соединен с седьмым адресным входом блока ПЗУ, выход второго (n-1)-входового элемента ИЛИ соединен с восьмым адресным входом блока ПЗУ, шестой выход которого соединен с первым входом второго двухвходового элемента И, выход которого соединен с шестым разрядом информационного входа девятиразрядного электронного ключа, второй вход соединен с выходом второго трехвходового элемента ИЛИ, третий вход которого является пятым входом модуля управляющего блока, первый, второй, третий, четвертый, пятый, седьмой, восьмой и девятый выходы блока ПЗУ соединены соответственно с первым, вторым, третьим, четвертым, пятым, седьмым, восьмым и девятым разрядами информационного входа девятиразрядного электронного ключа, управляющий вход которого соединен с выходом первого элемента задержки, первый разряд выхода соединен с R-входами второго и третьего RS-триггеров и с первым входом двухвходового элемента ИЛИ, а также является первым выходом модуля управляющего блока, второй разряд выхода соединен с S-входом второго RS-триггера, третий, четвертый, пятый, шестой и седьмой разряды выхода являются третьим, четвертым, пятым, шестым и седьмым выходами модуля управляющего блока соответственно, восьмой разряд выхода соединен с S-входом первого RS-триггера, девятый разряд выхода соединен со входом второго элемента задержки, выход которого соединен с S-входом третьего RS-триггера, выход которого соединен с информационным входом одноразрядного демультиплексора, первый выход которого является девятым выходом модуля управляющего блока, второй выход является десятым выходом модуля управляющего блока, выход инвертора соединен со вторым входом двухвходового элемента ИЛИ, выход которого соединен с R-входом первого RS-триггера, выход которого соединен со входом сброса r-разрядного счетчика, а также является восьмым выходом модуля управляющего блока, выход второго RS-триггера является вторым выходом модуля управляющего блока.

Сущность изобретения заключается в реализации операций умножения, сложения и нахождения разности чисел A и B по модулю P. Операндами являются целые числа A и B, которые находятся в диапазоне от 0 до (P-1) включительно.

Числа A, B и P, имеющие разрядность n, могут быть представлены в двоичном виде:

где a_i, b_i, p_i – коэффициенты в двоичном представлении чисел A, B и P соответственно, .

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

Операция нахождения разности чисел (A-B) по модулю P выполняется как операция нахождения суммы чисел A и (P-B) по модулю P. Модуль, уменьшаемое и вычитаемое последовательно считываются со входной шины во входные регистры, после чего значение P подается на вход модуля накапливающего сумматора по модулю, значение A подается на информационный вход накапливающего сумматора по модулю. Вычисление разности (P-B) производится путем сложения прямого кода модуля P c дополнительным кодом вычитаемого B. Полученное значение (P-B) подается на информационный вход накапливающего сумматора по модулю.

Вычисление произведения чисел A и B по модулю P производится следующим образом.

Произведение A·B(mod P) можно записать в виде:

где r_i – i-й частичный остаток.

Таким образом, операция умножения чисел A и B по модулю P может быть выполнена путем последовательного нахождения n частичных остатков вида:

где , и последующего сложения по модулю P тех из них, для которых коэффициент .

Частичные остатки могут быть вычислены по следующему правилу:

Нулевым частичным остатком является само число A. Для последовательного формирования остальных (n-1) частичных остатков используется n-разрядный накапливающий сумматор по модулю, на вход которого на первом такте поступает число A, а на каждом последующем такте – значение, которое на предыдущем такте было на его выходе. Операция умножения предыдущего частичного остатка на 2 по модулю P в таком случае осуществляется как сложение по модулю P с самим собой.

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

Арифметико-логическое устройство для сложения, вычитания и умножения чисел по модулю содержит три n-разрядных регистра 3, 4, 5, два n-разрядных накапливающих сумматора 8, 11 по модулю, n-разрядный двухвходовый мультиплексор 2, n-разрядный электронный ключ 12, входную n-разрядную шину 1, выходную n-разрядную шину 13, два n-разрядных инвертора 6, 7, n-разрядный сумматор 9, n-разрядный трехвходовый мультиплексор 10, где n – количество разрядов в двоичном коде операндов, а также модуль управляющего блока 14.

В качестве n-разрядных накапливающих сумматоров 8, 11 по модулю используются устройства, принимающие (n+1)-разрядный двоичный код модуля в инверсной форме (напр. патент РФ №2500017, МПК G06F 7/72, Бюл. № 33, 2013 г.).

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

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

Модуль управляющего блока 14 содержит два трехвходовых элемента ИЛИ 14.1, 14.9, два двухвходовых элемента И 14.2, 14.10, r-разрядный счетчик 14.3, r-входовый дешифратор 14.4, где r = ⌈log₂ (2n+4)⌉, трехразрядный демультиплексор 14.5, блок ПЗУ 14.6, два (n-1)-входовых элемента ИЛИ 14.7, 14.8, девятиразрядный электронный ключ 14.11, два элемента задержки 14.12, 14.17, инвертор 14.13, двухвходовый элемент ИЛИ 14.14, три RS-триггера 14.15, 14.16, 14.18, одноразрядный демультиплексор 14.19.

Блок ПЗУ 14.6 хранит десять девятиразрядных битовых строк, имеет десять адресных входов, каждый из которых соответствует строке с соответствующим номером, и девятиразрядный выход. Содержимое блока ПЗУ представлено в таблице 1. При подаче уровня логической «1» на один из адресных входов содержимое соответствующей строки подается на выход блока.

Схема, состоящая из первого элемента задержки 14.12, с выхода которого тактовые импульсы поступают на управляющий вход девятиразрядного электронного ключа 14.11, преобразует логические уровни, появляющиеся на выходе блока ПЗУ 14.6, в импульсы, используемые для управления компонентами арифметико-логического устройства. При этом величина задержки, вносимой первым элементом задержки 14.12, определяется временем завершения переходных процессов в схеме, подключенной к информационному входу девятиразрядного электронного ключа 14.11 (элементы 14.2-14.10), после прихода очередного тактового импульса на вход 18.

Таблица 1 – Содержимое блока ПЗУ

Величина задержки, вносимой вторым элементом задержки 14.17, определяется временем выполнения операции сложения по модулю вторым n-разрядным накапливающим сумматором 11 по модулю.

Первый вход первого трехвходового элемента ИЛИ 14.1, соединенный с адресным входом трехразрядного демультиплексора 14.5, является первым входом 15 модуля управляющего блока 14, второй вход, соединенный с первым входом второго трехвходового элемента ИЛИ 14.9, является вторым входом 16 модуля управляющего блока 14, третий вход, соединенный со вторым входом второго трехвходового элемента ИЛИ 14.9 и адресным входом одноразрядного демультиплексора 14.19, является третьим входом 17 модуля управляющего блока 14.

Выход первого трехвходового элемента ИЛИ 14.1 соединен со входом инвертора 14.13 и с первым входом первого двухвходового элемента И 14.2, второй вход которого является четвертым входом 18 модуля управляющего блока 14, выход соединен со входом первого элемента задержки 14.12 и со счетным входом r-разрядного счетчика 14.3, выходы которого соединены с соответствующими информационными входами r-входового дешифратора 14.4.

Первый и второй выходы r-входового дешифратора 14.4 соединены с первым и вторым адресными входами блока ПЗУ 14.6 соответственно, третий, четвертый и пятый выходы соединены с первым, вторым и третьим разрядами информационного входа трехразрядного демультиплексора 14.5 соответственно, каждый 2k-й выход соединен с (k-1)-м входом первого (n-1)-входового элемента ИЛИ 14.7, каждый (2k+1)-й выход соединен с (k-1)-м входом второго (n-1)-входового элемента ИЛИ 14.8, где k = 3, 4, …, n, (2n+2)-й выход соединен с девятым адресным входом блока ПЗУ 14.6, (2n+3)-й выход соединен с десятым адресным входом блока ПЗУ 14.6.

Первый, второй и третий разряды первого выхода трехразрядного демультиплексора 14.5 соединены с третьим, четвертым и пятым адресными входами блока ПЗУ 14.6 соответственно, первый разряд второго выхода соединен с шестым адресным входом блока ПЗУ 14.6, второй разряд второго выхода соединен с первым входом первого (n-1)-входового элемента ИЛИ 14.7, третий разряд второго выхода соединен с первым входом второго (n-1)-входового элемента ИЛИ 14.8.

Выход первого (n-1)-входового элемента ИЛИ 14.7 соединен с седьмым адресным входом блока ПЗУ 14.6, выход второго (n-1)-входового элемента ИЛИ 14.8 соединен с восьмым адресным входом блока ПЗУ 14.6.

Шестой выход блока ПЗУ 14.6 соединен с первым входом второго двухвходового элемента И 14.10, выход которого соединен с шестым разрядом информационного входа девятиразрядного электронного ключа 14.11, второй вход соединен с выходом второго трехвходового элемента ИЛИ 14.9, третий вход которого является пятым входом 19 модуля управляющего блока 14.

Первый, второй, третий, четвертый, пятый, седьмой, восьмой и девятый выходы блока ПЗУ 14.6 соединены соответственно с первым, вторым, третьим, четвертым, пятым, седьмым, восьмым и девятым разрядами информационного входа девятиразрядного электронного ключа 14.11, управляющий вход которого соединен с выходом первого элемента задержки 14.12, первый разряд выхода соединен с R-входами второго и третьего RS-триггеров 14.16, 14.18 и с первым входом двухвходового элемента ИЛИ 14.14, а также является первым выходом модуля управляющего блока 14, второй разряд выхода соединен с S-входом второго RS-триггера 14.16, третий, четвертый, пятый, шестой и седьмой разряды выхода являются третьим, четвертым, пятым, шестым и седьмым выходами модуля управляющего блока 14 соответственно, восьмой разряд выхода соединен с S-входом первого RS-триггера 14.15, девятый разряд выхода соединен со входом второго элемента задержки 14.17, выход которого соединен с S-входом третьего RS-триггера 14.18, выход которого соединен с информационным входом одноразрядного демультиплексора 14.19, первый выход которого является девятым выходом модуля управляющего блока 14, второй выход является десятым выходом модуля управляющего блока 14.

Выход инвертора 14.13 соединен со вторым входом двухвходового элемента ИЛИ 14.14, выход которого соединен с R-входом первого RS-триггера 14.15, выход которого соединен со входом сброса r-разрядного счетчика 14.3, а также является восьмым выходом модуля управляющего блока 14. Выход второго RS-триггера 14.16 является вторым выходом модуля управляющего блока 14.

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

В исходном состоянии r-разрядный счетчик 14.3 обнулен, на входы 15, 16, 17 подается логический «0». Для начала работы устройства и на протяжении всего цикла выполнения операции на один из входов 15, 16, 17 подается уровень логической «1»: на вход 15 – при выполнении умножения чисел по модулю, на вход 16 – при выполнении сложения чисел по модулю, на вход 17 – при выполнении вычитания чисел по модулю. При этом тактовые импульсы, поступающие на вход 18, начинают подсчитываться r-разрядным счетчиком 14.3. Результат подсчета подается на вход r-входового дешифратора 14.4, и на его выходах с номерами 1, 2, …, (2n+3) последовательно появляются уровни логической «1».

При работе устройства в режиме сложения или вычитания на адресный вход трехразрядного демультиплексора 14.5 подается уровень логического «0», что соответствует подключению третьего, четвертого и пятого выходов r-входового дешифратора 14.4 к третьему, четвертому и пятому входам блока ПЗУ 14.6.

Операция сложения n-разрядных чисел по модулю выполняется за пять тактов.

С приходом первого тактового импульса на вход 18 уровень логической «1» появляется на первом выходе блока ПЗУ 14.6, что приводит к появлению на первом выходе модуля управляющего блока 14 управляющего сигнала, поступающего на первые управляющие входы (входы сброса) n-разрядных накапливающих сумматоров 8, 11 по модулю и на управляющий вход первого n-разрядного регистра 3, в результате чего происходит сброс первого и второго n-разрядных накапливающих сумматоров 8, 11 по модулю, а также считывание кода модуля P со входной n-разрядной шины 1 в первый n-разрядный регистр 3. Также происходит подача уровня логической «1» на R-входы первого (посредством двухвходового элемента ИЛИ 14.14), второго и третьего RS-триггеров 14.15, 14.6 и 14.18, что приводит к переводу данных триггеров в нулевое состояние. В результате установки в состояние «0» первого RS-триггера 14.15 происходит закрытие n-разрядного электронного ключа 12, т.е. отключение информационного выхода второго n-разрядного накапливающего сумматора 11 по модулю от выходной n-разрядной шины 13. В результате установки в состояние «0» второго RS-триггера 14.16 на адресный вход n-разрядного двухвходового мультиплексора 2 поступает уровень логического «0», вследствие чего происходит подключение информационного входа третьего n-разрядного регистра 5 к входной n-разрядной шине 1. В результате установки в состояние «0» третьего RS-триггера 14.18 на младший и старший разряды адресного входа n-разрядного трехвходового мультиплексора 10 подаются уровни логического «0», вследствие чего происходит подключение информационного выхода третьего n-разрядного регистра 5 ко второму информационному входу второго n-разрядного накапливающего сумматора 11 по модулю.

С приходом второго тактового импульса на вход 18 уровень логической «1» появляется на четвертом выходе блока ПЗУ 14.6, что приводит к подаче на четвертый выход модуля управляющего блока 14 управляющего сигнала, который поступает на управляющий вход третьего n-разрядного регистра 5, в результате чего происходит считывание со входной n-разрядной шины 1 в данный регистр кода операнда A.

С приходом третьего тактового импульса на вход 18 уровни логической «1» появляются на третьем, шестом и девятом выходах блока ПЗУ 14.6. В результате появления уровня логической «1» на третьем выходе блока ПЗУ 14.6 управляющий сигнал появляется на третьем выходе модуля управляющего блока 14, откуда поступает на первый управляющий вход второго n-разрядного регистра 4, что приводит к считыванию в данный регистр кода операнда B со входной n-разрядной шины 1. В результате появления уровня логической «1» на шестом выходе блока ПЗУ 14.6 управляющий сигнал появляется на шестом выходе модуля управляющего блока 14, вследствие чего значение операнда A, хранящееся в третьем n-разрядном регистре 5, складывается по модулю с текущим значением, хранимым во втором n-разрядном накапливающем сумматоре 11 по модулю. Поскольку на первом такте был произведен сброс данного накапливающего сумматора по модулю, значение, хранящееся в нем, будет равно A. В результате появления уровня логической «1» на девятом выходе блока ПЗУ 14.6 на S-вход третьего RS-триггера 14.18 поступает задержанный по времени управляющий сигнал, который приводит к появлению на девятом выходе модуля управляющего блока 14 уровня логической «1», который подается на младший разряд адресного входа трехвходового n-разрядного мультиплексора 10, вследствие чего ко второму информационному входу второго n-разрядного накапливающего сумматора 11 по модулю подключается выход второго n-разрядного регистра 4, хранящего значение операнда B.

С приходом четвертого тактового импульса на вход 18 уровень логической «1» появляется на шестом выходе блока ПЗУ 14.6, в результате чего управляющий сигнал появляется на шестом выходе модуля управляющего блока 14, с которого подается на второй управляющий вход второго n-разрядного накапливающего сумматора 11 по модулю. Значение операнда B, хранящееся во втором n-разрядном регистре 4, складывается по модулю P со значением A, хранимым во втором n-разрядном накапливающем сумматоре 11 по модулю.

С приходом пятого тактового импульса на вход 18 уровень логической «1» появляется на восьмом выходе блока ПЗУ 14.6, в результате чего управляющий сигнал подается на S-вход первого RS-триггера 14.15. Уровень логической «1» с выхода первого RS-триггера 14.15 подается на вход сброса r-разрядного счетчика 14.3, устанавливая счетчик в нулевое состояние, а также на восьмой выход модуля управляющего блока 14, откуда поступает на управляющий вход n-разрядного электронного ключа 12, вследствие чего результат выполнения операции, хранящийся во втором n-разрядном накапливающем сумматоре 11 по модулю, подается на выходную n-разрядную шину 13. Сброс r-разрядного счетчика 14.3 происходит по фронту управляющего импульса, поступающего на вход сброса.

Закрытие n-разрядного электронного ключа 12 происходит при поступлении тактового импульса на вход 18 при начале нового цикла выполнения операции умножения, сложения или вычитания по модулю, либо при установке на всех входах 15, 16, 17 уровня логического «0».

Операция нахождения разности n-разрядных чисел по модулю также выполняется за пять тактов. Отличие работы устройства в режиме вычитания от работы в режиме сложения заключается в том, что в результате подачи уровня логической единицы на вход 17 одноразрядный демультиплексор 14.19 подает сигнал с выхода третьего RS-триггера 14.18 на десятый, а не девятый выход модуля управляющего блока 14. Таким образом, на третьем такте работы устройства уровень логической «1» подается не на младший, а на старший разряд адресного входа n-разрядного трехвходового мультиплексора 10, в результате чего ко второму информационному входу второго n-разрядного накапливающего сумматора 11 по модулю подключается выход n-разрядного сумматора 9, на первый информационный вход которого подается код модуля P, на второй информационный вход подается инверсный код операнда B, а на вход переноса – уровень логической «1», что соответствует вычислению разности (P-B). Полученное значение на четвертом такте складывается со значением A, хранимым во втором n-разрядном накапливающем сумматоре 11 по модулю.

Операция умножения n-разрядных чисел по модулю выполняется за (2n+3) тактов. При работе устройства в режиме умножения на адресный вход трехразрядного демультиплексора 14.5 подается уровень логической «1», что соответствует подключению третьего, четвертого и пятого выходов r-входового дешифратора 14.4 к шестому, седьмому (посредством первого (n-1)-входового элемента ИЛИ 14.7) и восьмому (посредством второго (n-1)-входового элемента ИЛИ 14.8) входам блока ПЗУ 14.6 соответственно.

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

С приходом третьего тактового импульса на вход 18 уровень логической «1» появляется на втором, третьем и пятом выходах блока ПЗУ 14.6. В результате появления уровня логической «1» на втором выходе блока ПЗУ 14.6 происходит подача управляющего сигнала на S-вход второго RS-триггера 14.16, что приводит к установке на втором выходе модуля управляющего блока 14 уровня логической «1», поступающего на адресный вход n-разрядного двухвходового мультиплексора 2, вследствие чего данный мультиплексор подключает информационный выход первого n-разрядного накапливающего сумматора 8 по модулю к информационному входу третьего n-разрядного регистра 5. В результате появления уровня логической «1» на третьем выходе блока ПЗУ 14.6 управляющий сигнал появляется на третьем выходе модуля управляющего блока 14, откуда поступает на первый управляющий вход второго n-разрядного регистра 4, что приводит к считыванию в данный регистр кода операнда B со входной n-разрядной шины 1. В результате появления уровня логической «1» на пятом выходе блока ПЗУ 14.6 управляющий сигнал появляется на пятом выходе модуля управляющего блока 14, откуда поступает на второй управляющий вход (вход тактовых импульсов) первого n-разрядного накапливающего сумматора 8 по модулю, вследствие чего в данный накапливающий сумматор записывается значение операнда A, поступающее с информационного выхода третьего n-разрядного регистра 5.

С приходом на вход 18 каждого 2k-го тактового импульса, где k = 2, 3, …, n, уровень логической «1» появляется на пятом и шестом выходах блока ПЗУ 14.6. В результате появления уровня логической «1» на пятом выходе блока ПЗУ 14.6 управляющий сигнал появляется на пятом выходе модуля управляющего блока 14, откуда поступает на второй управляющий вход (вход тактовых импульсов) первого n-разрядного накапливающего сумматора 8 по модулю, вследствие чего хранимое в нем значение складывается по модулю Р с текущим частичным остатком, находящимся в третьем n-разрядном регистре 5, т.е. происходит формирование следующего частичного остатка. Уровень логической «1», появившийся на шестом выходе блока ПЗУ 14.6, поступает на первый вход второго двухвходового элемента И 14.10. Если при этом значение младшего разряда числа, хранимого во втором n-разрядном регистре 4, равно 1, то на вход 19 модуля управляющего блока 14, являющийся третьим входом второго трехвходового элемента ИЛИ 14.9, подается уровень логической «1», который поступает с выхода данного элемента ИЛИ на второй вход второго двухвходового элемента И 14.10, вследствие чего на шестом выходе модуля управляющего блока 14 появляется управляющий сигнал, поступающий на второй управляющий вход второго n-разрядного накапливающего сумматора 11 по модулю, что приводит к сложению по модулю P хранимого в нем значения с текущим частичным остатком. Если значение младшего разряда числа, хранимого во втором n-разрядном регистре 4, равно 0, управляющий сигнал на шестом выходе модуля управляющего блока 14 не появляется и прибавление текущего частичного остатка к содержимому второго n-разрядного накапливающего сумматора 11 не производится.

С приходом на вход 18 каждого (2k+1)-го тактового импульса, где k = 2, 3, …, n, уровень логической «1» появляется на четвертом и седьмом выходах блока ПЗУ 14.6. В результате появления уровня логической «1» на четвертом выходе блока ПЗУ 14.6 управляющий сигнал подается на четвертый выход модуля управляющего блока 14, с которого поступает на управляющий вход третьего n-разрядного регистра 5, что приводит к записи в данный регистр частичного остатка, поступающего с информационного выхода первого n-разрядного накапливающего сумматора 8 по модулю. Данный частичный остаток будет использован на следующем такте выполнения операции. В результате появления уровня логической «1» на седьмом выходе блока ПЗУ 14.6 управляющий сигнал подается на седьмой выход модуля управляющего блока 14, с которого поступает на второй управляющий вход второго n-разрядного регистра 4, в результате чего происходит сдвиг значения, хранимого в данном регистре, на один разряд вправо.

С приходом на вход 18 (2n+2)-го тактового импульса уровень логической «1» появляется на шестом выходе блока ПЗУ 14.6. Если при этом младший разряд числа, находящегося во втором n-разрядном регистре 4, равен 1, на шестой выход модуля управляющего блока 14 поступает управляющий сигнал, в результате чего производится сложение по модулю P последнего частичного остатка со значением, хранимым во втором n-разрядном накапливающем сумматоре 11 по модулю.

С приходом на вход 18 (2n+3)-го тактового импульса уровень логической «1» появляется на восьмом выходе блока ПЗУ 14.6, в результате чего управляющий сигнал подается на S-вход первого RS-триггера 14.15. Уровень логической «1» с выхода первого RS-триггера 14.15 подается на вход сброса r-разрядного счетчика 14.3, устанавливая счетчик в нулевое состояние, а также на восьмой выход модуля управляющего блока 14, откуда поступает на управляющий вход n-разрядного электронного ключа 12, вследствие чего результат выполнения операции умножения чисел по модулю, хранящийся во втором n-разрядном накапливающем сумматоре 11 по модулю, подается на n-разрядную выходную шину 13.

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

Пусть n=4, A=7, B=9, P=13. Операция умножения по модулю выполняется за (2n+3)=11 тактов.

На первом такте производится считывание со входной шины 1 кода модуля P=13₁₀=1101₂ в первый регистр 3.

На втором такте со входной шины 1 считывается код множителя A=7₁₀=0111₂ в третий регистр 5.

На третьем такте со входной шины считывается код множителя B=9₁₀=1001₂ во второй регистр 4, а код множителя A=7₁₀=0111₂ записывается в первый накапливающий сумматор 8 по модулю.

На четвертом такте происходит вычисление первого частичного остатка путем сложения по модулю P=13 значения, находящегося в третьем регистре 5, со значением, хранимым в первом накапливающем сумматоре 8 по модулю: 7+7≡1 (mod 13). Поскольку младший разряд B=1001₂ равен 1, к содержимому второго накапливающего сумматора 11 по модулю прибавляется значение нулевого частичного остатка: 0+7≡7 (mod 13).

На пятом такте сдвигается на один разряд вправо содержимое второго регистра 4, в котором хранится значение множителя B=1001₂, т.е. B^/=0100₂, а также происходит запись первого частичного остатка, равного 1, в третий регистр 5.

На шестом такте происходит вычисление второго частичного остатка: 1+1≡2 (mod 13). Младший разряд B^/=0100₂ равен 0, поэтому первый частичный остаток, хранящийся в третьем регистре 5, не прибавляется к содержимому второго накапливающего сумматора 11 по модулю.

На седьмом такте сдвигается на один разряд вправо содержимое второго регистра 4, в котором хранится значение B^/=0100₂, т.е. B^//=0010₂, а также происходит запись второго частичного остатка, равного 2, в третий регистр 5.

На восьмом такте происходит вычисление третьего частичного остатка: 2+2≡4 (mod 13). Младший разряд B^//=0010₂ равен 0, поэтому второй частичный остаток, хранящийся в третьем регистре 5, не прибавляется к содержимому второго накапливающего сумматора 11 по модулю.

На девятом такте сдвигается на один разряд вправо содержимое второго регистра 4, в котором хранится значение B^//=0010₂, т.е. B^///=0001₂, а также происходит запись третьего частичного остатка, равного 4, в третий регистр 5.

Поскольку младший разряд B^///=0001₂ равен 1, на десятом такте к содержимому накапливающего сумматора 11 по модулю прибавляется значение третьего частичного остатка, хранящегося в третьем регистре 5: 7+4≡11 (mod 13).

На одиннадцатом такте содержимое второго накапливающего сумматора 11 по модулю подается на выходную шину 13. Таким образом, результат операции умножения по модулю равен 11. Умножение выполнено корректно, поскольку 7∙9≡11 (mod 13)

Рассмотрим процесс выполнения устройством операции сложения чисел по модулю для заданных ранее значений n, A, B, P.

На первом такте производится считывание со входной шины 1 кода модуля P=13₁₀=1101₂ в первый регистр 3.

На втором такте со входной шины 1 считывается код слагаемого A=7₁₀=0111₂ в третий регистр 5.

На третьем такте со входной шины 1 считывается код слагаемого B=9₁₀=1001₂ во второй регистр 4. Значение операнда A, хранящееся в третьем регистре 5, записывается во второй накапливающий сумматор 11 по модулю. Ко второму информационному входу второго накапливающего сумматора 11 по модулю подключается выход второго регистра 4, хранящего значение операнда B.

На четвертом такте значение A, хранящееся во втором накапливающем сумматоре 11 по модулю, складывается по модулю 13 со значением B, поступающим с выхода второго регистра 4: 7+9≡3 (mod 13).

На пятом такте содержимое второго накапливающего сумматора 11 по модулю подается на выходную шину 13. Таким образом, результат операции сложения по модулю равен 3.

Рассмотрим процесс выполнения устройством операции нахождения разности чисел по модулю.

На первом такте производится считывание со входной шины 1 кода модуля P=13₁₀=1101₂ в первый регистр 3.

На втором такте со входной шины 1 считывается код уменьшаемого A=7₁₀=0111₂ в третий регистр 5.

На третьем такте со входной шины 1 считывается код вычитаемого B=9₁₀=1001₂ во второй регистр 4. Значение операнда A, хранящееся в третьем регистре 5, записывается во второй накапливающий сумматор 11 по модулю. Ко второму информационному входу второго накапливающего сумматора 11 по модулю подключается выход сумматора 9, на первый информационный вход которого подается код модуля P=1101₂, на второй информационный вход подается инверсный код вычитаемого B_инв=0110₂, а на вход переноса – уровень логической «1». Результат работы сумматора 9 равен 1101₂+0110₂+1=10100₂. Поскольку сумматор имеет разрядность n=4, на его выход поступает значение 0100₂=4₁₀.

На четвертом такте значение A, хранящееся во втором накапливающем сумматоре 11 по модулю, складывается по модулю P=13 со значением, поступающим с выхода сумматора 9: 7+4≡11 (mod 13).

На пятом такте содержимое второго накапливающего сумматора 11 по модулю подается на выходную шину 13. Таким образом, результат операции вычитания по модулю равен 11. Операция выполнена верно, поскольку 7-9≡11 (mod 13).