Результат интеллектуальной деятельности: ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО

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

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

Наиболее близким по технической сущности к заявляемому изобретению является вычислительное устройство, содержащее сумматоры и мультиплексоры (см. патент РФ № 2717915, МПК G06F 7/72 (2006.01), H03M 7/18 (2006.01), 26.03.2020. Бюл. № 9). Недостатком данного вычислительного устройства является низкое быстродействие.

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

Для достижения технического результата в вычислительное устройство, содержащее (n-2) сумматоров и (n/2-1) мультиплексоров, где n-разрядность входного числа, образующих (n/2-1) ступеней преобразования, на первые информационные входы первых сумматоров всех ступеней преобразования подается инверсный двоичный код модуля, информационные выходы первого сумматора i-й ступени преобразования, где i=1,.., n/2-1, соединены с первыми информационными входами мультиплексора этой же ступени преобразования, а выходы переноса соединены с первыми управляющими входами соответствующих мультиплексоров, первый информационный выход мультиплексора (n/2-1)-й ступени преобразования является информационным выходом двоичного кода остатка устройства, дополнительно введены (n/2-1) сумматоров, на первые информационные входы вторых сумматоров всех ступеней преобразования подается инверсный двоичный код удвоенного модуля, на первые информационные входы третьих сумматоров всех ступеней преобразования подается инверсный двоичный код утроенного модуля, информационные выходы вторых и третьих сумматоров всех ступеней преобразования соединены со вторыми и третьими информационными входами соответственно мультиплексоров этих же ступеней преобразования, выходы переноса вторых и третьих сумматоров всех ступеней преобразования соединены со вторыми и третьими управляющими входами соответственно мультиплексоров этих же ступеней преобразования, на входы переноса всех сумматоров подается код логической единицы, j-е разряды вторых информационных входов всех сумматоров и четвертых информационных входов мультиплексоров i-й ступени преобразования, где j=(0;1), соединены с (n-2i-j-1)-ми разрядами двоичного кода входного числа соответственно, второй и третий разряды вторых информационных входов трех сумматоров и четвертых информационных входов мультиплексора первой ступени преобразования соединены с (n-2)-м и (n-1)-м разрядами двоичного кода входного числа соответственно, первые информационные выходы мультиплексоров i-й ступени преобразования, где i=1,.., n/2-2, соединены со сдвигом на два разряда в сторону старших со вторыми информационными входами сумматоров и четвертыми информационными входами мультиплексоров (i+1)-й ступени преобразования, первые информационные выходы мультиплексора (n/2-1)-й ступени преобразования являются выходом двоичного кода остатка, вторые информационные выходы мультиплексоров являются информационными выходами двоичного кода неполного частного устройства, причем мультиплексоры содержат два элемента ИЛИ, три инвертора, два трехвходовых элемента И, двухвходовый элемент И, четыре ключа и блок элементов ИЛИ, информационный выход которого является первым информационным выходом мультиплексора, информационные входы соединены с информационными выходами соответствующих ключей, первые информационные входы которых являются соответствующими информационными входами мультиплексора, управляющий вход четвертого ключа соединен с выходом первого трехвходового элемента И, первый вход которого соединен с выходом первого инвертора, второй вход соединен с выходом второго инвертора и со вторым входом второго трехвходового элемента И, третий вход соединен с выходом третьего инвертора, с третьим входом второго трехвходового элемента И и со вторым входом двухвходового элемента И, вход первого инвертора является первым управляющим входом мультиплексора и соединен с первым входом второго трехвходового элемента И, выход которого соединен с управляющим входом первого ключа и первым входом второго элемента ИЛИ, вход второго инвертора является вторым управляющим входом мультиплексора и соединен с первым входом двухвходового элемента И, выход которого соединен с управляющим входом второго ключа и первым входом первого элемента ИЛИ, вход третьего инвертора является третьим управляющим входом мультиплексора и соединен с управляющим входом третьего ключа и со вторыми входами элементов ИЛИ, выходы которых являются вторыми информационными выходами мультиплексора.

Сущность изобретения заключается в реализации следующего способа вычисления остатка 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_n-3·2^n-3+a_n-4·2^n-4+ . . . +a₃·2³+a₂·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 – количество разрядов в представлении чисел, n – четное.

Задача состоит в том, чтобы по известным A и P отыскать остаток R и неполное частное Q. Остаток 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)

Перепишем выражение (2) в следующем виде, объединив по два соседних слагаемых:

A = (a_n-1·2^n-1+a_n-2·2^n-2)+ (a_n-3·2^n-3+a_n-4·2^n-4)+ . . . +(a₃·2³+a₂·2²)+(a₁·2+a₀), (8)

Из каждой суммы в скобках в выражении (8) вынесем 2ⁱ за скобки, где , принимает только четные значения:

A = 2^n-2(a_n-1·2+a_n-2)+2^n-4(a_n-3·2+a_n-4)+ . . . +2²(a₃·2+a₂)+(a₁·2+a₀), (9)

В выражении (9) перед каждой из n/2 образовавшихся сумм вида (a_i+1·2+a_i), получаем множитель 2ⁱ, где , принимает только четные значения.

Далее вынесем в (9) наименьшую ненулевую степень 2 за скобки:

A = 2²(2^n-4(a_n-1·2+a_n-2)+ 2^n-6 (a_n-3·2+a_n-4)+ . . . + (a₃·2+a₂))+(a₁·2+a₀), (10)

Выполняя последовательно преобразование (10) (n/2)-2 раз получим:

A = 2²(2²…(2²(a_n-1·2+a_n-2)+(a_n-3·2+a_n-4))+ . . . + (a₃·2+a₂))+(a₁·2+a₀), (11)

где 2² встречается (n/2)-1 раз.

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

R = (2²(2²…(2²(a_n-1·2+a_n-2)+(a_n-3·2+a_n-4))+ . . . + (a₃·2+a₂))+(a₁·2+a₀)) mod P. (12)

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

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

Вначале на первой ступени преобразования вычисляют величину

t ₁=(2²(a_n-1·2+a_n-2)+(a_n-3·2+a_n-4)) mod P. (13)

На второй ступени преобразования вычисляют величину

t ₂=(2²t₁+(a_n-5·2+a_n-6)) mod P. (14)

На последней (n/2-1)-й ступени преобразования вычисляют величину

t_{n /2-1}=(2²t_n/2-2+(a₁·2+a₀)) mod P, (15)

которая и является искомым остатком R от числа A по модулю P.

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

По определению величина t_i-1 лежит в диапазоне 0≤t_i-1≤P-1, поэтому в соответствии с выражениями (13)-(15) величина

t_i=2² t_i-1 +(a _n-2i-1·2+a _n-2i-2), (16)

до приведения ее по модулю может принимать значения в диапазоне от 0 до 4P-1. Приведение по модулю величины t_i осуществляется по следующим правилам

t_i (mod P)=t_i, если 0 ≤ t_i < P, (17)

t_i (mod P)=t_i - P, если P≤ t_i < 2P,

t_i (mod P)=t_i - 2P, если 2P ≤ t_i < 3P,

t_i (mod P)=t_i - 3P, если 3P ≤ t_i < 4P.

Разряды неполного частного Q на каждом этапе вычислений принимают значения в соответствии с таблицей 1.

Таблица 1.

Условия попадания значения t_i в один из указанных в таблице 1 интервалов определяются значениями сигналов переноса на выходах переноса сумматоров, осуществляющих операцию вычитания (t_i – kP), где k=1, 2, 3 в соответствии с таблицей 2.

Таблица 2.

Таким образом, если значение сигналов переноса равно «1» на выходах переноса всех трех сумматоров, то t_i (mod P)=t_i - 3P, если значение сигналов переноса равно «1» на выходах переноса двух сумматоров, то
t_i (mod P)=t_i - 2P, если значение сигнала переноса равно «1» на выходах переноса одного сумматора, то t_i (mod P)=t_i – P. Если значение сигналов переноса равно «0» на выходах переноса всех трех сумматоров, то тогда
t_i (mod P)=t_i, т.е. операция вычитания не выполняется.

На фиг.1 представлена схема вычислительного устройства.

Вычислительное устройство содержит (3n/2-3) сумматоров 1 и (n/2-1) мультиплексоров 2, где n-разрядность входного числа, образующих (n/2-1) ступеней преобразования, вход 3 подачи двоичного кода числа A, выход 4 двоичного кода неполного частного Q и выход 5 двоичного кода остатка R от числа A. На первые информационные входы первых сумматоров 1 всех ступеней преобразования подается инверсный двоичный код модуля, на первые информационные входы вторых сумматоров 1 всех ступеней преобразования подается инверсный двоичный код удвоенного модуля, на первые информационные входы третьих сумматоров 1 всех ступеней преобразования подается инверсный двоичный код утроенного модуля. На входы переноса всех сумматоров 1 подается код логической единицы. Информационные выходы первого, второго и третьего сумматоров 1 всех ступеней преобразования соединены со первыми, вторыми и третьими информационными входами соответственно мультиплексоров 2 этих же ступеней преобразования. Выходы переноса первых, вторых и третьих сумматоров 1 всех ступеней преобразования соединены с первыми, вторыми и третьими управляющими входами соответственно мультиплексоров 2 этих же ступеней преобразования, j-е разряды вторых информационных входов всех сумматоров 1 и четвертых информационных входов мультиплексоров 2 i-й ступени преобразования, где j=(0;1), соединены с (n-2i-j-1)-ми разрядами входа 3 двоичного кода числа A соответственно. Второй и третий разряды вторых информационных входов трех сумматоров 1 и четвертых информационных входов мультиплексора 2 первой ступени преобразования соединены с (n-2)-м и (n-1)-м разрядами входа 3 двоичного кода числа A соответственно. Первые информационные выходы мультиплексоров 2 i-й ступени преобразования, где i=1,.., n/2-2, соединены со сдвигом на два разряда в сторону старших со вторыми информационными входами сумматоров 1 и четвертыми информационными входами мультиплексоров 2 (i+1)-й ступени преобразования. Первые информационные выходы мультиплексора 2 (n/2-1)-й ступени преобразования являются выходом 5 двоичного кода остатка R от числа A. Вторые информационные выходы мультиплексоров 2 являются информационными выходами 4 двоичного кода неполного частного Q устройства, первый информационный выход мультиплексора (n/2-1)-й ступени преобразования является информационным выходом 5 двоичного кода остатка R.

На фиг.2 представлена схема мультиплексоров 2.

Мультиплексоры 2 содержат два элемента ИЛИ 6, три инвертора 7, два трехвходовых элемента И 8, двухвходовый элемент И 9, четыре ключа 10 и блок элементов ИЛИ 11, информационный выход которого является первым информационным выходом мультиплексора 2, информационные входы соединены с информационными выходами соответствующих ключей 10, первые информационные входы которых являются соответствующими информационными входами мультиплексора 2, управляющий вход четвертого ключа 10 соединен с выходом первого трехвходового элемента И 8, первый вход которого соединен с выходом первого инвертора 7, второй вход соединен с выходом второго инвертора 7 и со вторым входом второго трехвходового элемента И 8, третий вход соединен с выходом третьего инвертора 7, с третьим входом второго трехвходового элемента И 8 и со вторым входом двухвходового элемента И 9, вход первого инвертора 7 является первым управляющим входом мультиплексора 2 и соединен с первым входом второго трехвходового элемента И 8, выход которого соединен с управляющим входом первого ключа 10 и первым входом второго элемента ИЛИ 6, вход второго инвертора 7 является вторым управляющим входом мультиплексора 2 и соединен с первым входом двухвходового элемента И 9, выход которого соединен с управляющим входом второго ключа 10 и первым входом первого элемента ИЛИ 6, вход третьего инвертора является третьим управляющим входом мультиплексора 2 и соединен с управляющим входом третьего ключа 10 и со вторыми входами элементов ИЛИ 6, выходы которых являются вторыми информационными выходами мультиплексора 2.

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

На вход 3 устройства подается двоичный код числа A от которого необходимо сформировать остаток R и неполное частное Q. Старшие разряды числа A подаются на вход первой ступени преобразования, а младшие – на вход последней.

На первые информационные входы первых сумматоров 1 всех ступеней преобразования подается инверсный код модуля P, вторых сумматоров 1 – удвоенный инверсный код модуля P, а третьих сумматоров 1 – утроенный инверсный код модуля P.

На первой ступени преобразования осуществляется вычисление значения t₁=(2²(a_n-1·2+a_n-2)+(a_n-3·2+a_n-4)) mod P. Причем вычисление значения
2²(a_n-1·2+a_n-2)+(a_n-3·2+a_n-4) осуществляется путем подачи соответствующих разрядов a_n-1…a_n-4 на соответствующие входы первой ступени преобразования. Для приведения этого значения по модулю P с помощью сумматоров 1 осуществляют одновременное вычитание значений P, 2P и 3P. Сигналы переноса в виде логических единиц на выходах сумматоров 1 появятся в зависимости от того в каком диапазоне находится входное значение в соответствии с табл. 2 и далее поступят на соответствующие управляющие входы мультиплексора 2.

Управляющие сигналы мультиплексора 2 (см. Фиг. 2) открывают один из ключей 10.

Если управляющий сигнал появляется на всех трех управляющих входах, то окажется открытым третий ключ 10. Управляющий сигнал с третьего управляющего входа откроет третий ключ 10 и через третий инвертор 7 в виде логического нуля поступит на третьи входы трехвходовых элементов И 8 и на второй вход двухвходового элемента И 9, запрещая прохождение управляющих сигналов с их первых входов на их выходы. В результате первый, второй и четвертый ключи 10 окажутся закрытыми и на выход мультиплексора поступит значение 2²(a_n-1·2+a_n-2)+(a_n-3·2+a_n-4) - 3P с его третьего информационного входа.

Если управляющий сигнал появляется на первом и втором управляющих входах мультиплексора 2, то аналогичным образом окажется открытым только второй ключ 10, а первый, третий и четвертый ключи 10 окажутся закрытыми. В результате на выход мультиплексора 2 поступит значение с его второго информационного входа 2²(a_n-1·2+a_n-2)+(a_n-3·2+a_n-4) - 2P.

Если управляющий сигнал появляется только на первом управляющем входе мультиплексора 2, то аналогичным образом окажется открытым только первый ключ 10, а второй, третий и четвертый ключи окажутся закрытыми. В результате на выход мультиплексора 2 поступит значение 2²(a_n-1·2+a_n-2)+(a_n-3·2+a_n-4) - P с его первого информационного входа.

Если же на управляющих входах мультиплексора 2 будут только нулевые сигналы, то они, поступая через инверторы 7 и первый трехвходовый элемент И 8, откроют четвертый ключ 10 и на выход мультиплексора 2 поступит значение с его четвертого информационного входа 2²(a_n-1·2+a_n-2)+(a_n-3·2+a_n-4).

Сформированное на первой ступени преобразования значение
t₁=(2²(a_n-1·2+a_n-2)+(a_n-3·2+a_n-4)) mod P поступает со сдвигом на два разряда в сторону старших (т.е. фактически осуществляя умножение на 2²) на вход следующей ступени преобразования. На младшие два разряда подаются сигналы a_n-5, a_n-6 разрядов входного числа A.

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

Так как на каждой ступени преобразования осуществляется обработка одновременно двух разрядов входного числа, то через (n/2-1) преобразований на выходе 5 устройства сформируется двоичный код остатка R от числа A по модулю P, а на выходе 4 устройства сформируется двоичный код неполного частного Q.

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

Пусть входное число A=248₁₀=11111000₂, модуль P=5₁₀=00000101₂, разрядность n=8. Двоичные прямые и инверсные коды значений модуля P, 2P, 3P представлены в табл. 3.

Таблица 3.

Значения сигналов при работе устройства на входах и выходах сумматоров 1 и мультиплексоров 2 представлены в табл. 4.

Таблица 4.

Номер ступени преобразования приведен в первом столбце таблицы 4. «Сумматор 1», «Сумматор 2» и «Сумматор 3» соответственно первый, второй и третий сумматоры 1, «Мультиплексор» - обозначение мультиплексоров 2, «вход 1» и «вход 2», соответственно первый и второй информационные входы сумматоров 1 и мультиплексора 2, «вход 3» - вход переноса сумматоров 1 и третий информационный вход мультиплексора 2 «вход 4» - четвертый информационный вход мультиплексора 2, «выход 1» - информационные выходы сумматоров 1 и мультиплексора 2, «выход 2» - выход переноса сумматоров 1 или второй информационный выход мультиплексора 2.

В результате на информационных выходах 5 мультиплексора 2 третьей ступени преобразования окажется код числа 00000011₂=3₁₀, который и является вычисленным остатком R числа A=248 по модулю P=5, а на выходах 4 устройства образуется двоичный код 110001₂=49₁₀, который и является неполным частным Q. Непосредственной проверкой устанавливаем, что 248=49·5 + 3, что доказывает правильность функционирования устройства.

В устройстве прототипе вычисление остатка осуществляется за (n-1) последовательных шагов преобразования, а в предлагаемом устройстве за (n/2-1) шагов. В результате быстродействие предлагаемого технического решения по сравнению с устройством прототипом будет выше не менее чем в два раза.