RU2007037C1

RU2007037C1 - Recurrent generator of remainders of arbitrary modulo

Info

Publication number: RU2007037C1
Authority: RU
Inventors: Вячеслав Иванович Петренко; Александр Федорович Чипига
Original assignee: Вячеслав Иванович Петренко; Александр Федорович Чипига
Priority date: 1991-06-17
Filing date: 1991-06-17
Publication date: 1994-01-30

Abstract

FIELD: computer engineering. SUBSTANCE: device has register, unit of switches, inverter, unit for generation of partial remainders, unit of adders and delay gate. EFFECT: increased functional capabilities. 4 cl, 6 dwg

Description

Изобретение относится к вычислительной технике и может быть использовано в устройствах для формирования элементов конечных полей, в устройствах для формирования кодовых последовательностей, построение которых основывается на теории конечных полей, а также в устройствах, функционирующих в СОК. The invention relates to computer technology and can be used in devices for forming elements of finite fields, in devices for forming code sequences, the construction of which is based on the theory of finite fields, as well as in devices operating in RNS.

Известно устройство для формирования остатка по произвольному модулю от числа, содержащее два регистра, два элемента ИЛИ, вычитатель, схему сравнения и мультиплексор, соединенные между собой функционально [1] . A device is known for forming a remainder modulo an arbitrary number, containing two registers, two OR elements, a subtractor, a comparison circuit, and a multiplexer interconnected functionally [1].

Недостатком известного устройства является его низкое быстродействие. A disadvantage of the known device is its low speed.

Наиболее близким по технической сущности к предложенному является устройство для формирования остатка по произвольному модулю от числа, содержащее регистр, блок ключей, блок сумматоров и элемент задержки, соединенные между собой функционально [2] . The closest in technical essence to the proposed one is a device for generating a remainder modulo an arbitrary number, containing a register, a block of keys, a block of adders and a delay element interconnected functionally [2].

Недостатками известного устройства являются низкая надежность его функционирования и небольшая область функциональных возможностей. The disadvantages of the known device are the low reliability of its operation and a small area of functionality.

В рекуррентный формирователь остатков по производному модулю, содержащий блок сумматоров, элемент задержки и регистр, выходы которого соединены с управляющими входами блока ключей, введены блок формирования частичных остатков и инвертор, а блок сумматоров выполнен в виде ярусов из N - 1 сумматоров по произвольному модулю, количество которых в каждом ярусе равно N/2ⁱ, где i - номер яруса блока, а N - разрядность входного числа формирователя, при этом первый и второй информационные входы сумматоров по произвольному модулю первого яруса являются информационными входами блока сумматоров, выходы сумматоров по произвольному модулю i-го яруса, кроме последнего, соединены соответственно с первыми и вторыми информационными входами сумматоров по произвольному модулю (i + 1)-го яруса, выход сумматора по произвольному модулю последнего яруса является выходом блока сумматоров, а третьи и четвертые информационные входы всех сумматоров по произвольному модулю соединены соответственно с входами прямого и инверсного значений модуля блока сумматоров, причем информационный вход формирователя соединен с информационным входом регистра, вход записи которого соединен с входом начала вычислений формирователя и входом элемента задержки, выход которого является выходом конца вычислений формирователя, вход модуля которого соединен с входом инвертора, первыми входами блока формирования частичных остатков и входом прямого значения модуля блока сумматоров, вход инверсного значения модуля которого соединен с выходом инвертора и вторыми входами блока формирования частичных остатков, выходы которого соединены с информационными входами блока ключей, выходы которого соединены с информационными входами блока сумматоров, выход которого является информационным выходом формирователя.In the recurrent residual generator for the derived module, containing the adder block, a delay element and a register whose outputs are connected to the control inputs of the key block, the partial residual generator and inverter are introduced, and the adder block is made in the form of tiers of N - 1 adders in an arbitrary module, the number in each tier which is equal to N / 2 ^i, where i - block tier number, and N - bit input number generator, wherein the first and second data inputs of the adders of the first tier module arbitrary yavlyayuts information inputs of the adder block, the outputs of the adders in an arbitrary module of the i-th tier, except for the last, are connected respectively to the first and second information inputs of the adders in an arbitrary module of the (i + 1) -th tier, the output of the adder in an arbitrary module of the last tier is the output of the adder block and the third and fourth information inputs of all adders in an arbitrary module are connected respectively to the inputs of direct and inverse values of the module of the adder block, and the information input is formed I am connected to the information input of the register, the recording input of which is connected to the input of the beginning of the shaper's calculations and the input of the delay element, the output of which is the output of the end of the shaper's calculations, the input of the module of which is connected to the inverter input, the first inputs of the partial residual formation block and the direct value of the adder block module input , the input of the inverse value of the module of which is connected to the output of the inverter and the second inputs of the block forming partial residues, the outputs of which are connected to the information inputs odes of the key block, the outputs of which are connected to the information inputs of the adder block, the output of which is the information output of the shaper.

Блок формирования частичных остатков содержит N - 1 формирователей частичных остатков, на каждый из которых подается код модуля в прямом и в инверсном виде, причем выход предыдущего формирователя частичных остатков является информационным выходом блока и соединен с входом последующего формирователя частичных остатков, на информационный вход первого формирователя подан код единицы. The partial residual forming unit contains N - 1 partial residual formers, each of which is supplied with the module code in direct and inverse form, the output of the previous partial residual former being the information output of the block and connected to the input of the subsequent partial residual former to the information input of the first former unit code has been submitted.

Сумматор по произвольному модулю содержит последовательно соединенные комбинационный сумматор и формирователь частичных остатков, причем информационные входы комбинационного сумматора являются информационными входами сумматора по произвольному модулю, а информационный выход формирователя частичных остатков, на управляющие входы которого подан код модуля в прямом и в инверсном виде, является информационным выходом сумматора. An adder modulo an arbitrary module contains a combinational adder and a partial residual shaper connected in series, the information inputs of the combinational adder being information inputs of an adder in an arbitrary modulus, and the information output of the partial residual shaper, to the control inputs of which the module code is sent in direct and inverse form, is information the output of the adder.

Формирователь частичных остатков содержит элемент ИЛИ, ключ, а также последовательно соединенные первый и второй сумматоры, причем второй вход второго сумматора соединен с выходом ключа, управляющий вход которого соединен с выходом элемента ИЛИ, а выход второго сумматора является информационным выходом формирователя, вход модуля соединен с информационным входом ключа, а вход модуля в инверсном виде - с первым входом первого сумматора, второй вход которого является информационным входом формирователя, разряд переноса соединен с первым входом элемента ИЛИ, второй вход которого соединен с выходом переноса первого сумматора, на вход переноса которого подается уровень логической "1". The partial residual shaper contains an OR element, a key, and also the first and second adders connected in series, the second input of the second adder connected to the output of the key, the control input of which is connected to the output of the OR element, and the output of the second adder is an information output of the shaper, the module input is connected to information input key, and the input of the module in inverse form with the first input of the first adder, the second input of which is the information input of the shaper, the transfer bit is connected to the first progress of OR, a second input coupled to an output of the first adder transfer in whose transfer input is logic level "1".

Известно, что позиционные системы счисления строятся следующим образом. Выбирается некоторое число m - основание системы счисления, и каждое число А представляется в виде комбинации его степеней с коэффициентами a_i, i =

, принимающими значения от 0 до m - 1. Для случая двоичной системы счисления (m = 2) всякое число А можно представить в виде
A = a_N2^N + a_N-12^N-1 + . . . + a₁2¹ + a_o, (1) где a_i, i =

принимают значение "0" или "1".It is known that positional number systems are constructed as follows. A certain number m is selected — the base of the number system, and each number A is represented as a combination of its degrees with coefficients a _i , i =

taking values from 0 to m - 1. For the case of a binary number system (m = 2), any number A can be represented as
A = a _N 2 ^N + a _N-1 2 ^N-1 +. . . + a ₁ 2 ¹ + a _o , (1) where a _i , i =

take the value "0" or "1".

Для вычисления остатка от числа А по модулю Р достаточно в выражении (1) просуммировать частичные остатки по модулю Р от чисел 2ⁱдля тех i, для которых коэффициент a_i = 1. Способ вычисления частичных остатков состоит в следующем. Частичный остаток от 2^о для любого модуля (Р ≥2) всегда равен единице. Частичный остаток от 2¹ в два раза превышает (с учетом операции приведения по модулю) частичный остаток от 2^о и т. д. , т. е. частичный остаток от 2ⁱ в два раза превышает частичный остаток от 2^i-1. Таким образом, вычисление частичного остатка от 2ⁱзаключается в умножении на два частичного остатка от 2^i-1 и приведения результата по модулю Р. Операция приведения по модулю Р для чисел, не превышающих величину 2Р - 1, реализуется следующим образом. Если значение частичного остатка не превышает величину Р, то оно остается без изменения, если число лежит в интервале от Р до 2Р - 1, то из него вычитается модуль Р, а результат является остатком. Операции умножения на два (как видно из выражения (1)) может быть реализована сдвигом всех разрядов умножаемого числа на один влево либо подачей разрядов множимого на выход результата, в такой последовательности: 2ⁱ разряд множимого на 2ⁱ⁺¹ разряд произведения, i =

.To calculate the remainder of the number A modulo P it is enough to sum in the expression (1) the partial residuals modulo P of the numbers 2 ⁱ for those i for which the coefficient a _i = 1. The method for calculating the partial residuals is as follows. Partial remainder of ^about 2 for any module (p ≥2) is always equal to unity. The partial remainder of 2 ¹ is twice as large (taking into account the reduction operation modulo) the partial remainder of 2 ^о , etc., i.e., the partial remainder of 2 ⁱ is twice as large as the partial remainder of 2 ^i-1 . Thus, the calculation of the partial remainder of 2 ⁱ consists in multiplying by two partial residues of 2 ^i-1 and bringing the result modulo P. The operation of casting modulo P for numbers not exceeding 2P - 1 is implemented as follows. If the value of the partial remainder does not exceed the value of P, then it remains unchanged, if the number lies in the range from P to 2P - 1, then the module P is subtracted from it, and the result is the remainder. The operations of multiplying by two (as can be seen from expression (1)) can be realized by shifting all the bits of the multiplied number by one to the left or by applying the bits of the multiplicable result to the output, in the following sequence: 2 ⁱ digit of the multiplicable by 2 ^{i + 1} digit product, i =

.

На фиг. 1 представлена функциональная электрическая схема рекуррентного формирователя остатков по произвольному модулю; на фиг. 2 - блока формирования частичных остатков; на фиг. 3 - блока ключей; на фиг. 4 - блока сумматоров по модулю; на фиг. 5 - сумматора по модулю; на фиг. 6 - формирователя частичных остатков. In FIG. 1 is a functional electrical diagram of a recurrent residual shaper modulo; in FIG. 2 - block formation of partial residues; in FIG. 3 - key block; in FIG. 4 - block adders modulo; in FIG. 5 - adder modulo; in FIG. 6 - shaper partial residues.

Формирователь содержит (фиг. 1) регистр 1, блок 2 ключей, инвертор 3, блок 4 формирования частичных остатков, блок 5 сумматоров и элемент 6 задержки. Число А, от которого необходимо сформировать остаток, подается на вход 7 устройства. Вход 8 начала вычисления соединен с входом записи регистра 1 и входом элемента 6 задержки. Вход 9 модуля соединен с первыми информационными входами блока 4 формирования частичных остатков, блока 5 сумматора по модулю и с входами инвертора 3. Выход 10 блока 5 является информационным, а выход 11 элемента 6 задержки - выходом окончания процесса формирования остатка. The shaper contains (Fig. 1) register 1, block 2 keys, inverter 3, block 4 for the formation of partial residuals, block 5 adders and element 6 delays. The number A, from which it is necessary to form a remainder, is fed to input 7 of the device. The input 8 of the beginning of the calculation is connected to the input of the register 1 and the input of the delay element 6. The input 9 of the module is connected to the first information inputs of the block 4 forming partial residuals, block 5 of the adder modulo and with the inputs of the inverter 3. The output 10 of block 5 is informational, and the output 11 of the delay element 6 is the output of the end of the residue formation process.

Блок 4 формирования частичных остатков (фиг. 2) содержит N - 1 формирователей 12 частичных остатков, соединенных последовательно друг с другом по рекуррентному принципу, причем на вход первого формирователя подан код единицы, выходы разрядов предыдущего формирователя подаются на входы последующего формирователя со сдвигом на один разряд влево (реализация процедуры умножения), а выходы каждого формирователя являются информационными выходами блока. Block 4 of the formation of partial residues (Fig. 2) contains N - 1 formers 12 of partial residues connected in series with each other according to the recurrence principle, and the unit code is applied to the input of the first shaper, the discharge outputs of the previous shaper are fed to the inputs of the subsequent shaper with a shift of one discharge to the left (implementation of the multiplication procedure), and the outputs of each shaper are the information outputs of the block.

Блок 2 ключей (фиг. 3) содержит N ключей 13, на информационные входы которых подаются коды с выходов формирователей 12, управляющие входы соединены с информационными выходами регистра 1, а информационные выходы являются информационными выходами блока. Block 2 of the keys (Fig. 3) contains N keys 13, on the information inputs of which codes from the outputs of the shapers 12 are supplied, the control inputs are connected to the information outputs of the register 1, and the information outputs are information outputs of the block.

Блок 5 сумматоров содержит (фиг. 4) сумматоры 14 по произвольному модулю. На каждый сумматор 14 подается код модуля в прямом и в инверсном виде. Каждый сумматор 14 содержит (фиг. 5) последовательно соединенные комбинационный сумматор 15, информационные входы которого являются информационными входами сумматора 14, и формирователь 16 частичных остатков. В состав формирователя частичных остатков (фиг. 6) входит первый 17 и второй 18 сумматоры, элемент ИЛИ 19 и ключ 20. Block 5 adders contains (Fig. 4) adders 14 in an arbitrary module. For each adder 14, the module code is supplied in direct and inverse form. Each adder 14 contains (Fig. 5) series-connected combination adder 15, the information inputs of which are the information inputs of the adder 14, and the shaper 16 of the partial residuals. The composition of the shaper of partial residues (Fig. 6) includes the first 17 and second 18 adders, the OR element 19 and the key 20.

Рекуррентный формирователь остатков по произвольному модулю работает следующим образом. A recurrent shaper of residuals modulo an arbitrary module works as follows.

В исходном состоянии на вход 9 модуля подается код модуля P_j, по которому необходимо формировать остатки. Поэтому на первые входы блоков 4 и 5 подается код модуля в прямом, а на вторые входы через инвертор 3 - в инверсном виде. Так как на вход первого формирователя 12 частичных остатков подается код единицы, а выходы разрядов предыдущего формирователя подключены на входы последующего формирователя со сдвигом на один разряд влево, на выходах блока 4 сформированы частичные остатки по модулю P_j от чисел 2ⁱ, i =

.In the initial state, the module code P _j is supplied to the input of the module 9, by which it is necessary to form residues. Therefore, at the first inputs of

blocks

4 and 5, the module code is supplied in direct, and at the second inputs through inverter 3 - in inverse form. Since the unit code is supplied to the input of the first shaper 12 of partial residuals, and the bit outputs of the previous shaper are connected to the inputs of the subsequent shaper with a shift by one bit to the left, partial residues modulo P _j from the numbers 2 ⁱ , i =

.

Число А через вход 7 поступает на информационные входы регистра 1. Одновременно на вход 8 начала вычисления подается импульс, который поступает на вход элемента 6 задержки и на вход записи регистра 1. Поэтому код числа А записывается в регистр 1, появляется на его информационных выходах и поступает на управляющие входы блока 2 ключей. В зависимости от того, на управляющий вход какого из ключей 13 поступает логическая "1", тот из ключей 13 оказывается открытым и коммутирует на свои выходы значения с информационных входов, на которые с информационных выходов блока 2 поступают частичные остатки по модулю Р. В результате на соответствующие входы блока 5 сумматоров поступают остатки от чисел 2ⁱ для тех i, для которых коэффициент a_i = 1 в представлении (1) числа А, записанного в регистр 1. Блок 5 сумматоров суммирует по модулю P_j частичные остатки и результат суммирования выдается на информационный выход 10 устройства. Одновременно с выхода элемента 6, время задержки которого равно времени работы блоков 2 и 5, на выход 11 поступает импульс, сигнализирующий об окончании процесса формирования остатка.The number A through the input 7 is fed to the information inputs of the register 1. At the same time, the pulse 8 is applied to the input 8 of the calculation, which is fed to the input of the delay element 6 and to the input of the register 1. Therefore, the code of the number A is written to register 1, appears on its information outputs and arrives at the control inputs of a block of 2 keys. Depending on the control input of which of the keys 13 receives a logical "1", that of the keys 13 is open and commutates to its outputs the values from the information inputs, to which the partial outputs modulo P. come from the information outputs of block 2. As a result the corresponding inputs of block 5 adders receive residues from numbers 2 ⁱ for those i for which the coefficient a _i = 1 in the representation (1) of number A written in register 1. Block 5 adders sums modulo P _j partial residuals and the result of the summation is issued on inf Formation output 10 of the device. Simultaneously with the output of element 6, the delay time of which is equal to the operating time of units 2 and 5, an output 11 receives a pulse signaling the end of the process of forming the residue.

При следующем цикле формирования остатка задается любое другое число А, которое поступает на вход 7, и работа всех элементов и блоков устройства повторяется. In the next cycle of the remainder formation, any other number A, which is input 7, is set, and the operation of all elements and units of the device is repeated.

Для смены модуля на вход 9 устройства подается очередной модуль P_j, формирователи 12 блока 4 формируют частичные остатки от чисел 2ⁱ, а с подачей очередного числа А работа элементов и блоков устройства повторяется.To change the module, the next module P _j is fed to the input 9 of the device, the formers 12 of block 4 form partial residues from the numbers 2 ⁱ , and with the supply of the next number A, the work of the elements and blocks of the device is repeated.

Блок 5 сумматоров работает следующим образом. На управляющие входы каждого сумматора 14 блока 5 поступает значение модуля в прямом и инверсном виде, а на информационные входы сумматоров 14 первого ряда поступают остатки от чисел 2ⁱ для тех i, для которых a_i = 1. Остатки от суммирования по модулю попарно поступают на второй ряд сумматоров и т. д. , поэтому остаток от суммирования по модулю оказывается на выходах блока 5 и поступает на информационный выход 10 устройства.Block 5 adders works as follows. The control inputs of each adder 14 of block 5 receive the module value in direct and inverse form, and the information inputs of the adders 14 of the first row receive the residues from the numbers 2 ⁱ for those i for which a _i = 1. The residues from the summation modulo pairwise arrive at the second row of adders, etc., therefore, the remainder of the summation modulo appears at the outputs of block 5 and enters the information output 10 of the device.

Сумматор 14 по произвольному модулю работает следующим образом. Комбинационный сумматор 15 осуществляет суммирование остатков, поступающих на его информационные входы, а формирователь 16 частичных остатков в зависимости от значений кода модуля в прямом и инверсном виде, поступающих на его входы, приводит по модулю значение суммы. The adder 14 modulo an arbitrary module operates as follows. The combinational adder 15 sums up the residuals arriving at its information inputs, and the shaper 16 partial residuals depending on the values of the module code in direct and inverse form arriving at its inputs, gives the modulus of the sum value.

Формирователь 12 (16) частичных остатков работает следующим образом. Сумматор 17, на разряд переноса которого постоянно подан уровень логической "1", за счет подачи на его вход кода модуля в инверсном виде выполняет функцию вычитания модуля из числа А, старший разряд которого подается на вход элемента ИЛИ 19. Если разность меньше нуля, то сумматор 18 добавляет к этой разности код модуля (т. е. входное число было меньше модуля), если разность больше нуля, то ключ 20, на вход которого подается код модуля, оказывается закрытым и эта разность поступает на выход без изменения через сумматор 18 формирователя. Таким образом, на выходе формирователя 12 частичных остатков сформирован остаток от числа, воздействующего на его входы, по модулю Р. (56) Авторское свидетельство СССР N 1396281, кл. H 03 M 7/18, 1986. Shaper 12 (16) of partial residues works as follows. The adder 17, to the transfer bit of which the logic level “1” is constantly applied, by feeding the module code in its inverse form, performs the function of subtracting the module from the number A, the highest bit of which is fed to the input of OR 19. If the difference is less than zero, then the adder 18 adds to this difference the module code (i.e., the input number was less than the module), if the difference is greater than zero, then the key 20, to the input of which the module code is supplied, is closed and this difference is output without change through the adder 18 of the shaper . Thus, at the output of the shaper of 12 partial residues, the remainder of the number acting on its inputs is formed modulo R. (56) Copyright certificate of the USSR N 1396281, cl. H 03 M 7/18, 1986.

Авторское свидетельство СССР N 1633495, кл. H 03 M 7/18, 1989. USSR copyright certificate N 1633495, cl. H 03 M 7/18, 1989.

Claims

1. A recurrent residual generator for an arbitrary module, comprising an adder block, a delay element and a register, the outputs of which are connected to the control inputs of the key block, characterized in that a partial residual generator and an inverter are introduced into it, and the adder block is made in the form of tiers of N - 1 adders modulo arbitrary, the number of which is equal in each tier N / 2 ^i, where i - block tier number, and N - bit input number generator, the first and second data inputs of adders arbitrary modulo n the first tier are the information inputs of the adder block, the outputs of the adders by an arbitrary module of the i-th tier, except for the last, are connected respectively to the first and second information inputs of the adders by an arbitrary module of the i + 1-tier, the output of the adder by an arbitrary module of the last tier is the output of the block adders, and the third and fourth information inputs of all adders in an arbitrary module are connected respectively to the inputs of direct and inverse values of the module of the adder block, and the information the first input of the shaper is connected to the information input of the register, the recording input of which is connected to the input of the start of calculations of the shaper and the input of the delay element, the output of which is the output of the end of the calculations of the shaper, the input of the module of which is connected to the input of the inverter, the first input of the block for the formation of partial residues and the input of the direct value of the module block adders, the input of the inverse value of the module of which is connected to the output of the inverter and the second input of the block forming partial residues, the information outputs of which connected to the information inputs of the key block, the outputs of which are connected to the information inputs of the adder block, the output of which is the information output of the shaper.

2. The shaper according to claim 1, characterized in that the partial residue forming unit comprises N - 1 partial residue shapers whose direct module inputs are connected to the first input of the partial residue forming block, the second input of which is connected to the inverse values of the N - 1 module partial remnants, the output of the i-th partial remover, where i = 1, N - 1, is the i-th information output of the partial residual block and is connected to the information input of the (i + 1) -th partial remnant atkov, an information input of the first partial shaper residues and first output unit for generating the partial balances are connected to a bus unit code.

3. The shaper according to claim 1, characterized in that the adder in an arbitrary modulus comprises a combinational adder and a partial residual shaper connected in series, the inputs of the combinational adder being the first and second information inputs of the adder in an arbitrary module, the output of which is connected to the output of the partial residual shaper, the inputs of direct and inverse values of the module of which are the third and fourth information inputs of the adder, respectively, according to an arbitrary module.

4. Shaper on PP. 2 and 3, characterized in that the partial residual shaper comprises adders in series, an OR element, and a key, and the direct value input of the partial residual shaper module is connected to the information input of the key, the output of which is connected to the second input of the second combination adder, the output of which is the output of the shaper partial residues, the input of the inverse value of the module of which is connected to the first input of the first combination adder, the second input of which is connected to the information input tors, partial residues carry bit which is connected to the first input of the OR gate, a second input coupled to an output of the first transfer Raman adder whose transfer input is connected with the bus logic unit, and the output of OR - the control input of the key.