SU1633495A1 - Device for generating arbitrary modulo residue - Google Patents

Abstract

The invention relates to computing and can be used in devices for generating code sequences, the construction of which is based on the theory of finite fields. The aim of the invention is to increase speed. The goal is achieved by the fact that a device for forming a residual containing registers 9 and 10, elements OR 4 and 5, a subtractor 13, a comparison circuit II and a multiplexer 18, contains the elements OR 6, 7 and 8, a comparison circuit 12, a delay element 14, an adder 15, a group of blocks of 16 And elements and a block 17 of a permanent memory with links. 1 il.

Description

The invention relates to computing and can be used in devices for generating elements of finite fields, as well as in devices for normalizing code sequences, the construction of which is based on the theory of finite fields.

The aim of the invention is to increase speed.

The drawing shows a diagram of an apparatus for forming a remainder in an arbitrary modulus of a number.

The device contains input 1 Start calculating the device, input 2 of the device module, input 3 of the device number, first through fifth elements OR 4-8, first 9 and second 10 regs of the initial state

The first, first, and second 12 schemes were compared to 2Qs. In block 17

, subtractor 13, delay element 14, adder 15, group of blocks 16 elements And, block 17 of permanent memory, multiplexer 18, output 19 End of calculation of the device and output 20 25 of the result of the device.

The principle of operation of the device for forming a residue of an arbitrary modulus of a number is to implement the following method of converting modulo numbers.

It is known that positional number systems are constructed according to the following principle. Some number m is chosen as the base of the number system, and each number A is represented as a combination of its values with coefficients a1,, k, taking values from 0 to n-1, i.e. as

thirty

35

The known remnants of the numbers P.1, with which the prep devices are recorded. Module P is carried out by a number formulant, given with a set code, and supplied with a device module. The number A comes in binary code. After the number and the module at input 1, the beginning of the deduction pulse, which, for the IPI 4, goes to read the resolution for the resolution input for 10 and for the input of the element. At the register 10, the plexer 18 occurs and at the outputs of block 1 there are residues from numbers

akrn

 ++ a, m + a0,

(ABOUT

afc- 2 (modP) ++ a, 2 (modP) +

clean-sum + a0 (modP). (4)

Since for a binary lazy system, the coefficients a | take two values O or 1, then, to the world, the pre-calculated residues modulo P from the numbers 21 for those i, 0 for which is a coefficient, we obtain the remainder modulo P from the number A.

with which it is assumed in the permanent storage device (ROM / 5 is remembered the pre-calculated residuals from the numbers 2.

The device works as follows

In the initial state, all registers

For modules R.

the device works,

Q cleared. In block 17

memory pred5

0

five

0

The pre-calculated residuals from the numbers 2 modulo R.1, with which the device is supposed to work, are recorded. The module Pj, according to which the formation of residual numbers is carried out, is given by a parallel binary code supplied to the input 2 of the device module. The input number 3 receives the number A in the parallel binary code. After the codes and the module are fed, the input of the device to input 1 of the beginning of the calculation is given by a pulse, which, passing through the IPI 4, enters the read enable input of memory block 17, the write enable register 10 and the input of delay element 14. At the same time, the n register 10 through the multiplexer 18 records the number, and at the outputs of the memory block 17, the remainder of the numbers 21 modulo

where k is the width of the represented number. For the case of a binary number system, expression (1) takes the form

It is also known that comparisons can be added termwise, i.e. if A, B (modP) ,, (modP), then

fair dyrazhenis

A, + AfcsB, +. . .. bk (raodP).

Taking into account (2) and (3), you can record (3)

to sat

(ak, 2

, -t-a, 2 + aOmodP

45

50

3)

55

Liu R

J.

R

entrance

The memory unit 17 has k outputs, each of which consists of ' 1 bits, necessary for representing the residuals of the numbers 2 modulo P; Depending on which of the 16 blocks of elements AND receives the logical 1, that of the blocks of 16 elements of H turns out to be open and switches its value from the second input to its output. As a result, the corresponding inputs of the adder 15 receive the residues from the numbers 2, for those L for which the coefficient in the representation (2) of the number written in register 10, the adder 15 performs the summation of the numbers arriving at its inputs, and this sum in the binary parallel the code appears on its

output In this case, the first input of the comparison circuit I1 is affected by the mode code n, and the second input is a code calculated by the sum from the output of the adder 15. At this time, a pulse appears at the output of the delay element 14, which arrives at the control input of the comparison circuit , allows comparison of codes of numbers acting on its inputs. If, as a result of the comparison, it turns out that the code of the number acting on the second input of the comparison circuit is less than the module code, then the output of the Less comparison circuit II is the pulse that arrives at the second control input of the multiplexer 1 and through the OR 7 element at the resolution input write register 9. As a result, the multiplexer switches its second input to the output and, in this case, the residual code from the output of the adder 15 is written to the register 9, and an output appears at the output of the device calculating output. but completed and in register 9 recorded code residue. If, as a result of the comparison, the pulse is at the output of Equal to the comparison circuit 11, this indicates that the remainder of the number is equal to the module, which means that the number is identically equal to zero. In this case, the pulse from the output Equal to the comparison circuit 11, passed through the element ICI 8, zeroed the register 9 and through the element OR 5 enters the output. The end of calculation 19 of the device. The appearance of a pulse at the output of the More comparison circuit I1 indicates that the formation of the residue is not completed. Impulse from the output More comparison circuit 11 arrives at the control input of comparison circuit 12, allowing comparison of the codes of numbers acting on its inputs. In this case, its first input is affected by the module code, and the second input is affected by the number code from the output of the subtractor 13, which is numerically equal to the difference of the code from the output of the adder 15 and the module code. If, as a result of the operation of the circuit 12, the comparison pulse is equal at its output equal to, then this indicates that the code of the number is identically equal to zero modulo. At the same time, this pulse, the passage through the element OR 8, goes to the zero input of register 9 and to the second input of the element OR 5. As a result, you

five

20

25

d

thirty

35

40

45

50

five

In the course of 19 Ustrons, a pulse appears. End of the calculation, and at exit 20 a code of zero appears. If a pulse appears at the output of Less Comparison 12, then this also indicates that the Lormation of the residue is complete. This pulse through the element OR 6 is fed to the first control input of the multiplexer I8 and through the element OR 7 to the input of the recording resolution of the register 9. As a result, the output of the multiplexer 18 is switched to its third input and to the register 9 the code of the output from the remainder 13 is described. At the same time, at the output 19, an impulse End of scaling appears, and at the outputs 20 - the code of the remainder of the number by mod. If, on the other hand, the impulse in accordance with the output of the More Comparison Scheme, then this indicates that the Formation of the remainder has not yet been completed. This pulse goes through the element OR 6 to the first control input of the multiplexer 18, switches its output to its third input, and also goes to the second input of the element OR 4. At the same time, the operation of the device is repeated. However, the register 10 does not write the code of the number Ak, but the code MHCJV, from the output of the subtractor 13, affecting the information input of the register 10 through the multiplexer 18. The process of forming the modulo of the number continues until the outputs of the adder I5 or the subtractor 13 does not show a number less than or equal to the modulus, which will be numerically equal to the remainder of the number A modulo P :.

Claims (1)

Invention Formula A device for forming the remainder in an arbitrary modulus of a number containing the first and second registers, the first and second elements OR, the subtraction, the first comparison circuit and the multiplexer, with the input of the module of the device connected to the input of the readable subtractor and the first information input of the first comparison circuit, the input The commencement of the device calculation is connected to the first input of the first OR element, the output of the second element OR is connected to the output of the device Calculation end, the output of the first register is the output of the device result, in the course of the device number is connected with the first information input of the multiplexer, the output of which is connected to the information input of the first register, the first and second inputs of the second OR element are connected respectively to the write enable and reset inputs of the first register, characterized in that, in order to improve performance, by the fifth OR elements, the delay element, the adder, the group of AND blocks, the permanent memory block and the second comparison circuit, the multiplexer output is connected to the information input of the second register, the output bits The ports of which are connected to the first inputs of the corresponding blocks of elements AND groups, the outputs of which are connected to the inputs of the corresponding adders, the output of which is connected to the second information input of the first comparison circuit, the input of the decremented subtractor and the second information input of the multiplexer, the first and second control inputs of which connected respectively with the output of the third OR element and with the combined output of Less than the first comparison circuit and the first input of the fourth OR element, the input of the device module connected to the first data input of the second circuit Editor H, .Lazarenko ----- --- --- Compiled by A. Klyuev Tehred L. Oliynyk Order 622 Circulation 455 VNIIPI State Committee for Inventions and Discoveries at the State Committee on Science and Technology of the USSR 111035, Moscow, Zh-35, 4/5 Raushsk nab. Q from 5 0 comparison and the address input of the fixed memory block, the output of the group of which is connected to the second inputs of the corresponding blocks of elements AND group, the output of the reader is connected to the second information input of the second comparison circuit and the third information input of the multiplexer, the enable input of the memory block is connected to the output The first OR element, the recording resolution input of the second register and the input of the delay element, the output More of the second comparison circuit is connected to the first input of the third OR element and the second input of the second OR circuit, the output is equal to the second input of the fifth OR element, the output is less than the second comparison circuit connected to the second input of the third OR element and the second input of the fourth OR element, the output of which is connected to the first input of the second OR element, the second input connected to the output of the fifth OR element, the second input of which is connected to the output Equal to the first comparison circuit, the output More than which is connected to the resolution input of the second comparison circuit, the resolution input of the first comparison circuit En with the release of the delay element. Proofreader S.Shevkun Subscription