SU1120325A1 - Arithmetic modulo n unit - Google Patents

Abstract

1. ARISMETIC DEVICE. HU MODULE containing the first modular adder, modular subtractor, first and second quadrants, with the inputs of the first and second quadrants connected respectively to the outputs of the first modular adder and modular subtractor, whose inputs are respectively combined and are: the inputs of the first and second operands of the device, respectively t it is due to the fact that, in order to expand the functionality by performing the device operations of addition and addition, it contains the first, second and third switches, The OR element, the second and third modular adders, the first outputs of the first and second quadrants are connected respectively to the first and second inputs of the second modular adder, the output of which is the output of the higher-order result (H, module) arithmetic unit, input the transfer of the second modular adder is connected to the transfer output of the third modular adder and is the transfer output of the arithmetic unit; the first information inputs of the first and second switches are connected respectively directly to the inputs of the first and second operands of the arithmetic unit, the second information inputs of the first and second KOMNryTaTopoB are connected respectively to the second outputs of the first and second quadrants, the outputs of the first and second switches are connected respectively to the first and second inputs of the third modular / summator, the output of which is connected to the first switch the information input of the cracked switch, the second information input of which is connected to the output of the modular subtractor, and the output is the output of the younger "- primary the result of the arithmetic unit, the first and second control inputs of the first and second and 00 switches, respectively, are combined, connected to the inputs of the IW9 SP element, and are the inputs of the Multiply and Addition operations (| of the practical device, the output of the OR element is connected to the first the control input of the third switch, the second control input of which is an input of operations; Addition of the arithmetic unit. 2. The device according to claim 1, wherein the second modular adder comprises the first and second groups of rm adders on the bases of the residual system

Description

classes, a group of n commutators and a NOT element, and the corresponding inputs. The inputs JX (j 1j2, ...., n) are the sum MaropqB of the first and second groups are pairwise united and are correspondingly the first and second inputs of the second modular adder, the outputs of the JX adders the first and second groups are connected respectively to the first and second information inputs jx of switches To the groups whose outputs are the output of the second modular adder, the first I and second control inputs of the switches of the group are respectively combined and connected respectively to the output element NOT and the transfer input of the second modular imatmator, to which the input element is NOT.

3. The device according to claim 1, wherein the third modular adder contains a group of h adders on the basis of the residual class system, an additional siesi on the first basis of the residual class system, a switch, a zero-storage unit, a null-adder, two the OR element, the first and second inputs of the group adders being the first and second inputs of the third modular sum, respectively.

20325

the torus, the first and second inputs of the additional adder on the first base of the residual class system are connected to the corresponding inputs of the first cyi-iMaTopa group, the output of the additional adder is connected to the first information input of the switch, the second information input of which is combined with the first input of the zero accumulator and connected to the output of the first adder the groups, the switch outputs and the B-x (B 2 J .... h) of the group adders are the output of the third modular adder, the inputs of the storage unit of the constant constants are connected respectively to the In-vpsodam hsummatorov group output constants nulevizatsii storage unit connected to the second input of the adder nulevizatsii group

(1 О, рт-1, Рт-2, +1) the outputs of which are connected to the corresponding input - the first element OR, the group t - x (1.2 ,, .., р / 2) outputs from the zero-output mmator is connected to the corresponding inputs of the second OR element, the output of the first and second OR elements are connected respectively to the first 4 and second inputs of the switch, the output of the second OR element is the transfer output of the third modular sump,

The invention relates to computing and can be used in the construction of computers of high speed,

An arithmetic unit in the system of residual classes is known, containing registers of the first and second operands, registers of control codes of the first and second operands, a block of modular adders, three adders, three blocks of permanent memory, a multiplication unit, three groups of elementoB, and a control unit and the corresponding link ziO o The disadvantages of this device are a large amount of equipment and low speed, due to the elephantiness of the control algorithm.

Closest to the invention is an arithmetic unit modulo containing a modular adder, first and second modular subtractors, first and second quadrants, a division unit by a constant, the output of which is the output of the device, and the input connected to the output of the second modular subtractor whose inputs are connected to the outputs of the first and second quadrants respectively, the inputs of the KOTopioc are connected respectively to the outputs of the modular adder and the first modular subtractor, whose inputs are respectively combined and are The inputs of the device operands 2.

A disadvantage of the known arithmetic unit is its limited functionality. 31 The aim of the invention is to extend the functionality by performing additional addition and addition operations on the device. The goal is achieved by the arithmetic unit of a module containing the first modular adder, modular subtractor, first and second quadrants, the inputs of the first and second quadrants connected to the outputs of the first modular adder and modular subtractor, whose inputs are respectively combined and are inputs, respectively, of the first and second operands of the device, contains the first, second and third switches, the element OR, the second and third modular adders, the first outputs of the first O and the second quadrants / are connected respectively to the first and second inputs of the second modular adder, the output of which is the output of the highest e, -ary result of the result (, module) of the arithmetic unit, the transfer input of the second modular adder is connected to the transfer output of the third modular adder and is the output of the transfer arithmetic

the first information inputs of the first and second switches are connected respectively to the inputs of the first and second operands of the arithmetic device; the second information inputs of the first and second switches are connected respectively to the second outputs of the first and second quadrants; the outputs of the first and second switches are connected to the first and second inputs respectively The third modular adder whose output is connected to the first information input of the third switch, the second information input which is connected to the output of the modular detractor, and the output is the output of the lower c}, the minor bit of the result of the arithmetic unit, the first and second control inputs of the first and second switches are respectively combined, connected to the first and second inputs of the OR element, respectively, and are inputs of operations Multiplication and Computational arithmetic unit, the output of the element OR is connected to the first control input of the third communclass, the switch, the storage unit of the nullification constants, zeroing adder, two while the first and second inputs of the group adders are the first and second inputs of the third modular adder, the first and second inputs of the additional adder on the first base of the residual classes system are connected to the corresponding inputs of the first group ad, the output of the additional adder is connected to the primary the information input of the switch, the second information input of which is combined with the first input of the zeroing adder and connected to the output of the first group adder, the outputs of the comm Ator and Bx (B 2, ..., p) adders of the group are the output of the third modular adder, the inputs of the storage unit of the nullification constants are connected respectively to the outputs of the Bx adders of the group, the output of the storage unit of the nullification constants is connected to the second input of the zeroing adder , a group of k-x (X O, p, -1, p -2, ..., p / 2 + 1) outputs of which are connected to the corresponding controller, the second control input of which is the input of the operation Addition of the arithmetic unit. In this case, the second modular adder contains two groups of adders on the bases of the system of residual classes, a group of n commutators and the element NOT, and the corresponding inputs j -X (J 1, 2p) of the adders of the first and second groups are pairwise combined and are respectively the first and the second inputs of the second modular adder, the outputs jx of the adders of the first second group are connected respectively to the first and second information inputs jx of the switches to the B group, the outputs of which are the code of the second modular adder, the first and second control inputs of the group of switches respectively coupled and connected respectively to the output of NOT circuit and the input of the second module transferring the adder connected to the input of NOT. In addition, the third modular adder contains a group of n adders, on the bases of the system of residual classes, an additional adder on the first base of the system of residual 511 inputs of the first element OR group-X (L 1,2 ,, ..,) of the outputs of the null elimination is connected to the corresponding inputs of the second OR element, the outputs of the first and second OR elements are connected respectively to the first and second inputs of the switch, the output of the second OR element is the transfer output of the third modular adder. FIG. 1 is a block diagram of an arithmetic unit modulo; FIGS. 2 and 3 are functional diagrams of the second and third modular adders, respectively. The device contains the first module of the new adder 1, the modular subtractor 2, the first 3 and the second 4 quad, the first 5 and the second 6 switches, the second 7 and the third 8 modular adders, the third switch 9 and the element OR 10. The second modular adder 7 contains the first 11 and second 12 groups of adders, switch groups 13 and the NOT 14 element, and the third modular cooler 8 — a group of adders 15, an additional adder 16, a switch 17, a nullization constant storage unit 18, a nulling adder 19, and OR elements 20 and 21. The basis of the arithmetic device p the module is supposed to be a representation of each operand in the code of the system of residual classes of SOCs from the set of h bases p such that 24, P., H ,, ci, -., lB ((b, ft, ..., b ,, where 5 /., / 3; is the smallest non-negative deduction of the numbers A and B on the base of P.; When adding operands A and B lying in the range of c, the result 5 can reach the value of the fact Overflow with P 2 is detected by zeroization, in the course of which and the result of the summation, such constants are subtracted so that the result is either O or c. If the result of zeroization is O, then 5 C, P 0. If the result of zeroization is 1, then S С-, П 1. Subtraction with is equivalent to changing the value of the deduction on the basis of P-2 to the opposite (C sum, P -), 5. At P 2, the zero point is carried out on the basis of m p. p, and the fact of overflow is determined by deducting the base P. This leads to a significant increase in speed. To increase the speed, zeroing is carried out in one step at once on all bases, except the first. At the same time, the storage unit for constant null-ing has p. p, - .. p words. The subtraction operation in this device is accomplished as an addition. the direct code of the first operand and the additional code of the second operand applied to the inputs of the first and second operands of the device. The modular adders 1, 11, and 15 form the sum of the operands arriving at them along the bases of the SOC, and the modular subtractor 2 and the adder 19 nullify the difference between the operands arriving at them along the bases of the SOC. Modular adders 12 and 16 form the values of the amounts reduced by a for the corresponding base. The zeroing adder 19 operates at the base p, the result, represented in code 1 of p, comes from its output to the elements OR 20 and 21 to form the transfer. The null constant storage unit 18 represents a fixed memory containing minimum nuization numbers. All modular adders and subtractors can be performed with combinational 3J. The operation of cutting in the proposed device is performed by the formula. () four . 4 The advantage of this formula is that it does not require a quadratic range to represent the product. . We introduce the following notation: С А + В, d А -В, As a result of squaring and dividing by 4, we have, 0, Is, -,) g (s, g,).% Where C and s3 are the highest c-digit bits squared.c, C, and d are the lower c-primary bits of squares. Arithmetic unit modulo works as follows. One of the control inputs to the switches 5.6 or 9 is given a signal corresponding to the operation performed by the device: Multiplication, Addition or Addition. Then, the initial numbers A and B, in the form of binary deduction codes on the basis of the SOC, are fed to the inputs of the first modular adder 1 and the modular subtractor, which form their sum and difference, respectively. When performing the operation Supplement (-), the result of the subtraction from the modular subtractor 2 is fed to the second information input of the third switch 9, which is open at the second control input, and the exit code is removed from the output. The output of the second modular accumulator 7 and output of the third modular The adder 8 is not polled. When performing the operation. Adding (+) to the second control inputs opens the second 5 and third 6 switches and the first control input through the ISh 10 element opens the third switch 9. Operands through The first information inputs. The first and second 6 switches arrive at the input of the third modular adder 8, from which output the result goes to the first information input of the third switch 9, the output of which removes the result of the addition. The transfer signal is removed from the transfer output of the third modular adder 8. The output of the second modular adder 7 is not polled. When executing the multiplication operation (x) by nepBbW, the first 5 and second 6 switches are opened by the control inputs and the third switch 9 is opened via the first control input through the OR 10 elements 9. Operands received at the inputs of the first modular sum of matrix 1 and modular subtractor 2 in the form of + V, is fed to the inputs of the first 3 and second 4 quadrants, respectively, at the output of which the results appear in the form of, Cp, d and Ed. The values of e d. arrive at the second modular adder 7, the values of C and 5 through the first 5 and second 6 switches to the inputs of the third modular adder 8, which forms the lower C, is the first discharge of the product with a weight of °, which, having passed the third switch 9, appears the output of the latter. At the same time, the third adder 8 generates a transfer signal, which goes to the device’s output and the second modular adder’s output. 7. If P O, then the output through the switches 13 is the result of the summation C and d from the adders 1 1. If P 1, then the output through the switches 13 receives the result C + 5., + 1 from the outputs of the adders 12. The result at the output of the second modular adder 7 is the highest-order partial-output. During the operation Multiply, the output of the transfer of the third modular adder 8 is not polled. The proposed arithmetic unit modulo can be used simply as an arithmetic unit in the system of residual classes, if all three operations are polled, only the output of the third switch 9 is polled. Thus, the proposed unit arithmetic unit modulo only limestone, which performs only one modular operation multiplication, performs addition and subtraction in the system of residual classes, addition and multiplication of a-ary numerals. computes the additional code of the second operand, i.e. performs instead of one six different operations.

 / 7

Phi.1

Pe / H o ffjTOff

 Sjtoff

. ,, ..

f dfTfopoi jco

f-n

//

/ /

/ 7

I. I Imr - .. i4.

/

/

Nti

/ f

/ - / 7- /;

a

Si)

2.J

Claims (3)

1. ARITHMETIC DEVICE. MODULE, containing the first modular adder, modular subtractor, 'first and second quadrators, and the inputs of the first and second quadrators are connected respectively to the outputs of the first modular adder and modular subtractor, the inputs of which are respectively combined and are inputs of the first and second operands of the device, respectively, which, in order to expand the functionality by performing addition and addition operations on the device, it contains the first, second, and third switches, an element OR, the second and third modular adders, with the first outputs of the first and second quadrators connected respectively to the first and second inputs of the second modular adder, the output of which is the output of the highest-level digit of the result (q, is the module) of the arithmetic device, the transfer input of the second modular the adder is connected to the transfer output of the third modular adder and is the transfer output of the arithmetic device, the first information inputs of the first and second switches are connected respectively to the input the first and second operands of the arithmetic device, the second information inputs of the first and second switches are connected respectively to the second outputs of the first and second quadrants, the outputs of the first and second switches are connected respectively to the first and second inputs of the third modular / adder, the output of which is connected to the first information input of the third switch , the second information input of which is connected to the output of the modular subtracter, and the output is the output of the lower q, -ary discharge of the result ar device, the first and second control inputs of the first and second switches are respectively combined, connected to the inputs of the OR element and are inputs of the operations Multiplication and Addition of the arithmetic device, the output of the OR element is connected to the first control input of the third switch, the second control input of which is the input of operations Arithmetic addition devices. 2. The device according to π. 1, the second modular adder containing the first and second groups of rm adders on the bases of the system of residual classes, a group of η commutators and an element NOT, with the corresponding inputs j -x (j = 1,2, ... ., ^) the adders of the first and second groups are combined in pairs and are respectively the first and second inputs of the second modular adder, the outputs jx of the adders of the first and second groups are connected respectively to the first and second information inputs jx of the B switches of the group, the outputs of which are the outputs of the second modular . the adder, the first AND second control inputs of the group switches are respectively combined and connected respectively to the output of the NOT element and the transfer input of the second modular • adder to which the input of the NOT element is connected. 3. The device according to p. ^ Characterized in that the third modular adder contains a group of η adders on the bases of the system of residual classes, an additional suv ^ aTor on the first base of the system of residual classes, a commutator, a block of storing constant zeroing, an adder of zeroing, two elements OR, the first and second inputs of the adders of the group are respectively the first and second inputs of the third modular sum 1120325 torus, the first and second inputs of the additional adder on the first base of the system of residual classes are connected to the corresponding inputs of the first adder of the group, the output of the additional adder is connected to the first information input of the switch, the second information input of which is combined with the first input of the zeroing adder and connected to the output of the first adder of the group, the outputs of the switch and Bx (B = 2, .. .. k) the group adders are the output of the third modular adder, the inputs of the storage unit of the zeroing constants are connected respectively to the outputs of the B-adders of the group, the output of the storage unit of the zeroing constants is connected to the second the input of the nullization adder, group 1 <-x (k = 0, ρ, -1, ρ, -2, Ρ _{ί / 2} +1) of the outputs of which is connected to the corresponding inputs of the first OR element, group gx (6 = 1 , 2 ..... / 2) the outputs of the zeroing adder are connected to the corresponding inputs of the second OR element, the outputs of the first and second · OR elements are connected respectively to the first and second inputs of the switch, the output of the second OR element is the transfer output of the third modular adder. ·