JPH03228122A - Addition circuit - Google Patents

Abstract

PURPOSE: To provide a high-speed and easily realizable addition circuit with a relatively less gate using amount by allowing an adder to have the serial connection constitution of cells for generating intermediate carry signals. CONSTITUTION: Respective blocks are provided with the 2-4 pieces of 1-bit cells. In such blocks, two ripple carry outputs Cout0 (i) and Cout1 (i) are generated. In the start cells of the respective blocks, carry inputs Cin0 and Cin1 are respectively defined as '0' and '1'. The two carry outputs Cout generate the carry output Cout block (j) of the block at, present by being combined with a carry input Cin block (j) inputted to the block at present. Then, the chaining of the two carries (Cout0-Cin0 and Cout1-Cin1) are simultaneously and successively propagated in all the blocks. In this case, the intermediate carry signals of respective bit pairs are independently and successively propagated through continuous stages. Thus, this high-speed addition circuit is obtained with the relatively less gate amount.

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to carry in digital adders and the like, and particularly to a high-speed carry method that greatly reduces carry propagation delay with a relatively small amount of gate usage.

Adding two N-bit operands to obtain an N-bit result (often referred to as carry propagation addition) is a fundamental operation in digital processors. Various carry schemes have been used in the past to perform this operation.

A so-called ripple adder may be used to easily perform carry propagation addition. Ripple adders require relatively few transistors per bit, but are relatively slow - for boat fishing. The ripple adder is thus a basic but slow adder that is often used as a standard for measuring the performance of other adders.

FIG. 1 is a diagram showing a typical ripple adder cell. In FIG. 1, A(1) and B(i)+ are the bits of each of the two operands being added, and C
1n(i) is the carry input from the previous stage ripple adder cell, Cout (i) is the carry output from this ripple adder cell, and D(
1) is the sum of this ripple adder cell.

The carry output of one ripple adder cell becomes the carry input of the next stage ripple adder cell. Table IK
A program written in a PASCAL-like language illustrates the logical operation of an N-bit ripple adder. In the program shown in Table 1, "+" indicates a logical sum, "." indicates a logical product, and l'-XORJ indicates an exclusive logical sum.

or Table 1 i = Oto N-I DOBEGINK(i)
= Aii) + B(i)G(1)2A(1)・
B(g) P(i) = A(i) XORB(i) Cout(i)
=G(i) + (K(i) −C1n(i))
=Cin (i + I) D(i) = P(i) XORC1n(i)nd The ripple adder can be made faster by adding a carry lookahead circuit. To implement a carry look-ahead adder, the ripple adder is, for example, four 9
It consists of blocks consisting of sopul adda cells. Each block of the four high-speed adders has an additional gate K as shown in FIG.
l'', the carry output from the previous block passes through this block and is propagated to the next block.

The carry look-ahead adder is relatively fast and can be constructed inexpensively with MO3 circuits.

As another method, 1. R, E, Transactions
On Electronic Computers (1, R,
E, Transact 1ons on Ele
ctronic Com fourters) magazine June 1960
Monthly issue, page 226, 5klansk
There is a conditional phase adder announced by Mr.

Although conditional sum addition operates at very high speed, it requires significantly more processing than the relatively slow addition described above. As a result, conditional phase addition becomes very expensive per bit. In fact, this method is not widely used.

As mentioned above, various carry schemes have been used in the past to perform carry propagation addition.

However, these known schemes were often too slow for new generations of computers, or were much more complex and expensive than expected.

SUMMARY OF THE INVENTION It is an object of the present invention to eliminate the drawbacks of the above-mentioned conventional methods and to provide a high-speed carry method for conditional carry addition that is fast and easy to implement.

The adder to which the present invention is applied has a structure in which cells that generate intermediate carry signals are connected in series. Therefore, the intermediate carry signal of each of these bit pairs can propagate independently through successive stages one after the other. Therefore, according to the present invention, the delay time of the full adder can be reduced compared to the known example, and the complexity of the circuit can be kept relatively low.

The invention is also applicable to incrementor priority encoders. Examples of these applications are also discussed below.

Since the fast carry scheme of the present invention requires relatively few types of cells, they can be easily combined in a regular manner as shown below when constructing an adder, incrementer, or priority encoder of arbitrary length. be able to. Therefore, according to the present invention, it is possible to realize a circuit with a high absolute speed, and even when an LSI is manufactured using either bipolar or MO3 technology, it can be constructed at low cost by suppressing design complexity. .

Hereinafter, the present invention will be explained in detail with reference to the drawings.

In the following, two adders A, B are disclosed that use the fast carry scheme of the present invention to perform carry propagation addition, referred to as conditional carry addition. It will be understood from the following explanation that the configurations of these two adders A and B can be applied not only to adders but also to incrementers and priority encoders. Table 2 shows a comparison between a known scheme and a conditional carry adder using the present invention. In Table 2, the speed of the adder is indicated by the number of gate delay stages required to perform the full addition. The data shown in Table 2 is for a 32-bit adder.

3A and 3B are diagrams showing a conditional carry adder A according to a first embodiment of the present invention, and Table 3 shows logical expressions related to the conditional carry adder A. Figure 3A shows 3
Cells of different species are shown. They are a start cell, an arbitrary number (even zero) of continuation cells, and an end cell.
It is a cell.

FIG. 3B is a diagram showing an example of a cell configuration in the case of a 9-bit adder. In this embodiment, each flock includes 2 to 4 1-bit cells. In other words, block OK2
1 cell, 3 cells in block l, and block 2
It has four cells. For example, the second block (j
=1) has three cells, bit number 2
is the start cell, bit number 3 is the continuation
ue) cell, and bit number 4 is the end cell.

Table ripple + 7 da carry lookahead adder Conditional phase adder Conditional carry add Speaker conditional carry adder B For table full adder: Cin block (0) Cin adder For each block j : Cin 0 (0) ” 0 Cin 1 (0) = 1 Cout block (j) = Cout O (imax)
+(Cout 1 (i max) conflict Cin block (
'')] = C1n block (j+1 For each bit house of block J: K (i) = A (i) + B (1) G (1)
Two people (1)・B(1) P(i) = A(i) XORB(i) Cout 0
(i) = G(i) + (K(i) ・Cin O(g)
]=C1nO(i+1) Cout 1(i)" G(i)+ [K(t)-Ci
n 1(i))=Cin 1(i+l) Cin(i)=Cin 0(i)+(Cin 1(i
)・Cin block (j)] 1) (i) = P(i)
XORC1n (il basic K, 2 ripple carry outputs Co in each block (for example in "=0~2)
ut 0(il and Cout 1(i) are generated. At the start cell of each block, the carry force C1
Note that nQ and C1n1 are defined as 0° and "l", respectively. These two carry outputs Cout are the carry human power C input into the current block.
Combining with the in block ('') generates the carry output Cout block ('') of the current block from K. ” In every block of twenty to two, those two carry chains (CoutO-Cin Q and Coutl-C
in l ) are simultaneously propagated one after another. Block O first generates its carry output and then propagates to block IK. Thereafter, only one gate delay is required for the carry to "jump over" each block. Therefore, in conditional carry adder A, when the carry propagation delay time is minimized, the block size, that is, the bit length, increases in an arithmetic progression (i.e., 2.3.4) as the block number increases. . . . etc.), so the total delay time increases approximately in proportion to the square root of the bit length of the operand.

Therefore, the conditional carry adder A has 17% more elements per bit than the carry lookahead adder, as seen from Table 2.
A 25% performance improvement can be obtained with just an increase. Similarly, the conditional carry adder A is constructed from 1-bit cells, and does not use cells spanning multiple bits as in other high-speed technologies. This makes it possible to create an integrated circuit with a regular layout that is easy to implement and uses chip area efficiently.

A second embodiment using the high-speed carry method of the present invention,
Conditional carry adder B is shown in FIG. 4, and a program written in a PASCAL-like language illustrating its operation is shown in Table 4. The program in Table 4 shows the case where the operand length is N bits, and here 2 * * J
” represents 2J.

The configuration of this embodiment is similar to conditional carry adder A (Figures 3A and 3B), and similarly the inputs are assumed to be C1n0 = 1 and C1n1 = 1, and the carry output is Calculated according to

Table 4 For i -0to (N-1) Do B
EGIN Couj O(0,i)-Afil ・Bf
il -CH1lCou+ 1 (0,I)-person fil
+B fit -K11lPfil
-Afil
W Ll −(K*W−1−W/2) L2−(K rate W+W) D.

EGIN For -(LO) to (Ll-1)D.

EGIN CoulO(j.

Cou (J i ) -Cout0 (j-1,i)i) -Co
ut l (j-1,i)nd For-(Ll)to (L2-1) Do BEGIN
CouLO(j.

Cout 1 (i.

i) −CoulO(j −t, i)+(Cout1
(i-1・Cout0(j-L Ll-1)) i) -Cout o (1-1,+)+(C!
o u+ I (j-+.

・CouN (j'2.Ll-1)) 1) ) nd C1nfol - Cin adder K-LOG2 (to) For i -0to (N-1) D.

Dfil -Pt1l
(j, i) are generated assuming that the carry inputs to that bit are 0' and "1", respectively. however,
Assume that j゛ is the stage number and "1" is the bit number.The purpose of this is that the carry input given from the lower order for the entire block of bits is "0" and "l", respectively.
” to generate a carry input for each focus. Each successive stage performs this function and also generates a carry output Cout for this block.
1 and Cout Q.

As shown in stage 4 of Figure 4, the final carry input for each bit (Cout Q(k,i) in Table 4)
and Coutl (k, i)) are generated, the carry input Cin for the adder selects the correct carry input for each bit (C1n(i+1) in Table 4). and this selected carry input is the appropriate P
It shows that the final sum D(0) to D(7) is generated by exclusive ORing with bits P(0) to P(7).

As can be understood from Fig. 4, conditional carry adder B
The main differences between the conditional carry adder A and the conditional carry adder A are as follows. In conditional carry adder B, the block size increases by a power of 2, that is, in a geometric progression, but the block size of conditional carry adder A is As mentioned above, it increases in an arithmetic progression. Therefore, the total delay time of conditional carry adder B is proportional to the base 2 logarithm of the number of bits to be added.

The carry of the conditional carry adders A and B can be applied to either an incrementer or a priority encoder. An incrementer is a circuit that adds 1 to a number represented by N bits, and a priority encoder generates an output that encodes the highest priority (most significant) bit in an N-bit input (for example, an 8-bit to 3-bit encoder). or a 10-bit to 4-bit encoder).

In the incrementer shown in FIG. 5, which uses a carry in the conditional carry adder B, the second inputs B(0) to B(7) in addition are not used. Can be set to zero. At this time, G and P generated at stage O in FIG. 4 are as follows.

K=AB20G2A+B=Ap=AXORB=A Similarly, if the incrementer is always enabled, the Cin signal can be set to "1°".

In this way, the conditional carry adder B shown in FIG.
However, the incrementer shown in FIG. 5 can be constructed by removing all logically redundant gates. Using a similar redundant gate removal method,
The incrementer shown in FIG. 6 is constructed based on the conditional carry adder A of FIG. 3A. Similar to the adders shown in FIGS. 3A and 3B, the continuation cells of FIG. 6 can be used as many times as necessary in each block.

FIG. 7 is a diagram showing an 8-bit to 3-bit priority encoder using the fast carry scheme of conditional carry adder B. Similar to the incrementer described above, B(0) ~
B (Force input is set to ``0'' and carry signal is set to ``1''.

In this embodiment, the carry input is shown as "enabled" and is inverted to keep the priority encoder enabled. (In other words, the enable terminal is actually grounded and given "0'.") Each output cell has a three-state buffer 30
and is enabled by the corresponding gate 40. The logic elements in the first four rows allow 8-bit human power A
Among (7) to AffO), it is guaranteed that only the buffer 30 corresponding to the most significant bit that is 1' is enabled. Each 3-state buffer 3 for each output cell
The inputs to 0 are wired with appropriately binary weighted signals corresponding to the bit numbers of each operator input. In this way, each three-state buffer 30 is composed of three buffers connected in parallel, forming three encode output lines with 3-bit output. The output settings for each three-state buffer 30 when enabled are as follows: A(0) digit is set to 0, 0.0,
(The 11th digit is 0° 0.1, etc., the A (7) digit is 1.1.
It is set up to 1. Outputs of eight buffers (one from each digit) corresponding to the lower 3-bit inputs to each 3-state buffer are connected in common to form an encoded (0) output, which is intermediately weighted. was done (
8 buffers (one from each digit) corresponding to the inputs (i.e. weight 2) are connected in common to form the encode(1) output, and 8 buffers corresponding to the topmost input (
(one from each digit) are commonly connected to form the encode (2) output. These three encode lines then provide appropriately weighted outputs to perform the 8-bit to 3-bit encoder function, and provide appropriately enabled priority numbers. In addition to adding the appropriate number of three-state buffers for each pit in a manner similar to the incrementer described above, the technique of redundant cell elimination can be used to create the conditional carry adder shown in Figure @3A. The priority encoder shown in FIG. 8 can be constructed based on A. In this case as well, the continuation cells shown in FIG. 8 can be used as many times as necessary in each block.

[Brief explanation of drawings]

FIG. 1 is a circuit diagram showing a 1-bit ripple adder according to the prior art, FIG. 2 is a circuit diagram showing a carry look-ahead adder according to the prior art, and FIG. 3A is a circuit diagram showing the high-speed carry method of the present invention. FIG. 3B is a block diagram illustrating the configuration of the adder shown in FIG. 3A when the bit length is expanded. FIG. 4 is a circuit diagram showing the adder used in this invention. A circuit diagram showing an adder, FIGS. 5 and 6 are circuit diagrams showing an incrementer using the high-speed carry method of the present invention, and FIGS. 7 and 8 are circuit diagrams showing an incrementer using the high-speed carry method of the present invention. This is a circuit diagram showing the priority encoder. A, B: Operand, D: Sum, Cin: Carry input, Cout: Carry output procedure amendment December 1990 288

Claims (1)

[Claims] In an adder circuit for adding two N-digit operands, the following (A) to (C): (A) one input row having a plurality of first cell means: the first each of the cell means accepts a first pair of digits from said two operands and provides a plurality of first logic output signals to adjacent cell means in a subsequent row; (B) a plurality of second; A plurality of intermediate rows having third and fourth cell means: (B-1) Said second cell means receives selected ones of the logic output signals from adjacent cell means in the immediately preceding row. passing a selected one of the logic output signals from the adjacent cell means in the immediately preceding row to the adjacent cell means in the subsequent row; (B-2) Said third cell means passes selected ones of the logic output signals from the adjacent cell means in the immediately preceding row to the adjacent cell means in the subsequent row; combining selected ones of the logic output signals from the cell means with selected ones of the logic output signals from adjacent cell means in the cell means to form a first pair of carry output signals; (B-3) said fourth cell means applies selected ones of the logic output signals from adjacent cells in the immediately preceding row to adjacent cell means in the subsequent row; pass to adjacent cell means; (C) one output row having a plurality of fifth cell means; said fifth cell means pass selected logic output signals from adjacent cell means in the preceding row; 2 carry input signals to produce a final summed digit output; the plurality of intermediate rows are coupled between the input row and the output row, and a first intermediate row In the row, the second, third, and fourth
A selected one of the cell means is arranged to be repeated for every R position, and in a second intermediate row connected to the first intermediate row, the second, third, and A selected one of the fourth cell means is arranged to be repeated every S position, and in a third intermediate row joined to the second intermediate row, a selected one of the fourth cell means , and a selected one of the fourth cell means are arranged to be repeated every T position, and said repetition length (R, S, T) is such that the intermediate row number is 1.
An adder circuit that forms a geometric sequence that doubles every time the number increases.