JPH0467211B2 - - Google Patents

Description

[Detailed description of the invention]

[Field of Industrial Application] The present invention relates to an adder circuit, and more particularly to an adder circuit that significantly reduces carry propagation delay with relatively low gate usage. BACKGROUND OF THE INVENTION 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 can be used to easily perform carry propagation addition. Ripple adders require fewer transistors per bit, but are generally relatively slow. The ripple adder is thus a basic but slow adder that is often used as a basis for measuring the performance of other adders. FIG. 1 is a diagram showing a typical ripple adder cell. In Figure 1, A(i) and B(i) are the respective bits of the two operands being added, Cin(i) is the carry input from the previous ripple adder cell, and Cout(i) is the carry input from the previous ripple adder cell. ) is the carry output from this ripple adder cell, and D(i) 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 1 shows N written in PASCAL-like language.
A program is shown to explain the logical operation of the bit ripple adder. In addition, in the program in Table 1, "+" stands for logical sum, "・" stands for logical product, and "XOR"
indicates exclusive OR. Table 1 For i=0 toN−1 DO BEGIN K(i)=A(i)+B(i) G(i)=A(i)・B(i) P(i)=A(i)XOR B( i) Cout(i)=G(i)+[K(i)・Cin(i)] =Cin(i+1) D(i)=P(i)XOR Cin(i) End Ripple adder is a carry look ahead The speed can be increased by adding a circuit. To realize a carry look-ahead adder, the ripple adder is
For example, it consists of a block consisting of four ripple adder cells. Each block of the four high-speed adders has a gate added to it, as shown in FIG.
The carry output from the previous block passes through this block and is propagated to the next block. Carry lookahead adders are relatively fast and can be constructed inexpensively using MOS circuits. Alternatively, IRE Transactions
On Electronic Computers (I.
RETransactions on Electronic Computers)
In the June 1960 issue of the magazine, page 226, there is a conditional sum adder published by Mr. Sklansky as ``addition logic using conditional sums''.
Conditional sum addition works very fast, but
It requires significantly more logic than the relatively slow addition described above. As a result, conditional sum addition results in a very high price 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 methods are often too slow for new generations of computers;
Otherwise, it was far more complex and expensive than expected. [Object of the invention] The present invention solves the problems of the prior art described above,
The purpose of this invention is to provide a high-speed and easy-to-implement adder circuit. [Summary of the Invention] According to one embodiment of the present invention, an adder circuit has a series connection configuration of cells that generate an intermediate carry signal. Therefore, the intermediate carry signal of each of these bit pairs can be propagated independently and successively through successive stages. 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 can also be applied to incrementors and priority encoders. Examples of these applications are also discussed below. Since the adder circuit of the present invention requires relatively few types of cells, it can be easily combined in a regular manner as shown below to construct an adder, incrementer, or priority encoder of arbitrary length. I can do it. Therefore, according to the present invention, it is possible to realize a circuit with high absolute speed, and also to realize a circuit with high absolute speed.
No matter which MOS technology is used to manufacture LSIs, they can be constructed at low cost with minimal design complexity. [Embodiments of the Invention] Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings. In the following, two adders A, B are disclosed that perform carry propagation addition, also called conditional carry addition. Adder B is an embodiment of the present invention, and adder A is an adder that shares the general principle of the carry method with adder B. 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, adder speed is indicated by the number of gate delay stages required to perform a full addition. The data shown in Table 2 is
This is the case for a 32-bit adder. 3A and 3B are diagrams illustrating conditional carry adder A, and Table 3 is a logical expression related to conditional carry adder A. Three different types of cells are shown in Figure 3A. They start
cells, any number (even zero) of continuation cells, and end cells. FIG. 3B is a diagram showing an example of a cell configuration in the case of a 9-bit adder. In this adder, each block has 2 to 4 1-bit cells. That is, two cells in block 0, three cells in block 1, and three cells in 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 continue cell, and bit number 4 is the end cell.

【table】

[Table] Basically, in each block (for example, j = 0 ~
2) Two ripple carry outputs Cout0(i) and Cout1(i) are generated. Note that in the start cell of each block, carry inputs Cin0 and Cin1 are defined as "0" and "1", respectively. These two carry outputs Cout are the carry input Cin block input to the current block.
(j) generates the carry output Cout block (j) of the current block. In all blocks from j=0 to 2, those two carry chains (Cout0-Cin0 and Cout1-Cin1) are propagated one after another simultaneously. Block 0 first generates its carry output and propagates to block 1. Thereafter, only one gate delay is required for the carry to "jump over" each block. Therefore, in the 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 (that is, 2, 3, 3, etc.) as the block number j increases. 4, . . . ), the total delay time increases approximately in proportion to the square root of the bit length of the operand. Therefore, conditional carry adder A can achieve a 25% performance improvement compared to the carry lookahead adder by increasing the number of elements per bit by only 17%, as shown in Table 2. Similarly, conditional carry adder A is composed of 1-bit cells,
It does not use cells that span multiple bits like 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. FIG. 4 shows a conditional carry adder B, which is an embodiment of the present invention, and shows its operation.
Table 4 shows programs written in a PASCAL-like language.
Shown below. The program in Table 4 shows the case where the operand length is N bits, and here “2
〓〓j'' represents 2 ^j . The configuration of this embodiment is a conditional carry adder A.
(FIGS. 3A and 3B) and similarly the inputs are considered as Cin0=1 and Cin1=1 and the carry outputs are calculated accordingly.

[Table] In Figure 4, each stage has carry outputs Cout0(j,i) and Cout1(j,i) generated from each bit.
i) is generated assuming that the carry inputs to that bit are "0" and "1" respectively. However, it is assumed that "j" is the stage number and "i" is the bit number. The purpose of this is to generate a carry input for each bit assuming that the carry inputs applied from the lower order to the entire block of bits are "0" and "1", respectively. Each successive stage performs this function and
Also, carry output Cout1 and
Generates Cout0. As shown in stage 4 of Figure 4, the final carry input for each bit (Cout0 in Table 4)
(k, i) and Cout1 (k, i)) are generated, the carry input Cin to the adder becomes the correct carry input for each bit (Cin (i+
1) Select). This selected carry input is then exclusive-ORed with the appropriate P bits P(0)-P(7) to generate the final sum D(0)-D(7). ing. As can be understood from FIG. 4, the main differences between conditional carry adder B and conditional carry adder A are as follows. In conditional carry adder B, the block size increases as a power of 2.
That is, it increases in a geometric progression, but the size of the block of the conditional carry adder A increases in an arithmetic progression as described above. Therefore, the total delay time of conditional carry adder B is proportional to the base 2 logarithm of the number of bits being added. The carry of conditional carry adders A and B can be applied to either an incrementer or a priority encoder. The incrementer is a circuit that adds 1 to the number represented by N bits, and the priority encoder generates an output that encodes the highest priority (most significant) bit in the N bit input (for example, 8 bits - 3 bits).・Encoder or
(10-bit to 4-bit encoder). Figure 5 shows an incrementer using carry in conditional carry adder B. In the incrementer, the second inputs B(0) to B(7) in addition are not used, so they are set to zero. can be set.
At this time, K generated at stage 0 in Fig. 4,
G and P are as follows. K=A.B=0 G=A+B=AP P=A _XOR =A Similarly, if the incrementer is always enabled, the Cin signal can be set to "1". In this way, the incrementer shown in FIG. 5 can be constructed by removing all logically redundant gates as an incrementer from the conditional carry adder B shown in FIG. . Using a similar redundant gate removal method, the sixth one is constructed based on the conditional carry adder A in Figure 3A.
This is the incrementer shown in the figure. 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 method of conditional carry adder B. Similar to the incrementer described above, the B(0) to B(7) inputs are set to "0" and the carry signal is set to "1". In this priority encoder,
The carry input is shown as "enabled" and has been inverted to keep the priority encoder enabled. (In other words, the enable terminal is actually grounded and given "0"). Each output cell includes a three-state buffer 30 and is enabled by a corresponding gate 40. Logic elements in the first four rows select “1” among the 8-bit inputs A(7) to A(10).
Buffer 3 corresponding to the most significant bit
Only 0 is guaranteed to be enabled. The inputs to each three-state buffer 30 of each output cell are appropriately two-stated, corresponding to the bit number of each operator input.
The hexadecimal weighted signal is wired. In this way, each buffer 30 has three states connected in parallel.
It consists of three buffers, forming three encode output lines with 3-bit output. The output settings when each 3-state buffer 30 is enabled are as follows:
A(0) digit is 0,0,0, A(1) digit is 0,0,1
, and so on, up to the A(7) digit, 1, 1, 1. Then, the outputs of the eight buffers (one from each digit) corresponding to the lowest 3-bit input to each 3-state buffer are connected in common to form an encoded (0) output, which is intermediately weighted. (i.e. weight 2) The 8 buffers (one from each digit) corresponding to the inputs are connected in common to form the encoder (1) output, and the 8 buffers (one from each digit) corresponding to the most significant input ) are commonly connected to form the encode (2) output. And these three encoded lines are 8 bits - 3
Providing a suitably weighted output to perform the bit encoder function, a suitably enabled three-state buffer 30 selects the desired bit position corresponding to the most significant 1 in the input word. Supplies a number indicating the priority. In addition to adding the appropriate number of three-state buffers for each bit, similar to the incrementer described above,
By redundant gate removal techniques, the priority encoder shown in FIG. 8 can be constructed based on the conditional carry adder A shown in FIG. 3A. In this case as well, the continuation cells shown in FIG. 8 can be used as many times as necessary in each block. [Effects of the Invention] As explained in detail above, according to the present invention,
A high-speed addition circuit can be realized with a relatively small number of gates.

[Brief explanation of the drawing]

Figure 1 shows one of the ripple adders according to the prior art.
FIG. 2 is a diagram showing a carry look-ahead adder according to the prior art, FIGS. 3A and 3B are diagrams showing an adder circuit that performs high-speed carry, and FIG. 4 is a diagram showing an implementation of the present invention. The exemplary diagrams, FIGS. 5 through 8, are diagrams showing an incrementer and priority encoder applying the adder circuits of FIGS. 3A, 3B, and 4. A, B...operand, D...sum, Cin...carry input, Cout...carry output.

Claims (1)

[Claims] 1. 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 (B) 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 , 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; (B-2) passing to an adjacent cell means in the own row, and 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; ) said third cell means passes selected ones of the logic output signals from adjacent cell means in said immediately preceding row to said adjacent cell means in said immediately preceding row; a pair of output signals of a first carry; (B-3) said fourth cell means transmits selected ones of the logic output signals from adjacent cells in the immediately preceding row to adjacent cell means in the subsequent row; (C) one output row having a plurality of fifth cell means: said fifth cell means transmits selected logic output signals from adjacent cell means in the preceding row; a second carry input signal to produce a final summed digit output; the plurality of intermediate rows being coupled between the input row and the output row; In the middle row, the second, third,
and a selected one of the fourth cell means are arranged to be repeated for each R position, and in a second intermediate row connected to the first intermediate row, the second and fourth cell means 3, and selected ones of the fourth cell means are arranged to be repeated every S position, and in the third intermediate row connected to the second intermediate row, the second , the third, and the fourth cell means are arranged to be repeated every T positions, 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.