SU1188731A1 - Device for adding n-digit numbers in redundant number system - Google Patents

Abstract

1. DEVICE FOR ADDITIONAL / r-DISCHARGE NUMBERS IN AN EXCESSABLE CALCULATION SYSTEM, containing n summation blocks, the inputs of the first and second operands of which are the first and second inputs of the corresponding device bits, and the outputs of the device bits outputs, characterized in that in order to increase speed, it additionally contains a modulo-two adder, and each summing block contains a transfer signal generator and m modulo PJ adders (where, 1,2, ..., t; t are the number of bases of the residual classes system), each the first of which contains the first and second binary code decoders into the code one of P, the modulo matrix adder, the first and second groups of OR elements, and six groups of AND elements, and in each j-modulator adder P the inputs of the first and second decipherors are connected to the inputs of the first and second operands / -and groups of this summing block, and the outputs are connected respectively to the first and second inputs of the matrix modulo adder, the first output of which is connected to the first inputs of the first element And the first group, the second element And ory of the group, the element And the third group, each / -and the output of the matrix adder modulo, where, 3, ..., (Pj-1), is connected to the first inputs of the / -H element of the And group of the first, (/ 4-1) th element of the second group and ll-1) -th element of the third group, and P; -th output is connected to the first inputs of the P, -th element And the first group, the first element And the second group and (R / - 1) - the third element of the third group, the outputs of the elements of the first, second and third groups are connected respectively to the first, second and third inputs of the corresponding elements OR of the first group, the output of the first el OR of the first group is connected to the first inputs of the first element AND the fourth group, the second element AND the fifth group and the Pj-ro element AND the sixth group, the output of each 1st element OR the first group is connected to the first inputs of the / -th element AND the fourth group ( i + l) -ro of the element And the fifth group and the (i-1) -th element of the sixth group, the output of the P-th element OR of the first group is connected to the first inputs of the Ru-go element (Lment And the fourth group, the first element And the fifth group and (P / -1) -th element And the sixth group, the outputs of the elements And the fourth, fifth and sixth groups p are connected respectively to the first, second and third inputs of the corresponding elements OR of the second group, the second inputs of the elements AND the fourth groups of all adders modulo PI of this summing unit are connected to the output of zero transfer of the previous summing unit of the device, the second inputs of the elements And fifth groups of all adders modulo P, - this totaling block is connected to the output of the positive transfer of the previous summing block of the device, and the second inputs of elements of the sixth groups are connected to the output the negative transfer of the previous summing unit of the device, the inputs of the transfer signal generator, from the first to k, where K is connected to the corresponding outputs of matrix adders modulo all the adders modulo P of this summing block, the first output of the transfer Lob transfer signal generator is connected the negative transfer input of the next summing

Description

device block and the second inputs of elements And the third groups of all adders modulo PI of this summing block, the second output of the transfer signal generator is connected to the zero carry input of the next summing block of the device and the second inputs of elements And the first groups of all adders modulo Pj of this summing block, and the third output is connected to the input of the positive transfer of the next summing block of the device and the second inputs of the elements And the second groups of all adders modulo Pj of this summing block a, the outputs of the elements OR of the second group of each / -th adder modulo PI are connected to the output of the sum over the / -th base of the system of residual classes of this summing unit, the outputs of negative and positive transfers of the nth summing block are connected to the first and second inputs of the modulo adder two, third and fourth inputs of which are connected to the first and second inputs of the device characters, and the output is connected to the device's output.

2. The device according to claim 1, characterized in that the transfer signal generator contains the first and second decipherors of the code of the system of residual classes in the code "One of / (where), the first and the second

a swarm of the OR elements, the first and second elements are NOT and the AND element, with the inputs of the first and second decipher, from the first to the kth (where), are connected to the corresponding inputs of the transfer signal generator, and the outputs are connected respectively to the inputs of the first and second elements OR, the outputs of which are connected respectively to the first and third outputs of the transfer signal generator and to the inputs of the first and second elements NOT, the outputs of which are connected to the inputs of the element C whose output is connected to the second output of the signal generator perennial sa.

one

The invention relates to computing and can be used in specialized computers.

The purpose of the invention is to increase the speed of the device.

FIG. 1 shows a block diagram of a device for adding " -digit numbers in a redundant numbering system; FIG. 2 is a block diagram of a summing block; in fig. 3 is a block diagram of a transfer signal former; in fig. 4 is a block diagram of an adder modulo two.

The device contains n summing blocks 1, the inputs of which are connected to the corresponding bits of the first and second inputs of the device, and the adder 2 modulo two, the first and second inputs of which are connected to the inputs of the device characters, the outputs of the summing blocks are connected to the outputs of the bits of the device, the output of the adder modulo two connected to the output of the device sign.

Each summing block 1 contains m adders 3 modulo P / (where, 2, ... gp; m is the number of bases of the residual class system (SOC) and driver and transfer signals. Each adder modulo P; contains decipherors 5 and 6 of the binary code in the code “One of P ;, matrix adder 7 modulo, group of elements AND 8-13 and group of elements OR 14 and 15. Shaper 4 transfer signals contain descramblers 16 and 17 of the SOC code into the code One of R (where, elements OR

18 and 19, the elements are NOT 20 and 21, and the element is AND 22.

The adder 2 modulo two contains the elements NOT 23-25, the element OR 26, the elements AND 27-30 and the element OR 31.

Let m base Pj SOK be selected:

R I№j,

as the base of the redundant number system, one can accept the value: r R / 2-4

then the valid digits in this number system will be

Wi: -r / 2, - (g / 2-1), ..., -2 -1, 0,1,2, ..., r / 2-l, g / 2;

Let us denote the operands by x and y, and their sum by s. Their values can take the following values.

S.-, X; yt :-( T / 2 + 1), -G / 2, (g / 2-1), ...,

-2, -1,0,1,2, ..., g / 2-1, g / 2, g / 2 + 1.

In the following, negative values of digits will be denoted by a dash above the corresponding digit.

Taking into account the introduced notation, we can write down:

W, - (X; + y /) - rt; l + ti,

where with Wm, + Y.- WmaA-; t; - | 1 at Xi + yi Wmax; t ;. HID

Example. Choose a base system JUICE Pj 3; , P2Pz 60; . DETAILED MEASURES J W;; 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2,1, O,

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13;

S ,, X, -, y, -: And, GZ, f2, P, Go, 9, 8, 7, 6, 5, 4, 3, 2, T,

O, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14; Let the terms X and Y and their sum S in the r-ary number system be:

S +0 I. 24; 20; 18; eight

In the redundant g-ary number system, operands and sum are of the form:

The process of obtaining the sum is performed in two stages: first, an intermediate sum W and a carry vector t are formed, then the value of the sum is determined.

In this device, the values (s-1), S, and (s-f-1) are formed in each summing block 1 using groups of 11 -13 I.

At the control inputs, the elements of one of these groups are opened with the control signals -1 and O, arriving at them from the output of the transfer signal generator 4 of the lower order. Thus, the process of summing W + t is replaced by the process of selecting one of the three values of sum (s-1), s or (s + 1) and transmitting it through the elements of OR groups 15 to the output of the corresponding bit. The value of the sum of the outputs of the matrix adder 7 in the code

“One of the PN enters the inputs of the decoders 16 and 17 of the driver 4 transfer signals. Decoders are a collection of g / 2 elements AND per m inputs, Decipher 16 decrypts numbers in the range from 1 to g / 2 and using the OR element 18 generates the Negative Transfer (-1) signal, the decoder 17 decrypts numbers in the range from Zg / 4 to R-2 and with the help of the element OR 19 forms the signal “Positive transfer (+1). The signal "Zero transfer (0) is formed in the absence of signals (-1) and (-1-1).

The coding of g-ary numbers using the code JUICE is used to improve the speed of summing blocks 1, so

 as adders 3 for individual bases, the CRS can be small-sized, tabulated and working in parallel. No transfer between separate base adders Pi

0 makes it possible to perform the addition of r-ary numbers in one clock cycle. An artificial form is used to represent the r-th digits of the JUICE codes when the R / 2 value is used as the zero.

5 Positive g-ary numbers are encoded as:

+ x R / 2 + x (x60, g / 2 + 1),

negative g-ary digits are encoded as:

-xR / 2-x, (--x6- (r / 2-f 1), 0).

It is known that the sum.um of two numbers of JUICE in artificial form is obtained in two cycles: the first clock is the summation, the second clock is the correction of the result by the value of the constant R / 2.

Let the source operands in the redundant r-ary number system be the same as in the considered example, namely:

10 6

8 10 8 14

at 0

We encode each r-ary digit with the code of SOCs based on Pi 3; in artificial form and perform addition:

3,4,53,4,5 3,4,5 3,4,5

to;

(2.0.0) (0.0.1) (2.2.3)

 (1,0,3) (2,2,0) (1,1,4) (0,0,2) 50S-I-20 The result is the same as in the previous example. Moreover, this result is formed at the output of matrix adders: 7 In order not to perform the operation of calculating the constant R / 2, having a significant figure only on an even basis (in our case), it is advisable to perform the base adder 3 so that it produces a result with an offset of - (R / 2) p2 Structurally, this is done when constructing the matrix adder 7. Now using the elements AND groups 8-10, at the inputs of which the number w is represented in the code "One of P /, receive values (w-br); w; (w-d), which is equivalent to (w + 26) w and (w-26), since the unit of transfer in the preceding bit is equivalent to the value of the younger category: 3,4,5 3,4,5 3,4,5 3,4,5

(0,2,4) (1,0,1) (0,3,0) (2,2,3)

(1,0.3) (2,2,0) (1,1,4) (0,0,2) w 1 (2,2,2) (0,0,4) (2,3,3 ) (1,2,1)

guise w.

As a result, the sum at the output of the device has the form: groups of elements AND in the corresponding g-ary bits of the summing blocks 1: 9, 10, 10, 8. Modulator 2 modulo two in the sign bit gives the value 1. At the output of the elements OR of group 14 the number is: 3,4,5 3,4,5 3,4,5 I (1,0,3) (0,0,4) (2,3,3) (2,2,3) 38s8 V according to the carry signals from the lower order bits (1 1 1 9), in the upper g-ary bits of the summing blocks 1, the elements of the following groups open, 13, 13, 11, 12. The value passes through the elements of the groups 13 (w + 1 / through elements And groups 11 - value (w - 1), che And groups of 12 elements - in each g veOdnovremenno-ary discharge via signal transfer shaper 4 formed transfer signals that are received on the second inputs of the AND Groups 8-10 respectively:

t 0 | 1 1 1 О

Thus, the following signals are opened by the own carry signals.

3,4,5

3,4,5 (TAR

1 (2,1,4) 29 and On the elements of the OR groups of 15, the g-ary bit of the result for each of the bases is represented by a binary code in the artificial form of the SOC.

and / 4 4

I f

jrN /:

sixteen

18

v

Pm

eleven

nineteen

V

- /

0 fig. 3

V

+ /

u

v

: uh

Claims (2)

1. DEVICE FOR ADDING "-DIGITAL NUMBERS IN A REDUNDANT NUMERICAL SYSTEM, containing" summing blocks, the inputs of the first and second operands of which are the first and second inputs of the corresponding bits of the device, and the outputs are the outputs of the bits of the device, characterized in that, in order to improve performance , it additionally contains an adder modulo two, and each summing unit contains a shaper of transfer signals and m adders modulo Pi (where _; = 1,2, ..., "r;" r is the number of bases of the system of residual classes), each the first of which contains the first and second binary code decoders one of P, the matrix adder modulo the first and second groups of OR elements and six groups of AND elements, and in each jth adder modulo P the inputs of the first and second decoders are connected to the inputs of the first and second operands of the / group of this summing unit, and the outputs are connected respectively to the first and second inputs of the matrix adder modulo, the first output of which is connected to the first inputs of the first element And the first group, the second element And the second load pp, Pj-ro of the element AND of the third group, each / -th output of the matrix adder modulo, where / = 2,3, ..., (Pj-1), is connected to the first inputs of the / -th element AND of the first group, ( / + 1) of the element AND of the second group and the [I – 1) of the element AND of the third group, and The Pj-th output is connected to the first inputs of the Pj-ro element And the first group, the first element And the second group and the (Pj - 1) -th element And the third group, the outputs of the elements And the first, second and third groups are connected respectively to the first, second and by the third inputs of the corresponding OR elements of the first group, the output of the first OR element of the first group is connected to the first inputs of the first AND element of the fourth group, the second AND element of the fifth group and Pj-ro of the AND element of the sixth group, the output of each / th OR element of the first group is connected to the first inputs of the / th element and the fourth group of the (i + 1) -th element of the fifth group and the (i-1) -th element of the sixth group, the output of the Pth element OR of the first corpse is connected to the first inputs of the Pj-ro element of the fourth group , the first AND element of the fifth group and the (Pj — 1) -th element AND the sixth group, the outputs of the AND elements of the fourth, fifth and sixth groups are connected respectively to the first, second and third inputs of the corresponding OR elements of the second group, the second inputs of the AND elements of the fourth groups of all adders modulo Pj of this summing block are connected to the output of the zero the input of the previous summing unit of the device, the second inputs of the elements AND of the fifth groups of all adders modulo P of this summing block are connected to the positive transfer output of the previous summing unit of the device, and the second inputs of the elements of the sixth groups are connected to the negative transfer output of the previous summing unit of the device, inputs of the shaper transfer signals, from the first to k = -th, where k = P, are connected to the corresponding outputs of the matrix adders modulo all adders modulo P of this summing of the first block, the first output of the transfer signal generator is connected to the negative transfer input of the next summing unit of the device and the second inputs of the elements And of the third groups of all adders modulo Pj of this totalizing block, the second output of the transfer signal generator is connected to the zero transfer input of the next summing device block and the second inputs of the elements And the first groups of all adders modulo Pi of this summing block, and the third output is connected to the input of the positive transfer of the next sum unit of the device and the second inputs of the elements AND the second groups of all adders modulo Pj of the given summing block, the outputs of the OR elements of the second group of each / th adder modulo Pj are connected to the output of the sum on the / th base of the system of residual classes of this summing block, the outputs are negative and positive transfers of the nth summing unit are connected to the first and second inputs of the adder modulo two, the third and fourth inputs of which are connected to the first and second inputs of the signs of the device, and the output - with the output of the sign triplets. 2. The device according to π. 1, characterized in that the shaper transfer signals contains the first and second code decoders of the system of residual classes in the code "One of /?" (where R = n /? /), the first and second elements of OR, the first and second elements of NOT and the element And, and the inputs of the first and second ^ decoder, from first to kth (where "= ΣΡ /), are connected to the corresponding the inputs of the shaper of the transfer signals, and the outputs are connected respectively to the inputs of the first and second elements OR, the outputs of which are connected respectively with the first and third outputs of the shaper of the signals of the transfer and with the inputs of the first and second elements NOT, the outputs of which are connected to the inputs of the element And, the output of which is connected to the second exit formiro carrier of transfer signals.