Вычислительное устройство
COMPUTING DEVICE

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, устройствах цифровой обработки сигналов, в криптографических приложениях, а также в устройствах для формирования кодовых последовательностей, построение которых основывается на теории конечных полей.
Известно вычислительное устройство (патент RU 2348965, опубл. 10.03.2009), содержащее сумматоры и мультиплексоры, позволяющее формировать остаток от числа по модулю и неполное частное.
Недостатком данного устройства являются большой объем оборудования.
Наиболее близким по технической сущности к заявляемому изобретению является устройство для формирования остатка по произвольному модулю от числа (патент RU 2012137, опубл. 30.04.1994), содержащее регистр и блок формирования частного и остатка, позволяющее формировать остаток от числа по модулю и неполное частное.
Недостатком данного устройства являются большой объем оборудования.
Техническим результатом данного изобретения является сокращение объема оборудования.
Для достижения технического результата в вычислительном устройстве, содержащем первый n-разрядный регистр и блок формирования частного и остатка, информационные входы первого n-разрядного регистра соединены со входами кода числа устройства, а первый управляющий вход соединен со входом «Начало вычисления» устройства, первый информационный вход блока формирования частного и остатка соединен с выходом старшего разряда первого n-разрядного регистра, вторые информационные входы соединены со входами инверсного кода модуля устройства, первые информационные выходы соединены с выходами неполного частного устройства, а вторые информационные выходы соединены с выходами остатка устройства, первый n-разрядный регистр выполнен в виде сдвигового регистра, а блок формирования частного и остатка содержит n-разрядный сумматор, мультиплексор, второй (n-1)-разрядный регистр и третий (n-1)-разрядный регистр сдвига, причем вход подачи тактовых импульсов устройства соединен со вторым управляющим входом первого n-разрядного регистра и управляющим входом блока формирования частного и остатка, первые информационные входы n-разрядного сумматора соединены со вторыми информационными входами блока формирования частного и остатка, на вход переноса подается сигнал логической «1», информационные выходы соединены с первыми информационными входами мультиплексора, выходы которого, за исключением выхода самого старшего разряда, соединены с информационными входами второго (n-1)-разрядного регистра, информационные выходы которого соединены со вторыми информационными выходами блока формирования частного и остатка и со сдвигом на один разряд в сторону старшего со вторыми информационными входами n-разрядного сумматора и мультиплексора, самый младший разряд вторых информационных входов n-разрядного сумматора и мультиплексора соединен с первым информационным входом блока формирования частного и остатка, выход переноса n- разрядного сумматора соединен с управляющим входом мультиплексора и информационным входом третьего (n-1)-разрядного регистра сдвига, управляющий вход которого соединен с управляющим входом второго (n-1)-разрядного регистра и управляющим входом блока формирования частного и остатка, а информационные выходы соединены с первыми информационными выходами блока формирования частного и остатка.
Сущность изобретения заключается в реализации следующего способа вычисления остатка R и неполного частного Q от числа А по модулю Р. Пусть
где А - целое положительное число, от которого необходимо вычислить остаток;
Р - целое положительное число, называемое модулем;
Q - целое положительное число, являющееся неполным частным от деления А на Р;
R - целое положительное число, являющееся остатком от деления А на Р.
Причем
a
i
где ,  - коэффициенты, принимающие значение 0 или 1 в зависимости от значения числа А;
i
p,  - коэффициенты, принимающие значение 0 или 1 в зависимости от значения модуля Р;
i
q,  - коэффициенты, принимающие значение 0 или 1 в зависимости от значения неполного частного Q;
i
r,  - коэффициенты, принимающие значение 0 или 1 в зависимости от значения остатка R;
n - количество разрядов в представлении чисел.
Задача состоит в том, чтобы по известным А и Р отыскать остаток R и неполное частное Q. Остаток R является в терминах теории чисел вычетом числа А по модулю Р, поэтому говорят, что А сравнимо с R:
Значение остатка R может быть вычислено следующим образом:
Выражение (7) может быть представлено в следующем виде:
Из теории чисел известно, что операция приведения по модулю инвариантна к сложению и умножению, т.е. величина остатка не зависит от того, вычислен ли он от суммы (произведения) или от каждого слагаемого (сомножителя), а затем соответствующие частичные остатки просуммированы (перемножены) и от результата вычислен остаток по модулю.
Исходя из вышесказанного выражение (8) может быть представлено в виде
В таком виде значительно облегчается задача нахождения остатка R от числа А.
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
n-1
n-2
n-1
n-2
n-1
n-2
1
n-1
n-2
n-2
n-1
n-2
n-1
n-2
1
n-1
n-2
n-2
1
n-3
1
n-3
1
n-3
2
1
n-3
n-3
1
n-3
1
n-3
2
1
n-3
n-3
2
n-4
n-2
0
n-2
0
n-2
0
n-1
n-2
0
0
n-2
0
n-2
0
n-1
n-2
0
0
n-1
При проведении вычислений по модулю Р значение выражения (⋅2+) сравнивается с модулем Р. Если значение (⋅2+)≥Р, то из числа (⋅2+) вычитается значение модуля Р, то есть t=(⋅2+)-Р. При этом формируется ненулевой старший (n-1)-й разряд q неполного частного Q. Если (⋅2+)<Р, то число (⋅2+) остается без изменений t=(⋅2+), а значение старшего (n-1)-ого разряда q неполного частного Q принимается равным нулю. Полученное в результате значение t умножается на 2, складывается с  и сравнивается со значением Р. Если значение (t⋅2+)≥Р, то из (t⋅2+) вычитается значение модуля Р, то есть t=(t⋅2+)-Р, при этом формируется ненулевой (n-2)-й разряд q неполного частного Q. Если (t⋅2+)<Р, то число (t⋅2+) остается без изменений, t-(t⋅2+), а значение (n-2)-ого разряда q неполного частного Q принимается равным нулю. Полученное в результате значение tумножается на 2, складывается с  и сравнивается со значением Р и т.д. На последнем (n-1)-м шаге число (t⋅2+) сравнивается с модулем Р. Если значение (t⋅2+)≥Р, то из (t⋅2+) вычитается значение числа Р, то есть t=(t⋅2+)-Р, при этом формируется ненулевой младший разряд q неполного частного Q. Если (t⋅2+)<Р, то число (t⋅2+) остается без изменений t=(t⋅2+), а значение младшего разряда q неполного частного Q принимается равным «0». Полученное в результате значение R=t является остатком от деления числа А на число Р.
i
n-2-i
i
i
a
a
a
Операция умножения на два при вычислении выражения (t⋅2+) во всех случаях осуществляется сдвигом всех разрядов множимого на один в сторону старших. Суммирование осуществляется путем подачи коэффициента  на самый младший разряд множимого. Ввиду того, что коэффициенты  могут принимать значение «0» или «1», а самый младший разряд множимого после сдвига всегда будет равен «0», то переноса в следующий разряд при таком решении возникать не будет.
На фиг. 1 представлена схема вычислительного устройства для сложения чисел по модулю.
Вычислительное устройство содержит первый n-разрядный регистр 1, который выполнен в виде регистра сдвига, блок формирования частного и остатка 2, входы 7 кода числа устройства, вход 8 «Начало вычисления» устройства, входы 9 инверсного кода модуля устройства, вход 10 подачи тактовых импульсов устройства, выходы 11 неполного частного устройства и выходы 12 остатка устройства. Информационные входы первого n-разрядного регистра 1 соединены со входами 7 кода числа устройства, первый управляющий вход первого n-разрядного регистра 1 соединен с входом 8 «Начало вычисления» устройства. Первый информационный вход блока формирования частного и остатка 2 соединен с выходом старшего разряда первого n-разрядного регистра 1, вторые информационные входы соединены со входами 9 инверсного кода модуля устройства, первые информационные выходы соединены с выходами 11 неполного частного устройства, а вторые информационные выходы соединены с выходами 12 остатка устройства. Вход 10 подачи тактовых импульсов устройства соединен со вторым управляющим входом первого n-разрядного регистра 1 и управляющим входом блока формирования частного и остатка 2.
На фиг. 2 представлена схема блока формирования частного и остатка 2.
Блок формирования частного и остатка 2 содержит n-разрядный сумматор 3, мультиплексор 4, второй (n-1)-разрядный регистр 5 и третий (n-1) разрядный регистр сдвига 6. Первые информационные входы n-разрядного сумматора 3 соединены со вторыми информационными входами блока формирования частного и остатка 2. На вход переноса n-разрядного сумматора 3 подается сигнал логической «1», его информационные выходы соединены с первыми информационными входами мультиплексора 4. Выходы мультиплексора 4, за исключением выхода самого старшего разряда, соединены с информационными входами второго (n-1)-разрядного регистра 5, информационные выходы которого соединены со вторыми информационными выходами блока формирования частного и остатка 2 и со сдвигом на один разряд в сторону старшего со вторыми информационными входами n-разрядного сумматора 3 и мультиплексора 4. Самый младший разряд вторых информационных входов n-разрядного сумматора 3 и мультиплексора 4 соединен с первым информационным входом блока формирования частного и остатка 2, выход переноса n-разрядного сумматора 3 соединен с управляющим входом мультиплексора 4 и информационным входом третьего (n-1) разрядного регистра сдвига 6, управляющий вход которого соединен с управляющим входом второго (n-1)-разрядного регистра 5 и управляющим входом блока формирования частного и остатка 2.
Вычислительное устройство работает следующим образом.
В исходном состоянии первый n-разрядный регистр 1, второй (n-1)-разрядный регистр 5 и третий (n-1)-разрядный регистр сдвига 6 вычислительного устройства обнулены.
На входы 7 кода числа устройства подается код числа А, от которого необходимо вычислить остаток R и неполное частное Q по модулю Р. На входы 9 инверсного кода модуля подается код модуля Р в инверсном виде. По сигналу, подаваемому на вход 8 «Начало вычисления» устройства, код числа А с входов 7 кода числа устройства записывается в первый n-разрядный регистр 1.
a
n-1
Значение  старшего разряда числа А с выхода первого n-разрядного регистра 1 поступает на первый информационный вход блока формирования частного и остатка 2.
a
n-1
С первого информационного входа блока формирования частного и остатка 2 значение  старшего разряда поступает на самый младший разряд второго информационного входа n-разрядного сумматора 3 и на самый младший разряд второго информационного входа мультиплексора 4. На старшие (n-1) разряды вторых информационных входов n-разрядного сумматора 3 и мультиплексора 4 поступает сигнал с выхода второго (n-1)-разрядного регистра 5 со сдвигом на один разряд в сторону старшего.
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
n-1
n-1
n-1
n-1
n-1
n-2
n-2
n-1
n-2
n-1
n-2
1
n-1
n-2
n-3
n-2
n-1
n-2
n-1
n-2
n-3
На первом цикле, ввиду того что второй (n-1)-разрядный регистр 5 обнулен это будут нулевые сигналы. В результате на выходе n-разрядного сумматора 3 образуется сумма чисел  и модуля Р, представленного в дополнительном коде, т.е. фактически (-Р). Так как <Р (Р всегда ≥2, а  может принимать значение только «0» или «1»), то на выходе переноса n- разрядного сумматора 3 сигнал переноса будет отсутствовать. В результате мультиплексор 4 скоммутирует свой второй информационный вход на свой выход и на информационные входы второго (n-1)-разрядного регистра 5. С приходом тактового импульса на вход 10 подачи тактовых импульсов устройства значение  запишется в самый младший разряд второго (n-1)-разрядного регистра 5, а сигнал логического «0» запишется в самый младший разряд третьего (n-1)-разрядного регистра сдвига 6. Этим же тактовым импульсом значение кода числа А в первом n-разрядном регистре 1 сдвинется на один разряд в сторону старших и в его самом старшем разряде окажется записано значение . Перед началом второго тактового импульса на самый младший разряд вторых информационных входов n-разрядного сумматора 3 и на самый младший разряд вторых информационных входов мультиплексора 4 с первого информационного входа блока формирования частного и остатка 2 будет поступать значение  числа А. На старшие (n-1) разряды вторых информационных входов n-разрядного сумматора 3 и мультиплексора 4 будет поступать сигнал с выхода второго (n-1)-разрядного регистра 5 со сдвигом на один разряд в сторону старших. Таким образом, на вторые информационные входы n-разрядного сумматора 3 и мультиплексора 4 будет поступать значение (⋅2+). На первые информационные входы n-разрядного сумматора 3 поступает инверсный код модуля Р, а на вход переноса сигнал логической «1». В случае если значение (⋅2+) окажется больше модуля Р, то на выходе переноса n-разрядного сумматора 3 появится сигнал логической «1», который скоммутирует первые информационные входы мультиплексора 4 на его выходы и поступит на информационный вход третьего (n-1)-разрядного регистра сдвига 6. В результате прихода второго тактового импульса во втором (n-1)-разрядном регистре 5 будет записано число t=(⋅2+)mod Р, а в младшем разряде третьего (n-1)-разрядного регистра сдвига 6 будет записано q=1. Значение q=0 сдвинется во второй разряд этого регистра. В случае же если значение (⋅2+) окажется меньше модуля Р, то на выходе переноса n-разрядного сумматора 3 сигнал переноса окажется равным «0» и мультиплексор 4 скоммутирует на свои выходы сигнал со вторых информационных входов. Тогда после воздействия второго тактового импульса на вход 10 подачи тактовых импульсов устройства во второй (n-1)-разрядный регистр 5 будет записано число (⋅2+), а в младший разряд третьего (n-1)-разрядного регистра сдвига 6будет записано значение q=0. С приходом следующего тактового импульса на вход 10 подачи тактовых импульсов работа устройства повторится. В результате после прихода n-го тактового импульса во втором (n-1)-разрядном регистре 5 будет записан остаток R от числа А по модулю Р, а в третьем (n-1)-разрядном регистре сдвига 6 неполное частное Q.
Рассмотрим работу устройства на конкретном примере. Пусть А=26, Р=9, n=5. В двоичном представлении А=11010, P=01001. Инверсный код Р равен 10110, дополнительный код Р соответственно равен 10111.
a
а
а
a
а
4
3
2
1
0
По сигналу, подаваемому на вход 8, «Начало вычисления» устройства в первый 5-разрядный регистр 1 будет записано число А, причем =1, =1, =0, =1 и =0.
a
4
На первые информационные входы 5-разрядного сумматора 3 поступает инверсный код модуля Р=10110. На вторые информационные входы 5-разрядного сумматора 3 и на вторые информационные входы мультиплексора 4 на самый младший разряд поступит сигнал с пятого разряда первого 5-разрядного регистра 1 =1, на остальные разряды поступит нулевой сигнал обнуленного перед началом работы второго 4-разрядного регистра 5. С учетом сигнала переноса подаваемого на вход переноса 5-разрядного сумматора 3 на его информационных выходах образуется число 11000=00001+10110+1. Сигнал переноса на выходе переноса 5-разрядного сумматора 3 не появится. В результате мультиплексор 4 скоммутирует на свой выход число 00001 со второго информационного входа. Во второй 4-разрядный регистр 5 по приходу первого тактового импульса запишется число 0001. Этим же тактовым импульсом осуществится сдвиг числа А в первом 5-разрядном регистре 1 в сторону старших разрядов, то есть первый 5-разрядный регистр 1 перейдет в состоянии 10100. Также нулевой сигнал запишется в первый разряд третьего 4-разрядного регистра сдвига 6, который будет соответствовать четвертому разряду неполного частного от деления А на Р. На вторых информационных входах 5-разрядного сумматора 3 образуется число 00011, где старшие 4 разряда поступают с выхода второго 4-разрядного регистра 5, а младший разряд поступает с выхода пятого разряда первого 5-разрядного регистра 1. На информационных выходах 5-разрядного сумматора 3 при этом образуется число 11110=00011+10110+1. Сигнал переноса на выходе 5-разрядного сумматора 3 будет равен «0». Следовательно, вторым тактовым импульсом во второй 4-разрядный регистр 5 запишется число 0011, в младший разряд третьего 4-разрядного регистра сдвига 6 запишется сигнал логического «0» и сигнал логического «0» из первого разряда сдвинется во второй. Перед поступлением третьего тактового импульса на вторых информационных входах 5-разрядного сумматора 3 будет число 00110, на информационных выходах соответственно 11101=00110+10110+1. По приходу третьего тактового импульса во второй 4-разрядный регистр 5 запишется число 0110, а в первый разряд третьего 4-разрядного регистра сдвига 6 логический «0», сдвигая остальные сигналы в сторону старших разрядов.
Перед поступлением четвертого тактового импульса на вторых информационных входах 5-разрядного сумматора 3 будет число 01101, на его информационных выходах будет число 00100=01101+10110+1, а на его выходе переноса сигнал логической «1». В результате прихода четвертого тактового импульса во второй 4-разрядный регистр 5 запишется число 0100, так как мультиплексор 4 на свой выход скоммутируют сигнал со своих первых информационных входов, а в младший разряд третьего 4-разрядного регистра сдвига 6 запишется сигнал логической «1».
Перед поступлением пятого тактового импульса на вторых информационных входах 5-разрядного сумматора 3 и мультиплексора 4 будет число 01000, на информационных выходах 5-разрядного сумматора 3 появится число 11111=01000+10110+1, на выходе переноса сигнал логического «0». В результате воздействия пятого тактового импульса во второй 4-разрядный регистр 5 запишется число 1000 с выхода мультиплексора 4, скоммутированное с его первыми информационными входами, в первый разряд третьего 4-разрядного регистра сдвига 6 запишется сигнал логического «0», значения остальных разрядов сдвинутся в сторону старших.
2
10
2
10
Итак, в результате воздействия пяти тактовых импульсов во втором 4-разрядном регистре 5 будет записано число 1000=8, в третьем 4-разрядном регистре сдвига 6 будет записано число 0010=2, что соответствует исходным данным 26=2⋅9+8, где 2 это неполное частное, 8 остаток.
Технико-экономическая эффективность изобретения заключается в сокращении оборудования. Так устройство прототип содержит один регистр, 2n сумматоров и n мультиплексоров, то есть всего (3n+1)n-разрядных устройств. Изобретение содержит три регистра, один сумматор и один мультиплексор, то есть всего 4 устройства. При n=8 сокращение оборудования составит 25/4=6,25 раза.