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

Изобретение относится в вычислительной технике. Технический результат заключается в уменьшении энергопотребления. Устройство содержит три n-разрядных регистра, где n – разрядность входных чисел, инвертор, (n+1)-разрядный сумматор, мультиплексор, электронный ключ, входную и выходную n-разрядные шины, модуль управляющего блока. 2 ил.

 

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

Известно устройство для формирования остатка по произвольному модулю от числа, содержащее первый и второй регистр, первый и второй элементы ИЛИ, вычислитель, первую схему сравнения и мультиплексор (Авторское свидетельство СССР N 1633495, кл. H03M 7/18, 1989).

Недостатком данного устройства является низкое быстродействие процесса формирования остатка.

Известно устройство для формирования остатка по произвольному модулю от числа, содержащее l блоков формирования частичных остатков, (l+1) умножителей по модулю, сумматор по модулю и блок распределения коэффициентов (Патент РФ N 2324972, кл. G06F 7/72, H03M 7/18, 2008).

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

Наиболее близким по технической сущности к заявляемому изобретению является арифметико-логическое устройство для выполнения операции деления, содержащее три 8-разрядных регистра, 8-разрядный сумматор, мультиплексор, инвертор, счетчик количества циклов, схему выработки признаков результата, четыре триггера, входную и выходную шины, модуль управляющего блока, содержащий 8-разрядные регистры делителя и делимого, двухканальный 8-разрядный мультиплексор, логические элементы «Исключающее ИЛИ», 8-разрядный сумматор, восемь JK-триггеров, логические элементы «НЕ И», дешифратор, инверторы, логические элементы «И», двоичный 4-разрядный счетчик циклов и логические элементы «ИЛИ» (Бабич Н.П., Жуков И.А. Компьютерная схемотехника. Методы построения и проектирования: Учебное пособие. – К.: «МК-Пресс», 2004. – 576 с. рис. 9.22, стр. 308-322).

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

Техническим результатом данного изобретения является сокращение объема оборудования и, как следствие, уменьшение энергопотребления за счет исключения трех элементов «Исключающее ИЛИ», восьми JK-триггеров, двух инверторов, логического элемента «И», десяти логических элементов «НЕ И» и логического элемента «ИЛИ».

Для достижения технического результата в арифметико-логическое устройство для выполнения операции деления, содержащее три n-разрядных регистра, где n – разрядность входных чисел, инвертор, мультиплексор, модуль управляющего блока, входную и выходную n-разрядные шины, (n+1)-разрядный сумматор, причём первый управляющий вход первого n-разрядного регистра соединен с первым выходом модуля управляющего блока, а выход старшего разряда соединен с младшим разрядом первого информационного входа (n+1)-разрядного сумматора, информационный вход второго n-разрядного регистра соединен с входной n-разрядной шиной, управляющий вход соединен со вторым выходом модуля управляющего блока, а выход соединен с входом инвертора, выход которого соединен с младшими n разрядами второго информационного входа (n+1)-разрядного сумматора, младшие n разрядов информационного выхода которого соединены со вторым информационным входом мультиплексора, на первый вход модуля управляющего блока подается одноразрядный код команды формирования остатка по модулю, введен электронный ключ, причём информационный вход первого n-разрядного регистра соединен с входной n-разрядной шиной, второй управляющий вход с четвертым выходом модуля управляющего блока, а старший разряд выхода соединен с младшим разрядом первого информационного входа мультиплексора, на старший разряд второго информационного входа (n+1)-разрядного сумматора, а также на его вход переноса подается сигнал логической «1», а его выход переноса соединен с управляющим входом мультиплексора, выход которого соединен с информационным входом третьего n-разрядного регистра, управляющий вход которого соединен с третьим выходом модуля управляющего блока, выход соединен с информационным входом электронного ключа, а также со старшими n разрядами первого информационного входа (n+1)-разрядного сумматора, выходы младших (n-1) разрядов соединены со старшими (n-1) разрядами первого информационного входа мультиплексора, управляющий вход электронного ключа соединен с пятым выходом модуля управляющего блока, а выход соединен с выходной n-разрядной шиной, на второй вход модуля управляющего блока подаются тактовые импульсы.

Сущность изобретения заключается в реализации следующего способа вычисления остатка R от числа A по модулю P. Пусть

A = Q·P +R, (1)

где A – целое положительное число, от которого необходимо вычислить остаток;

P – целое положительное число, называемое модулем;

Q – целое положительное число, являющееся неполным частным от деления A на P;

R – целое положительное число, являющееся остатком от деления A на P.

Причем

A = a_n-1·2^n-1+a_n-2·2^n-2+ . . . +a₁·2¹+a₀, (2)

P = p_n-1·2^n-1+p_n-2·2^n-2+ . . . +p₁·2¹+p₀, (3)

Q = q_n-2·2^n-2+ . . . +q₁·2¹+q₀, (4)

R = r_n-2·2^n-2+ . . . +r₁·2¹+r₀, (5)

где a_i, – коэффициенты, принимающие значение 0 или 1 в зависимости от значения числа A;

p_i, – коэффициенты, принимающие значение 0 или 1 в зависимости от значения модуля P;

q_i, – коэффициенты, принимающие значение 0 или 1 в зависимости от значения неполного частного Q;

r_i, – коэффициенты, принимающие значение 0 или 1 в зависимости от значения остатка R;

n – количество разрядов в представлении чисел.

Задача состоит в том, чтобы по известным A и P отыскать остаток R. Остаток R является в терминах теории чисел вычетом числа A по модулю P, поэтому говорят, что A сравнимо с R по модулю P:

A R (mod P). (6)

Значение остатка R может быть вычислено следующим образом:

R = A (mod P)= (a_n-1·2^n-1+a_n-2·2^n-2+ . . . +a₁·2¹+a₀)mod P. (7)

Выражение (7) может быть представлено в следующем виде:

R = ((. . . (a_n-1·2+a_n-2)·2+. . . +a₁)·2+a₀) mod P . (8)

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

Исходя из вышесказанного, выражение (8) может быть представлено в виде

R = ((...(a_n-1·2+a_n-2)(mod P)·2+a_n-3)(mod P)·2+...+a₁)(mod P)·2+a₀)(mod P) (9)

В таком виде значительно облегчается задача нахождения остатка R от числа А.

При проведении вычислений по модулю P значение выражения
(a_n-1·2+a_n-2) сравнивается с модулем P. Если значение (a_n-1·2+a_n-2) ≥ P, то из числа (a_n-1·2+a_n-2) вычитается значение модуля P, то есть
t₁=(a_n-1·2+a_n-2)-P. Если (a_n-1·2+a_n-2)< P, то число (a_n-1·2+a_n-2) остается без изменений t₁=(a_n-1·2+a_n-2). Полученное в результате значение t₁ умножается на 2, складывается с и сравнивается со значением P. Если значение (t₁·2+a_n-3) ≥ P, то из (t₁·2+a_n-3) вычитается значение модуля P, то есть t₂=(t₁·2+a_n-3) - P. Если (t₁·2+a_n-3) < P, то число (t₁·2+a_n-3) остается без изменений, t₂=(t₁·2+a_n-3). Полученное в результате значение t₂ умножается на 2, складывается с и сравнивается со значением P и т.д. На последнем (n-1)-м шаге число
(t_n-2·2+a₀) сравнивается с модулем P. Если значение (t_n-2·2+a₀) ≥ P, то из (t_n-2·2+a₀) вычитается значение числа P, то есть t_n-1=(t_n-2·2+a₀) - P. Если (t_n-2·2+a₀) < P, то число (t_n-2·2+a₀) остается без изменений
t_n-1=(t_n-2·2+a₀). Полученное в результате значение R=t_n-1 является остатком от деления числа A на число P.

Операция умножения на два при вычислении выражения (t_i·2+a_n-2-i) во всех случаях осуществляется сдвигом всех разрядов множимого на один в сторону старших. Суммирование осуществляется путем подачи коэффициента a_i на самый младший разряд множимого. Ввиду того, что коэффициенты a_i могут принимать значение «0» или «1», а самый младший разряд множимого после сдвига всегда будет равен «0», то переноса в следующий разряд при таком решении возникать не будет.

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

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

Информационные входы первого и второго n-разрядных регистров 2, 3 соединены с входной n-разрядной шиной 1. Первый управляющий вход первого n-разрядного регистра 2 соединен с первым выходом модуля управляющего блока 10, второй управляющий вход с четвертым выходом модуля управляющего блока 10, а выход старшего разряда соединен с младшим разрядом первого информационного входа (n+1)-разрядного сумматора 5, а также с младшим разрядом первого информационного входа мультиплексора 6.

Управляющий вход второй n-разрядного регистра 3 соединен со вторым выходом модуля управляющего блока 10, а выход соединен со входом инвертора 4, выход которого соединен с младшими n разрядами второго информационного входа (n+1)-разрядного сумматора 5.

На старший разряд второго информационного входа (n+1)-разрядного сумматора 5, а также на его вход переноса подается сигнал логической «1», младшие n разрядов его информационного выхода соединены со вторым информационным входом мультиплексора 6, а его выход переноса соединен с управляющим входом мультиплексора 6.

Выход мультиплексора 6 соединен с информационным входом третьего n-разрядного регистра 7, управляющий вход которого соединен с третьим выходом модуля управляющего блока 10, выход соединен с информационным входом электронного ключа 8, а также со старшими n разрядами первого информационного входа (n+1)-разрядного сумматора 5, а выходы младших (n-1) разрядов соединены со старшими (n-1) разрядами первого информационного входа мультиплексора 6.

Управляющий вход электронного ключа 8 соединен с пятым выходом модуля управляющего блока 10, а выход соединен с выходной n-разрядной шиной 9. На первый вход 11 модуля управляющего блока 10 подается одноразрядный код команды формирования остатка по модулю, а на второй вход 12 подаются тактовые импульсы.

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

Модуль управляющего блока 10 содержит двухвходовый элемент И 10.1, двухвходовый элемент ЗАПРЕТ 10.2, r-разрядный счётчик 10.3, где , r-входовый дешифратор 10.4, n-входовый элемент ИЛИ 10.5, (n-1)-входовый элемент ИЛИ 10.6.

Первый вход двухвходового элемента И 10.1 является первым входом 11 модуля управляющего блока 10, второй вход является вторым входом 12 модуля управляющего блока 10, а выход соединен со счётным входом r-разрядного счётчика 10.3 и с запрещающим входом двухвходового элемента ЗАПРЕТ 10.2, выход которого соединён с управляющим входом r-разрядного счётчика 10.3, выходы которого соединены с соответствующими информационными входами r-входового дешифратора 10.4.

Первый выход r-входового дешифратора 10.4 соединен с первым выходом модуля управляющего блока 10, второй выход соединен со вторым выходом модуля управляющего блока 10. Каждый (2k+1)-й выход r-входового дешифратора 10.4, где k = 1, 2, …, n, соединен с k-м входом n-входового элемента ИЛИ 10.5, выход которого соединен с третьим выходом модуля управляющего блока 10. Каждый (2k+2)-й выход r-входового дешифратора 10.4, где k = 1, 2, …, n-1, соединён с k-м входом (n-1)-входового элемента ИЛИ 10.6, выход которого соединен с четвертым выходом модуля управляющего блока 10. (2n+2)-й выход r-входового дешифратора 10.4 соединен с пятым выходом модуля управляющего блока 10, а также с разрешающим входом двухвходового элемента ЗАПРЕТ 10.2.

Формирование остатка от n-разрядного числа A по модулю P осуществляется за (2n+2) тактов, где n – разрядность входных чисел.

В исходном состоянии r-разрядный счётчик 10.3 обнулён, на вход 11 команды формирования остатка подаётся логический «0». Для начала работы устройства и на протяжении всего цикла формирования остатка на вход 11 команды формирования остатка устройства подаётся сигнал логической «1». При этом тактовые импульсы, поступающие на вход тактовых импульсов 12, начинают подсчитываться r-разрядным счётчиком 10.3. Результат подсчёта подаётся на вход r-входового дешифратора 10.4, и на его выходах с номерами 1,…, (2n+2) последовательно появляются импульсы.

С приходом первого тактового импульса на вход тактовых импульсов 12 на первом выходе r-входового дешифратора 10.4 появляется сигнал логической единицы, который поступает на выход y₁ модуля управляющего блока 10. Сигнал с выхода y₁ модуля управляющего блока 10 поступает на управляющий вход первого n-разрядного регистра 2, в результате чего происходит считывание кода числа A с входной n-разрядной шины 1 в первый n-разрядный регистр 2.

С приходом второго тактового импульса на вход тактовых импульсов 12 сигнал логической «1» появляется на втором выходе r-входового дешифратора 10.4 и передаётся на выход y₂ модуля управляющего блока 10. Этот сигнал поступает на управляющий вход второго n-разрядного регистра 3, в результате чего происходит считывание в данный регистр кода модуля P.

С приходом (2k+1)-го тактового импульса, где k = 1, 2, …, n, сигнал логической «1» появляется на (2k+1)-м выходе r-входового дешифратора 10.4, откуда передаётся через n-входовый элемент ИЛИ 10.5 на третий выход модуля управляющего блока 10. Далее он поступает на управляющий вход третьего n-разрядного регистра 7 в результате чего происходит считывание в третий n-разрядный регистр 7 очередного частичного остатка.

С приходом (2k+2)-го тактового импульса, где k = 1,2,…,n-1, сигнал логической «1» появляется на (2k+2)-м выходе r-входового дешифратора 10.4, откуда передаётся через (n-1)-входовый элемент ИЛИ 10.6 на выход y₄ модуля управляющего блока 10. Сигнал с выхода y₄ модуля управляющего блока 10 поступает на управляющий вход первого n-разрядного регистра 2, что приводит к сдвигу находящегося в нем значения на один разряд в сторону старшего.

С приходом (2n+2)-го тактового импульса сигнал логической «1» появляется на (2n+2)-м выходе r-входового дешифратора 10.4, откуда поступает на выход y₅ модуля управляющего блока 10 и на разрешающий вход двухвходового элемента ЗАПРЕТ 10.2. С выхода y₅ модуля управляющего блока 10 сигнал поступает на управляющий вход электронного ключа 8, и результат формирования остатка от n-разрядного числа A по модулю P подаётся с выхода третьего n-разрядного регистра 7 на выходную n-разрядную шину 9. После спада (2n+2)-го тактового импульса на запрещающий вход двухвходового элемента ЗАПРЕТ 10.2 поступает логический «0» и на его выходе устанавливается сигнал логической «1», который подаётся на вход сброса r-разрядного счётчика 10.3 и, таким образом, обнуляет счётчик. Цикл формирования остатка завершён.

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

Пусть n = 4, A = 14, P = 5. Формирование остатка выполняется за (2n+2) = 10 тактов.

На первом такте производится считывание с входной n-разрядной шины 1 кода модуля A = 14 в первый n-разрядный регистр 2.

На втором такте с входной n-разрядной шины 1 считывается код значения P = 5 во второй n-разрядный регистр 3.

На третьем такте, поскольку значение суммы удвоенного обнуленного содержимого третьего n-разрядного регистра 7 и старшего разряда A = 1110₂ равное единице, меньше модуля P, в третий n-разрядный регистр 7 записывается новое значение частичного остатка q_нов = 0001₂, представляющего собой значение суммы удвоенного содержимого третьего n-разрядного регистра 7 и старшего разряда A.

На четвертом такте сдвигается на один разряд влево содержимое первого n-разрядного регистра 2, в котором хранится значение множителя A = 1110₂, т.е. теперь в первом n-разрядном регистре 2 будет число 1100₂.

На пятом такте, поскольку значение суммы удвоенного предыдущего частичного остатка q_пред = 0001₂ и старшего разряда A = 1100₂ равное трем, меньше модуля P, в третий n-разрядный регистр 7 записывается новое значение частичного остатка q_нов = 0011₂, представляющего собой значение суммы удвоенного предыдущего частичного остатка q_пред = 0001₂ и старшего разряда A = 1100₂.

На шестом такте сдвигается на один разряд влево содержимое первого n-разрядного регистра 2, в котором хранится значение множителя A = 1100₂, т.е. теперь в первом n-разрядном регистре 2 будет число 1000₂.

На седьмом такте, поскольку значение суммы удвоенного предыдущего частичного остатка q_пред = 0011₂ и старшего разряда A = 1000₂ равное семи, больше модуля P, в третий n-разрядный регистр 7 записывается новое значение частичного остатка q_нов = 0010₂, представляющего собой значение разности суммы удвоенного предыдущего частичного остатка q_пред = 0011₂ и старшего разряда A = 1000₂ со значением модуля P = 0101₂.

На восьмом такте сдвигается на один разряд влево содержимое первого n-разрядного регистра 2, в котором хранится значение множителя A = 1000₂, т.е. теперь в первом n-разрядном регистре 2 будет число 0000₂.

На девятом такте, поскольку значение суммы удвоенного предыдущего частичного остатка q_пред = 0010₂ и старшего разряда A = 0000₂ равное четырем, меньше модуля P, в третий n-разрядный регистр 7 записывается новое значение частичного остатка q_нов = 0100₂, представляющего собой значение суммы удвоенного предыдущего частичного остатка q_пред = 0010₂ и старшего разряда A = 0000₂.

На десятом такте содержимое третьего n-разрядного регистра 7 подаётся на выходную n-разрядную шину 9. Таким образом, результат операции формирования остатка по модулю равен 4. Операция выполнена корректно, поскольку 14 (mod 5) = 4.

Арифметико-логическое устройство для формирования остатка по произвольному модулю от числа, содержащее три n-разрядных регистра, где n – разрядность входных чисел, инвертор, мультиплексор, модуль управляющего блока, входную и выходную n-разрядные шины, (n+1)-разрядный сумматор, причём первый управляющий вход первого n-разрядного регистра соединен с первым выходом модуля управляющего блока, а выход старшего разряда соединен с младшим разрядом первого информационного входа (n+1)-разрядного сумматора, информационный вход второго n-разрядного регистра соединен с входной n-разрядной шиной, управляющий вход соединен со вторым выходом модуля управляющего блока, а выход соединен с входом инвертора, выход которого соединен с младшими n разрядами второго информационного входа (n+1)-разрядного сумматора, младшие n разрядов информационного выхода которого соединены со вторым информационным входом мультиплексора, на первый вход модуля управляющего блока подается одноразрядный код команды формирования остатка по модулю, отличающееся тем, что в него введены, электронный ключ, причём информационный вход первого n-разрядного регистра соединен с входной n-разрядной шиной, второй управляющий вход - с четвертым выходом модуля управляющего блока, а старший разряд выхода соединен с младшим разрядом первого информационного входа мультиплексора, на старший разряд второго информационного входа (n+1)-разрядного сумматора, а также на его вход переноса подается сигнал логической «1», а его выход переноса соединен с управляющим входом мультиплексора, выход которого соединен с информационным входом третьего n-разрядного регистра, управляющий вход которого соединен с третьим выходом модуля управляющего блока, выход соединен с информационным входом электронного ключа, а также со старшими n разрядами первого информационного входа (n+1)-разрядного сумматора, выходы младших (n-1) разрядов соединены со старшими (n-1) разрядами первого информационного входа мультиплексора, управляющий вход электронного ключа соединен с пятым выходом модуля управляющего блока, а выход соединен с выходной n-разрядной шиной, на второй вход модуля управляющего блока подаются тактовые импульсы, причём модуль управляющего блока содержит двухвходовый элемент И, двухвходовый элемент ЗАПРЕТ, n-входовый элемент ИЛИ, (n-1)-входовый элемент ИЛИ, r-разрядный счётчик, где , r-входовый дешифратор, причём первый вход двухвходового элемента И является первым входом модуля управляющего блока, второй вход является вторым входом модуля управляющего блока, а выход соединен со счётным входом r-разрядного счётчика и с запрещающим входом двухвходового элемента ЗАПРЕТ, выход которого соединён с управляющим входом r-разрядного счётчика, выходы которого соединены с соответствующими информационными входами r-входового дешифратора, первый выход которого соединен с первым выходом модуля управляющего блока, второй выход соединен со вторым выходом модуля управляющего блока, каждый (2k+1)-й выход, где k = 1, 2, …, n, соединен с k-м входом n-входового элемента ИЛИ, выход которого соединен с третьим выходом модуля управляющего блока, каждый (2k+2)-й выход r-входового дешифратора, где k = 1, 2, …, n-1, соединён с k-м входом (n-1)-входового элемента ИЛИ, выход которого соединен с четвертым выходом модуля управляющего блока, (2n+2) выход r-входового дешифратора соединен с пятым выходом модуля управляющего блока, а также с разрешающим входом двухвходового элемента ЗАПРЕТ.