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

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

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

Недостатками данных устройств являются большой объем оборудования.

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

Недостатком данного устройства является низкое быстродействие.

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

Для достижения технического результата в вычислительном устройстве, содержащем регистр кода числа, блок формирования частного и остатка, содержащий первый сумматор, регистр кода остатка, регистр кода неполного частного, входы кода числа, входы инверсного кода модуля, выходы кода остатка, выходы кода неполного частного, вход начала вычисления, вход подачи тактовых импульсов, причём входы кода числа соединены с информационными входами регистра кода числа, первые информационные входы блока формирования частного и остатка соединены со входами инверсного кода модуля, первые информационные выходы соединены с выходами кода остатка устройства, вторые информационные выходы соединены с выходами кода неполного частного устройства, первый управляющий вход соединён со входом подачи тактовых импульсов устройства, выходы регистра кода остатка соединены с первыми информационными выходами блока формирования частного и остатка, выходы регистра неполного частного соединены со вторыми информационными выходами блока формирования частного и остатка, вторые информационные входы первого сумматора соединены с первыми информационными входами блока формирования частного и остатка, на вход переноса подаётся сигнал логической единицы, первый управляющий вход регистра кода остатка соединён с первым управляющим входом блока формирования частного и остатка, регистр кода числа выполнен в виде двух n/2 – разрядных регистров сдвига, в блок формирования частного и остатка введены два сумматора, четырехвходовый мультиплексор, а регистр кода остатка выполнен в виде двух n/2 – разрядных регистров сдвига, причём четырехвходовой мультиплексор, содержит три инвертора, три элемента И, четыре ключа, блок элементов ИЛИ, два элемента ИЛИ, при этом чётные разряды входа кода числа устройства соединены с информационными входами первого n/2 – разрядного регистра сдвига, а нечётные разряды соединены с информационными входами второго n/2 – разрядного регистра сдвига, вход подачи тактовых импульсов устройства соединен с первыми управляющими входами первого и второго n/2 – разрядных регистров сдвига, вход начала вычисления устройства соединен со вторыми управляющими входами первого и второго n/2 – разрядных регистров сдвига и со вторым управляющим входом блока формирования частного и остатка, вторые и третьи информационные входы которого соединены соответственно со входами инверсного удвоенного кода модуля устройства и со входами инверсного утроенного кода модуля устройства, выход старшего разряда первого n/2 – разрядного регистра сдвига соединён с четвёртым информационным входом блока формирования частного и остатка, а выход старшего разряда второго n/2 – разрядного регистра сдвига соединён с пятым информационным входом блока формирования частного и остатка, вторые информационные входы второго и третьего сумматоров соединены соответственно со вторыми и третьими информационными входами блока формирования частного и остатка, информационные выходы регистра кода остатка соединены с первым информационным выходом блока формирования частного и остатка и со сдвигом на два разряда в сторону старшего с первыми информационными входами четырехвходового мультиплексора и первого, второго и третьего сумматоров, информационные выходы которых соединены соответственно со вторыми, третьими и четвертыми информационными входами четырехвходового мультиплексора, а выходы переноса соединены соответственно с его первым, вторым и третьим управляющими входами, на входы переноса второго и третьего сумматоров подаётся сигнал логической единицы, первые два младших разряда первых информационных входов четырехвходового мультиплексора, первых информационных входов первого, второго и третьего сумматоров соединены с четвертым и пятым информационными входами блока формирования частного и остатка, первые информационные выходы четырехвходового мультиплексора соединены с информационными входами регистра кода остатка, второй и третий информационные выходы соединены с младшими разрядами информационных входов третьего и четвертого n/2 – разрядных регистров сдвига соответственно, первые управляющие входы которых соединены с первым управляющим входом блока формирования частного и остатка, а вторые управляющие входы соединены со вторым управляющим входом блока формирования частного и остатка и вторым управляющим входом регистра кода остатка, информационные выходы третьего n/2 – разрядного регистра сдвига соединены чётными разрядами вторых информационных выходов блока формирования частного и остатка, а информационная выходы четвертого n/2 – разрядного регистра сдвига соединены с нечётными разрядами его второго информационного выхода, первый управляющий вход четырехвходового мультиплексора соединён со входом первого инвертора и первым входом второго элемента И, второй управляющий вход соединён со входом второго инвертора и с первым входом третьего элемента И, третий управляющий вход соединён со входом третьего инвертора, с управляющим входом четвертого ключа и с первыми входами первого и второго элементов ИЛИ, выход первого инвертора соединён с первым входом первого элемента И, выход второго инвертора соединён со вторыми входами первого и второго элементов И, выход третьего инвертора соединен с третьими входами первого и второго элементов И и со вторым входом третьего элемента И, выход первого элемента И соединен с управляющим входом первого ключа, выход второго элемента И соединён с управляющим входом второго ключа и со вторым входом первого элемента ИЛИ, выход третьего элемента И соединен с управляющим входом третьего ключа и со вторым входом второго элемента ИЛИ, информационные входы первого, второго, третьего и четвертого ключей соединены с первым, вторым, третьим и четвертым информационными входами четырехвходового мультиплексора соответственно, а выходы соединены с первыми, вторыми третьими и четвертыми входами соответственно блока элементов ИЛИ, выходы которого соединены с первыми информационными выходами четырехвходового мультиплексора, выход первого элемента ИЛИ соединен со вторым информационным выходом четырехвходового мультиплексора, а выход второго элемента ИЛИ соединён с его третьим информационным выходом.

Сущность изобретения заключается в реализации следующего способа вычисления остатка R и неполного частного Q от числа A по модулю P. Пусть

где A – целое положительное число, от которого необходимо вычислить остаток;

P – целое положительное число, называемое модулем;

Q – целое положительное число, являющееся неполным частным от деления A на P;

R – целое положительное число, являющееся остатком от деления A на P.

Причем

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вначале на первом такте вычисляют величину

На втором такте вычисляют величину

На третьем такте вычисляют величину

На последнем n/2-м такте вычисляют величину

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

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

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

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

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

Таблица 1.

старший разряд младший разряд Значение t_i 0 0 0 ≤ t_i < P 0 1 P≤ t_i < 2P 1 0 2P ≤ t_i < 3P 1 1 3P ≤ t_i < 4P

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

Таблица 2.

t_i t_i – P t_i – 2P t_i – 3P 0 ≤ t_i < P 0 0 0 P≤ t_i < 2P 1 0 0 2P ≤ t_i < 3P 1 1 0 3P ≤ t_i < 4P 1 1 1

Таким образом, если значение сигналов переноса равно «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 представлена схема вычислительного устройства.

Вычислительное устройство содержит первый n/2 – разрядный регистр сдвига 1.1, второй n/2 – разрядный регистр сдвига 1.2, блок формирования частного и остатка 2, входы кода числа устройства 3, входы инверсного кода модуля устройства 4, входы инверсного удвоенного кода модуля устройства 5, входы инверсного утроенного кода модуля устройства 6, выходы кода остатка устройства 7, выходы кода неполного частного устройства 8, вход начала вычисления устройства 9, вход подачи тактовых импульсов устройства 10.

Чётные разряды входа кода числа устройства 3 соединены с информационными входами первого n/2 – разрядного регистра сдвига 1.1, нечётные разряды соединены с информационными входами второго n/2 – разрядного регистра сдвига 1.2.

Входы инверсного кода модуля устройства 4, входы инверсного удвоенного кода модуля устройства 5 и входы инверсного утроенного кода модуля устройства 6 соединены соответственно с первыми, вторыми и третьими информационными входами блока формирования частного и остатка 2.

Вход начала вычисления устройства 9 соединен со вторыми управляющими входами первого 1.1 и второго 1.2 n/2 – разрядных регистров сдвига и со вторым управляющим входом блока формирования частного и остатка 2. Вход подачи тактовых импульсов устройства 10 соединен с первыми управляющими входами 1.1 и второго 1.2 n/2 – разрядных регистров сдвига и с первым управляющим входом блока формирования частного и остатка 2.

Первые информационные выходы блока формирования частного и остатка 2 соединены с выходами кода остатка устройства 7, вторые информационные выходы соединены с выходами кода неполного частного устройства 8.

Выход старшего разряда первого n/2 – разрядного регистра сдвига 1.1 соединён с четвёртым информационным входом блока формирования частного и остатка 2, а выход старшего разряда второго n/2 – разрядного регистра сдвига 1.2 соединён с пятым информационным входом блока формирования частного и остатка 2.

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

Блок формирования частного и остатка 2 содержит три сумматора 11.1, 11.2 и 11.3, четырехвходовый мультиплексор 12, регистр кода остатка 13, два n/2 – разрядных регистра сдвига 14.1 и 14.2.

Вторые информационные входы первого 11.1, второго 11.2 и третьего 11.3 сумматоров соединены соответственно с первыми, вторыми и третьими информационными входами блока формирования частного и остатка 2.

Выходы регистра кода остатка 13 соединены с первым информационным выходом блока формирования частного и остатка 2 и со сдвигом на два разряда в сторону старшего с первыми информационными входами четырехвходового мультиплексора 12 и первого 11.1, второго 11.2 и третьего 11.3 сумматоров, информационные выходы которых соединены соответственно со вторыми, третьими и четвертыми информационными входами четырехвходового мультиплексора 12, а выходы переноса соединены соответственно с его первым, вторым и третьим управляющими входами.

На входы переноса первого 11.1, второго 11.2 и третьего 11.3 сумматоров подаётся сигнал логической единицы.

Первые два младших разряда первых информационных входов четырехвходового мультиплексора 12, первых информационных входов первого 11.1, второго 11.2 и третьего 11.3 сумматоров соединены с четвертым и пятым информационными входами блока формирования частного и остатка 2.

Первые информационные выходы четырехвходового мультиплексора 12 соединены с информационными входами регистра кода остатка 13, второй и третий информационные выходы соединены с младшими разрядами информационных входов третьего 14.1 и четвертого 14.2 n/2 – разрядных регистров сдвига соответственно, первые управляющие входы которых соединены с первым управляющим входом блока формирования частного и остатка 2 и первым управляющим входом регистра кода остатка 13, а вторые управляющие входы соединены со вторым управляющим входом блока формирования частного и остатка 2 и вторым управляющим входом регистра кода остатка 13.

Информационные выходы третьего n/2 – разрядного регистра сдвига 14.1 соединены чётными разрядами вторых информационных выходов блока формирования частного и остатка 2, а информационная выходы четвертого n/2 – разрядного регистра сдвига 14.2 соединены с нечётными разрядами его второго информационного выхода.

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

Четырехходовой мультиплексор 12, содержит три инвертора 15.1, 15.2 и 15.3, три элемента И 16, 17 и 18, четыре ключа 19.1, 19.2, 19.3 и 19.4, блок элементов ИЛИ 20, два элемента ИЛИ 21.1 и 21.2.

Первый управляющий вход четырехвходового мультиплексора 12 соединён со входом первого инвертора 15.1 и первым входом второго элемента И 17, второй управляющий вход соединён со входом второго инвертора 15.2 и с первым входом третьего элемента И 18, третий управляющий вход соединён со входом третьего инвертора 15.3, с управляющим входом четвертого ключа 19.4 и с первыми входами первого 21.1 и второго 21.2 элементов ИЛИ.

Выход первого инвертора 15.1 соединён с первым входом первого элемента И 16, выход второго инвертора 15.2 соединён со вторыми входами первого 16 и второго 17 элементов И, выход третьего инвертора 15.3 соединен с третьими входами первого 16 и второго 17 элементов И, а также со вторым входом третьего элемента И 18.

Выход первого элемента И 16 соединен с управляющим входом первого ключа 19.1, выход второго элемента И 17 соединён с управляющим входом второго ключа 19.2 и со вторым входом первого элемента ИЛИ 21.1, выход третьего элемента И 18 соединен с управляющим входом третьего ключа 19.3 и со вторым входом второго элемента ИЛИ 21.2.

Информационные входы первого 19.1, второго 19.2, третьего 19.3 и четвертого 19.4 ключей соединены с первым, вторым, третьим и четвертым информационными входами четырехвходового мультиплексора 12 соответственно, а выходы соединены с первыми, вторыми третьими и четвертыми входами соответственно блока элементов ИЛИ 20, выходы которого соединены с первыми информационными выходами четырехвходового мультиплексора 12.

Выход первого элемента ИЛИ 21.1 соединен со вторым информационным выходом четырехвходового мультиплексора 12, а выход второго элемента ИЛИ 21.2 соединён с его третьим информационным выходом.

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

На входы кода числа 3 устройства подается двоичный код числа A, от которого необходимо сформировать остаток R и неполное частное Q по произвольному модулю P. На входы инверсного кода модуля 4 устройства подается инверсный код модуля , поступая далее на первые информационные входы блока 2 формирования частного и остатка. На входы инверсного удвоенного кода модуля 5 устройства подается инверсный удвоенный код модуля , поступая далее на вторые информационные входы блока 2 формирования частного и остатка. На входы инверсного утроенного кода модуля 6 устройства подается инверсный утроенный код модуля , поступая далее на третьи информационные входы блока 2 формирования частного и остатка.

Затем на вход начала вычисления устройства 9 подается сигнал, под воздействием которого в первый n/2 – разрядный регистр сдвига 1.1 записываются четные разряды двоичного кода числа A, а во второй n/2 – разрядный регистр сдвига 1.2 записываются нечетные разряды двоичного кода числа A. Под воздействием этого же сигнала регистр кода остатка 13, третий 14.1 и четвертый 14.2 n/2 – разрядные регистры сдвига блока 2 формирования частного и остатка устанавливаются в нулевое состояние.

Вначале на первом такте работы устройства на четвёртый информационный вход блока 2 формирования частного и остатка с выхода старшего разряда первого n/2 – разрядного регистра сдвига 1.1 поступает значение (a_n-1)-го разряда числа A, а на пятый информационный вход с выхода старшего разряда второго n/2 – разрядного регистра сдвига 1.2 поступает значение (a_n-2)-го разряда числа A. В блоке 2 формирования частного и остатка формируется значение t₁=(a_n-1·2+a_n-2) mod P и разряды q_n-1 и q_n-2 неполного частного, которые записываются в младшие разряды третьего 14.1 и четвертого 14.2 n/2 – разрядных регистров сдвига соответственно.

На втором такте работы устройства на четвёртый информационный вход блока 2 формирования частного и остатка с выхода старшего разряда первого n/2 – разрядного регистра сдвига 1.1 поступает значение (a_n-3)-го разряда числа A, а на пятый информационный вход с выхода старшего разряда второго n/2 – разрядного регистра сдвига 1.2 поступает значение (a_n-4)-го разряда числа A. В блоке 2 формирования частного и остатка формируется значение
t₂=(2² t₁+(a_n-3·2+a_n-4)) mod P и разряды q_n-3 и q_n-4 неполного частного. При этом разряды q_n-1 и q_n-2 неполного частного сдвигаются на один разряд в сторону старших в третьем 14.1 и четвертом 14.2 n/2 – разрядном регистрах сдвига соответственно, а в младшие разряды этих регистров записываются соответственно разряды q_n-3 и q_n-4 неполного частного.

На последнем n/2-м такте работы устройства на четвёртый информационный вход блока 2 формирования частного и остатка с выхода старшего разряда первого n/2 – разрядного регистра сдвига 1.1 поступает значение a₁ - го разряда числа A, а на пятый информационный вход с выхода старшего разряда второго n/2 – разрядного регистра сдвига 1.2 поступает значение a₀ - го разряда числа A. В блоке 2 формирования частного и остатка формируется значение t_n/2=(2²t_n/2-1+(a₁·2+a₀)) mod P, которое и является искомым остатком R от числа A по модулю P, а также формируются разряды q₁ и q₀ неполного частного. При этом значение t_n/2 будет записано в регистр 13 кода остатка и поступит на выходы 7 кода остатка устройства, четные разряды неполного частного будут записаны в третий 14.1 n/2 – разрядный регистр сдвига, а нечетные разряды неполного частного будут записаны в четвертый 14.2 n/2 – разрядный регистр сдвига и поступят на выходы 8 кода неполного частного устройства.

Блок 2 формирования частного и остатка работает следующим образом (см. Фиг. 2).

На вторые информационные входы первого 11.1, второго 11.2 и третьего 11.3 сумматоров в течение всего цикла вычисления остатка R и неполного частного Q от числа A по модулю P с первых, вторых и третьих информационных входов блока 2 формирования частного и остатка подается соответственно инверсный код модуля , инверсный удвоенный код модуля и инверсный утроенный код модуля . На входы переноса первого 11.1, второго 11.2 и третьего 11.3 сумматоров подается сигнал логической единицы. В результате первый 11.1, второй 11.2 и третий 11.3 сумматоры выполняют фактически операцию арифметического вычитания из числа, подаваемого на их первые информационные входы, модуля P, 2P или 3P соответственно. В случае, если число на первых информационных входах сумматоров 11.1, 11.2 и 11.3 больше или равно чем число на их вторых информационных входах, то на выходе переноса соответствующего сумматора появляется сигнал логической единицы.

На первом такте работы устройства c четвёртого и пятого информационных входов блока 2 формирования частного и остатка значения (a_n-1)-го и (a_n-2)-го разряда числа A поступают на младшие разряды первых информационных входов четырехвходового мультиплексора 12, первого 11.1, второго 11.2 и третьего 11.3 сумматоров. На вторые, третьи и четвёртые информационные входы четырехвходового мультиплексора 12, с информационных выходов первого 11.1, второго 11.2 и третьего 11.3 сумматоров поступают соответственно значения (a_n-12+ a_n-2)-P, (a_n-12+ a_n-2)-2P и (a_n-12+ a_n-2)-3P, а на первый, второй и третий управляющие входы с выходов переноса первого 11.1, второго 11.2 и третьего 11.3 сумматоров поступают соответственно значения сигналов переноса. На первых информационных выходах четырехвходового мультиплексора 12 окажется величина
t₁=(a_n-1·2+a_n-2) mod P, которая под воздействием тактового импульса с первого управляющего входа блока 2 формирования частного и остатка будет записана в регистр кода остатка 13, а на втором и третьем информационных выходах будут сформированы разряды q_n-1 и q_n-2 неполного частного, которые под воздействием этого же тактового импульса будут записаны в младшие разряды третьего 14.1 и четвертого 14.2 n/2 – разрядных регистров сдвига.

На втором такте работы устройства на первых информационных входах четырехвходового мультиплексора 12, первого 11.1, второго 11.2 и третьего 11.3 сумматоров будет сформировано значение 2²t₁+(a_n-3·2+a_n-4), причем значение t₁ поступит с выхода регистра кода остатка 13 со сдвигом на два разряда в сторону старших, а значения a_n-3·и a_n-4 поступят на младшие разряды с четвертого и пятого информационных входов блока 2 формирования частного и остатка. В результате суммирования на вторых, третьих и четвертых информационных входах четырехвходового мультиплексора 12 окажутся величины 2²t₁+(a_n-3·2+a_n-4)-P, 2²t₁+(a_n-3·2+a_n-4)-2P и
2²t₁+(a_n-3·2+a_n-4)-3P соответственно, а на первом, втором и третьем управляющем входах окажутся сигналы переноса с выходов переноса первого 11.1, второго 11.2 и третьего 11.3 сумматоров. Четырехвходовый мультиплексор 12 в соответствии с логикой своей работы сформирует на своих первых информационных выходах величину t₂=(2²t₁+(a_n-32+a_n-4)) mod P, которая под воздействием тактового импульса с первого управляющего входа блока 2 формирования частного и остатка будет записана в регистр кода остатка 13, а на втором и третьем информационных выходах будут сформированы разряды q_n-3 и q_n-4 неполного частного, которые под воздействием этого же тактового импульса будут записаны в младшие разряды третьего 14.1 и четвертого 14.2 n/2 – разрядных регистров сдвига. При этом разряды q_n-1 и q_n-2 неполного частного в третьем 14.1 и четвертом 14.2 n/2 – разрядных регистров сдвига соответственно будут сдвинуты на один в сторону старших.

На последнем n/2-м такте работы устройства на первых информационных входах четырехвходового мультиплексора 12, первого 11.1, второго 11.2 и третьего 11.3 сумматоров будет сформировано значение
2²t_n/2-1+(a₁·2+a₀), причем значение t_n/2-1 поступит с выхода регистра кода остатка 13 со сдвигом на два разряда в сторону старших, а значения a₁·и a₀ поступят на младшие разряды с четвертого и пятого информационных входов блока 2 формирования частного и остатка. В результате суммирования на вторых, третьих и четвертых информационных входах четырехвходового мультиплексора 12, окажутся величины 2²t_n/2-1+(a₁·2+a₀)-P, 2²t_n/2-1+(a₁·2+a₀)-2P и 2²t_n/2-1+(a₁·2+a₀)-3P соответственно, а на первом, втором и третьем управляющем входах окажутся сигналы переноса с выходов переноса первого 11.1, второго 11.2 и третьего 11.3 сумматоров. Четырехвходовый мультиплексор 12 в соответствии с логикой своей работы сформирует на своих первых информационных выходах величину t_n/2=(2²t_n/2-1+(a₁2+a₀))mod P, которая под воздействием тактового импульса с первого управляющего входа блока 2 формирования частного и остатка будет записана в регистр кода остатка 13, а на втором и третьем информационных выходах будут сформированы разряды q₁ и q₀ неполного частного, которые под воздействием этого же тактового импульса будут записаны в младшие разряды третьего 14.1 и четвертого 14.2 n/2 – разрядных регистров сдвига с одновременным сдвигом ранее записанных разрядов на один в сторону старших.

В результате после n/2 – го такта работы на первых информационных выходах блока 2 формирования частного и остатка будет сформирован код остатка R от числа A по модулю P, а на вторых информационных выходах неполное частное Q.

Четырехвходовый мультиплексор 12 работает следующим образом (см. Фиг. 3).

На i-м такте работы устройства, где , на первом информационном входе четырехвходового мультиплексора 12 образуется значение t_i=2²t_i-1+(a_n-2i-1·2+a_n-2i), на втором, третьем и четвертом информационных входах образуются значения t_i-P, t_i-2P и t_i-3P соответственно, при этом t₀=0.

Управляющие сигналы четырехвходового мультиплексора 12 открывают один из ключей 19.1-19.4.

Если управляющий сигнал появляется на всех трех управляющих входах четырехвходового мультиплексора 12, то окажется открытым четвертый ключ 19.4. Управляющий сигнал с третьего управляющего входа откроет четвертый ключ 19.4 и через третий инвертор 15.3 в виде логического нуля поступит на третьи входы элементов 16 и 17 И, а также на второй вход элемента И 18, запрещая прохождение управляющих сигналов с их первых входов на их выходы. В результате первый 19.1, второй 19.2 и третий 19.3 ключи окажутся закрытыми и на выход четырехвходового мультиплексора 12 поступит значение t_i-3P с его четвертых информационных входов.

Если управляющий сигнал появляется на первом и втором управляющих входах четырехвходового мультиплексора 12, то аналогичным образом окажется открытым только третий 19.3, а первый 19.1, второй 19.2 и четвертый ключи 19.4 окажутся закрытыми. В результате на выход четырехвходового мультиплексора 12 поступит значение t_i-2P с его третьих информационных входов.

Если управляющий сигнал появляется только на первом управляющем входе четырехвходового мультиплексора 12, то аналогичным образом окажется открытым только второй ключ 19.2, а первый 19.1, третий 19.3 и четвертый 19.4 ключи окажутся закрытыми. В результате на выход четырехвходового мультиплексора 12 поступит значение t_i-P с его вторых информационных входов.

Если же на управляющих входах четырехвходового мультиплексора 12 будут только нулевые сигналы, то они, поступая через инверторы 15.1-15.3 и первый элемент И 16, откроют первый ключ 19.1 и на выход четырехвходового мультиплексора 12 поступит значение t_i с его первых информационных входов.

Значения с выходов ключей 19.1-19.4 поступают через блок элементов ИЛИ 20 на первые информационные выходы четырехвходового мультиплексора 12.

В результате на первом информационном выходе четырехвходового мультиплексора 12 всегда образуется значение (2²t_i-1+(a_n-2i-1·2+a_n-2i)) mod P.

Разряды неполного частного Q формируются на втором и третьем информационных выходах четырехвходового мультиплексора 12 с помощью первого 21.1 и второго 21.2 элементов ИЛИ в соответствии с логикой таблиц 1 и 2.

Технико-экономическая эффективность изобретения заключается в увеличении быстродействия формирования остатка от числа по модулю и неполного частного. Так устройство прототип осуществляет вычисление остатка от n – разрядного числа по произвольному n – разрядному модулю за n тактов работы. Изобретение аналогичное вычисление осуществляет за n/2 тактов работы за счет параллельной обработки четных и нечетных разрядов входного числа. При этом увеличение быстродействия произойдет в 2 раза.

Источники информации

1. Петренко В.И., Сидорчук А.В. Вычислительное устройство // Патент России №2348965. Опубл. 10.03.2009. Бюл. №7.

2. Петренко В.И., Чипига А.Ф. Устройство для формирования остатка по произвольному модулю от числа. Патент России №2012137. Опубл. 30.04.1994.

3. Петренко В.И. Вычислительное устройство // Патент России №2661797. Опубл. 19.07.2018. Бюл. № 20.

Вычислительное устройство относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, устройствах цифровой обработки сигналов, в криптографических приложениях, а также в устройствах для формирования кодовых последовательностей, построение которых основывается на теории конечных полей. Техническим результатом является увеличение быстродействия формирования остатка от числа по модулю и неполного частного. Устройство содержит два n/2 – разрядных регистра сдвига, блок формирования частного и остатка, содержащий три сумматора, четырехвходовый мультиплексор, регистр кода остатка, два n/2 – разрядных регистра сдвига. 3 ил., 2 табл.

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