Programmable Logic Array Adder

The present invention relates to adders and more particularly relates to adders which are embodied in programmable logic arrays.

The performing of logic in an array of identical circuit elements each located at a unique intersection of an input and output line in a grid of intersecting input and output lines is well known. There are many such arrangements of arrays for performing logic. One of them is called a programmable logic array (PLA). An example of one type of PLA can be seen in Cox, et al. U.S. Pat. No. 3,987,287. In this PLA input decoders generate min terms and feed them into a first array called a product term generator or an AND array to generate product terms which are functions of the inputs to the decoders. These product terms are fed to a second array called a sum of product term or OR array so as to increase the number of functions that can be performed using these product terms without geometrically increasing the size of the AND array needed to perform these functions. The output of the OR array is fed to latches so that both sequential and combinatorial logic can be performed using this PLA.

Logical functions have been performed by these latches in the prior art. For example, in certain PLAs the latches perform an Ex-OR function. Pages 3635 to 3655 of the May 1975 issue of the IBM Technical Disclosure Bulletin describe an adder which is embodied in PLAs of this type.

In accordance with the present invention a new carry lookahead adder is provided using programmable logic arrays with output latches that perform an AND function. This adder is more efficient than presently known adders embodying feedback through to the AND/OR arrays. This adder has means for feeding every like order set of digits A.sub.i B.sub.i of two multi digit numbers A.sub.0, A.sub.1, . . . A.sub.n-1 and B.sub.0, B.sub.1 . . . B.sub.n-1 into a separate two bit decoder of a PLA and including circuit means in the product term and sum of product term generating arrays to generate any order sum digit S.sub.i of a binary sum of two numbers, S.sub.1, S.sub.2 . . . S.sub.n as the output of one of the latches of the PLA in accordance with either of the following two formulas: ##EQU1##

Other improvements are in the generating of the carry out digit, in the replacement of individual product terms each with a sum of available product terms, and in the arrangement of the strings of sum digits to produce the most efficient use of product terms. Therefore it is an object of the present invention to generate a new adder for embodiment in programmable logic array structures.

It is another object of the invention to generate a new adder for use in a programmable logic array structure that has latches that perform an AND function.

It is a further object of the invention to provide an array logic adder which requires less product terms than known array logic adders using latches that perform an ADD function.

These and other objects of the invention will be apparent from the particular description of the preferred embodiment of the invention of which:

FIG. 1 is a schematic representation of an adder;

FIG. 2 is a diagram showing how FIGS. 2A and 2B are to be placed together to show an adder in accordance with the present invention;

FIG. 3 is a table showing logical functions that can be performed in the AND array of a programmable logic array being fed by two bit decoders.

FIG. 1 shows two n-bit numbers A.sub.0 A.sub.1 . . . A.sub.n-1 and B.sub.0 B.sub.1 . . . B.sub.n-1 being added together with an input carry C.sub.in, by circuitry to produce an n-bit sum S.sub.0 S.sub.1 . . . S.sub.n-1 and an output carry C.sub.out. The circuitry 8 performing the adder function is in the form of programmable logic arrays (PLAs) shown schematically in FIG. 2.

In FIG. 2 corresponding bits of two 8-bit numbers A.sub.0, A.sub.1 . . . A.sub.7 and B.sub.0, B.sub.1 . . . B.sub.7 are fed in pairs to 2-bit decoders 10. The decoders 10 each generate a pulse on a different one of four output lines for each of the four possible combinations of the true and complement of the input bits A.sub.i and B.sub.i supplied to them. Each output line of any decoder 10 is connected to a separate input line 11 of an AND array 12. The blocks 14 in FIG. 2 represent the intersection of each set of four input lines 11 from one decoder 10 with an output line 16. Within each block 14 there are four possible NOR gate connections. These NOR gates are used to connect any of the input lines 11 of the set to the output line 16 passing through the block 14. Selective connection of the input lines to the output line allows one of 16 different logical functions to be performed in any block on the two inputs A.sub.i and B.sub.i to one of the decoders 10 and placed on that output line by the combination of the decoders and the NOR gates within one of the blocks 14.

The different logical functions are shown in the table of FIG. 3. In the table, each of the four columns represents one of the input lines in a four input line set 11 of the AND array. The heading on the columns indicates the combination of true and/or complements of the inputs A.sub.i and B.sub.i fed to the decoder 10 connected to that set of input lines which produces a pulse on the input line represented by the column. The legend on the sixteen rows of the table are all the possible functions that can be performed in the two inputs A.sub.i and B.sub.i to the decoder. The squares formed by the intersection of a row and column each represent an intersection between the input line represented by the column and the output line passing through the block. The number 1 in any square indicates there must be a connection between the input line and the output line at that intersection to generate the function indicated by the legend for that row while the number 0 in the box indicates that there must be no connection to generate that function. Of the 16 possible functions only 6 are of interest in the performance of addition in accordance with the present invention. These are marked G.sub.i ; G.sub.i ; P.sub.i ; P.sub.i ; H.sub.i and H.sub.i in FIG. 3. Performing logic operations using arrays and 2-bit decoders in this manner is well known and can be found in Cox, et al. U.S. Pat. No. 3,987,287, issued Oct. 19, 1976.

Now referring solely to FIG. 2, the row of the AND array represents a product term. For example, row 5 in FIG. 2 contains the product term H.sub.6 G.sub.7, where H.sub.6 is a function of the inputs (A.sub.6, B.sub.6) and G.sub.7 is a function of (A.sub.7, B.sub.7). A blank in any box 14 represents a "don't care" condition in the generation of the product term. The output line 16 for each row of the AND array is connected to an input line of an OR array 18. Each box 20 in the OR array represents the intersection of one of the input lines of the OR array with one of the output lines 21 of the OR array. A one in any one box indicates a connection in the form of a NOR circuit between the input line and the output line at that intersection. An empty box 20 means there is no connection between the intersection of input and output lines represented by that particular box. Thus, each column of boxes 20 in the OR array 10 represents the OR of sum of the product terms in the AND array connected to the output line 21 by the NOR circuits as denoted by the 1s in the boxes of the column. For example, the left-most column of the OR array represents the OR of the product terms shown in rows 35 through 38.

Pairs of adjacent OR columns are ANDED into polarity-hold latches 22. The outputs of the AND circuits 22 are the outputs of the PLAs and the outputs of the adder. Thus, the output C.sub.out is the AND of the two left-most OR columns.

With this type of PLA, an adder design will now be developed, so that each output represents an AND of two functions, each function representing an OR of product terms. A product term will be an AND of functions of the individual bit position inputs to the adder, and the input carry.

(1)

The functions performed on corresponding bits A.sub.i and B.sub.i of the n bit inputs to the adder by the decoders 10 and the NOR circuits in one of the boxes 14 in the AND array are: ##EQU2##

Referring to equations (2), G.sub.i means both bits A.sub.i AND B.sub.i are on, and H.sub.i means one of bits A.sub.i and B.sub.i is on and the other is off. It will be appreciated that a carry C.sub.i out of a sum bit position i will occur if A.sub.i AND B.sub.i are on OR will occur if one of bits A.sub.i and B.sub.i is on and the other is off AND a carry in is received. This can also be expressed as C.sub.i =G.sub.i +H.sub.i .multidot.G.sub.i+1. From equations (2) P.sub.i means bits A.sub.i OR B.sub.i are on. Although some redundancy is introduced, a carry C.sub.i out of a sum bit position i will occur if A.sub.i AND B.sub.i are on OR will occur if either A.sub.i OR B.sub.i (or both) are on AND a carry in is received. This alternate carry expression is simpler from a logic implementation point of view and can be more compactly stated as C.sub.i =G.sub.i +P.sub.i .multidot.G.sub.i+1. Thus in situations where sharing of product terms does not proscribe redundancy, an equivalent order P term can be substituted for any of the H terms of the following equation (3).

By noting that while not carry C.sub.i =P.sub.i +H.sub.i .multidot.P.sub.i+1 it also is true that C.sub.i =P.sub.i +G.sub.i .multidot.P.sub.i+1 and therefore similar redundancy can be advantageously but selectively introduced into equation (4).

Using known carry-look ahead methods, any carry and its complement can be expressed as: ##EQU3##

A sum bit can be expressed as a function of the preceding carry, expanded to a function of some distant carry, and then converted to an AND of two OR functions. One OR function includes the distant carry as one OR term, while the other OR function includes the complement of the distant carry as one OR term. ##EQU4##

Where * indicates that an equivalent order P term may be substituted for the indicated H term and

Where ** indicates that an equivalent order G term may be substituted for the indicated H term.

A similar expression for S.sub.i can be derived to yield equation (9). ##EQU5## Note that some of the product terms in equation (9), H.sub.i .multidot.G.sub.i+1, etc. are common with some of the product terms of equation (3). Similarly for equations (8) and (4). This means that the sum and one of the carries of the same bit position share some product terms.

Equations (8) and (9) indicate that an intermediate carry can service a string of several succeeding (next higher-order) sum bits.

Three types of strings are identified:

1. Low-Order String:

The sum bits are generated as ORs or product terms, as in equations (10) and (11) for the low-order bit and equations (12) and (13) for a higher-order bit. The output latch for a sum bit needs but a single input. If an ANDing latch is included for uniformity, as in FIG. 2, the two OR array outputs to be ANDed are generated identically. Product terms are also generated to represent both polarities of the carry out of the string, according to equations (3) and (4), to be used to generate the succeeding string of sum bits. Note that product terms can be shared between the positive high-order sum bit S.sub.i and the negative output carry C.sub.i of the string, equations (12) and (4), to require only one additional product term for C.sub.i. Similar sharing is possible between S.sub.i and C.sub.i, equations (13) and (3). ##EQU6## 2. Intermediate Strings:

Each sum bit is generated according to equation (8) or (9), making use of the carries generated out of the immediately preceding (lower-order) string. Product terms are again generated to represent both polarities of the carry out of each string, according to equations (3) and (4), to be used to generate the succeeding string of sum bits.

3. High-Order String:

Each sum bit is generated according to equation (8) or (9), making use of the carries generated out of the immediately preceding (lower-order) string. One polarity of the output carry of the string is generated, being equivalent to the output carry of the adder, Cout. Cout is generated as a function of the next lower-order intermediate carry C.sub.q+1 according to equation (14) or (15). ##EQU7##

The H.sub.o terms will be shared with high order sum bits and therefore substitution for H.sub.o terms will not prove to be advantageous. ##EQU8##

The product terms for C.sub.q+1 or C.sub.q+1 are already available from the preceding string. Of the remaining unique product terms of Cout, all but two, G.sub.o and H.sub.o .multidot. . . . .multidot.H.sub.q, are common with some of the product terms of S.sub.o generated according to equation (9). Therefore, Cout needs only two additional product terms over those required for the sum bits. Similarly, if the high-order string of sum bits is positive, implemented according to equation (8), the negative output carry Cout needs but two additional product terms, P.sub.o and H.sub.o .multidot. . . . .multidot.H.sub.q.

The number of product terms can be further reduced through additional product sharing as follows:

1. The product term (H.sub.i .multidot. . . . .multidot.H.sub.i+j) in equation (8) or (9) for a sum bit S.sub.i or S.sub.i can be replaced by the OR of the two product terms (H.sub.i-1 .multidot.H.sub.i .multidot. . . . .multidot.H.sub.i+j) and (H.sub.i-1 .multidot. . . . .multidot.H.sub.i+j) of the next higher sum bit S.sub.i-1 or S.sub.i-1 in the same string. In turn, the product term (H.sub.i-1 .multidot. . . . .multidot.H.sub.i+j) can be replaced by the OR of the two product terms (H.sub.i-2 .multidot.H.sub.i-1 .multidot. . . . .multidot.H.sub.i+j) and (H.sub.i-2 .multidot. . . . .multidot.H.sub.i+j) of the sum bit S.sub.i-2 or S.sub.i-2 in the same string. The replacement can be continued in this fashion through the two product terms (H.sub.i-w .multidot.H.sub.i-w+1 .multidot. . . . .multidot.H.sub.i+j) and (H.sub.i-w .multidot. . . . .multidot.H.sub.i+j) of the highest order sum bit of the string, S.sub.i-w or S.sub.i-w.

For a low-order or an intermediate string, the product term (H.sub.i-w .multidot. . . . .multidot.H.sub.i+j) can be further replaced by the OR of some of the product terms of the opposite polarity output carry of the same string. For a positive high-order sum bit S.sub.i-w of a string, the product term (H.sub.i-w .multidot. . . . .multidot.H.sub.i+j) is replaced by: ##EQU9## of the output carry of the string, C.sub.i-w, while for a negative high-order sum bit S.sub.i-w of a string, it is replaced by: ##EQU10## of the output carry of the string, C.sub.i-w.

2. The second highest order sum bit of a low-order string or an intermediate string is selected to be of opposite polarity from the highest order sum bit of the string. This permits additional product term sharing between the two high-order sum bits of the string. For example, a positive high-order sum bit S.sub.i of a low-order string is generated according to equation (12). The product terms (H.sub.i .multidot.H.sub.i+1 .multidot.G.sub.i+2) through (H.sub.i .multidot. . . . .multidot.C.sub.in) of equation (12), together with the product terms (H.sub.i .multidot.H.sub.i+1 .multidot. . . . G.sub.i+2) through (H.sub.i .multidot. . . . .multidot.C.sub.in) of equation (3) representing the output carry C.sub.i of the string, can replace the product terms (H.sub.i+1 .multidot.G.sub.i+2) through (H.sub.i+1 .multidot. ... .multidot.C.sub.in) of the negative second highest order sum bit S.sub.i+1 of the same string when applying equation (13) to S.sub.i+1. Similarly, a positive high-order sum bit S.sub.i of an intermediate string is generated according to equation (8). The product terms (H.sub.i .multidot.H.sub.i+1 .multidot.G.sub.i+1) through (H.sub.i .multidot. ... .multidot.G.sub.i+j) of equation (8), together with the product terms (H.sub.i .multidot.H.sub.i+1 .multidot.G.sub.i+2) through (H.sub.i .multidot. ... .multidot.G.sub.i+j) of equation (3) representing the output carry C.sub.i of the string, can replace the product terms (H.sub.i+1 .multidot.G.sub.i+2) through (H.sub.i+1 .multidot. . . . .multidot.G.sub.i+j) of the negative second highest order sum bit S.sub.i+1 of the same string when applying equation (9) to S.sub.i+1.

In the same fashion, some of the product terms of a negative high-order sum bit S.sub.i beginning with (H.sub.i .multidot.H.sub.i+1 .multidot. . . . .multidot.P.sub.i+j), together with some of the product terms beginning with (H.sub.i .multidot. . . . .multidot.P.sub.i+j) of the output carry C.sub.i, can replace some of the product terms beginning with (H.sub.i+1 .multidot.P.sub.i+j) of the second highest order sum bit S.sub.i+1 --of a low-order string or an intermediate string.

The number of unique product terms needed for the various strings are derived as follows:

1. Low-Order String:

Using equations (10) and (12) or (11) and (13), the sum bits take 2, 4, 6, etc. product terms for succeeding high-order sum bits. For K sum bits, the number is K(K+1). The output carries of the string take (K+2) using equations (3) and (4) and noting that one of the carries shares all but one product term with the high-order sum bit of the string. Product terms saved due to opposite polarity of the two high-order sum bits are (K-1). Therefore, the total number of product terms needed for a low-order string of H is:

(16)

2. intermediate String:

Using equations (8) or (9), the sum bits take 2, 4, 6, etc. product terms for succeeding higher-order sum bits. For K sum bits, the number is K(K+1). The output carries of the string take 2(K+L+1), less the number shared by one of the output carries with the high-order sum bit, (K-1), for a net of K+3+2L, where L is the number of low-order bit positions up to but not including this string. Product terms saved by replacing (H.sub.i .multidot. . . . .multidot.H.sub.i+j) in equations (8) or (9) are K, while those saved due to opposite polarity of the two high-order sum bits are (K-2). Therefore, the total number of product terms needed for an intermediate string of K is:

(17)

3. high-Order String:

Using equations (8) or (9), the sum bits take 2, 4, 6, etc. product terms for succeeding high-order sum bits. For K sum bits the number is K(K+1). The output carry of opposite polarity takes but two additional product terms according to equation (14) or (15), noting that some of the product terms are shared with those of the high-order sum bit. Product terms saved by replacing (H.sub.i .multidot. . . . .multidot.H.sub.i+j) in equations (8) or (9) and by sharing between the high order sum bit and the output carry are K. Therefore:

(18)

the next step is to optimize string sizes. The criterion is to normalize the number of unique product terms assigned to a string with respect to the string size, i.e. to divide the number by the string size. For the low-order string, the optimum size is 2. (This follows when T.sub.low divided by K is computed for K=1, 2, 3, etc., yielding 5, 4.5, 5, and higher values.) For the intermediate strings, we determine the location of the string expressed in terms of L (the number of lower-order bit positions) where a string of K+1 becomes equally as efficient as a string K. The breakeven value of L is derived as follows:

For string size K+1 to be as efficient as string size K, ##EQU11## It shows that for L=0.5, an intermediate string of size 3 is as efficient as one of size 2. With L=3.5, a string size 4 is as efficient as size 3, etc. We also note that successive breakeven values of L are incremented by successive integers of value K. For example, the transition of string size efficiency from 4 to 5 occurs at a value of L four greater than the transition from 3 to 4, and the transition from 5 to 6 occurs at a value of L five greater than that from 4 to 5, etc. This means that after a low-order string of 2, the optimum string sizes are 3, 4, 5, etc.

We shall now apply the above equations to the design of an 8-bit adder, the schematic of which appears in FIG. 2.

We arbitrarily choose positive strings. The first (low-order) string is two bits long; it includes the functions S.sub.6, S.sub.7, C.sub.7, C.sub.7 which require nine product terms according to equation (16).

The next string is an intermediate string where L is 2. The optimum string size is 3, which requires 18 product terms according to equation (17), producing S.sub.3, S.sub.4, S.sub.5, C.sub.3 and C.sub.3.

The last high-order string can only be of size 3 to produce S.sub.0, S.sub.1, S.sub.2 and C.sub.out and takes eleven new product terms as per equation (18).

In general, if the last string is equal to or one greater than the next-to-last string, the procedure is completed, even if this results in two equal high-order strings. If the last string is one less than the next-to-the-last string, the last string is increased by one while the low-order string is reduced by one to a 1-bit string. If the last string is at least two less than the next-to-last string, the last string is deemed a remainder to be absorbed into one or more preceding strings. Not more than one extra bit to a string is assigned. Priority is given to intermediate strings and then to the low-order string.

The following illustrates the procedure:

This procedure yields an optimum solution, although for the same number of bit positions, other optima may be possible.

Tables 1, 2 and 3 illustrate the arrangement of strings and the product terms needed for 8, 16 and 32 bit adders respectively according to the invention.

Referring again to FIG. 2 and recalling the description of the invention under low order strings and equations (12) and (13) it may be noted that the AND input gate latches 22 for the low order string of sum bits S.sub.6 and S.sub.7 may be replaced with simple latches. This will be made more apparent by noting that connections in the right most columns 20 of OR array 18 are duplicated for each input to the AND input gate latches.

The sharing to product terms of a lock ahead carry among more than one sum bit position is graphically portrayed by noting that carry product terms generated by first and second portions of AND array designated C.sub.6 and C.sub.6 are shared by sum bit positions S.sub.3, S.sub.4, and S.sub.5. In order to permit such sharing without interference, product terms of rows 10, 12, 15, 25, 26, 27 are made part of the summation of product terms for sum bit position S.sub.5 by way of example.

The sharing of product terms by the high order sum bit of a string of sum bits and the carry out from the string is shown graphically at rows 6, 8, 9, 35, 36, 37, 38, as well as at other rows for the intermediate string.

The sharing of product terms by a low order string or an intermediate order string may be improved by selecting the polarity of the two highest order sum bits of the string to be of opposite polarity as described earlier. This improvement is shown graphically in FIG. 2 at row 3.

From the description of the preferred embodiment of the invention one skilled in the art will recognize a variety of applications for the invention and appropriate modifications within the scope of the claims. An example of such modification is the selective substitution of P terms for H* terms and G terms for H** terms described earlier.