JP3445533B2 - Carry look ahead circuit - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a carry look ahead (CL) required for constructing a multi-bit length arithmetic unit.
A) Regarding the circuit.

[0002]

2. Description of the Related Art An input signal A (a <N-1>, a <
N-2>, ..., a <0>, hereinafter a <N-1: 0>) and the input signal B (b <N-1>, b <N-2>, ..., b <0>). , Hereinafter, b <N-1: 0>) is input and the addition is performed using a CLA circuit. A conventional CLA circuit is disclosed in Japanese Patent Laid-Open No. 3-1
There is one disclosed in Japanese Patent No. 50630. This CLA
Generally, the circuit performs operations in parallel when the input of the carry signal is “0” and “1” and selects and outputs one of the operation results according to the value of the lower carry signal. It is called a carry select adder.

This document discloses a conventional 4-bit CLA circuit as shown in FIG. In the bit-wise addition of the input signal A (a <3: 0>) and the input signal B (b <3: 0>), the propagate signal P <N-1> (a <N-1> and b EX-OR operation with <N-1>, AND signal G <N-1> (a <N-1> and b <N-1>)
Calculation). Then, the signals P <3: 0> and G <3: 0> and the carry CIN from the preceding stage are input to the CLA circuit, and the carry signal C <3: 0> is output.

FIG. 13 shows the structure of the CLA circuit having a structure for selecting and outputting one of the calculation results according to the carry value. CLA1 for calculating carry C <3: 0> when carry Cin from the previous stage and C for calculating carry C <3: 0> when carry Cin is 0
LA2 and LA2 are provided, and one of them is selected and output as the carry C <3: 0> according to the value of the carry Cin.

The 4-bit CLA circuit shown in FIG. 12 is arranged in group 0 of the 1st to 4th bits, and the CLA circuit shown in FIG. 13 is arranged in groups 1 to 7 of the 5th to 32nd bits.
When a 32-bit CLA circuit is configured by
As shown in FIG. Carry signal C <0> ~ starting from group 0 and ending with groups 1, 2, ...
C <3>, C <4> to C <7>, C <8> to C <11>, ... Are sequentially generated and transferred to the subsequent stage, and finally the carry signal C <28> from the group 7 ... C <31> is output.

[0006]

However, the above-mentioned conventional CLA circuit has the following problems. 1st bit carry C <0> to 32nd bit carry C <31>
The calculation delay time required to generate is as shown in FIG. Circuits CLA1 and CL in CLA circuits provided in groups 0 to 7 respectively
The time T1 required for the calculation in A2 is the same. However, the carry C <3> output from the group 0 is given to the CLA circuit of the group 1, and the delay time T in the multiplexer MUX which selectively outputs according to the carry C <3>.
2. The delay time T2 is cumulatively generated from the group 1 to the group 7, so that the delay time T1 + T2 * 7 finally occurs. Therefore, conventionally, there has been a problem that the time required for carry operation increases as the number of bits increases.

In view of the above circumstances, the present invention is capable of suppressing an increase in operation time even if the number of bits increases.
An object is to provide an LA circuit.

[0008]

The CLA circuit of the present invention comprises:
A propagate signal P of m bits each and at least one of a generate signal G and a kill signal K are given,
A group propagate signal PG and a group generate signal GG as the relevant group composed of m bits.
And a CLA circuit for generating at least one of the group kill signal KG, where the propagate signals P all have a first predetermined value, or the inverted propagate signals PB all have a second predetermined value. A logic circuit for outputting the group propagate signal PG having the first predetermined value and / or the inverted group propagate signal PGB having the second predetermined value, and the propagate gate signal P and / or the logical circuit. Inverted propagate signal PB
Are sequentially searched from the m-th bit of the most significant bit to the lower bits, and the second signal is searched first in the propagation signal P.
Of the inverted propagating signal PB, or a select signal S <i-1> for selecting the i-th bit of the inverted propagating signal PB in which the first predetermined value appears first. If the second predetermined value does not appear in any bit of the signal P, or the inverted propagate signal P
When the first predetermined value does not appear in any bit of B, a priority encoder for outputting "0" to the select signal S <i-1> for not selecting any bit, and the select signal S When <i-1> is input and "1" is input to the select signal S <i-1>, the i-th generation of the generation signal G and / or the kill signal K is generated. The signal G <i-1> and / or the kill signal K <i-1> are selected and output as the group generate signal GG and / or the group kill signal KG, respectively, and the select signal S <i-1> is output. When "0" is input to all of the above, a selector for outputting the group generate signal GG and / or the group kill signal KG having the second predetermined value is provided.

Further, the CLA circuit of the present invention is provided with a carry signal C, a propagating signal P of m bits each, and at least one of a generate signal G and a kill signal K, and the group is composed of m bits. Is a CLA circuit for generating a group propagate signal PG, at least one of a group generate signal GG and a group kill signal KG, and a group carry signal CG, wherein all the propagate signals P are a first predetermined value. Group propagate signal PG and / or the second group propagate signal PG having the first predetermined value when the inverted propagate signal PB has a second predetermined value.
The inverted group propagate signal P having a predetermined value of
A logic circuit for outputting GB and the propagate signal P and / or the inverted propagator signal PB are sequentially searched from the m-th most significant bit to a lower order, and the propagating signal P is first searched. Generating a select signal S <i-1> for selecting the i-th bit in which the second predetermined value appears or the inverted predetermined value first appears in the inverted propagation signal PB; If the second predetermined value does not appear in any bit of the propagate signal P, or if the first predetermined value does not appear in any bit of the inverted propagate signal PB, any bit is selected. In order to prevent this, a priority encoder that outputs "0" to all of the select signals S <i-1> and the select signal S <i-1> are input, and the select signal S <i-1> is set to "1". Is entered. Then, the i-th generate signal G <i-1> and the kill signal K <i-1> are selected from the generate signal G and the kill signal K, and the group carry signal CG and the group carry signal CG are selected, respectively. When it is output as an inverted group carry signal CGB and "0" is input to all of the select signals S <i-1>, the carry is carried out by the group propagate signal PG or the inverted group propagate signal PGB. And a selector for outputting the signal C as the group carry signal CG.

In this case, the logic circuit has an A-bit input of m bits.
It has an ND circuit and receives the propagate signal as input.
The ND calculation may be performed and the group propagate signal PG may be output.

Further, the CLA circuit of the present invention is a CLA for obtaining the carry signal CN of the most significant N-th bit which is necessary when adding the first input signal A and the second input signal B having the N-bit length as a whole. A circuit, wherein the N bits are divided into n (n = N / m) first groups of m bits each, and the m bits of the first input signal A and the second Of the input signal B, the first group propagate signal PG1, the first group generate signal GG1 and the first group propagate signal PG1 for each first group are given. N first CLA circuits of the first group hierarchy for generating the group kill signal KG1 of the above, and the above n n m CLA circuits each of p (p = n /
m) groups, each of which is provided with m first group propagate signal PG1, first group generate signal GG1, and first group kill signal KG1. , A second group propagate signal PG2 for each second group, a second group generate signal GG2, a second group kill signal KG
P second CLs of the second group hierarchy generating 2
A circuit and ... P are divided into m groups of q (q = p / m and q <m),
For each j-th group, the m-th j-1 th group propagate signal PG (j-1), the j-1 th group generate signal GG (j-1), and the j-1 th group. Given the group kill signal KG (j-1), the jth group propagate signal PGj, jth group for each jth group
Group generate signal GGj, the jth group kill signal KGj, and the qth jth CLA circuits in the jth group hierarchy, and the qth jth group propagate signals PGj, jth group propagation signals PGj. Group generate signal G
Gj and the jth group kill signal KGj are input, and the carry signal CN is output, and one j + 1th CLA circuit of the j + 1th group hierarchy is provided.

[0012]

BEST MODE FOR CARRYING OUT THE INVENTION An embodiment of the present invention will be described below with reference to the drawings.

The CLA circuit according to the present embodiment classifies the total number of bits N (N is an integer of 1 or more) into a group of a plurality of bits m (m is an integer of N or less), and each bit in each group. Group propagate signal PG, group generate signal GG in units of a group composed of a plurality of bits, using the propagate signal P <i>, generate signal G <i>, and kill signal K <i> of It is characterized in that the group kill signal KG is generated and the finally required carry signal CN-1 of the most significant bit is obtained using these signals.

For example, when N = 16 and m = 4, the input signals A and B are A = (a15 to a12, a11 to a8, a7 to a4, a3 to a0) (1) B = (b15 to b12) , B11 to b8, b7 to b4, b3 to b0) (2).

Then, carry C3, C for each group
7. Find C11. C3 = f (a3-a0, b3-b0) (3) C7 = f (a7-a4, b7-b4) + C3 (4) C11 = f (a11-a7, b11-b7) + C7 (5) C15 = f (A15-a11, b15-b11) + C11 (6)

In order to obtain such a carry for each group, it is necessary to generate a signal PG / GG / KG for each group from the signal P / G / K for each bit in the group. First CLA circuit C for performing calculation
The configuration of LA (1) is shown in FIG. The first CLA circuit CLA (1) outputs the signals PG / GG / KG as a group composed of 4 bits. In a circuit not shown, the signals P <3: 0> (= P <3> to P <0>) / G <3: 0> (= G <3
> To G <0>) / K <3: 0> (= K <3> to K <0>) are generated.

Then, the first CLA circuit CLA (1)
Is an AND circuit AN1 that generates a signal PG and a priority encoder P that generates a select signal S <3: 0>.
E and a selector SEL1 for generating the signals GG and KG according to the select signal S <3: 0>.

The AND circuit AN1 is given all the P <3: 0> signals, performs the AND operation as shown in the equation (7), and outputs the result as PG and / or a PGB signal which is the inverted PG. . PG = P <3> * P <2> * P <1> * P <0> (7) PGB = / (P <3> * P <2> * P <1> * P <0>) = / P <3> + / P <2> + / P <1> + / P <0> = PB <3> + PB <2> + PB <1> + PB <0> (8)

This is only when the 0th bit to the 3rd bit are propagating, that is, when P <3: 0> = "1", the carry signal Cin carried from the preceding group is unchanged. This corresponds to transfer to the subsequent group as the carry signal CG in the group. In this case, the signals GG and KG are both "0".

At least 1 of all P <3: 0> signals
If one is "0", the operation of the priority encoder PE is required. The priority encoder PE is a NOR circuit NR11 to which the inverted priority signal PB <3: 0> is input, inverters IN11 and IN12 to which the output of the circuit NR11 is input, and a NOR circuit to which the outputs of the inverters IN12 and IN21 are input. N
R12, NOR circuit NR21 to which the inverted priority signal PB <3: 1> is input, inverters IN21 and IN22 to which the output of the circuit NR21 is input, and inverter IN
NOR circuit NR2 to which the outputs of 22 and IN31 are input
2 and the NOR circuit NR3 to which the signals PB <3: 2> are input
1. Inverter IN3 to which the output of the circuit NR31 is input
1 and IN32, NOR circuit NR32 to which outputs of inverters IN32 and IN42 are input, and inverters IN41, IN42 and IN4 to which signal PB <3> is input
3. The NOR circuit NR41 receives the output of the inverter IN43 and the ground potential "0". And
Select signals S <0> to S <3> are output from the NOR circuits NR12, NR22, NR32, and NR41, respectively.

The priority encoder PE uses at least one of the signals P <3: 0> being "0" (or at least one of the signals PB <3: 0> being "1"). ) Determines which of the signals G <3: 0> and K <3: 0> should be the signals GG and KG as a group. Here, the signal PB <3> is searched in order, and if the signal PB <3> is “1”, the signal S <
3> = “1” and all others are “0”. Signal PB <3
When> is “0” and the signal PB <2> is “1”, the signal S <2> = “1” and all others are “0”. In this way, one of the signals S <3: 0> becomes "1" and the other signals become "0".

Such a select signal S <3: 0> is input to the selector SEL1. The selector SEL1 has multiplexers MUX1 and MUX2. And
The select signal S <3: 0> is input to each of the multiplexers MUX1 and MUX2, the bit signals G <3: 0> and K <3: 0> of “1” are selected, and the signals as a group respectively. It is output as GG and KG.

Here, the signals GG and KG are expressed by the following equations. GG = P <3> * P <2> * P <1> * G <0> + P <3> * P <2> * G <1> + P <3> * G <2> + G <3> (9 ) KG = P <3> * P <2> * P <1> * K <0> + P <3> * P <2> * K <1> + P <3> * K <2> + K <3> ( 10)

When the signals GG and KG are expressed by using the select signals S <3: 0>, they are as follows.

First, the following logical expression is introduced. Q <0> = PG = P <3> * P <2> * P <1> * P <0> = / (PB <3> + PB <2> + PB <1> + PB <0>) (11) Q <1> = P <3> * P <2> * P <1> = / (PB <3> + PB <2> + PB <1>) (12) Q <2> = P <3> * P <2 > = / (PB <3> + PB <2>) (13) Q <3> = P <3> = / PB <3> (14) / Q <0> = PGB = / (P <3> * P <2> * P <1> * P <0>) = PB <3> + PB <2> + PB <1> + PB <0> (15) / Q <1> = / (P <3> * P <2 > * P <1>) = PB <3> + PB <2> + PB <1> (16) / Q <2> = / (P <3> * P <2>) = PB <3> + PB <2> (17) / Q <3> = / P <3> = PB <3> (18) S <0> = Q <1> * / Q <0> (19) S <1> = Q <2> * / Q <1> (20) S <2> = Q <3> * / Q <2> (21) S <3> = 1 * / Q <3> (22) Where, P <3> * PB Since <3> = P <2> * PB <2> = P <1> * PB <1> = P <0> * PB <0> = “0” (23), Serial (11) to (18) are as follows. S <0> = P <3> * P <2> * P <1> * (PB <3> + PB <2> + PB <1> + PB <0>) = P <3> * P <2> * P <1> * PB <0> (24) S <1> = P <3> * P <2> * (PB <3> + PB <2> + PB <1>) = P <3> * P <2> * PB <1> (25) S <2> = P <3> * (PB <3> + PB <2>) = P <3> * PB <2> (26) S <3> = 1 * PB <3> = PB <3> (27)

Further, PB <3> * G <3> = G <3>, PB <2> *
G <2> = G <2>, PB <1> * G <1> = G <1>, PB <0> * G <0
From> G = <0>, the following relation is obtained. S <0> * G <0> + S <1> * G <1> + S <2> * G <2> + S <3> * G <3> = P <3> * P <2> * P <1 > * PB <0> * G <0> + P <3> * P <2> * PB <1> * G <1> + P <3> * PB <2> * G <2> + PB <3> * G <3> = P <3> * P <2> * P <1> * G <0> + P <3> * P <2> * G <1> + P <3> * G <2> + G <3> = GG (28) S <0> * G <0> + S <1> * G <1> + S <2> * G <2> + S <3> * K <3> = P <3> * P <2 > * P <1> * PB <0> * K <0> + P <3> * P <2> * PB <1> * K <1> + P <3> * PB <2> * K <2> + PB <3> * K <3> = P <3> * P <2> * P <1> * K <0> + P <3> * P <2> * K <1> + P <3> * K <2 > + K <3> = KG (29) Therefore, the following equations (30) and (31) are obtained.

[0027]   GG = S <0> * G <0> + S <1> * G <1> + S <2> * G <2> + S <3> * K <3> (30)   KG = S <0> * K <0> + S <1> * K <1> + S <2> * K <2> + S <3> * K <3> (31)

As shown in the above equations (8), (24) to (27) and FIG. 1, the select signals S <3: 0> are PB <
It is a logic called a priority encoder that takes 3: 0> as input.

That is, as described above, PB <3>, PB <2
>, PB <1>, PB <0> in this order, PB <i> =
When "1" (however, i = 3 to 0), S <i> =
“1”, other S <j> are “0” (where j is 3 to 0 other than i), and PBG = “1”.

When all of PB <3>, PB <2>, PB <1> and PB <0> are “0”, all S <i> = PGB = “0”.

Therefore, the equations (30) and (31) are expressed by the signal G
Each logic for generating G / KK has a select signal S <3: 0 among four signals G <3: 0> and K <3: 0>.
> Means that it is a multiplexer (4-1 MUX).

As described above, the first CLA circuit CLA
(1) shows the AND circuit AN1 and the priority encoder P in units of a group of 4 bits.
E, a selector SEL1 are provided, and a priority signal PG, a generate signal GG, and a kill signal KG in units of groups are generated.

Here, the first CLA circuit CLA (1) has a configuration for generating all the signals PG, GG, and KG. However, it may be configured to generate the signals PG and GG, or the signals PG and KG.
When generating the signals PG and GG, the selector SEL1
Has only a multiplexer MUX1 and signals PG and K
When generating G, it has only multiplexer MUX2.

Next, the second CLA circuit CLA (2) will be described.

The second CLA circuit CLA (2) is different from the first CLA circuit CLA (1) in that not only the group propagate signal PG, the group generate GG, and the group kill KG in the group, Group carry signal CG using these signals PG, GG and KG
And output. As a specific configuration, as shown in FIG. 2, the AND circuit AN1 and the priority encoder PE have the same configuration as that of the first embodiment, but the configuration of the selector SEL11 is different, and further AND
Circuits AN11 and AN12 are added.

The selector SEL11 is a multiplexer MU.
Multiplexer MUX1 having X11 and MUX12
1 is the select signal S <3: 0> output from the priority encoder PE, G <3: 0> for each bit, the carry signal C from the lower group, and the signal PG output from the AND circuit AN1. Is entered. Multiplexer MU
X12 is a select signal S <3: 0> and K <3: 0> for each bit.
And the inverted carry signal CB from the lower group
And the signal PG are input.

As described above, when all the signals P <3: 0> are "1", the signal PG of "1" and the signal PGB of "0" are output. In this case, the carry signal C and the inverted carry signal CB from the lower group are directly output as the group carry signal CG and the inverted group carry signal CGB of the group. In this case, the signals PGB are all "0". Therefore, the AND circuits AN11 and AN12, to which the signal PGB is input, output the signals GG and KG of "0", respectively.

When at least one of the signals P <i> is "0", the signal PG is "0" and the signal PGB is "1". In this case, the signals CG and CGB are generated by the signal G <i> corresponding to the select signal S <i> having the value “1” of the signals G <3: 0> and K <3: 0>, respectively. , K <i
> Is first selected, and this is output as signals CG and CGB as a group, respectively. further,
The AND circuit AN11 has a signal PGB of "1" and a signal CG.
And are input, and the signal GG is output. AND circuit A
The signal PGB of "1" and the signal CGB are input to N12, and the signal KG is output.

The signal CG is expressed as a logical expression as follows. CG = PG * Cin + GG (32) CGB = / CG = PG * / Cin + KG (33)

Using the above equations (30) and (31),   CG = PG * Cin + S <0> * G <0> + S <1> * G <1> + S <2> * G <2>           + S <3> * G <3> (34)   CGB = PG * / Cin + S <0> * K <0> + S <1> * K <1> + S <2> * K <2>           + S <3> * K <3> (35)

Here, the above (7), (24) to (27)
From the formula, the only signal among the signals PG and S <3: 0> is “1”.
And all other signals become "0".

Therefore, the above equations (34) and (35) are
The logic for generating the group carry signals CG and CGB is
It is a 5-1 multiplexer that selects five signals Cin and G <3: 0> and five signals / Cin and K <3: 0> by five selection signals PG and S <3: 0>. Become. Then, from equations (9), (10), (32), and (33), CG * PGB = GG (36) CGB * PGB = KG (37)

Therefore, as described above, PG = “0”
When (PGB = "1"), CG = G from the equation (36)
G and KG = CGB.

FIG. 3 shows a time chart of input / output signals in the second CLA circuit CLA (2). Here, the solid lines indicate the levels of the signals P, G, and K, and the dotted lines indicate the levels of the inverted signals PB, GB, and KB, respectively.

The signals P <3: 0>, G <3: 0>, K <3: 0> and the group carry signal C from the lower group are clocks CLK.
The group propagate signal PG, the group generate signal GG, the group kill signal KG, and the group carry signal CG are output at the same timing with an operation delay time.

Here, the second CLA circuit CLA (2) has a configuration for generating all the signals PG, GG, KG, CG, CGB. However, the signals PG, GG and C
It may be configured to generate G or the signals PG, KG and CGB. When generating the signals PG, GG and CG, the selector SEL1 is the multiplexer MU.
It has only X1, and accordingly, the AND circuit AN11 is used to generate the signal CG. When generating the signals PG, KG and CGB, only the multiplexer MUX2 is provided and A
The signal KG is generated using the ND circuit AN12.

Next, the above-mentioned first CLA circuit CLA
Using (1) and the second CLA circuit CLA (2),
FIG. 4 shows the configuration when a 32-bit CLA circuit is configured. This CLA circuit has three group hierarchies
It is divided into 2 "and is the first in the group hierarchy" 0-1 ".
The CLA circuit CLA (1) of "2" is used for the group hierarchy "2"
Then, the second CLA circuit CLA (2) is used.

In the group hierarchy "0", groups 7-0
Signals PG <7>, GG <7>, KG in each CLA circuit
<7>, PG <6>, GG <6>, KG <6>, ..., PG <0>, GG <
0> and KG <0> are generated.

In the group hierarchy "1", four groups 7 to 4 and groups 3 to 0 are combined into one, and 16-bit signals PGG <1>, GGG <1>, and KG are combined.
G <1> to PGG <0>, GGG <0>, and KGG <0> are generated.

In the group hierarchy "2", signals PGGG, GGGG, KGGG in which all 32 bits are combined are generated, and further a final carry signal CGGG is generated. This signal CGGG corresponds to the carry signal C <31> of the 32nd bit.

FIG. 5 shows the time required for calculation in the CLA circuit configured as described above. When the delay times in the group layers “0”, “1”, and “2” are the same T11, the total is T11 * 3. This calculation delay time T11 * 3 means that only delay times for three layers are accumulated. Therefore, according to the present embodiment, the calculation time is shortened as compared with the case where the calculation delay time for each group is accumulated as in the conventional CLA circuit shown in FIG.

Next, the CLA circuit CLA shown in FIG.
AND circuit AN1 included in (1), priority
An example of a specific circuit configuration of each of the encoder PE and the selector SEL1 is shown.

The AND circuit AN1 is a combination of an inverter and a NAND circuit generally known as a pseudo-NMOS type, as shown by a circuit symbol in FIG. 6A. The circuit diagram is shown in FIG. While the clock CLK is at low level, the N-channel transistor N1 connected between the ground terminal and the node ND1 is turned on,
Discharge the node ND1. When the clock CLK becomes high level, the P-channel transistor P1 turns on and the N-channel transistor N1 connected between the node ND1 and the ground terminal turns off.

Signals P <3: 0> are inverter IN
Node ND after being inverted through 104-IN101
1 and the node ND2 are connected to the gates of N-channel transistors N14 to N11, respectively.
Only when all of the signals P <3: 0> are "1", the transistors N14 to N11 are all turned off, and the node ND1 is charged by the transistor P1 and outputs the signal PG of "1". At least one of the signals P <3: 0>
When one is "0", the transistor receiving this signal is turned on and the node ND1 is connected to the ground terminal,
The signal PG of "0" is output. The transistor P1 is a P-channel transistor having a small size such that a voltage close to the ground terminal appears at the node ND1 when at least one of the transistors N11 to N14 is turned on even when the transistor P1 is turned on. A pseudo NMOS type A that operates in synchronization with such a clock CLK
By using the ND circuit AN1, the circuit operation can be speeded up.

FIG. 7 shows an example of the circuit structure of the priority encoder PE. This encoder PE also performs a dynamic operation in synchronization with the clock CLK. Signal PB
The NOR circuit to which <3: 0> is input has P-channel transistors P11 to P14 and N-channel transistors N21 to
It is composed of N32. Power supply terminal and each node ND
P-channel transistor P11 between 11 and ND14
To P14 are connected, and the clock CLK is input to the gate. While the clock CLK is low level, the node ND1
1 to ND 14 are charged.

Transistors N21 to N24 are connected in parallel between node ND11 and node ND21, and transistor N25 is connected between node ND21 and the ground terminal. Transistors N26 to N28 are connected in parallel between the node ND12 and the node ND22, and a transistor N29 is connected between the node ND22 and the ground terminal. Transistors N30 to N31 are connected in parallel between the node ND13 and the node ND23, and a transistor N32 is connected between the node ND23 and the ground terminal. Furthermore, the nodes ND14 and ND24
A transistor N33 is connected between
A transistor N34 is connected between 4 and the ground terminal.

Transistors N25, N29, N32, N
The clock CLK is input to the gate of 34, the signal PB <0> is input to the gate of the transistor N21, the signal PB <1> is input to the gates of the transistors N22 and N26, and the signals are input to the gates of the transistors N23, N27, and N30. PB <2> is input and transistors N24, N28,
The signal PB <3> is input to the gates of N31 and N33.

While the clock CLK is at the low level, the P-channel transistors P11 to P14 are turned on and the node ND
11 to ND14 are all charged. When the clock CLK becomes high level, N-channel transistors N25, N
29, N32, N34 are turned on and the nodes ND21 to ND
24 is discharged.

A high level signal is output from the node ND11 only when all of the signals PB <3: 0> are "0", and a low level signal is output when at least one of them is "1". Then, it is inverted by the inverter IN111 and outputs the signal PGB. A high level signal is output from the node ND12 only when all of the signals PB <3: 1> are "0", and a low level signal is output when at least one of them is "1". Inverted by IN113, inverter IN11
It is input to the NOR circuit NR101 together with the output of 2 and outputs the signal S <0>. Only when all of the signals PB <3: 2> are "0", a high level signal is output from the node ND13, and when at least one of them is "1", a low level signal is output and the inverter Inverted by IN115, NOR with output of inverter IN114
It is input to the circuit NR102 and outputs the signal S <1>. When the signal PB <3> is "0", a high level signal is output from the node ND14, and when it is "1", a low level signal is output, inverted by the inverter IN117, and output from the inverter IN116. It is input to the NOR circuit NR103 and outputs the signal S <2>. Also,
The output of the inverter IN117 is the inverter IN118.
And then further inverted by the NOR circuit NR104 and output as a signal S <3>.

The multiplexers MUX1 and MUX2 included in the selector SEL1 are, for example, as shown in FIG.
The configuration shown in (b) is provided. Multiplexer M
In the UX1, the P-channel transistor P21 is connected between the power supply terminal and the node ND31, and the N-channel transistors N41 and N41 are connected between the node ND31 and the ground terminal.
42 are connected in series, N-channel transistors N43 and N44 are connected in series in parallel, N-channel transistors N45 and N46 are connected in parallel, and N-channel transistors N47 and N46 are connected in parallel.
48 is connected. Transistors N41, N43,
Signals S <0: 3> are input to the gates of N45 and N47,
The signal G <0: 3> is input to the gates of the transistors N42, N44, N46, N48.

While the clock CLK is at low level, the transistor P21 is turned on and the node ND31 is charged.
When the clock CLK becomes high level, signals S <0> and G <0>, signals S <1> and G <1>, signals S <2> and G <2>, signals S <3> and G <3. If there is at least one combination in which both are “1”, the node ND
31 goes low. The level of the node ND1 is inverted by the inverter IN121 and output as the signal GG.

The multiplexer MUX2 also has a configuration similar to that of the multiplexer MUX1.
This corresponds to the signal G <3: 0> in the UX1 replaced with the signal K <3: 0>. P between the power supply terminal and the node ND32
The channel transistor PT22 is connected to the node ND
N-channel transistor N5 is connected between 32 and the ground terminal.
1 and N52 are connected in series, and in parallel with this, N-channel transistors N53 and N54 are connected in series,
In parallel with this, N-channel transistors N55 and N56
Is connected in parallel with the N-channel transistor N5.
7 and N58 are connected. Transistor N51,
The signal S <0: 3> is input to the gates of N53, N55, and N57, and the transistors N52, N54, N56, and N58 are input.
The signal K <0: 3> is input to the gate of the.

While the clock CLK is at low level, the transistor P21 is turned on and the node ND31 is charged.
When the clock CLK becomes high level, the signals S <0> and K <0>, the signals S <1> and K <1>, the signals S <2> and K <2>, the signals S <3> and K <3. If there is at least one combination in which both are “1”, the node ND
31 goes low. The level of the node ND31 is inverted by the inverter IN121 and output as the signal KG.

As the circuit for generating the P, G, K signals for each bit, for example, the circuits shown in FIGS. 9A to 9D may be used. The circuit shown in FIG. 9A is given two input signals A and B (/ A and / B), performs a logical sum operation between A and B to generate and output a signal P. To do. The clock CLK is input to the gate of the P-channel transistor P31, and the node ND41 is charged during the low level. When the clock CLK becomes high level, the N-channel transistor N63 is turned on by inputting this level to the gate. N-channel transistors N61, N6
Signals A, / B, to the gates of 2, N64, and N65, respectively.
/ A and B are input, and the node ND41 charged according to the combination of these levels maintains the charged state or discharges. The level of the node ND41 is inverted by the inverter IN131 and output as the signal P.

The circuit shown in FIG. 9B outputs a signal PB obtained by adding inversion to the logical sum between the two input signals A and B. In this circuit, the combinations A, / B, / A, B of signals input to the gates of the transistors N61, 62, 64, 65 in the circuit of FIG. 9A are changed to A, B, / A, / B.
It is equivalent to the one replaced by.

The circuit shown in FIG. 9C is to perform a logical product operation between A and B and output a signal G.
A clock CL is applied to the gate of the P-channel transistor P33.
K is input, and the node ND43 is charged during the low level. When the clock CLK becomes high level, this level is input to the gate of the N-channel transistor N83 and turned on. The signals A and B are input to the gates of the N-channel transistors N81 and N82, respectively, and the node ND43 charged according to the combination of these levels maintains the charged state or discharges. The level of the node ND43 is inverted by the inverter IN133, and the signal G
Is output as.

The circuit of FIG. 9 (d) performs an exclusive OR operation between A and B and outputs a signal K. This circuit
The combination of signals A and B input to the gates of the transistors N81 and 82 in the circuit of FIG.
It corresponds to the one replaced with B.

Further, an example of a circuit for generating the carry signal Cin for each bit synchronized with the clock CLK and the waveforms C and CB of the inverted carry signal / Cin is shown in FIGS. 10A and 10B, respectively.

As shown in FIG. 10A, the waveform C of the carry signal Cin can be generated by inputting the clock signal CLK and the carry signal Cin to the AND circuit AN21 and performing a logical product operation. it can. In addition, FIG.
As shown in, the waveform CB of the carry signal / Cin is
The clock signal CLK and the carry signal / Cin inverted by the inverter IN141 are input to the AND circuit AN22,
It can be generated by performing a logical product operation.

The above-described embodiment is an example and does not limit the present invention. For example, in the circuit configuration shown in FIG. 4, the operation of 32 bits is divided into groups of 4 bits as a whole, and the signals PG, GG, and KG for each group are obtained in three group layers, and finally, The carry signal CGGG is obtained. However, the number of bits and the number of layers for each group can be set differently depending on the number of bits.

The specific circuit configurations of the AND circuit AN1, the priority encoder PE, and the selector SE are examples, and various modifications are possible.

[0072]

As described above, in the CLA circuit of the present invention, the signals P, G, K of m bits are given to the group of m bits, and the signals PG, GG, and Since the KG is obtained, the calculation delay time can be shortened by using the signals PG, GG, and KG obtained for each group in a plurality of groups even when the carry of an operation having a large number of bits is obtained.

[Brief description of drawings]

FIG. 1 is a circuit diagram showing a configuration of a first CLA circuit according to an embodiment of the present invention.

FIG. 2 is a circuit diagram showing a configuration of a second CLA circuit according to the same embodiment.

FIG. 3 is a time chart showing the waveform of each signal in the second CLA circuit.

FIG. 4 is a first and second CLA in the above embodiment.
3 is a circuit diagram showing a circuit configuration when a 32-bit CLA circuit is configured using the circuit. FIG.

5 is an explanatory diagram showing a calculation delay time in the CLA circuit shown in FIG.

FIG. 6 is a circuit diagram showing an example of a circuit configuration of an AND circuit AN1 in the first and second CLA circuits.

FIG. 7 is a circuit diagram showing an example of a circuit configuration of a priority encoder PE in the first and second CLA circuits.

FIG. 8 is a selector SEL1 in the first CLA circuit.
3 is a circuit diagram showing an example of the circuit configuration of FIG.

FIG. 9 shows signals P, G, for each bit in the same embodiment.
The circuit diagram showing an example of the composition of the circuit which generates K.

FIG. 10 is a carry signal C and an inverted carry signal C for each bit synchronized with the clock CLK in the embodiment.
The circuit diagram showing an example of the composition of the circuit which generates the waveform of B.

FIG. 11 is a circuit diagram showing a configuration of a conventional 32-bit CLA circuit.

FIG. 12 is a circuit diagram showing a configuration of a CLA circuit of group 0 in the CLA circuit.

FIG. 13 is a circuit diagram showing a configuration of a 4-bit CLA circuit that constitutes the same CLA circuit.

FIG. 14 is an explanatory diagram showing a calculation delay time in the CLA circuit.

[Explanation of symbols]

PE priority encoders AN1, AN11, AN12, AN21 to AN22 A
ND circuits NR11, NR12, NR21, NR22, NR31,
NR32, NR41, NR101 to NR104 NOR
Circuits IN11, IN12, IN21, IN22, IN31,
IN32, IN41 to IN43, IN101 to IN10
4, IN111 to IN118, IN121, IN12
2, IN131, IN133, IN141 Inverters MUX1, MUX2, MUX11, MUX12 Multiplexers SEL1, SEL11 Selectors P1, P11, P21 to P22, P31, P33 P channel transistors N1, N11 to N14, N21 to N34, N41 to N4.
8, N51 to N58, N61 to N65, N81 to N83
N-channel transistors ND1, ND2, ND11 to ND14, ND21 to ND
24, ND31 to ND32, ND41, ND43 nodes

Claims (4)

(57) [Claims] 1. A propagate signal P of m bits (m is an integer of 1 or more), a generate signal G and a kill signal K.
Of at least one of the groups, and the group propagate signal PG for the group is configured by m bits.
And a carry look ahead (hereinafter referred to as CLA) circuit for generating at least one of the group generate signal GG and the group kill signal KG, wherein the propagate signal P has a first predetermined value, or When all the inverted propagate signals PB have the second predetermined value, the group propagate signal PG having the first predetermined value and / or the inverted group propagate signal PGB having the second predetermined value are output. The output logic circuit and the propagating signal P and / or the inverted propagating signal PB are sequentially searched from the most significant bit m to the lower, and the propagating signal P is first searched for the second signal. , Or the first predetermined value of the inverted propagate signal PB appears first i (i
Is an integer greater than or equal to 1 and less than or equal to m), the select signal S <i-1> for selecting the second bit is generated, and the second predetermined value does not appear in any of the bits of the propagate signal P. , Or the priority signal that outputs “0” to the select signal S <i-1> in order to prevent any bit from being selected when the first predetermined value does not appear in any bit of the inverted propagate signal PB. When an encoder and the select signal S <i-1> are input, and “1” is input to the select signal S <i-1>, among the generate signal G and / or the kill signal K , The i-th generate signal G <i-1> and / or the kill signal K <i-
1> to select the group generate signal G
G and / or output as the group kill signal KG,
When "0" is input to all of the select signals S <i-1>, the group generate signal GG having the second predetermined value and / or the group kill signal KG.
A CLA circuit comprising: a selector for outputting 2. A carry propagate signal C, a propagate signal P for every m bits, and at least one of a generate signal G and a kill signal K are given, and a group propagate signal for the group composed of m bits. PG
And a group carry signal CG and at least one of a group generate signal GG and a group kill signal KG, wherein the propagate signal P has a first predetermined value, or inversion. Outputs the group propagate signal PG having the first predetermined value and / or the inverted group propagate signal PGB having the second predetermined value when all the propagate signals PB have the second predetermined value. And a logical circuit for performing the above-mentioned propagation, and / or the inverted propagation signal PB are sequentially searched from the m-th most significant bit to the lower order, and the first of the propagation gate signals P is the second. The i-th bit in which the predetermined value appears or the first predetermined value appears in the inverted propagate signal PB is selected. To generate the select signal S <i-1>, and when the second predetermined value does not appear in any bit of the propagate gate signal P, or in any bit of the inverted propagate gate signal PB. When the first predetermined value does not appear, a priority encoder that outputs "0" to all of the select signals S <i-1> so as not to select any bit, and the select signal S <i-1> And "1" is input to the select signal S <i-1>, the i-th generate signal G <i-1> of the generate signal G and the kill signal K is input. And kill signal K <i-1>,
When the group carry signal CG and the inverted group carry signal CGB are respectively output and "0" is input to all of the select signals S <i-1>, the group propagate signal PG or the inverted group propagate signal is output. A CLA circuit comprising: a selector that outputs the carry signal C as the group carry signal CG in response to a signal PGB. 3. The logic circuit has an m-bit input AND circuit, receives the propagate gate signal, performs an AND operation, and outputs the group propagate gate signal PG. Alternatively, the CLA circuit described in 2. 4. The carry signal CN of the most significant N-th bit necessary for adding a first input signal A and a second input signal B having a total N (N is an integer of 1 or more) bits. A CLA circuit for obtaining the N bits, wherein the N bits are n (n is an integer of 1 or more, and n = N / m) first n bits each having m (m is an integer of 1 or more) bits.
The first input signal A and the second input signal B of m bits for each propagate signal P, generate signal G, and kill signal K for each first group. A first group propagate signal PG1 and a first group generate signal GG for each group of 1
1, n first CLA circuits of the first group hierarchy for generating the first group kill signal KG1, and each of the n n CLA circuits are p (p is an integer of 1 or more,
(p = n / m) groups, and m first group propagate signals PG for each second group.
1, the first group generate signal GG1 and the first group kill signal KG1 are given, and the second group propagate signal PG2 and the second group propagate signal PG2 for each second group are supplied.
Group generation signal GG2 and second group kill signal KG2 of p second CLA circuits of the second group hierarchy and ... P q units of q units (q is 1 or more). Is an integer and is divided into q = p / m and q <m) groups,
For each j-th (j is an integer of 1 or more) group, the m-th j-1th group propagate signal PG (j-
1), the j-1th group generate signal GG
(J-1), the (j-1) th group kill signal KG (j
-1) is given to generate j-th group propagate signal PGj, j-th group generate signal GGj, and j-th group kill signal KGj for each j-th group, q-th group hierarchy A j-th CLA circuit, q-th j-th group propagate signal PGj, a j-th group generate signal GGj, and a j-th group kill signal KGj, and outputs the carry signal CN. One j + 1th C in the j + 1 group hierarchy
A CLA circuit comprising: a LA circuit.