KR950015180B1 - High speed adder - Google Patents

Abstract

No content.

Description

High Speed Computing Adder

1 is a diagram for explaining a 4-bit full adder according to a conventional example.

2 is a diagram illustrating the number of gate steps required for carry propagation in a general full adder circuit.

3 illustrates a 4-bit full adder (hereafter referred to as a carry lookahead adder) with a lookahead carry generator.

4 is a logic diagram of the lookahead carry generator shown in FIG.

5 is a diagram for explaining a fast computing type adder according to the present invention.

FIG. 6 is a diagram showing the configuration of a carry " 1 " adder and a carry " 0 " adder shown in FIG.

* Explanation of symbols for main parts of the drawings

50: adder 51,54: carry " 1 " adder

52,55 Carry "0" adder 53,56: Multiplexer

60,71: exclusive logic gate 62,73: AND gate

72: inverter 74: OR gate

The present invention relates to a fast computation type adder, and in particular, adds to the lower bit group by dividing the bits of a plurality of input variables for addition into predetermined bit groups and adding them to the same, respectively (i.e., carry generation existence / no signal). The present invention relates to a fast computing type adder which achieves a high speed of the parallel addition processor by selecting different addition results in the case of carrying or not carrying a higher bit group using a).

As is well known, the adder is adopted as the most basic computing device in a data processing system such as a computer with a data processing function or a video signal processing system applied to the processing of video signals. An adder capable of high speed operation is required.

FIG. 1 is a diagram illustrating a 4-bit full adder according to a conventional example. The 4-bit full adder is a 4-bit configuration that adds 4 bits of mantissa and 4 bits of an addend. Four full adders (10, 12, 14, 16).

According to the 4-bit full adder of this configuration, the addition value S4 is obtained as soon as the inputs a4 and b4 are inputted to the adder 16, whereas the input carry C4 has a front carry C3 thereof. Until the steady state value is obtained, it is not settled at its final steady state value, and similarly, the carry C3 has to wait for the carry C2, thus descending to the carry C1. Therefore, the final output S4 and the carry C5 settle to the final steady state values only after the carry propagates through all the steps.

As described above with reference to the full adder circuit shown in FIG. 2 for the number of gate steps involved in the carry propagation, the general full adder logically excludes two input variables Ai and Bi to be summed. A half-adder consisting of an exclusive OR gate 20 for processing and an AND gate 22 for AND processing the two input variables Ai and Bi; An exclusion logic gate 24 that generates an additive value Si by performing an exclusive OR operation on the result Pi of the exclusion OR gate 20 and the preceding carry Ci, and the exclusion logic gate 20. A half-adder consisting of an AND gate 26 for ANDing the output Pi of ") and the preceding carry Ci; OR gate 28 for outputting carry (Ci + 1) by OR-processing the output of the AND gate 22 and the output of the AND gate 26, wherein the two inputs denoted Ai and Bi are shown. The variable represents two significant bits to be summed, and the third input Ci represents a carry raised from the previous lower significant position.

In the above configuration, the output Pi of the exclusiveization logic gate 20 and the output Gi of the AND gate 22 are propagated through their respective gates and then settle to their steady-state values. Gi is common to all full adders and is determined only by the bits of the input figma (eg Ai) and the mantissa (eg Bi).

The signal from the input carry Ci to the output carry C (i + 1) propagates through the AND gate and the OR gate, which constitute two gate stages. In other words, for example, if the parallel adder has four full adders, the output carry C5 will have a gate of 2 × 4 = 8 steps from C1 to C5, so the total propagation time of the adder is one half adder and eight gates. It is the propagation time for the sum of the steps. Thus, for example, an N-bit parallel adder is designed to go through its 2N gate steps to fully carry a carry. That is, the propagation time of the carry becomes a limiting factor for the speed of adding two numbers in parallel.

Thus a parallel adder or any combination circuit will always have some value at its output, but the output will not be justified unless it has enough time to propagate through the gate connected from the input to the output. And since all other arithmetic operations are implemented by successive additions, the time spent addition and mediation is very serious.

Accordingly, the principle of the look-ahead carry is widely used to shorten the carry propagation time. Now, the principle of the look-ahead carry will be described with the full adder shown in FIG. If you first define two new binary variables, Pi = Ai Bi, where Gi = AiBi, respectively, and the sum and carry of the outputs are Si = Pi Ci, (i + 1) = Gi + PiCi, respectively

Here, Gi is called carry generate, and when Ai and Bi are both 1, an output carry is generated regardless of an input carry, and Pi is related to propagation of a carry from Ci to C (i + 1). Since it is a term, it is called a carry propagate.

Then, using the Boole function for the carry output of each stage in the general look-ahead carry generator shown in FIG. 4 and substituting its values from the previous equations for each Ci, each output carry is:

C2 = G1 + P1C1,

C3 = G2 + P2C2 = G2 + P2 (G1 + P1C1) = G2 + P2G1 + P2P1C1,

C4 = G3 + P3C3 = G3 + P3G2 + P3P2G1 + P3P2P1C1,

C5 = G4 + P4G3 = P4P3G2 + P4P3P2G1 + P4P3P2P1C1

Each function can be implemented as a single stage of an AND gate followed by an orgate (or two-level NAND) because it is expressed in the form of sum of products of the Boolean function for each output carry. Do.

The configuration of a 4-bit parallel adder (carry lookahead adder) having such a lookahead carry generator is shown in FIG. 3. The carry lookahead adder shown in FIG. 3 carries a carry for each mantissa and the singer. Exclusive logic gates (XOR: 31, 33, 35, 37) and AND gates (32, 34, 14) for generating generation variables (P1, P2, P3, P4) and carry propagation variables (G1, G2, G3, G4). 36, 38, a lookahead carry generator 40 for generating a final carry C5 based on each carry generation variable Pi, a carry propagation variable Gi, and a carry input C1, Exclusively connected to the outputs C2, C3 and C4 of the head carry generator 40 and carrying the carry generation variables P1, P2, P3 and P4 at one end to obtain the addition results S1, S2, S3 and S4. The logic logic gates 39, 41, 43, 45 are provided.

According to such a carry lookahead adder, the output of each summation requires two Exclusive-OR gates, the output of the first Exclusive-OR generates a variable Pi, and the AND gate generates a variable Gi. As such, all P and G are generated in two gate steps. The carry then propagates through the lookahead carry generator 40 and is applied as an input to the second Exclusive-OR gate. Therefore, after the P and G signals have settled to their steady state values, all output carry is generated by delaying the two stages of the gate, so that the outputs from S2 to S4 have the same propagation delay time.

Therefore, according to the carry lookahead adder described above, since the occurrence of carry is observed in advance, the operation speed is faster than other adders. However, when the number of small bits is added to the case of adding a large number of bits, In the case of adding a larger number of bits, there is a disadvantage that more gate steps and operation time are required.

SUMMARY OF THE INVENTION The present invention has been made in view of the above-described conventional functions, and the upper bit group is carried while the lower bit group is being operated while the plurality of bit groups of the plurality of input variables to be added are divided into n bit groups and operated simultaneously. It is an object of the present invention to provide a fast operation type adder which realizes high speed operation by simultaneously calculating the operation for the presence / absence of the same and outputting the calculation result of the upper bit group calculated in advance according to the operation result of the lower bit group. .

In order to achieve the above object, according to the present invention, an addition result is performed on a first bit group divided from a plurality of bit groups of a plurality of input variables, and the result of the addition and whether or not there is a carry occurrence according to the addition result are obtained. A plurality of operations for carrying out a calculation on the case of whether or not there is a carry generation on the first addition means for outputting a signal and at the same time as the addition operation in the first addition means; A second addition means composed of an adder, an addition result of the plurality of adders constituting the second addition means on the basis of a signal of the presence or absence of carry generation from the first addition means, and an addition result currently output A multiplexer for outputting a signal for whether or not a carry occurs according to the first and second bits in the divided plurality of bit groups simultaneously with the addition operation in the first adding means and the second adding means. A third adding means composed of a plurality of adders each performing an operation on the case of having a carry generation with or without a carry, and the third adding means based on a signal of having or without a carry generation provided from the multiplexer. There is provided a fast computing type adder comprising a multiplexer for selectively outputting the addition result of a plurality of adders.

According to a preferred embodiment of the present invention, the plurality of adders constituting the second adding means and the third adding means each have a carry " 1 " adder set to a high level and a carry " 0 " It is configured with an adder and configured to simultaneously compute the assigned bit string.

According to the fast computing type adder according to the present invention configured as described above, a plurality of bit groups of a plurality of input variables to be added are divided into n bit groups, and the addition result of the lower bit string is used (that is, whether a carry generation is present or not). By selecting the addition result for the upper bit group (that is, selecting from the addition result when the carry occurs and the addition result when the carry does not occur), the parallel addition process is performed at a high speed, so that the operation speed is further improved.

Hereinafter, the present invention will be described in detail with reference to the accompanying drawings.

FIG. 5 is a diagram showing the configuration of the fast computing adder according to the present invention, where 50 is the first group of bits of a plurality of input variables (for example, A and B) each having a predetermined number of bits (for example, 22 bits). For example, 0 to 7 bits are added to output the addition result S1, and the multiplexer 53, which will be described later, sets the signal C1 for the presence or absence of the carry generation according to the addition result to a low or high level. 51 and 52 denote second bit groups (eg, 8 to 14 bits) of the input variables A and B when an addition operation is performed on the first bit group in the first adder 50. Is an adder constituting the second adding means for performing arithmetic operations on the case where the carry occurs and the case where the carry does not occur.

Here, one of the adders 51 and 52 (in the present invention, the adder of the adder 51 is a carry " 1 " adder, and a carry generation signal Ci preset at a high level is applied to one input terminal of the adder 51. The second input group (for example, 8 to 14 bits) of the plurality of input variables (for example, A and B) is input to two other input terminals to perform an addition processing operation for the case of carry generation. The adder 52 is a carry " 0 " adder, and a carry generation signal Ci predetermined at a low level is input to one input terminal of the adder 52, and the plurality of input variables (2) to the other two input terminals. For example, a signal of a second bit group (eg, 8 to 14 bits) of A and B is input to perform an addition processing operation for a case in which no carry occurs.

Reference numeral 53 denotes a signal for the presence or absence of a carry generation from the first adder 50 (for example, when a carry occurs, a high level signal C1 is output, but a low level signal C1 when no carry is generated). Outputting results of the plurality of adders 51 and 52 constituting the second adding means, and carry-out according to the addition result currently output from the adders 51 and 52. A multiplexer for applying a non-signal signal C2 to the multiplexer 56, which will be described later, wherein the multiplexer 53 is the adder 51 when the signal C1 from the first adder 50 is at a high level. Is output as the addition result S2 to the second group of output signals, whereas when the signal C1 from the first adder 50 is at a low level, the output signal of the adder 52 is output to the second bit. It outputs as addition result S2 about a group.

Further, 54 and 55 have a configuration similar to the adders 51 and 52 of the second adding means, so that the input when the addition operation is performed in the first adder 50 and the adders 51 and 52 of the second adding means. And an adder constituting third addition means for performing arithmetic operation on the case where the carry occurs and the case where the carry does not occur, for the third group of bits (eg, 15 to 21 bits) of the variables A and B.

Here, the adder of one of the adders 54 and 55 (in the present invention, adder 54) is a carry " 1 " adder, and the carry generation signal Ci preset at a high level at one input of the adder 54. ) Is input to the other two input terminals, and a signal of the third bit group (for example, 15 to 21 bits) of the plurality of input variables (for example, A and B) is input to perform an add processing operation in the case of carry generation. Done. The adder 55 is a carry " 0 " adder, and a carry generation signal Ci, which is set at a low level, is input to one input terminal of the adder 55, and the plurality of input variables (e.g. The third bit group (for example, 15 to 21 bits) of A, B is added to perform an add processing operation for a case in which no carry occurs.

Reference numeral 56 denotes an addition result of the plurality of adders 54 and 55 constituting the third adding means, using the signal C2 with or without carry generation provided from the multiplexer 53 as a selection signal. Selective output multiplexer.

Here, the multiplexer 56 outputs the output signal of the adder 54 as an addition result S3 for the third group of bits when the signal C2 from the multiplexer 53 is at a high level. When the signal C1 from the multiplexer 53 is at the low level, the output signal of the adder 55 is output as an addition result S3 for the third bit group.

On the other hand, the adders 52 and 55, if the input carry Ci is " low ", as shown in FIG. 6A, a plurality of input variables Ai and Bi to be added due to the characteristics of the exclusion logic gate. Carry the exclusion logic gate 60 which outputs the addition value Pi as the result value Si and the result Gi generated by ANDing the plurality of input variables Ai and Bi. +1)) and the AND gate 62 to output.

In addition, the adders 51 and 54, when the input carry Ci is " high 1 ", add value Pi of the plurality of input variables Ai and Bi to be added, as shown in FIG. AND processing of the exclusion logic gate 71 which obtains?, The inverter 72 which inverts the output of the exclusion logic gate 71 to obtain a final result value Si, and the plurality of input variables Ai and Bi. The AND gate 73 and the AND processing result Gi by the AND gate 73 and the output Pi of the exclusion logic gate 71 are ORed to carry C (i + 1). OR gate 74 to generate.

According to the present invention constructed as described above, among the bit groups of the input variables A and B each formed of a plurality of bit groups, for example, the first adder 50 for the least significant bit group, for example, for the bit group of the intermediate level. In the second adding means (51, 52), for example, the addition operation is performed simultaneously by the third adding means (54, 55) for the most significant bit group. In the second adding means (51, 52), the first adder ( The addition operation is performed for the case where the carry is generated or when no carry is generated with respect to the addition result in step 50). In the third adding means 54, 55, the second adding means 51, 52 performs the addition operation. The addition operation is performed for the case where the carry occurs and the case where the carry does not occur. Accordingly, the multiplexer 53 advances in advance in the corresponding adder in the second adding means 51, 52 based on the carry-on / non-signal C1 that is different from the addition result S1 of the first adder 50. The calculated addition result S2 is outputted, and the carry generation wired / wireless signal C2 according to the addition result S2 is applied to the rear multiplexer 56, and the multiplexer 56 receives the multiplexer 56. Based on the carry generation presence / absence signal C2, the addition result S3 calculated in advance in the corresponding adder in the third adding means 54, 55 is outputted. Compared with the conventional addition method to determine the operation speed is significantly improved.

In other words, in the case of adding the input variables A and B respectively formed with 22 bits, for example, 8 bits (for example, 0 to 7 bits) to the first adder 50 and 7 to the second adding means 51 and 52. When a bit group is allocated to calculate 7 bits (for example, 15 to 21 bits) in the bits (for example, 8 to 14 bits) and the third adding means (54, 55), the first adder (50) is used using a parallel processing technique. ) And the adders 51 and 52 of the second adding means and the adders 54 and 55 of the third adding means simultaneously start adding to the assigned bit group. Accordingly, when the addition result S1 according to the addition operation for the least significant bit group is obtained in the first adder 50, the adders 51 and 52 of the second adding means carry carry on the bit group of the intermediate level. The value S2 at the time of occurrence and the carry ratio is calculated | required, and the value S3 at the time of carry generation and the carry ratio for the most significant bit group is calculated by the adders 54 and 55 of the said 3rd addition means.

In this state, a high level or low level signal C1 indicating whether or not a carry is generated according to the addition result S1 in the first adder 50 is supplied to the multiplexer 53 as a selection signal. When the signal C1 is a signal indicating a carry generation, the multiplexer 53 outputs an addition result S2 calculated in advance by the adder 51, while a signal indicating a carry ratio occurs. In this case, the addition result S2 calculated in advance in the adder 52 is output. In addition, a signal C2 having a high level or a low level indicating whether or not a carry occurs according to the addition result S2 in the adder 51 or 52 currently selected and output is selected as a selection signal through the multiplexer 53. Is applied to the multiplexer 56. Accordingly, the multiplexer 56 outputs the addition result S3 as the final normal value calculated in advance in the adder 54 when the signal C2 is a signal representing the carry generation, while the carry multiple generation 56 indicates the carry ratio. If it is a signal, the adder 55 outputs the addition result S3 as the final normal value calculated in advance.

The fast arithmetic adder of the present invention configured and operated as described above has a gate of 44 steps when a general carry look-ahead adder adds a plurality of 22-bit input variables. It can be seen that only 11ns of delay time is required, and in the case of implementing the multiplier using another fast computing type adder according to the present invention, the speed of the multiplier (40MHZ) by the conventional adder using only the carry lookahead technique is used. Computational results were obtained at a speed of 1.5 times (61 MHz).

According to the present invention as described above, since the carry of the lower bit adder is used as a selection signal for selecting the output of the adder taking into account whether or not the carry of the upper bit is carried out, the addition result related to the upper bit is immediately selected and outputted. Not only is significantly faster, but also the computing function of the computer or the associative signal processing apparatus can be further increased.

Claims (4)

First addition means (50) for performing an addition to the first bit group divided from the plurality of bit groups of the plurality of input variables to be added and outputting a result of the addition and a signal of whether or not a carry is generated according to the addition result; And a plurality of adders (51, 52) for performing a calculation on a case of whether or not a carry occurs with respect to the second bit group among the divided plurality of bit groups simultaneously with the addition operation in the first adding means (50). A result of addition of the adders (51, 52) of the second adding means on the basis of a signal for the presence or absence of carry generation from the first adding means (50), A multiplexer 53 for outputting a signal for the presence or absence of a carry generation according to the result of the addition, and an addition operation of the divided plurality of bit groups simultaneously with the addition operation in the first adding means 50 and the second adding means. In the case of carrying or not carrying 3 bits group A third adding means composed of a plurality of adders 54 and 55 for performing arithmetic operations on each of the plurality of adders; and the adder of the third adding means based on a signal of whether or not a carry generation is provided from the multiplexer 53; And a multiplexer (56) for selectively outputting the addition result of 54, 55. 2. The plurality of adders constituting the second adding means and the third adding means, respectively, have a carry " 1 " adder 51 and 54 whose one end is set to a high level and a carry " A fast computing type adder, comprising 0 "adders (52, 55) configured to simultaneously compute the assigned bit strings. 3. The carry logic of claim 2, wherein the carry " 0 " adders 52 and 55 output the addition value Pi of the plurality of input variables added as a result value Si, and the plurality of carry logics 60 and 55, respectively. And an AND gate 62 for outputting a result Gi generated by AND processing the input variable as a carry C (i + 1). 3. The exclusion logic gate 71 according to claim 2, wherein the carry " 1 " adders 51 and 54 obtain the addition value Pi of the plurality of input variables to be added and the exclusion logic gate 71 of the exclusion logic gate 71. An inverter 72 for inverting the output Pi to obtain a final result value Si, an AND gate 73 for ANDing the plurality of input variables, and an AND processing result Gi and the result of the AND gate 73. And an OR gate (74) for ORing the output (Pi) to produce a carry (C (i + 1)).