ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО Российский патент 2020 года по МПК G06F7/72 H03M7/18 

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

Известно устройство для формирования остатка по произвольному модулю от числа, содержащее регистры, элементы ИЛИ, вычислитель, схемы сравнения, мультиплексор, элемент задержки, сумматор, группу блоков элементов «И» и блок постоянной памяти со связями (см. АС СССР №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.

Число может быть представлено в позиционной двоичной системе счисления в виде:

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

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

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

.

.

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

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

При проведении вычислений по модулю P на первой ступени преобразования значение выражения (2a_n-1+a_n-2) сравнивается с модулем P, где n - количество разрядов числа A. Если значение (2a_n-1+a_n-2)≥P, то из числа (2a_n-1+a_n-2) вычитается значение модуля P, то есть
t₁=(2a_n-1+a_n-2)-P. При этом формируется ненулевой старший (n-2)-й разряд неполного частного Q. Если (2a_n-1+a_n-2)<P, то число (2a_n-1+a_n-2) остается без изменений t₁=(2a_n-1+a_n-2), а значение старшего (n-2)-го разряда неполного частного Q принимается равным нулю. Полученное на первой ступени преобразования значение t₁ на второй ступени преобразования умножается на 2, складывается с a_n-3 и сравнивается со значением P. Если значение (2t₁+a_n-3) ≥ P, то из (2t₁+a_n-3) вычитается значение модуля P, то есть t₂=(2t₁+a_n-3)-P, при этом формируется ненулевой (n-3)-й разряд неполного частного Q. Если (2t₁+a_n-3)<P, то число (2t₁+a_n-3) остается без изменений t₂=(2t₁+a_n-3), а значение
(n-3)-го разряда неполного частного Q принимается равным нулю. Полученное в результате значение t₂ на третьей ступени преобразования умножается на 2, складывается с a_n-4 и сравнивается со значением P и т.д. На (n-1)-й ступени преобразования число (2t_n-2+a₀) сравнивается с модулем P. Если значение (2t_n-2+a₀) ≥ P, то из (2t_n-2+a₀) вычитается значение числа P, то есть t_n-1=(2t_n-2+a₀)-P, при этом формируется ненулевой младший разряд неполного частного Q. Если (2t_n-2+a₀) < P, то число (2t_n-2+a₀) остается без изменений t_n-1=(2t_n-2+a₀), а значение младшего разряда неполного частного Q принимается равным нулю. Полученное в результате значение R=t_n-1 является остатком от деления числа A на число P. Операция умножения на два во всех случаях осуществляется сдвигом всех разрядов множимого на один в сторону старших. Сравнения выполняются на каждой ступени преобразования с использованием сумматора и мультиплексора. Сумматор выполняет операцию вычисления выражения 2x_i+a_(n-i-1)-P, где x_i – результаты вычислений на предыдущей ступени преобразования. Значение модуля P подается на информационный вход сумматора в дополнительном коде, что эквивалентно выполнению вычитания. Значение a_(n-i-1) подается на самый младший разряд второго информационного входа сумматора, который в результате сдвига кода x_i на один разряд в сторону старших оказывается свободен. Мультиплексор управляется сигналом переноса с сумматора, который при 2x_i+a_(n-i-1) ≥ P принимает значение «1», при 2x_i+a_(n-i-1) < 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 первой ступени преобразования.

Вычислительное устройство работает следующим образом.

На первые информационные входы сумматоров 1 подается дополнительный код модуля P со входов 4 устройства. На вторые информационные входы сумматора 1 первой ступени преобразования подается код двух старших разрядов числа A a_n-1 и a_n-2, причем код разряда a_n-2 подается на младший разряд сумматора 1, а код разряда a_n-1 подается на второй разряд. Аналогичным образом подается код двух старших разрядов на второй информационный вход мультиплексора 2 первой ступени преобразования. Сумматор 1 первой ступени преобразования выполняет операцию (2a_n-1+a_n-2)-P. Если значение
(2a_n-1+a_n-2) окажется ≥P, то на выходе переноса сумматора 1 появится «1», которая подключит к выходу мультиплексора 2 первой ступени преобразования его первый информационный вход и на его выходе появится значение t₁=(2a_n-1+a_n-2)-P. Если же значение (2a_n-1+a_n-2) окажется <P, то на выходе переноса сумматора 1 появится «0» и информационный выход мультиплексора 2 первой ступени преобразования окажется скоммутированным с его вторым информационным выходом. В результате на информационном выходе мультиплексора 2 первой ступени преобразования окажется число t₁=(2a_n-1+a_n-2). Число t₁ с информационного выхода мультиплексора 2 со сдвигом на один двоичный разряд в сторону старшего (что эквивалентно умножению на 2) поступит на вторые информационные входы сумматора 1 и мультиплексора 2 второй ступени преобразования. Значение a_n-3–го разряда входного числа A поступит на младшие разряды вторых информационных входов сумматора 1 и мультиплексора 2 второй ступени преобразования. В результате на вторых информационных входах сумматора 1 и мультиплексора 2 второй ступени преобразования образуется число (2t₁+a_n-3), а на информационном выходе сумматора 1 второй ступени преобразования образуется число (2t₁+a_n-3)-P, которое поступает на первый информационный вход мультиплексора 2 второй ступени преобразования. Если число (2t₁+a_n-3) окажется ≥ P, то на выходе переноса сумматора 1 второй ступени преобразования появится «1», которая, поступая на управляющий вход мультиплексора 2 второй ступени преобразования подключит к его информационным выходам первые информационные входы. В результате на информационном выходе мультиплексора 2 появится число t₂=(2t₁+a_n-3)-P, в противном случае появится число t₂=(2t₁+a_n-3).

Аналогично происходит работа устройства и на остальных ступенях преобразования.

В результате после выполнения (n-1) таких преобразований на выходе 6 устройства окажется код остатка Q от числа A по модулю P, а на выходах 5 – код неполного частного Q.

Рассмотрим работу вычислительного устройства на примере.

Пусть входное число 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₁₀.

Вычислительное устройство относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах цифровой обработки сигнала и в криптографических приложениях. Технический результат - сокращение объема оборудования и, как следствие, уменьшение энергопотребления за счет исключения n сумматоров. Устройство содержит сумматоры и мультиплексоры. Данное вычислительное устройство позволяет достичь результат путем последовательного выполнения (n-1) операций, где n – количество разрядов входного числа A. В ходе i-й операции значение (2t_i+a_n-2-i) сравнивается с модулем P путем вычисления разности (2t_i+a_n-2-i)-P, где i=1, …, (n-1), и формируется (n-i-1)-й разряд неполного частного Q. При выполнении (n-1)-й операции результатом вычисления числа A по модулю P будет являться значение разности, полученное на последнем (n-1)-м шаге. 1 ил.

Вычислительное устройство, содержащее (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)-й разряд двоичного кода входного числа соединен со вторым разрядом второго информационного входа мультиплексора и со вторым разрядом второго информационного входа сумматора первой ступени преобразования.