TWI406172B - A multi-bits parallel prefix adder and the domino logics for implementing the adder - Google Patents

Abstract

This invent is a hardware based ADDER circuit architecture which employs a special logic computation to accelerate the addition of two multi-bit inputs. Moreover, in this invent a variety of multi-bit operation which with 2 based numbers of bits can be implemented. For example, 16 bits, 32 bits, 64 bits, .... And the total logic stages can be altered by choosing a prober radix to adapt for different demand of calculation. In addition, this invent proposed an improved Domino logic circuit design which utilizes the advantages of simplified logic operation to minimize the area and speed up operating frequency of the ADDER.

Description

Multi-bit parallel prefix carry adder and domino logic circuit implementing the same

The present invention is an arithmetic addition system that can be applied to VLSI, PCB boards, or actually wired circuits to add the desired results.

The adder of the known technique is a conventional chopping carry adder (Carry Ripple Adder as shown in Figure 1). The logic is as follows: S _i = A _i ⊕ B _i ⊕ C _{i -1}

C _i = A _i . B _i + C _{i -1} . ( A _i + B _i )

Where C _i is the carry of the next bit, so that the next meta-recognition result S _i+1 can be known, and its operation is transmitted from the minimum bit carry result to the largest bit. The time spent is O(n), where n is the number of bits computed.

An improved technique is known as a carry-prefix adder (Carry Look-ahead Adder is shown in Figure 1). The following transfer bit ( P _i ) and generated bit ( G _i ) are used to process the carry value: P _i = A _i + B _i

G _i = A _i . B _i

C ₁ = A ₁ . B ₁ + C ₀ . ( A ₁ + B ₁ )= G ₁ + C ₀ . P ₁

C ₂ = A ₂ . B ₂ + C ₁ . ( A ₂ + B ₂ ) = G ₂ + G ₁ . P ₂ + C ₀ . P ₁ . P ₂

C ₃ = A ₃ . B ₃ + C ₂ . ( A ₃ + B ₃ ) = G ₃ + G ₂ . P ₃ + G ₁ . P ₂ . P ₃ + C ₀ . P ₁ . P ₂ . P ₃

By analogy, if the logic gate complexity is not considered, the carry of the largest bit can be known from the carry of the least bit, so that the operation speed can be improved. A technique can reduce the complexity of the logic gate, that is, distinguish the bit elements, and each block performs the carry processing separately. A number of carry-prefix adders have been derived, and the Parallel-Prefix Adder is more efficient than other architectures. Representative architectures include Kogge-Stone adder, Ling adder, and INTEL sparse carry prefix adder.

Figure 2 and Figure 3 are the 2 base and 4 base Kogge-Stone adder architectures, respectively, and the partitions are divided into 2 and 4 units, and the required number of stages is Where R is the base and T is the number of bits. The concept is that the partition is processed by the carry, but since the near position of each bit must be learned by the least bit carry operation, in the case of the partition carry processing, in the later stage calculation The length of the signal transmission wire path will increase step by step, and the operation time will also increase. The carry logic can be expressed as follows: 2 base: G _i,im =G _i +G _im . P _i

P _i,im =P _i~(im)

4 base: G _{i, i-3m} = G _i + G _im . P _i +G _i-2m . P _i~(im) +G _i-3m . P _i~(i-2m) P _i,i-3m =P _i~(i-3m)

It can be seen from the formula and the figure that using a larger cardinality can reduce the number of stages of the required operation, and can also reduce the calculation time.

Another improved adder architecture is called the Ling adder, and is disclosed in U.S. Patent No. 5,719,803, "High Speed Addition Using Ling's Equation and Dynamic CMOS Logic" (February 17, 1998), which discloses an increase in the use of Ling adders. The computation time of the non-critical path reduces the computation time on the critical path, thereby reducing the overall computation time. Since the formula is derived, we know that G _i = G _i . P _i , then the logic of the Kogge-Stone adder can be rewritten as: G _i,im =G _i +G _im . P _i =G _i . P _i +G _im . P _i =P _i . (G _i +G _im )=P _i . H _i

H _i =G _i +G _im

H is processed by the logic of the carry prefix tree to obtain the same result as Kogge-Stone. H _i is obtained by the logical OR operation of the Boolean function. It is known from the concept of electronics that the speed of the gate is excellent. In the "and" gate, so here will be faster to know the value of H on the critical path to complete the operation of the entire adder, but it will make the P operation speed on the non-critical path slower, but does not affect the whole The speed of the adder.

In recent years, in the "Sparse Tree Adder Circuit" (November 9, 2006 announcement) proposed by Intel Corporation in US Patent No. 0,253,523, Intel Corporation proposed to use a sparse carry prefix tree architecture to reduce the winding of the adder implementation. The complexity, as shown in Figure 4, reduces the delay of the adder by reducing the charge on the winding to reduce the delay of the adder. This architecture has been patented by Intel Corporation.

The present invention uses a special wiring method to interconnect P _i and G _i so that it can be quickly delivered to the output.

In the following description, A and B represent two input values to be calculated; S represents the calculated output value; i represents the number of bits; R represents the number of radix; T represents the total number of bits of the adder; P _{i ~( i -2)} represents P _i . P _{i -1} . P _{i -2} ; subscript G _{n , i} represents the i-th bit operation element of the nth stage; upper and lower lines Represents the inverse of G _i .

The number of stages of the adder varies with the total number of bits T and the selected value of R. Total need Level, where For the upper Gaussian symbols in mathematics, the connection methods for each level are listed below: Level 1: P _i = A _i + B _i

G _i = A _i . B _i

Let n be any positive integer.

For the i-th bit that satisfies i=R×n: G _{1, i} = G _i + G _{i -1} . P _i + G _{i -2} . P _{i ~( i -1)} + G _{i -3} . P _{i ~( i -2)} )

Level 2: Let n be any positive integer.

For the i-th bit that satisfies i=R×n:

Level 3: Let n be any positive integer.

For the i-th bit that satisfies i=R×n:

The number of stages in the middle is omitted and can be derived according to the formula.

First Level: Let n be any positive integer.

For the i-th bit that satisfies i=R×n:

First Level +1: Let n be any positive integer.

For the i-th bit that satisfies i=R×n: S _i = Psum _i for the i-th bit that satisfies i=R×n+1:

For the i-th bit that satisfies i=R×n+2:

For the i-th bit that satisfies i=R×n+3:

In the above formula, level 2 ~ The levels are organized into a table, such as Table.1, and if the subscript is negative, the logical value of the operation is 0.

When carrying the carry synthesis logic: G _i +...+G _i-(R-2)m . P _i~i-(R-3)m +G _i-(R-1)m . P _i~i-(R-2)m R represents the cardinality of the carry synthesis. If it is a traditional logic pull-down circuit, each will need R pull-down paths, and a total of R(R+1)/2 transistors are needed, but if The factorization is simplified and the logic formula is observed. It is found that the signal P _i~i-(Rn)m can be proposed one by one, n is the number of steps, and G _{i-(R-n+1)m is} removed, and the next step can be repeated. Step, then observing the circuit, after passing through the transistor controlled by the signal P _i~i-(Rn)m , an independent path of the transistor controlled by the signal G _{i-(R-n+1)m is} formed outside, By analogy, a logic pull-down circuit of Figure 9 and Schema 10 will be formed, the content of which includes carry-in combination of various cardinalities.

The adder circuit can be completed by connecting according to the above formula and matching the required combination circuit (such as an AND gate logic circuit or an OR gate logic circuit).

Taking Figure 5 as an example, the base R value is 4, and the operation logic is as shown in Table.2:

Taking Figure 6 as an example, its base R value is 8, and the operation logic is as shown in Table.3:

In order to achieve faster operation speed, we use domino logic circuit, the dynamic logic circuit has less fan-in, and the output capability is not worse than static logic. If in a pipeline processing system, dynamic logic circuit will be used. Improve the operation speed, and the dynamic domino logic circuit ensures the logic correctness in the continuous operation processing. The reason is that the dynamic logic is divided into two phases. The first phase is pre-charging. At this time, the output is logic "1". The second phase is logic operation. The pull-down logic circuit starts to work, and the output is determined according to the input logic. Logic "1" or discharge to logic "0". If it is a multi-level dynamic logic circuit, the clock signal that controls the charging or logic operation reaches the latter stage earlier, so that the latter stage performs the logic operation earlier. At this time, the pre-charged output of the previous stage, the logic "1", will drive the latter stage. The logic pulls down the circuit, causing a logic error. Then use the dynamic domino logic circuit, add an inverter after the dynamic logic, so, in the pre-charging phase, the output will be logic "0", so it will be less than the dynamic logic output logic "1", will drive the next level The operation pull-down logic, when the operation result of the previous stage is known, if the logic pull-down circuit acts, the output of the dynamic domino logic will be changed from logic "0" to logic "1", thereby driving the logic pull-down circuit of the next stage, so In a multi-level dynamic domino logic circuit system, it can be seen as a domino, and the latter stage pushes the latter stage to ensure the order of operations and the correctness of logic. In a specific process, if the dynamic logic circuit needs to remain at logic "1" for a long time, the charge may be lost through the logic pull-down circuit because of the process relationship. Usually, a compensation charge device (Keeper) is added to the output, and the output is first passed. An inverter is connected to a P-type transistor, and its drain is connected back to the output of the dynamic logic. If the inverter is to maintain a logic "1", the logic "0" via the inverter will drive the P-type transistor, and the charge that is lost by the logic pull-down circuit and the foot transistor before the inverter is supplemented by the highest potential. , you can correct the logic error caused by leakage.

Here, the adder is a pipeline system, each stage represents each node in the pipeline, and then the dynamic domino logic circuit is used to increase the operation speed. The first stage is the transmission bit ( P _i ) and the generation bit ( G _i ). The logic operation, as shown in Figure 7 and Figure 8, is the first stage, so the traditional footed dynamic domino logic circuit is used. The logic pull-down circuit is finally controlled by the underlying transistor, and its input is the clock signal. After the second stage, for the carry synthesis circuit, the carry-in synthetic dynamic domino logic circuit is used, as shown in Figure 9, which is a dynamic domino logic circuit with a foot transistor. According to the characteristics of the dynamic domino logic circuit, the footless domino logic is used. The circuit of the tenth circuit is as follows: the dynamic domino logic circuit is driven by the pre-level operation result. The pull-down circuit, even if the clock signal of the latter stage is in the logic operation state, still has to wait for the operation result of the previous stage, and knows that the key to enter the logic operation state after the control is the result of the operation of the previous stage. Therefore, the transistor whose circuit is controlled by the clock signal can be deleted, so that in the logic pull-down process, the first transistor is reduced, which can increase the speed of the logic pull-down, thereby improving the operating speed of the overall system. Therefore, in this system, the carry processing logic after the second stage all uses the dynamic domino logic circuit without the foot transistor.

At the final stage of the whole system, the result of the operation is selected for the carry. The logic of the carry is used to select the final result as logic "0" or logic "1". Here, a XOR, a partial addition ( Psum ) result and a carry are used. A logical XOR operation will result in an addition. Figure 11 and Figure 12.

100‧‧‧ Carry Forward Adder

200‧‧‧2 base Kagge-Stone adder

300‧‧‧4 base Kogge-Stone adder

400‧‧‧Intel 32-bit adder

500‧‧‧64 bit 4 base parallel prefix carry adder

600‧‧‧256 bit 8 base parallel prefix carry adder

700‧‧‧Transmission Bit Dynamic Domino Logic Circuit

800‧‧‧ Generate bit dynamic domino logic circuit

900‧‧‧With foot transistor carry-in synthetic dynamic domino logic

1000‧‧‧No foot transistor carry-in synthesis dynamic domino logic circuit

1100‧‧‧With foot transistor carry and partial addition result selection logic

1200‧‧‧No foot transistor carry and partial addition result selection logic

701, 801, 901, 1001, 1101, 1201‧‧‧ reverser

702~705, 802~806, 902~913‧‧‧Optoelectronics

1002~1012, 1103~1114, 1203~1313‧‧‧Optoelectronics

1102, 1202‧‧‧ logic gate

Figure 1 A 32-bit forward-looking carry adder.

Figure 2 2 base Kogge-Stone adder.

Figure 3 4 base Kogge-Stone adder.

Figure 4 Intel 32-bit sparse tree adder.

Figure 5 64-bit 4 base parallel prefix carry adder

Figure 6 256-bit 8 base parallel prefix carry adder

Figure 7: Transmission bit generation logic

Figure 8 Generates bit generation logic

Figure 9: Foot-shaped transistor carry synthesis dynamic domino logic

Figure 10 No-foot transistor carry synthesis dynamic domino logic

Figure 11 has a foot transistor carry and a partial addition result selection logic circuit

Figure 12: No-foot transistor carry and partial addition result selection logic

500‧‧‧Adder

1000‧‧‧No foot transistor carry-in synthetic dynamic logic domino circuit

1200‧‧‧No foot transistor carry and partial addition result selection logic

Claims (5)

A fast adder connection method, A and B represent two input values to be calculated; S represents the calculated output value, i represents the number of bits, R represents the base (radix), and T represents the total number of adders. The subscript P _{i ~( i -2)} represents P _i . P _{i -1} . P _{i -2} , subscript G _{n , i} represents the ith bit operation element of the nth stage, and the input to output includes the following operation levels: (1) Level 1: _Performing an 'or' operation on A _i and B _i Obtaining P _i , doing a 'and' operation of A _i and B _i to obtain G _i , and performing a 'mutual exclusion' operation on A _i and B _i to obtain Psum _i , which will be G _i , G _{i -1} , G _{i -2} , G _{i -3} and the associated P _i do 'or' to get the output G _{1, i} ; (2) level 2: the first level of the output of G _{1, i} , , , Doing 'or' with the relevant P _i to get the output G _{2, i} ; (3) Level 3: G _{2, i of} the second stage output , , Doing 'or' with the relevant P _i to get the output G _{3, i} ; (4) Level: will be -1 level output , Do the 'or' operation with the associated P _i to get the output ;(5) +1 level: will be Level output Performing a 'mutual exclusion' operation with the associated Psum _i yields the result S _{i of} this adder operation. A domino logic circuit for implementing a fast adder, comprising: a dynamic logic circuit having a first transistor, a second transistor and a pull-down circuit, wherein the first transistor and the second transistor system are external Clock signal control, wherein the pull-down circuit has a series of transistors in series, in addition to the In addition to the transistors, the drains of each transistor are connected to the drain of a transistor, and the source of the transistor is connected to the original series path. The source of the transistor; the drain of the first transistor is connected to the source of the first transistor of the dynamic logic circuit, and the drain of the first transistor of the dynamic logic is connected to the highest potential , the first The source of the transistor is connected to the drain of the second transistor of the dynamic logic circuit, the source of the second transistor of the dynamic logic circuit is connected to the lowest potential; a compensation P-type transistor, the drain of which is connected to the dynamic logic One output of the circuit, the source is connected to the highest potential to compensate the output value of the dynamic logic circuit; an inverter whose input is connected to the output of the dynamic logic, outputs an output signal, and the output signal is opposite to the input signal To, feedback control the compensation P-type transistor. A domino logic circuit for implementing a fast adder, comprising: a dynamic logic circuit having a first transistor and a pull-down circuit, wherein the first transistor system is controlled by an external clock signal, wherein the pull-down circuit has a series of transistors in series, in addition to the In addition to the transistors, the drains of each transistor are connected to the drain of a transistor, and the source of the transistor is connected to the original series path. The source of the transistor; the drain of the first transistor is connected to the source of the first transistor of the dynamic logic circuit, and the drain of the first transistor of the dynamic logic is connected to the highest potential , the first The source of the transistor is connected to the lowest potential; a compensation P-type transistor whose drain is connected to one of the output terminals of the dynamic logic circuit, and the source is connected to the highest potential to compensate the output value of the dynamic logic circuit; The phase sensor has an input connected to the output of the dynamic logic, and outputs an output signal, and the output signal is opposite to the input signal to control the compensation P-type transistor. A domino logic circuit as claimed in claim 2, further comprising: an exclusive circuit logic circuit, wherein an input signal is an output signal of the inverter. A domino logic circuit as claimed in claim 3, further comprising: an exclusive circuit logic circuit, wherein an input signal is an output signal of the inverter.