Результат интеллектуальной деятельности: Вычислительное устройство

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

Известно вычислительное устройство (патент 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 в зависимости от значения числа А;

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

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

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

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

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

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

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

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

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

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

При проведении вычислений по модулю Р значение выражения (a_n-1⋅2+a_n-2) сравнивается с модулем Р. Если значение (a_n-1⋅2+a_n-2)≥Р, то из числа (a_n-1⋅2+a_n-2) вычитается значение модуля Р, то есть t₁=(a_n-1⋅2+a_n-2)-Р. При этом формируется ненулевой старший (n-1)-й разряд q_n-2 неполного частного Q. Если (a_n-1⋅2+a_n-2)<Р, то число (a_n-1⋅2+a_n-2) остается без изменений t₁=(a_n-1⋅2+a_n-2), а значение старшего (n-1)-ого разряда q_n-2 неполного частного Q принимается равным нулю. Полученное в результате значение t₁ умножается на 2, складывается с a_n-3 и сравнивается со значением Р. Если значение (t₁⋅2+a_n-3)≥Р, то из (t₁⋅2+a_n-3) вычитается значение модуля Р, то есть t₂=(t₁⋅2+a_n-3)-Р, при этом формируется ненулевой (n-2)-й разряд q_n-3 неполного частного Q. Если (t₁⋅2+a_n-3)<Р, то число (t₁⋅2+a_n-3) остается без изменений, t₂-(t₁⋅2+a_n-3), а значение (n-2)-ого разряда q_n-3 неполного частного Q принимается равным нулю. Полученное в результате значение t₂ умножается на 2, складывается с a_n-4 и сравнивается со значением Р и т.д. На последнем (n-1)-м шаге число (t_n-2⋅2+a₀) сравнивается с модулем Р. Если значение (t_n-2⋅2+a₀)≥Р, то из (t_n-2⋅2+a₀) вычитается значение числа Р, то есть t_n-1=(t_n-2⋅2+a₀)-Р, при этом формируется ненулевой младший разряд q₀ неполного частного Q. Если (t_n-2⋅2+a₀)<Р, то число (t_n-2⋅2+a₀) остается без изменений t_n-1=(t_n-2⋅2+a₀), а значение младшего разряда q₀ неполного частного Q принимается равным «0». Полученное в результате значение R=t_n-1 является остатком от деления числа А на число Р.

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

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

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

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

По сигналу, подаваемому на вход 8, «Начало вычисления» устройства в первый 5-разрядный регистр 1 будет записано число А, причем a₄=1, а₃=1, а₂=0, a₁=1 и а₀=0.

На первые информационные входы 5-разрядного сумматора 3 поступает инверсный код модуля Р=10110. На вторые информационные входы 5-разрядного сумматора 3 и на вторые информационные входы мультиплексора 4 на самый младший разряд поступит сигнал с пятого разряда первого 5-разрядного регистра 1 a₄=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 будет записано число 1000₂=8₁₀, в третьем 4-разрядном регистре сдвига 6 будет записано число 0010₂=2₁₀, что соответствует исходным данным 26=2⋅9+8, где 2 это неполное частное, 8 остаток.

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