Adder With Fast Detection of Sum Equal to Zeroes or Radix Minus One

This patent application relates to circuits for detecting zero sums and radix less 1 sums in data processing equipment and more particularly to circuits which detect such sums prior to the actual summation.

In digital computers a common requirement accompanying an adder is to detect the condition when all the sum bits are equal to zero. While not as common, it is sometimes necessary to detect the condition when all the sum bits are equal to the radix less 1, for example, in the binary case when all the sum bits are equal to 1 or in the decimal case when all the sum bits are equal to 9. In the prior art those conditions are found by first performing the addition and then ANDing the result with ZEROS or with NINES or with ONES to determine whether such a sum has been found. Obviously, the detection of such a sum cannot occur until after the summation is complete. Since in many cases the attainment of a sum will complete a machine cycle the further logic operations that are necessary to AND the sum with ZEROS, with NINES or with ONES will take an additional machine cycle and the branch operations which key off the detection will be delayed. It is, therefore, the general object of this invention to eliminte the need of such an additional machine cycle by providing means for detecting a sum of all ZEROS, all ONES, all NINES or indeed of any radix less 1 sum prior to or at least concurrently with the production of the sum. It is an additional object of the invention to incorporate the detection circuits into an adder with carry look-ahead in such a manner that the circuits for generating existing digit functions can be utilized in the detection process.

This invention is to logic circuits which detect a summation of all ZEROS or a summation of all radix less 1 digits without first performing the addition. In the binary case, the carry generate, carry propagate and half-sum functions generated for use in the carry look-ahead adder are utilized as input to the detection circuits. In the decimal case where a BCD representation of the sum is used, the carry generate and carry propagate functions are generated by providing threshold functions for input to both carry look-ahead and detection circuits.

The foregoing and other objects, features and advantages of the invention will be apparent from the following detailed description of the invention as illustrated in the accompanying drawings wherein:

FIG. 1 is a block diagram of prior art binary carry look ahead adders such as are described in detail in the first two incorporated references.

FIGS. 2A, 2B and 2C are logic circuits such as are used in the FIG. 1 adder.

FIG. 2D is a diagram illustrating the operation of the NAND/AND-DOT logic family.

FIG. 3 is a logic circuit representation of a first embodiment of the invention.

FIGS. 4-8 are circuits describing other embodiments of the invention.

FIG. 9 is similar to FIG. 1 showing a typical adder for an n-digit radix-r parallel adder with carry look ahead.

FIG. 10 is an adder for the radix r showing the digit function generation necessary for detecting zeros and radix less 1 summations prior to the actual addition.

FIG. 11 is a logic circuit for operating on the digit functions produced in FIG. 10 to obtain a ZEROS detection.

FIG. 12 is similar to FIG. 11 for the detection of a summation of the radix less 1.

FIG. 13 is similar to FIG. 1 and shows a typical decimal adder with carry look ahead.

FIG. 14 shows circuits to derive the digit functions necessary to detect a summation of all ZEROS and all NINES.

FIG. 15 shows logic circuits which operate on the functions produced in FIG. 14 to detect a summation of all ZEROS.

FIG. 16 is similar to FIG. 15 for the detection of all NINES.

FIG. 17 is an alternative implementation to FIG. 14.

Before describing the circuits through which the zero sum bits are detected in an adder it is desirable first to describe the mathematics upon which these circuits rest. For purposes of illustration both the circuits and the following mathematics will be restricted to a 32 bit adder, although the invention is applicable to adders of any size.

The following mathematical analysis will begin with the binary adder and then will be extended to adders of higher radices notably decimal.

In the case of a 32 bit adder, let A with subscripts 0 to 31 represent the 32 bits of the addend and let B with subscripts 0 to 31 equal the 32 bits of the augend. Therefore, in equation form:

where the subscripts refer to the bit positions, 0-31, high-to-low order, respectively.

It is well known that in performing additions there are various functions of individual bit positions which are useful both in analysis and for circuit design. One such function expresses the condition of a half-sum or exclusive OR of the two bits at a bit position. That is, if you take the two individual bits (one from the addend and one from the augend) comprising a bit position and add them, and if one, and only one, of those individual bits is on, then you have the half sum or exclusive OR condition. To express the relationship mathematically with H designating the half-sum:

thus, the function H is equal to A exclusive Ored with B at an individual bit position K, and also the function H is equal to A .sup.. B + A .sup.. B. The latter mathematical description says that if you do not have an A and you do have a B or if you have an A and you do not have a B then you have the function H.

A second very useful function of an individual bit position may be termed the carry generate, G, which expresses the condition in which both A and B bits are on. That is, mathematically:

this function is called a carry generate since when the A and B bits are added, it will result in a carry over to the next high order position.

A third very useful function of an individual bit position is the carry propagate, P, which may be defined as the OR condition where either the A bit or the B bit is on. Mathematically:

this function is called a propagate since when the A and B bits are added, it will propagate a one that is carried into it from the next low order bit position.

These functions of the individual bit positions may be related mathematically. For example, the function H which is the condition where one, and only one, of the two individual bits are on, can be expressed by stating that: if the condition P, where one or both bits are on, is ANDed with the not of function G, which says that either one is on or neither are on, the result is one, i.e., H, since one is the common condition. Therefore, H = P .sup.. G.

Also, the function G may be related to the functions H and P. Function G represents the condition where both A and B bits are on. H represents the function where only one is on, and P represents the function where one or both are on. The function H is equal to the inverse of H and expresses the condition of either zero bits on or two bits on. If H is ANDed with the P function the result expresses the condition where zero or two are ANDed with one or two, and since the only condition in common is two, which says that both bits are on, the AND of H and P results in the function G. Mathematically: G = H .sup.. P.

To state the relationship of H and G to the function P we may note that P is the case where one or two bits are on. H is the condition where only one bit is on, and G is the condition where both bits are on. Therefore, if one bit H is on or both bits G are on, the P condition is expressed by the ORing of functions H and G, that is, the condition in which either one or two bits are on. Mathematically: P = H + G.

Of course, the complements of each of these functions are also true and for convenience all of these functions are grouped and stated below:

In addition to the 32 bit positions being added in the adder, there is an additional bit to be included among the inputs. It is the input carry C.sub.in from a previous operation.

To analyze the operations of an adder, the functions H, G and P can be profitably utilized. For example, one of the objects of the present invention is the early detection of the generation of a sum of all zeros in an adder. That is, detecting such a sum even before the summation is completed. Upon analysis, it is clear that there are three conditions which can produce a sum of all zeros. One of these conditions is present if all the inputs are zeros, that is, all of the A bit positions and all of the B bit positions, and the carry in bit, are all zeros. To express that mathematically, we need only say that all of the inputs are P and C.sub.in.

The second condition in which a sum of all zeros is generated is where the input carry is zero, where the A and B bits of the low order 31 bit positions are all zero and where in the high order bit both the A and the B bits are one. In that case, the high order bit position produces a zero when added and there is a generated output carry.

The second condition is also present if the A and B bits of the 30 low order bit positions are all zeros, the carry in bit is zero, bit position one has both A and B bits on, and in the high order bit position one, and only one, of the bits is on. The sum here will again produce all zeros in the adder with the carry from bit position one leaving a zero in its wake.

The second condition is also present if the low order 29 bits are zeros, the carry in bit is zero, bit position two has both bits on and bit position zero and one each have exactly one bit on. Again, there is a generated carry in bit position two that propagates leving zeros in its wake. The expression of this second condition can be continued through all of the remaining bit positions.

The third condition producing a sum of all zeros is where the carry in bit is on, and all bit positions have one, and only one, bit on. In this case the carry in bit will propagate through all of the positions leaving zeros in its wake.

The above are the three conditions, and the only three conditions that can produce a sum of all zeros. These conditions may be expressed mathematically:

In equation 1 above, the first line represents the first condition, that is, where all inputs are zeros. The second line represents one case of the second condition where C.sub.in is zero and the low order 31 bits are zeros, but both bits are on in the high order bit. The third line represents a second case of the second condition where C.sub.in is zero, the low order 30 bits are zero, both bits are on in the first bit position, and one, and only one, bit is on in the high order bit position. The remaining terms expressing the second condition are not written out, but finally, the last variation of this second condition is shown in the next to last line of equation 1. Here, C.sub.in is zero, both bits are on in the low order bit position, and one, and only one, bit is on in each of the high order 31 bit positions. The bottom line of equation 1 represents the third condition where the carry in, C.sub.in, is on and all 32 bits of the adder have one, and only one, bit on in each bit position.

While a circuit for equation 1 might be built, it is desirable to combine as many terms as possible to achieve the most economical and fastest circuit arrangement possible. Therefore, in combining the terms of equation 1 we may first note that P is a common factor to all bit positions in both lines 1 and 2 from bit position 1 through 31, while (P.sub.0 + G.sub.0) represents the uncommon factor. Since the factor (P.sub.0 + G.sub.0) = H.sub.0, H.sub.0 can be substituted.

Thus, with the first two terms of equation 1 combined as above, equation 2 below may be written.

The next compression of terms involves the first two lines in equation 2. Note, that P is a common factor to all of the bit positions in both lines from 2 through 31. Thus, we can factor out (H.sub.0 .sup.. P.sub.1) + (H.sub.0 .sup.. G.sub.1). This factor can be rewritten (H.sub.0 + P.sub.1) .sup.. (H.sub.0 + G.sub.1) thus producing equation 3 below, noting that H.sub.0 .sup.. H.sub.0 = G.sub.1 .sup.. P.sub.1 = 0.

The process of combining the first two terms of equation 3 is repeated again and again until only a single term remains as shown in equation 4 below.

Equation 4 represents an expression for which circuits can be built to operate in a very efficient and quick manner. There is, however, an opportunity to simplify the circuit by making use of the output carry of the adder C.sub.out to replace the expression (G.sub.1 + . . . + G.sub.31 + C.sub.in). Circuits to generate output carries are found in the incorporated patents and adders with such circuits are generally known in the art as carry look ahead adders. The alternate equation is:

The alternate expression is based on the fact that in equation 4 there was a series of G terms. Since the G function represents the condition where both A and B bits are on, it represents the situation in which there is an output carry from that bit position. Therefore, it is possible to replace this expression, which would involve an OR circuit with a large number of inputs, with the simple carry out term. That is what is shown in equation 5. Since it is possible to find the carry out prior to the summation due to the carry look ahead feature of adders, equation 5 becomes a preferred implementation for the detection of the zeros sum. It should be noted that circuits based on equation 5 may take at least one additional logic level to arrive at the zero sum (and therefore some additional time), but the number of circuits involved to detect the zero sum will be fewer than for equation 4.

In deriving equation 5, note that C.sub.out can be expressed as in equation 6 below.

Equation 6 is an exhaustive list of all of the conditions that can produce C.sub.out. In equation 1 those factors which contain a G term represent the conditions where a carry is being generated in one bit position and emerges as a carry out, leaving zeros in its wake as it propagates through the Hs. This can be expressed by the carry out term by substituting for each G factor that which is shown in equation 6. For example, if you substitute equation 6 for G.sub.0 in equation 1, the first term of C.sub.out goes in directly, that is, G.sub.0. The second term is H.sub.0 .sup.. G.sub.1 .sup.. P.sub.1. Substituting now for P.sub.1 its value of H.sub.1 .sup.. G.sub.1 the term contains the factors G.sub.1 .sup.. G.sub.1 which reduces the term to zero. Similarly, all of the other terms in the expansion will contain the G.sub.K .sup.. G.sub.K resulting in zeros for all terms except the first one which was the G.sub.0. Therefore, the substitution of C.sub.out into equation 1 will result in a simple replacement of C.sub.out for each G.sub.K term in the expansion. The result of such a substitution is shown in equation 7 below.

Equation 7 may now be compressed iteratively by combining the first two terms in much the same manner as was previously described concerning the compression of equation 1 to generate equation 4. For example, the first two terms in equation 7 can be combined as shown below.

Compressing all of the terms in this manner derives the expression which is shown in equation 5.

It should be noted that in implementing equation 5, it is first necessary to produce the value C.sub.out after which circuits would have to be provided for performing the operations of equation 5.

To speed the operation, note that since C.sub.out includes G.sub.0 as a term according to equation 6,

so that

Equation 8 may be restated as shown below in equation 9.

Equation 9 is a valuable variation on equation 5 because an adder design generally produces the single bit functions H, P and G earlier than C.sub.out. Therefore, a circuit based on equation 9 will permit a single level of delay between the generation of C.sub.out and the production of ZEROS.

It should also be noted that the function ZEROS may be expressed as a function of some intermediate carry as well as the output carry. This is shown below in equation 10.

Equation 10 provides the circuit designer the facility of using some intermediate carry in the detection of the ZEROS sum. Since intermediate carries may be produced prior to the output carry, the operation may again be made faster although additional logic circuits will be needed.

The zero-sum detect method can be generalized to all radices. It is particularly useful for decimal.

where the subscripts, 0 through n-1, refer to digit positions high-to-low order, respectively.

The following functions of a digit position, K, will be used:

(K).sub.r-1 = the normalized algebraic sum, A.sub.K + B.sub.K, of digit position K which is equal to r-1 (the weight of digit position K is normalized to r.sup.0 = 1)

(K).sub.r = the normalized algebraic sum, A.sub.K + B.sub.K, of digit position K which is equal to r.

(K).sub.0 = the normalized algebraic sum, A.sub.K + B.sub.K, of digit position K which is equal to 0.

For binary (r=2), the functions (K).sub.r-1, (K).sub.r, and (K).sub.0 correspond to H.sub.K, G.sub.K, P.sub.K, respectively.

The conditions for generating a sum of all zeros are enumerated in equation 11.

Equation 11 shows that the ZEROS sum is generated by one of three conditions. The first condition is where the algebraic sum of each addend-augend pair is ZERO and C.sub.in = 0. The second condition is, if the normalized algebraic sum of one, and only one, addend-augend pair is equal to r, (in the decimal case that would be 10) a carry is generated in that digit position. In each trailing position, the addend-augend pair must produce an algebraic sum of ZERO and C.sub.in must be zero. In each leading digit position the addend-augend pair must produce the normalized algebraic sum of r-1, (in the decimal case 9) which permits the generated carry to pass through leaving ZEROS in its wake. The third condition is if C.sub.in equals 1 and the normalized algebraic sum r-1 is produced in each digit position. That permits the input carry to pass through leaving ZEROS in its wake.

Next, a compression of terms in equation 11 may be performed in a manner similar to the compression already explained with reference to equation 1, that is, the first two terms of equation 11 are combined and then the resulting term with the next term and so on until eventually only a single term remains as shown in equation 12 below.

where (0) .sub.0,r means that the normalized algebraic sum, (A.sub.0 + B.sub.0), is equal to o or r.

A circuit based on equation 12 may be built to detect a sum of zeros for any radix.

The alternate implementation which makes use of the output carry C.sub.out or an intermediate carry is not applicable when some radix other than 2 is used. The reason is apparent if you consider that for r=2,

Note that (K).sub..sub..ltoreq.r means that the normalized algebraic sum, (A.sub.K + B.sub.K), is equal to or larger than r with a maximum possible value of 2(r-1).

Thus, a circuit built on equation 12 will detect the zero sum regardless or radix and cannot be simplified with the use of the functions generated from the carry look ahead circuits except in the case of a binary adder.

For the decimal adder the radix equals 10 and equation 12 becomes:

Let (A.sub.8, A.sub.4, A.sub.2, A.sub.1) and (B.sub.8, B.sub.4, B.sub.2, B.sub.1) be the BCD (binary-coded decimal) representation of the decimal addend and augend respectively. The subscripts, 8, 4, 2 and 1 refer to the weight of the respective bits of the decimal digit. Then,

equations (14), (15) and (16) are the individual digit functions. They may be readily derived from a truth table but in words they represent the following. For equation 14, if the addend/augend pair at each BCD weight position is zero, the sum is zero. For equation 15, if either addend or augend bit but not both at weight position 8 is on and if neither bit at weight position 4 is on, 8 is contributed to the sum; or if both bits at weight position 4 are on, eight is contributed to the sum. In either case, if that 8 is added to the situation where both bits are off at weight position 2 but one and only one bit is on at weight position 1, the result is nine. Also, if four is contributed by position 4, and 4 is contributed by position 2 and 1 is contributed by position 1, the result is nine. A similar analysis can be made of equation 16.

The following description is to provide the mathematical basis for those circuits detecting whether a sum of two numbers is comprised of digits each of value one less than the radix, an analysis similar to that just completed for the detection of all ZEROS. As in the ZERO sum detect case, the object is to provide circuits which will detect the radix less 1 condition independently of the sum. Before describing the circuits through which the radix less 1 sum bits are detected in an adder, it is desirable first to describe the mathematics upon which these circuits rest. For purposes of illustration both the circuits and the following mathematics will be restricted to a 32-bit adder although the invention is applicable to adders of any size.

The following mathematical analysis will begin with the binary adder and then will be extended to adders of higher radices, notably decimal.

Notations herein will correspond to those in the previous description concerning the detection of all ZEROS. For example,

where the subscripts refer to the bit positions, 0-31, high-to-low-order, respectively.

The half sum H, carry generate G, and carry propagate P functions of the individual bit positions described above, will also be used in the following description with respect to the detection of a 32-bit sum of all ONES. Also, as before, an input carry C.sub.in is included among the inputs.

Upon analysis we find that there are three conditions which can produce a sum of all ONES. One of these conditions is where all inputs are ONES (G and C.sub.in) so that every bit position generates and accepts a carry to produce a sum equal to one.

The second condition in which a sum of all ONES is generated is where one, and only one, bit position has an addend-augend pair equal to zero (P) thus converting a carry into that particular bit position into a sum equal to one and precluding a carry from that bit position into the next higher order bit position. At the same time the trailing bit position inputs as well as the input carry are all ones so that they produce a trailing sum of one bits and they carry one into the bit position of condition P. Also, each of the leading bit positions must produce a half sum H that becomes a sum bit of one in the absence of a carry.

The third condition which produces a sum of all ONES is where the carry in is zero and all bit positions produce a half sum H so that no carrys are produced and all bit position sums remain one.

To express the above three conditions mathematically:

Next, the first two terms of equation 17 are combined to yield equation 18 below since (G.sub.0 + P.sub.0) = H.sub.0.

The first two terms of equation 18 are combined to yield equation 19, noting that H.sub.0 .sup.. H.sub.0 = P.sub.1 .sup.. G.sub.1 = 0.

The process of combining the first two terms is repeated until only a single term remains, as shown in equation 20.

A circuit can be built implementing equation 20 and such a circuit would be fast acting. However, an alternate implementation which might take an additional level of logic and, therefore, be somewhat slower but which would need fewer circuits to implement, makes use of the functions generated in the carry look ahead portion of a carry look ahead adder. This alternate implementation makes use of the input carry C.sub.out to replace the expression in equation 20

The output carry can be generated early; i.e., prior to the sum, so that ONES is available concurrently with or earlier than the sum. The alternate equation is:

It is derived as follows; C.sub.out can be expressed as in equation 22.

Equation 22 is now substituted for each P (P.sub.0, P.sub.1, etc.) term is equation 20 to yield equation 23. For each substitution of a P.sub.K with C.sub.out, only the corresponding term in equation 22 is relevant (i.e., the term containing P.sub.K); the other terms drop out because H.sub.K, P.sub.K, and G.sub.K are mutually exclusive.

Equation 23 is now reduced iteratively by combining the first two terms until only a single term remains. That expression is

where (C.sub.out + H.sub.0) is interchangeable with (C.sub.out + G.sub.0) since C.sub.out includes P.sub.0 and G.sub.0 + P.sub.0 = H.sub.0.

Generally, an adder design produces the single-bit functions, H, P, and G, earlier than C.sub.out. Equation 24 may therefore be restated as in equation 25 to permit a single level of delay between the production of C.sub.out and the detection of ONES.

ONES may also be expressed as a function of some intermediate carry, C.sub.K, as follows:

The method for detecting a sum of all ones can be generalized to radices > 2. The corresponding condition is for each sum digit to be equal to radix-less-one when normalized to the lowest integer position (radix.sup. 0 = 1).

where the subscripts, 0 through n-1, refer to digit positions high-to-low-order, respectively.

The following functions of a digit position, K, will be used:

(K).sub.2(r.sub.-1) = the normalized algebraic sum, (A.sub.K + B.sub.K), is equal to 2 (r- 1)

(K).sub.r.sub.-2 = the normalized algebraic sum, (A.sub.K + B.sub.K), is equal to 2 (r-2)

(K).sub.r.sub.-1 = the normalized algebraic sum, (A.sub.K + B.sub.K), is equal to (r- 1)

For binary (r=2), the functions (K).sub.2(r.sub.-1) , (K).sub.r.sub.-2, (K).sub.r.sub.-1 correspond to G.sub.K, P.sub.K, H.sub.K, respectively.

The conditions for generating a sum all of whose digits are equal to radix-less-one are enumerated in equation 27. The function will be referred to as SDRLO which stands for Sum Digits Radix Less One.

In words, SDRLO is generated if one of the three conditions is satisfied:

1. In each digit position, the normalized algebraic sum (A.sub.K + B.sub.K) is 2(r-1) and C.sub.in = 1. Each digit position generates a carry with a remainder of r- 2 which combined with the carry entering the digit produces a final sum of r- 1.

2. The normalized algebraic sum in one and only one digit position (A.sub.K + B.sub.K) is r-2. In each trailing digit position the normalized algebraic sum is 2(r-1) which produces a carry; C.sub.in = 1; and in each leading digit position the normalized algebraic sum is r-1. Therefore, the respective carry that enters a trailing digit position as well as the digit position K produces a sum digit of r-1. Since no carry is generated in digit position K, the leading digit positions retain sums of r-1.

3. C.sub.in is 0 and the normalized algebraic sum in each digit position (A.sub.K + B.sub.K) is r-1.

The next step is to compress equation 27 by combining the first two terms. That equation is then simplified by the combining of its first two terms and the compression process is continued until the equation reaches a single term which is shown below.

A circuit to implement equation 28 may be built to detect SDRLO for any radix.

The alternate implementation which makes use of the output carry, C.sub.out, or an intermediate carry is not applicable to radices greater than two. The reason is apparent from equation 29 below. For radix = 2, (K).sub..sub.<(r.sub.-1) = (K).sub.r.sub.-2, while for radix > 2, (K).sub.<.sub.(r.sub.-1) .noteq. (K).sub.r.sub.-2.

Note that (K).sub.<.sub.(r.sub.-1) means that the normalized algebraic sum of a digit position (A.sub.K + B.sub.K) is less than r-1 with a minimum value of 0.

For decimal (r=10), equation 28 becomes:

Let (A.sub.8, A.sub.4, A.sub.2, A.sub.1) and (B.sub.8, B.sub.4, B.sub.2, B.sub.1) be the BCD (binary-coded decimal) representation of the addend and augend digits respectively. The subscripts (8, 4, 2, 1) refer to the weight of the respective bits comprising a decimal digit.

Then,

equations 31, 32 and 33 are the individual digit functions that are readily derived from a truth table. It is assumed that an input digit has a range of values 0-9 and values 10-15 are "don't-care" conditions, i.e., A.sub.8 .sup.. (A.sub.4 + A.sub.2) = B.sub.8 .sup.. (B.sub.4 + B.sub.2) = 0.

FIG. 1 provides a simplified perspective of a typical prior art 32-bit parallel binary adder with the carry look ahead feature. Note that the augend and addend bits for each bit position are fed as inputs to the adder at the single bit position function circuits illustrated at 10, 11 and 12. The output of these single bit function circuits are the carry generate G, carry propagate P and half sum H functions (pulses) described above. The G and P pulses for each bit position are fed to the carry look-ahead logic circuits, generally designated at 13, for the production of carry pulses. Once produced these carries may be combined with the previously produced half sums to produce the sum of the addend and augend bits at each bit position. A complete explanation of adders with the carry look ahead feature is to be found in the incorporated references and no further discussion of the overall functioning of the adder or the equations on which it is based is necessary at this time. However, FIG. 2 will explain the manner in which single bit functions may be generated using the logic family of circuits known as NAND/AND-DOT.

Referring first to FIG. 2D note that two inputs V and W are fed into a NAND circuit 15 and two inputs X and Y are fed into a second NAND circuit 16, and the outputs of the two circuits 15 and 16 are dotted at 17. The result is (V .sup.. W) .sup.. (X .sup.. Y). This result is obtained since a NAND circuit output represents the ANDing of the input and then inverting the result. Consequently, the output of circuit 15 is V .sup.. W and the output of circuit 16 is X .sup.. Y. The AND-DOT at 17 is a joining together of the two outputs such that we have the output of circuit 15 AND the output of circuit 16. Another manner of expressing the output is through the application of deMorgan's Rule: (V + W) .sup.. (X + Y) = (V .sup.. W + X .sup.. Y). Unless otherwise labeled or identified, all rectangular blocks in the drawings are NAND/AND-DOT circuits in accordance with FIG. 2D.

Now refer to FIG. 2A which is a circuit showing the generation of the sum at digit K from the inputs A.sub.K and B.sub.K. As explained above in the mathematical analysis, the function G is defined as the carry generate of a bit position, the condition in which both A and B are on. Consequently, in a logic circuit such as circuit 18 in FIG. 2A the inputs A and B are ANDed together with a resulting output of G. However, since this is a NAND circuit and not a simple AND circuit the output is inverted and it is G. As explained above in the definitions of the carry propagate function P, P is the condition found when one or the other bit position is on or both are on, such that a carry into that bit position will be propagated to the next bit position. Therefore the function P can be implemented in NAND/AND-DOT logic by feeding input A into NAND circuit 19 resulting in an output of not A while input B is fed into the NAND circuit 20 resulting in an output of not B. Consequently, the outputs of circuits 19 and 20 together are not A and not B. If these two outputs are ANDed together at DOT 21 the result is the function P, that is, neither bit is on, and by inverting P at inverter circuit 22 the function P is obtained. From the basic functional relationships set forth above, the ANDing of P and G provides the function H. That is performed in NAND circuit 23 which since it is a NAND circuit and not a simple AND circuit results in the production of the complement H. The same ANDing function may be accomplished without the inversion simply by combining the two lines G and P together as shown by the grouped conductors 24. The half sum H and the complement of the half sum, H, may now be combined with the appropriate input carry to form the summation of the addend-augend pair at that digit position in the adder. Again, the expression for this summation is in the prior art and is explained in the incorporated references. Note that to obtain the inversion of the input carry an inverter circuit is used at 25 and note also that the NAND circuits 26 and 27 are DOT ANDed at 28 to produce the sum at digit K.

FIG. 2B is identical to FIG. 2A with one exception. In FIG. 2B the complement of the inputs is used, A.sub.K, B.sub.K, and the input carry is also inverted. The result using NAND/AND-DOT logic is the complement of the sum at the digit position.

FIG. 2C is another version of the adder using input carries where both the true input A and B, and the complement A and B, are initially available. The result is a faster adder but there is a need for additional logic circuits in order to take advantage of all of the inputs. A comparison of the three circuits shows that there are five logic levels A, B, C, D and E for the circuits shown in FIGS. 2A and 2B in addition to whatever number of logic levels are necessary to produce the carries over and above the two logic levels already provided, while for the circuit shown in FIG. 2C there are only two logic levels A and B in addition to those extra levels necessary to produce the carries. It is this reduction in logic levels that increases adder speed. Note, however, that five circuits, 18, 19, 20, 22, and 23 were all that were necessary to produce G, P, and H in FIGS. 2A and 2B while ten circuits (all at logic level A) are needed in FIG. 2C.

FIG. 3 is a circuit implementing equation 4 for the detection of a ZEROS sum. Certain circuit constraints of a practical nature have been embodied in the design of FIG. 3. These circuit constraints are (1) the maximum fan-in is assumed to be 8, (2) the maximum DOTting capability is 8 and (3) the maximum fan-out is equal to 11 minus the number of NANDs in the DOT.

The implementation shown in FIG. 3 makes use of deMorgan's Rule which is to the effect that the OR of two functions is equal to the inverse of the ANDing of the complement of the two functions. Consequently, the input signals shown at the first level of logic in FIG. 3 represent the complements of the functions shown in equation 4 so that the OR functions shown in equation 4 are converted to AND functions for the NAND logic family in use to implement this invention. Since the maximum fan-in to a logic circuit according to the circuit constraints defined above is 8, 8 inputs are shown to logic circuit 100, 8 to logic circuit 101, 8 to 102 and 8 to 103. Were a logic circuit available with a fan-in that could handle all of the inputs, a single block signifying such a logic circuit could replace the four blocks 100 through 103.

Similarly, at the first logic level A, the pulses H.sub.0 and P.sub.1 are combined in NAND circuit 104. NAND circuit 105 contains as inputs H.sub.1 and P.sub.2. Similar NAND circuits not shown are provided for each of the 32 factors in equation 4 of the H and P combination. The last factor in the chain has as inputs H.sub.31 and C.sub.in which are shown feeding NAND circuit 136.

According to equation 4 the output of each of the H and P ANDs are ORed together. Consequently, the output of each of the H and P NAND circuits (which is inverted) must be ANDed together and this may be done in DOT fashion such as shown in DOTs 137, 138, 139, 140, 141 and 142. While maximum DOTting according to the circuit design constraints above is 8, maximum DOTting cannot be used in this circuit at this point since the third constraint tells us that the maximum fan-out is equal to 11 minus the number of NANDs in the DOT. We note from the second logic level B that the fan-in must equal 5 since there are 5 NAND circuits in that level. Consequently, the maximum DOTting which can be used is 6 according to the third circuit restraint. At the second logic level NAND circuits 143, 144, 145, 146 and 147 provide an ANDing signal for the inverse of what was to be ORed in equation 4. Note at each NAND circuit 143-147 contains 7 inputs, thus satisfying the first circuit constraint defined above. The output of circuits 143-147 is then ANDed together to produce the ZEROS sum except that since circuits 143 through 147 are NAND circuits the result is an inverted ZEROS sum. Thus, a circuit has been provided to implement equation 4 and it should be noted that the production of the ZEROS sum is totally independent of the carry look ahead feature of the adder. Once the individual bit position pulses H and G have generated it takes only two additional logic levels to detect a summation which results in all zeros. This detecting operation can be accomplished while the carry-look-ahead circuits are generating carries and thus the detection will be completed before the final summation is made.

FIG. 4 is an alternative implementation for detecting the ZEROS sum and is based on equation 9 which makes use of the carry look ahead feature of the adder, specifically making use of the final carry, C.sub.out. Such a circuit provides the least number of additional logic circuits necessary for inclusion in an adder to implement the early detection of a ZEROS sum according to the invention herein. A comparison of this logic to the number of logic circuits in FIG. 3 illustrates the simplified nature of the circuit found in FIG. 4. However, there is additional delay in detecting the ZEROS sum when using the circuit of FIG. 4 since the ZEROS sum cannot be obtained until the input signal C.sub.out is finally obtained in the carry look ahead portion of the adder. In FIG. 4, the detection of a ZEROS sum occurs one logic level after the production of C.sub.out and therefore would occur simultaneously with the summation of A, B and carry bits in the parallel binary adder shown in the incorporated references.

The H and P inputs of equation 9 are ANDed by NAND circuits 150 as shown at logic level A in FIG. 4. This factor is then ANDed with C.sub.out in circuit 151 and ANDed with H.sub.0 in circuit 152 at logic level B. The two factors are then ANDed at Dot 153 producing the complement of the ZEROS sum. Again, NAND/AND-DOT logic has been used with the circuit constraints mentioned above.

FIG. 5 provides still another alternative implementation for detecting the ZEROS sum. The circuits shown in FIG. 5 is based on equation 10 above where the carry look ahead feature of the adder is used in obtaining the ZEROS sum, but instead of using C.sub.out some intermediate carry signal is used. Actually any intermediate carry can be used but in the particular implementation shown in FIG. 5, the carry into the 24th bit of the 32-bit adder has been used. The purpose of using an intermediate carry is to obtain a detection of the ZEROS sum sooner than would be possible if it were necessary to wait for the production of C.sub.out. This may be readily observed with respect to the incorporated reference entitled "A One Microsecond Adder Using One Megacycle Circuitry." Refer to FIG. 10 of that reference, and it is obvious that in that particular circuit the carry bits at the four low order positions are generated at a logic level earlier than any other of the carry bits. In the incorporated reference the next 16 low order carry bits are generated at a next logic level and finally the remaining carry bits for that particular adder. Using the circuit technology in which the instant invention has been explained, the low order seven carry bits would be obtained on the first clock cycle (logic level) of the carry look ahead portion of the adder since the circuit constraint herein has a maximum fan-in of 8 lines. Consequently, C.sub.24 would be produced on the very first logic level of the carry look ahead operation. For that reason C.sub.24 has been chosen as the intermediate carry pulse to be used in the circuit implementation shown in FIG. 5. Again, however, any intermediate carry could be used. Note that the circuit of FIG. 5 uses fewer logic circuits than the implementation of FIG. 3, but uses considerably more logic than the circuit of FIG. 4. Generally, the use of the C.sub.out pulse provides the least logic, the use of only the C.sub.in pulse requires the most logic and the use of an intermediate carry pulse will be inbetween. Conversely, the use of only the C.sub.in pulse provides the fastest circuit, the use of the C.sub.out pulse the slowest circuit and the use of an intermediate carry pulse somewhere inbetween.

In FIG. 5 note that the combination of H and P pulses is made in logic circuits 160 while the combination of H and G pulses is made in circuits 161. These are then ANDed together in circuits 162 together with the intermediate carry pulse C.sub.24. The final AND is made at DOT 163 for detecting the ZEROS summation.

FIGS. 6, 7 and 8 follow the same rationale for the early detection of SDRLO that was just discussed above with respect to FIGS. 3, 4 and 5 relating to the early detection of a ZEROS sum. FIG. 6 relates to FIG. 3, FIG. 7 relates to FIG. 4 and FIG. 8 relates to FIG. 5.

In FIG. 6 equation 20 has been implemented for the early detection of a sum of all ONES in the binary adder. Again, NAND/AND-DOT logic has been used with the same circuit constraints that were identified above relating to fan-in, fan-out and DOTting. In FIG. 6 the H and P pulses representing the H and P factors of equation 20 are ANDed together in four NAND logic circuits 170. The H and G pulses together with the C.sub.in signals are ANDed together in the 32 NAND logic circuits shown at 171. The outputs of the circuits 170 and 171 are then ANDed together in five NAND logic circuits 172, and the final AND is made at DOT 173 for the detection of ONES. Note, for NAND circuits 170 a maximum fan-in of 8 inputs is provided. Since there are 5 logic circuits 172 to handle the outputs of logic circuits 170 together with C.sub.in, a fan-out of 5 is required from logic circuits 171. With that requirement the maximum allowed DOTting for circuits 171 is 6.

FIG. 7 shows an implementation of the circuit for detecting SDRLO when C.sub.out is used according to equation 25. Again, this circuit is much simpler than the previous circuit but is slower since the final AND cannot be accomplished until the C.sub.out pulse has been obtained through the operation of the carry look ahead circuits. Since the discussion of this circuit follows that for FIG. 4, no further description is needed here.

FIG. 8 shows an implementation of equation 26 where an intermediate carry pulse has been utilized in the formation of SDRLO. In this case C.sub.24 has been chosen so that FIG. 8 will coincide with that already described in FIG. 5. As a result, no further discussion of FIG. 8 is needed.

FIG. 9 is a typical n-digit radix-r parallel adder with carry look ahead. FIG. 9 is similar to FIG. 1 which was a parallel adder with carry look-ahead for the binary case. For example, the inputs to the adder, the augend A and the addend B, are shown entering the digit function circuits 10', 11' and 12' and the circuits which implement these digit functions are similar to the single bit function circuits 10, 11 and 12 of FIG. 1. However, for a generalized radix the functions (pulses) are expressed as shown at 30, 31 and 32 (for the high order digit) instead of the simple G, P and H binary functions. Digit pulses 30 and 31 (for all digit positions) are fed to the carry look ahead circuits of the adder in a similar manner to G and P in FIG. 1. The output of the carry look ahead circuits 13' are the carry pulses for each digit position. They are fed back to the summation circuits for each digit position to produce the final sum in a manner similar to that of FIG. 1.

FIG. 10 is a generalized radix representation of the adder of FIG. 9 with the additional circuits necessary for detecting a sum of ZEROS and a sum of digits of the radix less 1. Note that the carries from the carry look ahead circuits are not used to detect the ZEROS condition or the radix less 1 condition. The five functions (pulses) needed are shown at 180. Of these functions, the zero function at the Kth digit is used in the detection of the ZEROS sum together with the r function at the Kth digit and the r - 1 function at the Kth digit. For detecting the r - 1 sum at all digits, the function r - 2 for the Kth digit, the function 2(r - 1) for the Kth digit and the function r - 1 for the Kth digit are all needed. Thus, the function r - 1 at the Kth digit is common to both detection circuits.

FIG. 11 shows the circuits needed to implement equation 12 to detect the ZEROS sum for the case of a generalized radix using as inputs the three needed pulses generated at 180 in FIG. 10.

FIG. 12 shows the circuits necessary to implement equation 28 for the SDRLO sum and is similar to FIG. 11 for the ZEROS sum case using the three needed inputs generated at 180 in FIG. 10. FIGS. 10, 11 and 12 are designed with NAND/AND-DOT logic as are all other circuits herein.

FIG. 13 is a diagram of a typical prior art 8 digit (32-bit) parallel decimal adder with carry look ahead. The single bit function circuits and digit function circuit are shown at 10" , 11" and 12" . The inputs to these circuits for each decimal digit comprise the 4 bits of an augend representation and the 4 bits of an addend representation using the BCD (binary coded decimal) representation of the decimal digit. Circuits for implementing such an adder are found in the incorporated references.

FIG. 14 shows the circuits which must be incorporated in a parallel decimal adder using NAND/AND-DOT logic to produce needed functions for detecting a sum of all ZEROS and a sum of all NINES (SDRLO for r = 10). To understand this circuit, note that since the decimal function of the Kth digit for 2(r - 1) represents a test for the value 18, and since the G function represents the condition where both addend and augend bits are on, the G pulse for the order 8 in a BCD representation represents the condition in which both the addend and the augend contain the digit 8. If that is added to the condition in which both the addend and augend bits representing 1 are on, that is the G pulse for the order 1, the summation of the G.sub.8 pulse and the G.sub.1 pulse is 8 + 8 + 1 + 1 which is 18. Thus, the NAND circuit at 200 which ANDs G.sub.8 and G.sub.1 tests for the presence of 18 at the Kth digit.

In FIG. 14, it is next desired to test for the value 10 at the digit K. Ten can be produced in various fashions, 5 to be exact, through the combination of BCD orders of addend and augend bits. For example, 10 can be reached by detecting both the P pulse and the G pulse for the order 8 which represents the condition in which either the addend or the augend bit is on but not both. If one of the two bits is on an input of 8 is represented by that bit. If an input of 8 (P.sub.8 .sup.. G.sub.8) is added to an input of 2 the result is 10. Two is represented by the pulse G.sub.1 since G.sub.1 represents the condition in which the addend and the augend each contribute 1 in the first order position. At the same time, orders 4 and 2 contribute 0 which can be detected by P.sub.4 and P.sub.2. The P.sub.8 .sup.. G.sub.8 .sup.. P.sub.4 .sup.. P.sub.2 .sup.. G.sub.1 condition would be tested for in logic circuit 201.

Another possibility for reaching the value 10 is to AND the 8 provided by the pulse P.sub.8 with the pulse P.sub.2 which would represent a contribution of 2 by either the addend or the augend at the order 2 position. (Note that the AND P.sub.8 .sup.. P.sub.2 means that at least one bit in order 8 as well as in order 2 are on. This also implies that not more than one bit in order 8 as well as in order 2 is on, because a decimal digit cannot exceed a value of 9, i.e. it cannot have an order 8 bit on simultaneously with an order 4 or an order 2). Orders 4 and 1 contribute 0 as detected by P.sub.4 and P.sub.1. The condition P.sub.8 .sup.. P.sub.4 .sup.. P.sub.2 .sup.. P.sub.1 is tested for in logic circuit 204.

Another two possibilities for reaching the value 10 are as follows. Both bits are on in the 4th order which represents a contribution of 4 from both the addend and the augend, thus, a total of 8. This function is represented by the pulse G.sub.4. The 8 would be added to a 2 to achieve the value 10. The 2 can come from either order 1 alone (G.sub.1) while P.sub.2 contributes 0 or from order 2 along (P2.sup.. G2) while P.sub.1 contributes 0. (Again note that G.sub.4 being on implies P.sub.8 being on due to the fact that a decimal digit cannot exceed 9). These conditions, G.sub.4 .sup.. P.sub.2 .sup.. G.sub.1 + G.sub.4 .sup.. P.sub.2 .sup.. G.sub.2 .sup.. P.sub.1 are tested for by logic circuits 202 and 205 respectively.

The 5th possibility for reaching a value 10 is for a contribution of 4 from the fourth order, P.sub.4 .sup.. G.sub.4, a contribution of 4 from the second order, G.sub.2, AND a contribution of 2 from the first order, G.sub.1. Again G.sub.2 implies P.sub.8. The condition P.sub.4 .sup.. G.sub.4 .sup.. G.sub.2 .sup.. G.sub.1 is tested for in logic circuit 203. In a similar manner the functions for the Kth digit where the value is 9, where the value is 8 and where the value is 0 are tested for as shown in FIG. 14 and as will now be set forth in equation form.

Below, is a table of equations representing the conditions at which the 5 needed functions are found. It is from this table that the circuit of FIG. 14 is derived.

in FIG. 15 equation 13 is implemented in which the detection of a ZEROS sum is generated for the decimal case. FIG. 15 represents an 8 digit adder and uses NAND/AND-DOT logic with the circuit constraints previously noted. The functions necessary for the detection of a sum of all zeros are the functions for the value zero, the value 10 and the value 9. These functions are input to FIG. 15 from the circuit of FIG. 14.

FIG. 16 is an implementation of equation 30 for the detection of all NINES. Again, the needed functions produced in FIG. 14 are fed as inputs into the circuits of FIG. 16. The functions necessary for the detection of a sum of all NINES are the function for the value 18, for the value 8 and for the value 9.

FIG. 17 shows an alternative implementation for the decimal case. This circuit is designed with fewer logic circuits than the circuit shown in FIGS. 14, 15 and 16. The object of the design in FIG. 17 is to make use of commonality in the production of the digit functions which are necessary for the carry look ahead circuits and the digit functions which are necessary for the detection of a sum of all ZEROS and a sum of all NINES. While the generated carries are not of help in simplifying the circuitry for detecting all ZEROS or all NINES for a decimal adder, FIG. 17 does reduce the number of logic circuits necessary to detect those sums by making use of the common need for generating certain functions necessary in the production of generated carries and in the detection of all ZEROS or all NINES. In that manner certain logic circuits can do a double job and the need for separate circuits, one for the carry look ahead and one for the detection of a sum of digits is avoided. The method by which this is accomplished is to divide the digit functions into a summation of the three high order bits, the 8, 4 and 2 bits, separate from the summation of the low order bit.

FIG. 17 shows the true inputs of both addend and augend bits to the single bit function logic circuits 300. Only the true form or the complement form of the single bit functions is needed, and in the illustration the complement functions G and P have been chosen as an example.

At the next logic level circuits 301, the first group of three NAND circuits 303, 304 and 305 generate the digit function where the sum of the 8, 4 and 2 bits is equal to or greater than 12. The second group of two logic circuits 306 and 307, together with circuit 302, at level 301 produce a digit function whose summation of the three high order bits is equal to or greater than 10. The next two logic circuits at level 301 generate a digit function whose sum of the three high order bits is equal to or greater than 8. The fourth logic circuit group at level 301 generates a digit function whose sum of the three high order bits is equal to or greater than 6. Additional functions generated at level 301 are: a digit function whose sum of all bits is equal to 18, a digit function whose sum of all bits is equal to 0, and the complemented functions, G.sub.1 and P.sub.1.

At the next logic level 302 these functions are now used to generate the digit functions necessary as inputs to the carry look ahead circuits and the digit functions necessary as inputs for the detection of all NINES and all ZEROS.

The logic circuits which are shown in FIG. 17 are an implementation of the equations below:

where

as an example of the logic expressed by these equations note that for equation 39, where the function of the digit position K is to have a sum of the 8, 4 and 2 order bits equal or to greater than 12, the only three conditions which satisfy that digit condition are (1) where both bits in the 8 order position are on which provides a contribution of 16; (2) where one bit in the 8 bit position is on providing a contribution of 8 and one bit from the 4 order position is on providing a contribution of 4; and (3) where both bits at the 4 order position are on thus providing contribution of 8 and both bits at the two bit position are on providing a contribution of 4. These are the only three conditions which meet the requirement and that is what is expressed by equation 39. It should be noted that P.sub.8 .sup.. G.sub.2 is an impossibility since a decimal digit can never exceed nine and the above expression implies a ten at either an augend or an addend digit. While a similar explanation in words for the production of the other digit sums, equations 40, 41 and 42, can be made, the above should serve as an adequate example.

Having the threshold digit functions shown in equations 39, 40, 41 and 42 it is now possible to generate the functions necessary for the carry look ahead circuit as shown by equations 34 and 35. In equation 34 note that if the summation of the high order three bits provides a contribution of at least 10 the digit function equal to or greater than 10 will, of course, be generated. Note also that if the upper three bits contribute at least 8 and the low order bit contributes 2 the digit function has also been satisfied. Equation 35 for production of a digit function equal to or greater than 9 is found if the sum of the high order three bits is equal to or greater than 8 and at least one is contributed by the low order position.

Similarly, equations can be written for the production of those single digit functions which are necessary for the detection of ZEROS and NINES. For example, where the digit function is to be equal to 10 that may be found by equation 36 which tells us that if the contribution from the three high order positions is less than 12 but at least equal to 10, and the contribution from the low order digit function is 0, all conditions for the single digit function equal to 10 are met. Equation 36 also shows that 10 is found if the contribution of the digit function from the three high order bits is less than 10 but at least equal to 8, and the contribution from the low order position is 2, the digit function equal to 10 is found. The same analysis may be followed for equations 37 and 38 demonstrating how the production of the functions for the three high order bits provide inputs for the determination of the function for the digit equals 9 and the determination of the function for the digit equals 8. Again, the circuits for implementing these equations are in FIG. 17.

While the invention has been particularly shown and described with reference to a preferred embodiment thereof, it will be understood by those skilled in the art that the foregoing and other changes in form and details may be made therein without departing from the spirit and scope of the invention.