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

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

 

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

Известно вычислительное устройство (патент 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 - целое положительное число, являющееся остатком от деления А на Р.

Причем

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

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

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

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

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

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

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

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

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

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

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

При проведении вычислений по модулю Р значение выражения (an-1⋅2+an-2) сравнивается с модулем Р. Если значение (an-1⋅2+an-2)≥Р, то из числа (an-1⋅2+an-2) вычитается значение модуля Р, то есть t1=(an-1⋅2+an-2)-Р. При этом формируется ненулевой старший (n-1)-й разряд qn-2 неполного частного Q. Если (an-1⋅2+an-2)<Р, то число (an-1⋅2+an-2) остается без изменений t1=(an-1⋅2+an-2), а значение старшего (n-1)-ого разряда qn-2 неполного частного Q принимается равным нулю. Полученное в результате значение t1 умножается на 2, складывается с an-3 и сравнивается со значением Р. Если значение (t1⋅2+an-3)≥Р, то из (t1⋅2+an-3) вычитается значение модуля Р, то есть t2=(t1⋅2+an-3)-Р, при этом формируется ненулевой (n-2)-й разряд qn-3 неполного частного Q. Если (t1⋅2+an-3)<Р, то число (t1⋅2+an-3) остается без изменений, t2-(t1⋅2+an-3), а значение (n-2)-ого разряда qn-3 неполного частного Q принимается равным нулю. Полученное в результате значение t2 умножается на 2, складывается с an-4 и сравнивается со значением Р и т.д. На последнем (n-1)-м шаге число (tn-2⋅2+a0) сравнивается с модулем Р. Если значение (tn-2⋅2+a0)≥Р, то из (tn-2⋅2+a0) вычитается значение числа Р, то есть tn-1=(tn-2⋅2+a0)-Р, при этом формируется ненулевой младший разряд q0 неполного частного Q. Если (tn-2⋅2+a0)<Р, то число (tn-2⋅2+a0) остается без изменений tn-1=(tn-2⋅2+a0), а значение младшего разряда q0 неполного частного Q принимается равным «0». Полученное в результате значение R=tn-1 является остатком от деления числа А на число Р.

Операция умножения на два при вычислении выражения (ti⋅2+an-2-i) во всех случаях осуществляется сдвигом всех разрядов множимого на один в сторону старших. Суммирование осуществляется путем подачи коэффициента ai на самый младший разряд множимого. Ввиду того, что коэффициенты ai могут принимать значение «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.

Значение an-1 старшего разряда числа А с выхода первого n-разрядного регистра 1 поступает на первый информационный вход блока формирования частного и остатка 2.

С первого информационного входа блока формирования частного и остатка 2 значение an-1 старшего разряда поступает на самый младший разряд второго информационного входа n-разрядного сумматора 3 и на самый младший разряд второго информационного входа мультиплексора 4. На старшие (n-1) разряды вторых информационных входов n-разрядного сумматора 3 и мультиплексора 4 поступает сигнал с выхода второго (n-1)-разрядного регистра 5 со сдвигом на один разряд в сторону старшего.

На первом цикле, ввиду того что второй (n-1)-разрядный регистр 5 обнулен это будут нулевые сигналы. В результате на выходе n-разрядного сумматора 3 образуется сумма чисел an-1 и модуля Р, представленного в дополнительном коде, т.е. фактически (an-1-Р). Так как an-1<Р (Р всегда ≥2, а an-1 может принимать значение только «0» или «1»), то на выходе переноса n- разрядного сумматора 3 сигнал переноса будет отсутствовать. В результате мультиплексор 4 скоммутирует свой второй информационный вход на свой выход и на информационные входы второго (n-1)-разрядного регистра 5. С приходом тактового импульса на вход 10 подачи тактовых импульсов устройства значение an-1 запишется в самый младший разряд второго (n-1)-разрядного регистра 5, а сигнал логического «0» запишется в самый младший разряд третьего (n-1)-разрядного регистра сдвига 6. Этим же тактовым импульсом значение кода числа А в первом n-разрядном регистре 1 сдвинется на один разряд в сторону старших и в его самом старшем разряде окажется записано значение an-2. Перед началом второго тактового импульса на самый младший разряд вторых информационных входов n-разрядного сумматора 3 и на самый младший разряд вторых информационных входов мультиплексора 4 с первого информационного входа блока формирования частного и остатка 2 будет поступать значение an-2 числа А. На старшие (n-1) разряды вторых информационных входов n-разрядного сумматора 3 и мультиплексора 4 будет поступать сигнал с выхода второго (n-1)-разрядного регистра 5 со сдвигом на один разряд в сторону старших. Таким образом, на вторые информационные входы n-разрядного сумматора 3 и мультиплексора 4 будет поступать значение (an-1⋅2+an-2). На первые информационные входы n-разрядного сумматора 3 поступает инверсный код модуля Р, а на вход переноса сигнал логической «1». В случае если значение (an-1⋅2+an-2) окажется больше модуля Р, то на выходе переноса n-разрядного сумматора 3 появится сигнал логической «1», который скоммутирует первые информационные входы мультиплексора 4 на его выходы и поступит на информационный вход третьего (n-1)-разрядного регистра сдвига 6. В результате прихода второго тактового импульса во втором (n-1)-разрядном регистре 5 будет записано число t1=(an-1⋅2+an-2)mod Р, а в младшем разряде третьего (n-1)-разрядного регистра сдвига 6 будет записано qn-3=1. Значение qn-2=0 сдвинется во второй разряд этого регистра. В случае же если значение (an-1⋅2+an-2) окажется меньше модуля Р, то на выходе переноса n-разрядного сумматора 3 сигнал переноса окажется равным «0» и мультиплексор 4 скоммутирует на свои выходы сигнал со вторых информационных входов. Тогда после воздействия второго тактового импульса на вход 10 подачи тактовых импульсов устройства во второй (n-1)-разрядный регистр 5 будет записано число (an-1⋅2+an-2), а в младший разряд третьего (n-1)-разрядного регистра сдвига 6будет записано значение qn-3=0. С приходом следующего тактового импульса на вход 10 подачи тактовых импульсов работа устройства повторится. В результате после прихода n-го тактового импульса во втором (n-1)-разрядном регистре 5 будет записан остаток R от числа А по модулю Р, а в третьем (n-1)-разрядном регистре сдвига 6 неполное частное Q.

Рассмотрим работу устройства на конкретном примере. Пусть А=26, Р=9, n=5. В двоичном представлении А=11010, P=01001. Инверсный код Р равен 10110, дополнительный код Р соответственно равен 10111.

По сигналу, подаваемому на вход 8, «Начало вычисления» устройства в первый 5-разрядный регистр 1 будет записано число А, причем a4=1, а3=1, а2=0, a1=1 и а0=0.

На первые информационные входы 5-разрядного сумматора 3 поступает инверсный код модуля Р=10110. На вторые информационные входы 5-разрядного сумматора 3 и на вторые информационные входы мультиплексора 4 на самый младший разряд поступит сигнал с пятого разряда первого 5-разрядного регистра 1 a4=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», значения остальных разрядов сдвинутся в сторону старших.

Итак, в результате воздействия пяти тактовых импульсов во втором 4-разрядном регистре 5 будет записано число 10002=810, в третьем 4-разрядном регистре сдвига 6 будет записано число 00102=210, что соответствует исходным данным 26=2⋅9+8, где 2 это неполное частное, 8 остаток.

Технико-экономическая эффективность изобретения заключается в сокращении оборудования. Так устройство прототип содержит один регистр, 2n сумматоров и n мультиплексоров, то есть всего (3n+1)n-разрядных устройств. Изобретение содержит три регистра, один сумматор и один мультиплексор, то есть всего 4 устройства. При n=8 сокращение оборудования составит 25/4=6,25 раза.

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



 

Похожие патенты:

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

Изобретение относится к вычислительной технике. .

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

Изобретение относится к области вычислительной техники и может быть использовано в вычислительных системах для преобразования двоичных кодов в коды системы остаточных классов (СОК).

Изобретение относится к вычислительной технике, в частности к модулярным спецпроцессорам (СП), функционирующим в полиномиальной системе классов вычетов (ПСКВ) и способным сохранять работоспособное состояние при возникновении ошибки за счет реконфигурации структуры.

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

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

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к вычислительной технике и, в частности к непозиционным компьютерам. Технический результат заключается в обеспечении коррекции ошибок в кодовой комбинации ПСКВ на основе выполнения операции расширения оснований.

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

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

Изобретение относится к вычислительному устройству. Технический результат заключается в расширении функциональных возможностей за счет обеспечения вычисления остатка и неполного частного. Вычислительное устройство содержит связанные первый n-разрядный регистр и блок формирования частного и остатка, при этом n-разрядный регистр выполнен в виде регистра сдвига, а блок формирования частного и остатка содержит n-разрядный сумматор, мультиплексор, второй -разрядный регистр и третий -разрядный регистр сдвига. 2 ил.

Наверх