ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО
COMPUTING DEVICE

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах цифровой обработки сигналов и в системах управления.
Известно устройство для формирования остатка по произвольному модулю от числа, содержащее регистры, элементы ИЛИ, вычислитель, схемы сравнения, мультиплексор, элемент задержки, сумматор, группу блоков элементов «И» и блок постоянной памяти со связями (см. АС СССР №1633495, кл. H 03 M 7/18, 1991).
Недостатком известного устройства является низкая надежность, так как для его реализации требуется большой объем оборудования.
Известен комбинационный рекуррентный формирователь остатков, содержащий комбинационный формирователь частичных остатков, блок ключей и блок сумматоров по модулю (см. патент РФ №2029435, кл. 6 H 03 M 7/18, 20.02.1995, бюл. №5).
Недостатком данного устройства являются его ограниченные функциональные возможности, а именно отсутствие возможности формирования неполного частного.
Наиболее близким по технической сущности к заявляемому изобретению является вычислительное устройство, содержащее сумматоры и мультиплексоры (см. патент РФ № 2348965, МПК G06F 7/72 (2006.01), H03M 7/18 (2006.01), 10.03.2009. Бюл. № 7).
Недостатком данного вычислительного устройства является большой объем оборудования.
Техническим результатом изобретения является сокращение объема оборудования и как следствие уменьшения энергопотребления за счет исключения n сумматоров.
Для достижения технического результата в вычислительном устройстве, содержащем (n-1) сумматоров и (n-1) мультиплексоров, где n-разрядность входного числа, образующих (n-1) ступеней преобразования, причем i-я ступень преобразования, где i=2,.., n-1, соединена с (n-i-1)-м разрядом двоичного кода входного числа, а первая ступень преобразования соединена с (n-1)-м и (n-2)-м разрядами двоичного кода входного числа, на первые информационные входы сумматоров подается дополнительный двоичный код модуля, информационные выходы сумматора i-й ступени преобразования, где i=1,.., n-1, соединены с первыми информационными входами мультиплексора этой же ступени преобразования, а выходы переноса соединены с управляющими входами соответствующих мультиплексоров и являются информационными выходами двоичного кода неполного частного устройства, информационный выход мультиплексора (n-1)-й ступени преобразования является информационным выходом двоичного кода остатка устройства, информационные выходы мультиплексоров (1,.., n-2)-й ступеней преобразования соединены со сдвигом на один двоичный разряд в сторону старшего со вторыми информационными входами сумматоров (2,.., n-1)-й ступени преобразования соответственно, также информационные выходы мультиплексоров (1,.., n-2)-й ступени преобразования соединены со сдвигом на один двоичный разряд в сторону старшего со вторыми информационными входами мультиплексоров (2,.., n-1)-й ступени преобразования, i-й разряд двоичного кода входного числа, где i=0,.., n-2, соединен с младшим разрядом вторых информационных входов сумматоров и с младшим разрядом вторых информационных входов мультиплексоров (n-i-1)-й ступени преобразования, (n-1)-й разряд двоичного кода входного числа соединен со вторым разрядом второго информационного входа мультиплексора и со вторым разрядом второго информационного входа сумматора первой ступени преобразования.
Сущность изобретения заключается в реализации следующего способа формирования остатка по произвольному модулю.
Пусть требуется сформировать остаток R от числа A по модулю P и вычислить частное Q, то есть решить уравнение A=QP+R.
Число  может быть представлено в позиционной двоичной системе счисления в виде:
i
где a,  - коэффициенты, принимающие значения 0 или 1;
- количество разрядов в двоичном представлении числа .
Это выражение может быть представлено в следующем виде:
.
.
Из теории чисел известно, что операция приведения по модулю инвариантна к сложению и умножению, т. е. величина остатка не зависит от того, вычислен он от суммы (произведения) или от каждого слагаемого (сомножителя), а затем соответствующие частичные остатки просуммированы (перемножены) и от результата вычислен остаток по модулю.
В таком виде значительно облегчается задача нахождения остатка R от числа А.
n-1
n-2
n-1
n-2
n-1
n-2
1
n-1
n-2
n-1
n-2
n-1
n-2
1
n-1
n-2
1
n-3
1
n-3
1
n-3
2
1
n-3
1
n-3
1
n-3
2
1
n-3
2
n-4
n-2
0
n-2
0
n-2
0
n-1
n-2
0
n-2
0
n-2
0
n-1
n-2
0
n-1
i
(n-i-1)
i
(n-i-1)
i
i
(n-i-1)
i
(n-i-1)
При проведении вычислений по модулю P на первой ступени преобразования значение выражения (2a+a) сравнивается с модулем P, где n - количество разрядов числа A. Если значение (2a+a)≥P, то из числа (2a+a) вычитается значение модуля P, то естьt=(2a+a)-P. При этом формируется ненулевой старший (n-2)-й разряд неполного частного Q. Если (2a+a)<P, то число (2a+a) остается без изменений t=(2a+a), а значение старшего (n-2)-го разряда неполного частного Q принимается равным нулю. Полученное на первой ступени преобразования значение t на второй ступени преобразования умножается на 2, складывается с a и сравнивается со значением P. Если значение (2t+a) ≥ P, то из (2t+a) вычитается значение модуля P, то есть t=(2t+a)-P, при этом формируется ненулевой (n-3)-й разряд неполного частного Q. Если (2t+a)<P, то число (2t+a) остается без изменений t=(2t+a), а значение(n-3)-го разряда неполного частного Q принимается равным нулю. Полученное в результате значение t на третьей ступени преобразования умножается на 2, складывается с a и сравнивается со значением P и т.д. На (n-1)-й ступени преобразования число (2t+a) сравнивается с модулем P. Если значение (2t+a) ≥ P, то из (2t+a) вычитается значение числа P, то есть t=(2t+a)-P, при этом формируется ненулевой младший разряд неполного частного Q. Если (2t+a) < P, то число (2t+a) остается без изменений t=(2t+a), а значение младшего разряда неполного частного Q принимается равным нулю. Полученное в результате значение R=t является остатком от деления числа A на число P. Операция умножения на два во всех случаях осуществляется сдвигом всех разрядов множимого на один в сторону старших. Сравнения выполняются на каждой ступени преобразования с использованием сумматора и мультиплексора. Сумматор выполняет операцию вычисления выражения 2x+a-P, где x – результаты вычислений на предыдущей ступени преобразования. Значение модуля P подается на информационный вход сумматора в дополнительном коде, что эквивалентно выполнению вычитания. Значение aподается на самый младший разряд второго информационного входа сумматора, который в результате сдвига кода x на один разряд в сторону старших оказывается свободен. Мультиплексор управляется сигналом переноса с сумматора, который при 2x+a ≥ P принимает значение «1», при 2x+a < P принимает значение «0».
На фиг.1 представлена схема вычислительного устройства.
Вычислительное устройство содержит (n-1) сумматоров 1 и (n-1) мультиплексоров 2, где n-разрядность входного числа, образующих(n-1) ступеней преобразования, причем i-я ступень преобразования, где i=1,.., n-2,  соединена с (n-i-1)-м разрядом двоичного кода входного числа A, а первая ступень преобразования соединена с(n-1)-м и (n-2)-м разрядами двоичного кода входного числа A, входы 3 устройства являются входами подачи двоичного кода числа A, входы 4 устройства являются входами подачи дополнительного двоичного кода модуля P, выходы 5 устройства являются выходами кода неполного частного Q, а выходы 6 устройства являются выходами кода остатка R, на первые информационные входы сумматоров 1 со входов 4 устройства подается дополнительный двоичный код модуля P, информационные выходы сумматора 1 i-й ступени преобразования, где i=1,.., n-1, соединены с первыми информационными входами мультиплексора 2 этой же ступени преобразования, а выходы переноса соединены с управляющими входами соответствующих мультиплексоров 2 и соединены с выходами 5 устройства двоичного кода неполного частного Q, информационный выход мультиплексора 2 (n-1)-й ступени преобразования соединен с выходом 6 устройства двоичного кода остатка R, информационные выходы мультиплексоров 2 (1,.., n-2)-й ступеней преобразования соединены со сдвигом на один двоичный разряд в сторону старшего со вторыми информационными входами сумматоров 1 (2,.., n-1)-й ступени преобразования соответственно, информационные выходы мультиплексоров 2 (1,.., n-2)-й ступени преобразования соединены со сдвигом на один двоичный разряд в сторону старшего со вторыми информационными входами мультиплексоров 2 (2,.., n-1)-й ступени преобразования, i-й разряд двоичного кода входного числа A, где i=0,.., n-2, соединен с младшим разрядом вторых информационных входов сумматоров 1 и с младшим разрядом вторых информационных входов мультиплексоров 2(n-i-1)-й ступени преобразования, (n-1)-й разряд двоичного кода входного числа A соединен со вторым разрядом второго информационного входа мультиплексора 2 и со вторым разрядом второго информационного входа сумматора 1 первой ступени преобразования.
Вычислительное устройство работает следующим образом.
n-1
n-2
n-2
n-1
n-1
n-2
n-1
n-2
1
n-1
n-2
n-1
n-2
1
n-1
n-2
1
n-3
1
n-3
1
n-3
1
n-3
2
1
n-3
2
1
n-3
На первые информационные входы сумматоров 1 подается дополнительный код модуля P со входов 4 устройства. На вторые информационные входы сумматора 1 первой ступени преобразования подается код двух старших разрядов числа A a и a, причем код разряда aподается на младший разряд сумматора 1, а код разряда a подается на второй разряд. Аналогичным образом подается код двух старших разрядов на второй информационный вход мультиплексора 2 первой ступени преобразования. Сумматор 1 первой ступени преобразования выполняет операцию (2a+a)-P. Если значение(2a+a) окажется ≥P, то на выходе переноса сумматора 1 появится «1», которая подключит к выходу мультиплексора 2 первой ступени преобразования его первый информационный вход и на его выходе появится значение t=(2a+a)-P. Если же значение (2a+a) окажется <P, то на выходе переноса сумматора 1 появится «0» и информационный выход мультиплексора 2 первой ступени преобразования окажется скоммутированным с его вторым информационным выходом. В результате на информационном выходе мультиплексора 2 первой ступени преобразования окажется число t=(2a+a). Число tс информационного выхода мультиплексора 2 со сдвигом на один двоичный разряд в сторону старшего (что эквивалентно умножению на 2) поступит на вторые информационные входы сумматора 1 и мультиплексора 2 второй ступени преобразования. Значение a–го разряда входного числа A поступит на младшие разряды вторых информационных входов сумматора 1 и мультиплексора 2 второй ступени преобразования. В результате на вторых информационных входах сумматора 1 и мультиплексора 2 второй ступени преобразования образуется число (2t+a), а на информационном выходе сумматора 1 второй ступени преобразования образуется число (2t+a)-P, которое поступает на первый информационный вход мультиплексора 2 второй ступени преобразования. Если число (2t+a) окажется ≥ P, то на выходе переноса сумматора 1 второй ступени преобразования появится «1», которая, поступая на управляющий вход мультиплексора 2 второй ступени преобразования подключит к его информационным выходам первые информационные входы. В результате на информационном выходе мультиплексора 2 появится число t=(2t+a)-P, в противном случае появится число t=(2t+a).
Аналогично происходит работа устройства и на остальных ступенях преобразования.
В результате после выполнения (n-1) таких преобразований на выходе 6 устройства окажется код остатка Q от числа A по модулю P, а на выходах 5 – код неполного частного Q.
Рассмотрим работу вычислительного устройства на примере.
10
2
10
2
д
2
4
3
1
4
3
1
2
1
2
2
1
2
2
1
2
1
3
2
1
3
0
3
0
4
3
0
2
10
Пусть входное число A=27=11011, модуль P=5=00101, дополнительный код модуля P=11011, разрядность n=5. Сумматор 1 первой ступени преобразования формирует значение(2a+a)-P =10+1+11011=11110. На его выходе переноса формируется сигнал «0», следовательно на информационном выходе мультиплексора 2 первой ступени преобразования появится число с его второго информационного входа t=(2a+a)=10+1=11. Старший разряд неполного частного будет равен «0».  На вторых информационных входах сумматора 1 и мультиплексора 2 второй ступени преобразования образуется число(2t+a)=110+0=110. На информационном выходе сумматора 1 второй ступени преобразования образуется число (2t+a)-P=00110+0+11011=00001. На выходе переноса этого сумматора 1 образуется сигнал «1», который является следующим разрядом неполного частного и скоммутирует на информационные выходы мультиплексора 2 второй ступени преобразования сигнал с его первых информационных входов. В результате на информационных выходах мультиплексора 2 второй ступени преобразования окажется сигнал t=(2t+a)-P=00001. На вторых информационных входах сумматора 1 и мультиплексора 2 третьей ступени преобразования образуется число (2t+a)=00010+1=00011. На информационном выходе сумматора 1 третьей ступени преобразования образуется число (2t+a)-P=00010+1+11011=11110. На его выходе переноса формируется сигнал «0», следовательно на информационном выходе мультиплексора 2 третьей ступени преобразования появится число с его второго информационного входа t=(2t+a)= 00011. На вторых информационных входах сумматора 1 и мультиплексора 2 четвертой ступени преобразования образуется число (2t+a) = 00110+1 = 00111. На информационном выходе сумматора 1 четвертой ступени преобразования образуется число (2t+a)-P=00110+1+11011=00010. На выходе переноса этого сумматора 1 образуется сигнал «1», который является младшим разрядом неполного частного и скоммутирует на информационные выходы мультиплексора 2 четвертой ступени преобразования сигнал с его первых информационных входов. В результате на информационных выходах мультиплексора 2 четвертой ступени преобразования окажется код числа t=(2t+a)-P=00110+1+11011=00010, который и является вычисленным остатком: 27=5·5+2. На выходах 5 устройства неполного частного образуется двоичный код неполного частного 0101=5.