JPH0348534B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a carry look-ahead circuit in binary multi-bit parallel addition.

[Background technology and its problems]

Multiplying a binary multiplicand by a multiplier is a binary number obtained by multiplying the multiplicand by the least significant bit of the multiplier, and a binary number obtained by multiplying the multiplicand by the next bit of the multiplier. Calculations are performed by adding the respective binary numbers obtained by multiplying the respective bits of the multiplier (each referred to as a partial stage).

For example, in order to configure a parallel multiplier, in order to maximize the high-speed operation that is a feature of this multiplier, it is necessary to use the so-called Booth algorithm, which is an algorithm that reduces the number of partial product stages, and the partial product addition method. The so-called valance tree is a connection method that reduces the number of adder stages in the addition path, or the carry signal generated in the partial accumulation stage is
A so-called carry-save method is used in which carry signals are supplied to a lower partial stacking stage to shorten the carry signal propagation path in the partial product adding stage.

However, even if the speed-up method described above is used, at the final stage of the partial product addition stage, the carry signal generated at the least significant digit is transmitted through the carry signal propagation path that propagates it to the most significant digit. If the number of bits in the multiplicand or multiplier is large, this propagation path can extend to several tens of bits, and the propagation time of the carry signal is delayed, which is a major factor limiting the speedup of the multiplier. They were all one.

Therefore, in order to perform such a carry operation at high speed, a method is conventionally known in which a carry look-ahead circuit as shown in FIG. 1 is used in the multiplier.
FIG. 1 shows a circuit configuration for performing 10-bit parallel addition, and A ₁ to A ₁₀ and B ₁ to B ₁₀ respectively represent 10-bit binary numbers to be added in parallel. Also, F1 to F10 represent full adders,
C _IN is a carry input, C ₂ to C ₁₀ represent carry signals, and C _OUT represents a carry output. Further, S ₁ to S ₁₀ represent addition outputs. This parallel adder circuit is provided with carry look ahead circuits 1 and 2 in units of 4 bits, and the carry look-ahead circuits 1 and 2 are generated from the carry input C _IN and the addition inputs of the lower 4 bits A ₁ to A ₄ and B ₁ to B ₄ . Carry signal input to full adder F5
_C5 is obtained by the carry look ahead circuit 1. In addition, the carry look ahead circuit 2 outputs a carry signal.
Generate a carry signal _C9 generated from _C5 and the next 4-bit addition input of _A5 to _A8 and _B5 to _B8 ,
It is supplied to full adder F9. As is clear from this figure 1, carry input is input to the lowest digit.
Full adder F10 where C _IN is added with the most significant digit
The path propagated to is the NAND of the look-ahead circuit 1 above.
The signal is sent from gate 3 to NAND gate 4, from NAND gate 5 of look-ahead circuit 2 to NAND gate 6, and then to full adder F10 via full adder F9, and look-ahead circuits 1 and 2 are not provided. Faster propagation is now possible than in the case of However, if the carry look-ahead circuits 1 and 2 are configured with CMOS (complementary MOS) circuits as shown in the logic circuit shown in FIG. 1, the large number of elements due to CMOS makes wiring between elements complicated and increases cost. Also, due to the large number of multi-input gates, it takes time to charge and discharge the CMOS charge, making it difficult to fully realize high speed. Therefore, the general
A CMOS gate circuit configuration is rarely used, and even when a CMOS process is used, a PMOS (P channel) configuration is used, as shown in Figure 2.
Currently, a relatively simple ratio circuit configuration with a MOS (MOS) as a load is used. Here, the ratio circuit is a DMOS (depletion MOS) with a general E/D (enhance/depletion) configuration.
This is a circuit in which the load is replaced with a DMOS load. FIG. 2 shows a carry look ahead circuit for the lower 4 bits, and the higher 4 bits are also constructed of a similar circuit. By configuring the look-ahead circuit shown in Figure 2 as a ratio circuit using a PMOS load, high speed performance can be improved, and the number of elements used can be reduced compared to CMOS, so the overall number of elements can be reduced. I can do it. However, the wiring between the gates remains complicated, and the cost is insufficient. Also,
Since the gate is constructed with a ratio circuit, a direct current path is created between the power supplies, resulting in an increase in power consumption.

[Purpose of the invention]

The present invention was proposed in view of the above circumstances, and aims to provide a carry look-ahead circuit that uses fewer elements, has simple wiring between elements, consumes less power, and has high operating speed. purpose.

[Summary of the invention]

To achieve this objective, the carry lookahead circuit of the present invention combines two m-bit binary numbers (m≧2) a= _n 〓 ^i=
1 Ai2 ^i-1 , b= _n 〓 ⁱ⁼¹ Bi2 In the parallel addition of ^i-1 and the carry input C _IN from the lower order, (4m+1)
first conductivity type transistor group and (4m+1)
For the second conductivity type transistor group, +(+)[ _{-1 -1} +( _-1 +
Bm _-1 ) [{...}[ _{2 2} + ( ₂ + ₂ ) { _{1 1} +
( ₁ + ₁ ) _IN }]...]] and AmBm+(Am+Bm)[Am _-1 Bm _-1 +(Am _-1 +
Bm _-1 ) [{...} [A ₂ B ₂ + (A ₂ + B ₂ ) {A ₁ B ₁ +
(A ₁ +B ₁ ) C _IN }]...]] Forming a switch network expressed by the theoretical formula, connecting one end of the power supply to one end of the switch network constituted by the first conductivity type transistor group, Connecting the other end of the power supply to one end of the switch network constituted by the second conductivity type transistor group, connecting the other ends of the respective switch networks to each other, and connecting the connected end to the input of the complementary inverter, It is characterized in that the output of the inverter is used as a carry signal.

〔Example〕

Hereinafter, one embodiment of the present invention will be described based on the drawings.

FIG. 3 shows a carry look-ahead circuit according to the present invention constructed from, for example, a CMOS (complementary MOS) circuit. This figure 3 shows _a carry look ahead circuit in parallel addition of 3 bits of binary number.
A carry signal output C _OUT3 is obtained from a parallel addition input of 3-bit binary numbers A ₃ and B ₁ to B ₃ and a carry input C _IN from the lower order. This carry signal output C _OUT3 can be determined by the following equation for the addition inputs and carry inputs C _IN of A ₁ to A ₃ and B ₁ to B ₃ .

C _OUT3 = A ₃ B ₃ + (A ₃ + B ₃ ) [A ₂ B ₂ + (A ₂ + B ₂ ) {A ₁ B ₁ + (A ₁ + B ₁ ) C _IN }] ...(1) The above look-ahead circuit The function of equation (1) is realized by a complementary circuit using CMOS transistors, and includes a logic circuit section 150 and a complementary inverter 151.
It is composed of. The logic circuit section 150 is
For example, 13 transistors of the first conductivity type
PMOS (P channel MOS) transistor 100
to 112 and 13 which is a second conductivity type transistor
For example, the device is constructed of NMOS (N channel MOS) transistors 114 to 126. This number of 13 is due to the fact that the parallel addition input is 3 bits (m=3).
It is calculated by the equation (1) and corresponds to the 13 calculation elements (total number of A ₁ , B ₁ , etc.) on the right side of the equation (1) above. In addition, the complementary inverter 151
For example, PMOS transistor 113 and
It is composed of an NMOS transistor 127, and the carry signal output _COUT3 is obtained from the output terminal of the inverter 151. Also,
A positive power supply is connected to V _DD , and V _SS is grounded. In this way, the above carry look-ahead circuit connects the PMOS transistors 100 to 113.
The NMOS transistors 114 to 127 have a completely symmetrical configuration.

Next, the principle of operation of the carry look-ahead circuit will be explained. In the following explanation, V _DD is assumed to be logic 1 and V _SS
Assume that positive logic is used where is logic 0. In the logic circuit section 150, the input condition where the V _DD terminal and the _OUT3 node, which is the previous stage of the inverter 151, are in a conductive state, that is, the logic of _OUT3 is 1, is _OUT3 = _{3 3} + ( ₃ + ₃ ) [ _{2 2} + ( ₂ + ₂
) { _{1 1} + ( ₁ + ₁ ) _IN }] = _{3 3}・₃ + ₃ ) [ _{2 2} + ( ₂ + ₂ ) { _{1 1} + ( ₁ + ₁ ) ( _IN }] By calculating , _OUT3 = _{3 3} + ( ₃ + ₃ ) [ _{2 2} + ( ₂ + ₂
) { ₁ B ₁ + ( ₁ + ₁ ) _IN }] ...(2) becomes. On the other hand, the input condition where the V _SS terminal and the above _OUT3 node are in a conductive state, that is, _OUT3 becomes logic 0, is C _OUT = A ₃ B ₃ + (A ₃ + B ₃ ) [A ₂ B ₂ + (A ₂ + B ₂ ) {A ₁ B ₁ + (A ₁ + B ₁ ) C _IN }] ...(3). If all the combinations of input signal values in equations (2) and (3) are illustrated, it will be as shown in the Betsch chart in Figure 4, and Figure 4a shows the conditions for equation (2) and the 4th Figure b shows the conditions for equation (3). As is clear from this Betsch diagram, the state of equation (2) above and
There are no combinations of inputs that cause the states of equation (3) to overlap,
These equations (2) and (3) are in a contradictory relationship. In the above-mentioned look-ahead circuit, the transistor group of the above-mentioned PMOS transistors 100 to 112 is
A switch network is formed to realize the logical formula (2) above, and one end 130 of this switch network is connected to _VDD , which is one end of the power supply. Also,
The transistor group of the NMOS transistors 114 to 126 forms a switch network that realizes the logical formula (3) above, and one end 131 of this switch network is connected to the other end of the power supply, _VSS . It is becoming more and more common. Further, the other ends 132 and 133 of each switch network are connected to each other, and the connecting end, that is, the above-mentioned _OUT3 node is connected to the input of the complementary inverter 151. Here, to explain the correspondence between each switch network and the above logical formula, for the PMOS transistor group and equation (2), the logical sum of ₁ and ₁ , that is ( ₁ + ₁ ), is the transistors 104 and 103 connected in parallel. It is being done. That is, transistor 104,1
03 each form an individual switch. Also, the logical product of ( ₁ + ₁ ) and _IN, that is, ( ₁ + ₁ ) _IN , is the transistor 104,
This is done by connecting the parallel circuit 103 and the transistor 102 in series. In addition, _{1 1} is a transistor 100 connected in series,
101, and these and the transistor 1
04, 103, and 102 are connected in parallel to perform the operation { _{1 1} + ( ₁ + ₁ ) _IN }. Also, these transistor groups and ( ₂ + ₂ )
Transistors 10 connected in parallel to perform
6,105 are connected in series ( ₂ + ₂ )
The operation { _{1 1} + ( ₁ + ₁ ) _IN } is now performed. Similarly, the logical expression shown in equation (2) corresponds to the PMOS transistor groups 100 to 112, and the transistor groups 100 to 11 correspond to each other.
2 to form a switch network.
The same holds true for the correspondence between the NMOS transistor groups 114 to 126 and the logical formula shown in equation (3).

In this way, the carry look-ahead circuit is able to obtain the inverted signal _OUT3 of the above formula (1) at the _OUT3 node without creating a DC path between the power supply V _DD and the ground V _SS . That is, in the above-mentioned look-ahead circuit, it is possible to obtain exactly the same function as when the above-mentioned formula (1) is configured with a normal CMOS circuit as shown in the above-mentioned conventional example.

In multi-bit parallel addition, the calculation speed is determined by the carry speed from the least significant digit to the most significant digit, and the carry input in the carry look ahead circuit
C _IN is the speed at which the carry signal output C _OUT3 is determined to be sent. Considering the above logic circuit section 150, the input conditions for the carry input C _IN such that the inverted carry signal output _OUT3 becomes logic 1 are, for example.
C _IN , B ₁ , B ₂ , B ₃ become logic 0, and A ₁ , A ₂ , A ₃
This is the case when the logic becomes 1. Also, the input conditions for _OUT3 to be logic 0 for carry input C _IN are:
For example, C _IN , B ₁ , B ₂ , B ₃ become logic 1, and A ₁ ,
This is the case when A ₂ and A ₃ are logical 0. Considering the case where _OUT3 becomes logic 1, the charging and discharging path in this case is as shown in Figure 3.
From node a to node c in the PMOS transistor group,
Although the path passes through the node f and goes to the _OUT3 node, the speed of the discharging operation is not slower than that of the charging operation. In addition, considering the charging path within the NMOS transistor group at this time regarding charging operation with a slow operating speed, nodes g, i, and j are not charged because transistors 126, 124, and 118 are off, but are connected to nodes g, i, and j. Since h, k, and l are intermediate nodes of AND-connected transistors, the diffusion capacitance due to the source or drain is extremely small, and the charging speed does not slow down even during charging operation. Further, due to the simple configuration of the logic circuit section 150, most of the node capacitances are extremely small so that the speed will not be slowed down, and since the complementary inverter 151 is an inverter with a large load driving ability, the carry look-ahead circuit It has become possible to increase the operating speed of Note that the delay time per bit for the above 3-bit carry look-ahead circuit is as follows:
It has been confirmed by simulation that this is less than half of the case.

Above, we have described the look-ahead circuit for generating the carry signal C _OUT3 for every 3 bits. Two m-bit binary numbers (m≧2) a= _n 〓 ⁱ⁼¹ Ai2 ^i-1 , b= _n 〓 ^{i =1} Bi ^i-1
The carry look-ahead circuit for obtaining the carry signal in parallel addition for the carry input C _IN from the lower order is the first conductivity type transistor (4m+1)
For example, a group of PMOS transistors and (4m+1) transistors of the second conductivity type.
It may be configured by a group of NMOS transistors and a complementary inverter. At this time, the PMOS transistor group is + (+) [ _{-1 -1} + ( _-1
+ _-1 ) [{...}[ _{2 2} + ( ₂ + ₂ ) { _{1 1}
+ ( ₁ + ₁ ) _IN }〕...〕〕 A switch network of the logical formula is formed. Regarding the NMOS transistor group, AmBm + (Am + Bm) [Am _-1 Bm _-1 + (Am _-1
+Bm _-1 ) [{...}[A ₂ B ₂ + (A ₂ +B ₂ ) {A ₁ B ₁
+(A ₁ +B ₁ )C _IN }]...]] A switch network is formed which is expressed by the following logical formula. In this way, the present invention can realize a carry look-ahead circuit for any number of bits of 2 or more.

Here, two 4-bit binary numbers A ₁ to A ₄ and B ₁
Carry signal output from B ₄ and carry input C _IN
A carry look-ahead circuit every 4 bits that can obtain C _OUT4 will be explained with reference to FIG. The carry signal _COUT4 in the case of 4 bits is given by the following logical formula.

C _OUT4 = A ₄ B ₄ + (A ₄ + B ₄ ) [A ₃ B ₃ + (A ₃ + B ₃ ) [A ₂ B ₂ + (A ₂ + B ₂ ) {A ₁ B ₁ + (A ₁ +
B ₁ ) C _IN }]] …(4) Comparing the logical expression expressed by equation (4) with equation (1), we find that it is in the form of equation (1) with an underlined term added. There is. Also, this underlined term corresponds to circuit 2 of the broken line portion shown in FIG. 5 of the 4-bit look-ahead circuit.
00. in this way,
The carry look-ahead circuit according to the present invention has expandability, and when integrated into a circuit, it can be constructed with an optimal number of bits depending on process parameters or layout patterns. Also, the fifth
When compared with the carry look ahead circuit for every 4 bits shown in the figure, the circuit of the present invention has an extremely simple structure. In addition, the number of elements is reduced to 36 elements in the look-ahead circuit shown in Figure 5, compared to 52 elements when the logic circuit in Figure 2 is configured with a ratio circuit using a PMOS load. The wiring becomes simple and it is advantageous in terms of cost. Further, the carry look-ahead circuit of the present invention has a structure that does not have a direct current path between the power source and the ground, making it possible to extremely reduce power consumption.

FIG. 6 shows the configuration of a 10-bit parallel adder circuit in which the carry look-ahead circuit section of the 10-bit parallel adder circuit shown in FIG. 1 is replaced with the carry look-ahead circuit shown in FIG. In FIG. 6, for simplicity, the transistors are indicated by circles, and the signal lines to the gate electrodes are indicated by broken lines.

As described above, the carry look-ahead circuit according to the present invention has a high operating speed due to the simple circuit configuration, and if a parallel multiplier is configured using the look-ahead circuit, high-speed parallel multiplication can be performed. I can do it. Further, the above-mentioned look-ahead circuit has expandability and can be configured with a small number of elements, and the wiring between elements is simple, making it possible to realize the look-ahead circuit at low cost. Furthermore, since it does not have a DC path between the power supply and ground, it is a carry look-ahead circuit with extremely low power consumption.

Note that the carry look-ahead circuit may not be constructed from CMOS transistors, but may be constructed from bipolar transistors or the like.

[Effects of the Invention] As is clear from the above description, according to the present invention, a carry look-ahead circuit in multi-bit binary parallel addition is realized by a complementary circuit according to a logical formula for outputting a carry signal, and this By inputting the output of the complementary circuit to a complementary inverter, a carry signal output is obtained from the inverter. Therefore, the circuit configuration is simple, and high operating speed can be achieved even if the look-ahead circuit is configured with, for example, a CMOS transistor. Furthermore, since it is constructed with a small number of elements, wiring between the elements is simple, which is advantageous in terms of cost. Also,
Since there is no DC path between the power supply and ground, power consumption is extremely low.

[Brief explanation of drawings]

FIG. 1 is a 10-bit parallel addition circuit diagram showing a conventional carry look-ahead circuit, FIG. 2 is a diagram of another conventional carry look-ahead circuit, and FIG. 3 is a 3-bit carry look-ahead circuit diagram according to the present invention. FIG. 4 is a diagram showing a Betsch chart explaining the operating principle of the above-mentioned 3-bit carry look-ahead circuit, FIG. 5 is a diagram of a 4-bit carry look-ahead circuit according to the present invention, and FIG. FIG. 2 is a diagram of a 10-bit parallel addition circuit composed of a carry look-ahead circuit. 102 to 113...PMOS transistors,
114 to 127...NMOS transistor, 1
50...Logic circuit section, 151...Complementary inverter.

Claims (1)

[Claims] 1 Two m-bit binary numbers (m≧2) a= _n 〓 ⁱ⁼¹
Ai2 ^i-1 , b= _n 〓 ⁱ⁼¹ Bi2 ^i-1 and carry input from lower order
In parallel addition for C _IN , for (4m+1) first conductivity type transistor groups and (4m+1) second conductivity type transistor groups, +(+)[ _{-1 -1} +( _-1 +
Bm _-1 ) [{...}[ _{2 2} + ( ₂ + ₂ ) { _{1 1} +
( ₁ + ₁ ) _IN }]...]] and AmBm+(Am+Bm)[Am _-1 Bm _-1 +(Am _-1 +
Bm _-1 ) [{...} [A ₂ B ₂ + (A ₂ + B ₂ ) {A ₁ B ₁ +
(A ₁ +B ₁ ) C _IN }]...]] Forming a switch network expressed by the theoretical formula, connecting one end of the power supply to one end of the switch network constituted by the first conductivity type transistor group, Connecting the other end of the power supply to one end of the switch network constituted by the second conductivity type transistor group, connecting the other ends of the respective switch networks to each other, and connecting the connected end to the input of the complementary inverter, A carry look-ahead circuit characterized in that the output of the inverter is used as a carry signal.