JPH0610788B2 - Carrier propagation circuit - Google Patents

Description

The present invention relates to a carry propagation circuit for an arithmetic device, and more particularly to a carry propagation circuit suitable for a high speed arithmetic device.

[Conventional technology]

A conventional carry propagation circuit is an exclusive OR X _{i of} N-bit (N ≧ 1) signals X _i and Y _i expressed in binary as described in JP-A-60-17167. A signal of X _i · Y _i of Y _i and a logical product is generated for each bit and input to the carry propagation circuit (i = 0, 1, ... N−
1). Further, a method of a high-speed carry propagation circuit has been studied based on these inputs (for example, the conditional sum method). However, by giving redundant logic to the input data of the carry propagation circuit to speed up the signal generation circuit,
Moreover, no consideration was given to the point of collectively generating multi-bit propagation components using it.

Further, FIG. 7 shows a general example of 8-bit carry propagation.

The signal here is made with the logical product of EOR.

EOR is a logic circuit having a larger number of stages than the logical product.

[Problems to be solved by the invention]

The above-mentioned prior art does not consider the logic of the input signal generation circuit of the high-speed carry propagation circuit, and the delay time of the carry propagation circuit becomes the critical path of the arithmetic unit, so the calculation time is restricted in this part. There was a problem of being lost.

Further, the conditional sum method is used as a method for shortening the operation time, but in that case, there is a problem that the number of operation devices becomes large and the hardware increases.

An object of the present invention is to simplify the relationship between the input data generation circuit and the carry propagation circuit, to carry out carry propagation at high speed with only a small increase in hardware, and to increase the processing time of the arithmetic unit.

[Means for solving problems]

The feature of the first invention for achieving the above object is to provide an N-bit (N ≧ 1) signal X _i (i = 0 to 0) represented in binary.
In the circuit for propagating a carry generated during the operation of the N-1) and N-bit signal Y _i which is expressed by binary logical sum signal X _i between the signal X _i and the signal Y _i for each bit + Y _i , and the signal X _i and the signal Y _{i for} each bit
And a logical calculation unit for calculating a logical product signal X _i Y _i , and a pair of main terminals and a control terminal for controlling opening and closing between the pair of main terminals based on the logical sum signal X _i + Y _i. And N first electronic switches S1 _i each having a pair of main terminals connected in series, a pair of main terminals and the pair of main terminals based on the logical sum signals X _i and Y _i Control terminals for controlling opening and closing of the first electronic switch S and the pair of main terminals, respectively.
It is to have N second electronic switches S2 _i connected between one of the pair of main terminals of 1 _i and a predetermined potential.

The feature of the second invention is that an N-bit (N ≧ 2) signal X _i (i
= 0 to N-1) and an N-bit signal Y represented in binary
In the circuit for propagating a carry generated during the operation of the _i, every 2 bits, logical sum signal of the signal _{X j (j = 2i ≦ N} ) and the signal Y _j X _j + Y _j, a signal X _{j + 1} signal Y _{j + 1} logic sum signal of the _{X j + 1 + Y j +} 1, the logical sum signal X _j + Y _j and the logical sum signal _{X j + 1 + Y j +} 1
AND signal _{(X j + Y j) ·} (X j + 1 + Y j + 1), the logical product signal of the signal X _j and the signal Y _j X _j · Y _j signal X _j-1 and the signal Y with _{j- 1} and the logical product signal _{X j-1 · Y j-} 1, and the logical product signal X _j · Y _j and the aND signal X _j-1 · a
Y logical sum (X _j · Y _j) of the _{j-1 + (X j-} 1 · Y j-1) and the logic calculation unit for calculating a pair of main terminals and said logic product signal (X _j + Y _j ) ・ (X _{j + 1}
+ Y _{j + 1} ), and N / 2 first electronic switches each having a control terminal for controlling opening / closing between the pair of main terminals, and the pair of main terminals are connected in series, respectively. S1 _j
And a pair of main terminals and the logical sum signal (X _j · Y _j ) + (X _j-1
Y _j-1 ) and a control terminal for controlling opening / closing between the pair of main terminals, and the pair of main terminals are respectively connected to the pair of main terminals of the first electronic switch S1 _j . It is provided with (N / 2) +1 second electronic switches S2 _j connected between one side and a predetermined potential.

[Operation] In the first and second aspects of the present invention, the number of logic stages in the logic planning unit is equal, so that the speed can be increased.

Further, in the second invention, the number of electronic switches S1 _j and S2 _j may be N / 2, respectively, and the carry is propagated at high speed.
In addition, the circuit can be downsized.

〔Example〕

 Examples of the present invention will be described below.

A 64-bit adder 200 is shown in FIG. Adder 20
0 is a 64 (N = 64) bit addend X _i (i = 0 to N−)
1) and a 64-bit augend Y _i (i = 0 to N−1) for fixed-point arithmetic operation, and an adder for outputting a 64-bit result. A Y register 211 for holding a number, a carry input signal generation unit 201 for executing addition, a carry propagation unit 202, a carry generation circuit 203, an EOR (exclusive OR) circuit 215,
A W register 216 for holding the result, and further four signal bundles A _{0 to} A ₆₃ from the carry input signal generation circuit 201.
B _{0 to} B ₆₃ , C _{0 to} C ₃₁ , and D _{0 to} D ₃₉ are connected to each circuit.

The carry propagation circuit of the present invention is composed of a part of the logic calculation section of the carry input signal section 201 and the carry propagation section 202.

The operation of the adder circuit 200 shown in FIG. 2 will be specified. Addition X
_i is held in the X register 210, and the augend Y _i is held in the Y register 211. When the execution starts,
The values of the registers 210 and 211 are sent to the carry input signal generation unit 201. Here, four signals are generated.
Two of which are inputted through the signal beam _{C 0 ~C 31, D 0 ~D} 39 calculated by the logic calculation unit in the carry propagation section 202. One of the remaining two is input to carry generation circuit 203 and EOR circuit 215 through signal lines A _{0 to} A ₆₃ . The remaining one is input to the carry generation circuit 203 through the signal lines B _{0 to} B ₆₃ .

The values input through the signal lines C _{0 to} C ₃₁ and D _{0 to} D ₃₉ are propagated at high speed by the carry propagating unit 202 to generate a carry for each 8 bits. 7 bits of the value generated for each 8 bits are input to the carry generation circuit 203 through the signal lines E _{0 to} E ₆ . The last 1 bit is the signal line E ₇
Through the adder 200.

The carry generation circuit 203 includes a carry input signal generation circuit 20.
The signal from 1 and the signal from the carry propagation circuit 202 are input. Based on these inputs, carry generation for each 8 bits is performed. The signal generated here is input to the EOR circuit 215 through the signal bundles F _{0 to} F ₆₃ .

The EOR circuit 215 takes the EOR logic of the carry generated by the carry generation circuit 203 and the sum generated by the carry input signal generation circuit 201. This value is the result of addition and is input to and held in the W register 216.

FIG. 3 shows the carry propagation section 202 and the carry generation circuit 203 of FIG.

The carrier propagation unit 202 includes a carrier input signal generation circuit 201.
From the signal bundles C _{0 to} C ₃₁ , D _{0 to} D ₃₉ . This signal bundle is further divided into 4 bits and 5 bits, and each 8-bit carry propagation circuit 301-0 to 301
Input to -7. This circuit produces a carry every 8 bits. The output of each 8-bit carry propagation circuit is input to the carry generation circuit 203 through the signal bundles E _{0 to} E ₆ .

The carry generation circuit 203 receives the above signals and the carry input signal generation circuit 201 through the signal lines A _{0 to} A ₆₃ and B _{0 to} B ₆₃ . This signal bundle is further divided into 1 bit, 8 bits, and 8 bits, and each 8-bit carry generation circuit 302
It is input to -0 to 302-7. This circuit produces a carry of 8 bits each. The output of each 8-bit carry generation circuit is input to the EOR circuit 215 through the signal bundles F _{0 to} F ₆₃ .

The carry propagation section 202 generates a carry for each 8 bits, and the carry generation circuit 203 generates a carry for each bit. Carry propagation section 202 must perform carry generation for every 8 bits at a high circuit speed. In other words, the basic operation takes time because all 64 bits must be examined and propagated from the low order. The carry generation circuit
It suffices to execute only 8-bit propagation and carry generation in it.

Therefore, in order to increase the carry propagation speed, as in the present embodiment, only the carry propagation signal for every 8 bits is accurately calculated.
The logic along the way is to use something that is redundant and easy. This enables carry propagation at high speed.

FIG. 1 shows an 8-bit carry propagation unit 301-0 in FIG. 3 and a logical calculation unit 2010 which is a part of the carry input signal generation unit 201 in FIG.

In FIG. 1, an 8-bit signal X represented in binary.
_It shows a circuit for propagating a carry generated during the operation of _i (i = 0 to 7) and an 8-bit signal Y _{i represented in} binary.

The logic calculation unit 2010 is a part of the carry input signal generation unit 201 in FIG. 2, and the signal X _j (j = 2i ≦ N in this case 0, 2, 4, 6, in every 2 bits).
OR signal X _j + Y _j 8) and the signal Y _j, signal X _{j + 1} and the logical OR signal between the signal _{Y j + 1 X j + 1} + Y j + 1, the logical sum signal X _j + Y _j and the logical AND signal with sum signal X _{j + 1} + Y _{j + 1} {C _k = (X _j + Y _j ) · (X _{j + 1} + Y _{j + 1} )}, AND signal with signal X _j and signal Y _j X _j · Y _j signal X _j-1 and signal Y _j-1 AND signal X _j-1 · Y _j-1 and AND signal X _j · Y _j and AND signal X _j-1 · Y OR signal with _j-1 signal {D _k = (X _j · Y _j ) + (X _j-1 ·
Y _j-1 )} is calculated. here Is. N / 2 first electronic switches S1 _j (j = 2
i ≦ N) is a logical product signal C _k = (X _j + Y _j ) · (X _{j + 1} ) with a pair of main terminals.
+ Y _{j + 1} ) and a control terminal for controlling opening / closing between the pair of main terminals, and the pair of main terminals are connected in series to each other (N / 2) +1 second electrons Switch S2
_j (j = 2i ≦ N) is a pair of main terminals and the logical sum signal D _k = (X _j · Y _j ) +
And a control terminal for controlling opening and closing between the pair of main terminals based on (X _j-1 · Y _j-1 ), and the pair of main terminals are respectively connected to the pair of the first electronic switch S1 _j . It is connected between one of the main terminals and a predetermined potential GND.

Here, the first electronic switch S1 _j and / or the second electronic switch S2 _j is composed of a MOS transistor, preferably a field effect transistor such as an NMOS transistor.

The first electronic switch S1 _j of the NMOS transistor is closed (ON) when the AND signal C _k is at “high” level, and is open (OFF) when it is at “ow” level.

Also, the second electronic switch S2 of the NMOS transistor
_j is closed (ON) when the logical sum signal D _k is at "high" level
And becomes open (OFF) at the “ow” level.

In the first electronic switch S1 _j and the second switch S2 _j ,
If the second electronic switch S2 _j is conductive (ON),
Since the first electronic switch S1 _j may be open or closed, it does not malfunction.

This circuit is a dynamic circuit. Before the operation of this circuit, the signal line 111
Is pre-charged. During operation, the 8-bit carry propagation is performed by stopping the precharge, setting the clock CK to "High", and checking whether or not the charge of the signal line 111 is _extracted by the MOS transistor switch S3 _j . It should be noted that this circuit 301-0 is conventionally used for 4-bit propagation, and carries out 8-bit carry propagation by changing the input signal. That is, the calculation calculation unit 2010 is configured to perform NAND, NOR
The number of stages in this portion is the same as that of the conventional one, and the 4-bit carry propagation time and the 8-bit carry propagation time can be made equal only by changing the input signal.

Precharge sense circuit 110 is provided with a bipolar transistor S4, S4 based on the one main terminal of the first electronic switch S1 _6, the emitter of S4, a predetermined potential GND, and the collector of S4 are PMOS transistors It is connected to the power supply potential via the S5 _1.

The precharge sense circuit 110 and other specific examples are described in JP-A-60-175167, and can be applied to this embodiment.

In this embodiment, the dynamic circuit is shown, but it can be easily applied to the static circuit in the same manner.

FIG. 4 shows the carry input signal generator 201 of FIG.
64-bit data is input from the registers 210 and 211 through the signal lines 401 and 402, respectively. This circuit
The carry propagation unit 202, the carry generation circuit 203, and the EOR circuit 215 generate necessary signals.

FIG. 5 is a circuit diagram when the carry input signal generator 201 is further divided into 8 bits. In the conventional case, the signal of the carry propagation section 202 and the signal of the carry generation circuit are the same. In the case of this embodiment, the conventional signals A _{0 to} A ₇ , B _{0 are used.}
In addition to B ₇ to B ₇ , C _{0 to} C for carrying the carrier propagation at high speed
The signals of ₃ , D _{0 to} D ₄ are also generated at the same time. C _{0 to} C ₃ ,
The logic circuit that generates the signals D _{0 to} D ₄ corresponds to the logic calculator in the present invention.

Here, the signal generation delay times of A, B, C, and D are all equivalent to two stages of gates, and E used in conventional signal generation is used.
It can be executed in parallel with the OR logic circuit, which does not extend the critical path. That is, the carry input signal generation of the present embodiment is executed simultaneously with the conventional circuit, and the carry propagation is performed at high speed.

FIG. 6 shows another embodiment.

FIG. 6 shows an 8-bit signal X _i (i
= 0 to 7) and a circuit for propagating a carry generated in the operation of an 8-bit signal Y _{i represented} in binary.

The carry propagation circuit of FIG. 6 has a logical sum signal X _i + Y _i of the signal X _i and the signal Y _i for each bit, and a logical product signal X of the signal X _i and the signal Y _i for each bit. a logic calculation section 2010 for calculating a _i · Y _i, have severally and a control terminal for controlling opening and closing of the pair of main terminals on the basis of the pair of main terminals and a logical OR signal X _i + Y _i, a pair of main Eight first electronic switches S1 _i whose terminals are connected in series, respectively, and a pair of main terminals and a control terminal for controlling opening / closing between the pair of main terminals based on the AND signal X _i · Y _i And a pair of main terminals each have a predetermined potential G via one of the pair of main terminals of the first electronic switch S1 _i and the third electronic switch S3 _i.
8 second electronic switches S2 connected between ND and
It is composed of _i and. Precharge sense circuit 11
0 and the like are the same as those in FIG. The present embodiment is an example in which the precharge sense circuit 110 is provided in units of 4 bits to propagate the carry.

The embodiment of FIG. 6 and the conventional example of FIG. 7 show the same 8-bit carry propagation circuit, but there is a difference in the signal generation method in the logical calculation unit 2010.

In FIG. 7, which is a conventional example, a signal is generated by an EOR circuit corresponding to two stages, but in FIG. 6, the gate is equivalent to one stage of only AND and OR circuits, and the logic is simple and the speed is high.

〔The invention's effect〕

According to the first and second aspects of the present invention, the logical calculation unit can generate the logical sum and the logical product, which is simple, the amount of hardware is small, and the carry speed is higher than that of the conventional exclusive OR. A propagation circuit can be obtained.

Further, according to the second aspect of the present invention, since carry input signals of 2 bits are calculated in parallel by the logic calculation unit in the operation of N bits, the switches of the carry propagation unit need only a hardware amount of about N / 2. Therefore, it is possible to obtain a carry propagation circuit capable of performing carry propagation at high speed. Conventionally, carry propagation has been a constraint on the calculation time, so that the carry propagation time is N / 2, which has the effect of speeding up the calculation time and improving the performance of the calculation device.

Further, the logic calculation unit uses only a simple basic logic circuit, which is harder than the conventional two-set arithmetic device such as the conditional sum method for speeding up. The increase in is almost neglected. So, with only a small hardware increase,
High-speed calculation is possible, and there is an effect of simplifying hardware as compared with the conventional case.

[Brief description of drawings]

FIG. 1 is an 8-bit carry propagation circuit diagram which is an embodiment of the present invention, FIG. 2 is a diagram showing an example of an adder, FIG. 3 is a diagram showing a carry propagation and carry generation circuit, and FIG. FIG. 5 is a diagram showing a carry input signal generator, FIG. 5 is a diagram showing an 8-bit carry input signal generator, and FIG. 6 is a diagram showing an 8-bit carry propagation circuit according to another embodiment of the present invention. FIG. 7 is a diagram showing a conventional example. 301-0 ... 8-bit carry propagation section, 202 ... carry propagation section, 201 ... carry input signal generation section.

 ─────────────────────────────────────────────────── ─── Continuation of front page (72) Inventor Hideo Maejima 4026, Kuji-machi, Hitachi City, Hitachi, Ibaraki Prefecture Hitachi Research Laboratory, Hiritsu Manufacturing Co., Ltd. (56) References JP-A-62-32531 (JP, A)

Claims (8)

[Claims] 1. A carry generated in the operation of an N-bit (N ≧ 1) signal X _i (i = 0 to N−1) represented in binary and an N-bit signal Y _{i represented in} binary. in the circuit of propagating, logical sum signal X _i + Y _i, and the signals X _i and the signal Y _i for each bit of the signal X _i and the signal Y _i for each bit
And a logical calculation unit for calculating a logical product signal X _i Y _i , and a pair of main terminals and a control terminal for controlling opening and closing between the pair of main terminals based on the logical sum signal X _i + Y _i. And N first electronic switches S1 _i having the pair of main terminals connected in series, and the pair of main terminals based on the pair of main terminals and the logical product signals X _i and Y _i. Control terminals for controlling the opening and closing of the terminals, each of the pair of main terminals having the first electronic switch S.
1. A carrier propagation circuit comprising: N second electronic switches S2 _i connected between one of the pair of main terminals of 1 _i and a predetermined potential. 2. A carry generated in the operation of an N-bit (N ≧ 2) signal X _i (i = 0 to N−1) represented in binary and an N-bit signal Y _{i represented in} binary. In the circuit for propagating the signal, every two bits, the logical sum of the signal X _j (j = 2i ≦ N) and the signal Y _j , the signal X _j + Y _j , and the logical sum of the signal X _{j + 1} and the signal Y _{j + 1.} Signal X _{j + 1} + Y _{j + 1} , the logical sum signal X _j + Y _j and the logical sum signal X _{j + 1} + Y _{j + 1}
AND signal _{(X j + Y j) ·} (X j + 1 + Y j + 1), the logical product signal of the signal X _j and the signal Y _j X _j · Y _j signal X _j-1 and the signal Y with _{j- 1} and the logical product signal _{X j-1 · Y j-} 1, and the logical product signal X _j · Y _j and the aND signal X _j-1 · a
Y logical sum (X _j · Y _j) of the _{j-1 + (X j-} 1 · Y j-1) and the logic calculation unit for calculating a pair of main terminals and said logic product signal (X _j + Y _j ) ・ (X _{j + 1}
+ Y _{j + 1} ), and N / 2 first electronic switches each having a control terminal for controlling opening and closing between the pair of main terminals, and the pair of main terminals are connected in series with each other. S1
_i , a pair of main terminals and the logical sum signal (X _i · Y _i ) + (X _j-1
Y _j-1 ) and a control terminal for controlling opening / closing between the pair of main terminals, wherein the pair of main terminals are respectively one of the pair of main terminals of the first electronic switch S1 _i. And (N / 2) +1 second electronic switches S2 _j that are connected between the carrier propagation circuit and a predetermined potential. 3. The first aspect of the invention as set forth in claim 1
The carrier propagation circuit, wherein the electronic switch S1 _i and / or the second electronic switch S2 _i is a field effect transistor. 4. The carry propagation circuit according to claim 3, wherein the field effect transistor is a MOS transistor. 5. The bipolar transistor according to any one of claims 1, 3, and 4, wherein the N first electronic switches S1 _i include the pair of main terminals. N first electronic switches S1 _i connected in series to the bases of the bipolar transistors, respectively, and the N second electronic switches S2 _i are connected between the pair of main terminals respectively. A carry propagation circuit comprising N second electronic switches S2 _i connected between one of a pair of main terminals of the first electronic switch S1 _i and the emitter of the bipolar transistor. 6. The first aspect of the invention as set forth in claim 2
The carrier propagation circuit, wherein the electronic switch S1 _j and / or the second electronic switch S2 _j is a field effect transistor. 7. The carry propagation circuit according to claim 6, wherein the field effect transistor is a MOS transistor. 8. A bipolar transistor according to any one of claims 2, 6, and 7, wherein the N / 2 first electronic switches S1 _j are provided with the pair of bipolar transistors. N / 2 first electronic switches S whose main terminals are connected in series to the base of the bipolar transistor, respectively.
1 _j , and the N / 2 second electronic switches S2 _j have one of a pair of main terminals of the first electronic switch S1 _j and the emitter of the bipolar transistor between the pair of main terminals. A carry propagation circuit comprising N / 2 second electronic switches S2 _j connected between and.