Logical Circuit Array

The present invention relates to logical circuit arrays, and more particularly to an array topology for a dynamic logical circuit array, in which the AND and OR planes are folded together, with the gates of all logic cell transistors oriented in the same direction when the array is fabricated as an integrated circuit.

In the past, programmable logic arrays have been used to provide complex electronic circuitry on semiconductor chips. Typically, the circuit components, e.g. transistors, which form the programmable logic array are arranged in a grid-like manner, using horizontal "rows" and vertical "columns" for carrying various signals. One section of such programmable logic arrays uses rows to form an "AND plane". Another section uses columns to form an "OR plane".

The AND plane functions by looking at data which is present on various data columns in the array (separate from the columns which constitute the OR plane), and if the condition of all of the data columns looked at is "true", the associated AND plane row will be driven so that it is also "true". Thus, the AND function is a logical function in which the output follows the input if, and only if, all of the input signals are "true".

The OR plane of a programmable logic array looks at selected rows of the AND array, and if any one or more of the rows looked at are "true", the associated OR column will be forced "true". Thus, if any one of the inputs which the OR plane looks at is "true", i.e., the first input is true "or" the second input is true "or" the third input is true, etc., the output of the OR plane will be "true".

In addition to the AND plane and OR plane, other elements, such as memory cells, can be incorporated into a programmable logic array. With proper interconnection, the elements of a programmable logic array can be designed to perform many different functional tasks, thereby providing specialized digital processors for almost any end use imaginable.

One drawback to programmable logic arrays known in the art is that since the rows associated with the AND plane are horizontal, and the columns associated with the OR plane are vertical, the transistors associated with the AND plane are rotated 90.degree. with respect to the transistors associated with the OR plane. This presents difficulty in fabricating programmable logic arrays, in the form of integrated circuits, without wasting space on the semiconductor chip. In one attempt to save space, the AND plane and OR plane have been "folded" together, so that the transistors which provide the AND and OR functions are intermingled in one area of the array, instead of the AND plane being placed in one section of the array, with the OR plane in another section. Even in structures where the AND and OR planes have been folded, the AND and OR transistors were rotated 90.degree. with respect to one another.

It would be advantageous to provide a logical circuit array structure in which the array transistors all have their gates oriented in one direction, and do not have to be rotated by 90.degree. for the AND and OR plane connections. Such a structure would enjoy enormous space savings over prior programmable logic array designs. The present invention provides such a structure.

A logical circuit array is provided which comprises a plurality of AND rows R.sub.0 through R.sub.n and means for precharging the AND rows to one logic level. An additional row R.sub.a is provided along with means for precharging the additional row to another logic level. A plurality of data columns are provided, and an output column is coupled to AND row R.sub.0. A plurality of logic cells is divided among AND rows R.sub.0 through R.sub.n-1, each logic cell having an input terminal coupled to a data column, a first output terminal connected to the AND row with which the logic cell is associated, and a second output terminal connected to the next successive AND row in the array. A plurality of logic cells is also associated with AND row R.sub.n, each logic cell associated with AND row R.sub.n having an input terminal coupled to a data column, a first output terminal connected to AND row R.sub.n, and a second output terminal connected to additional row R.sub.a. The AND conditions of signals on the data columns are formed on the AND rows by the logic cells associated therewith, and the OR condition of the AND rows is formed on the output column.

The array can be expanded by providing additional groups of AND rows with associated logic cells, and means for precharging the additional AND rows to said one logic level. In such an expanded array, means are provided for coupling the first row of each additional group to an output column, and for coupling the last row of each additional group to the additional row R.sub.a. Memory elements can be interspersed within the array to enable complex logical functions to be implemented. Such memory elements can have an input coupled to one of the output columns and an output coupled to drive one of the data columns.

A logical circuit array in accordance with the present invention can be implemented in any of the well known technologies, such as NMOS or CMOS. In a preferred embodiment, the "one logic level" to which the AND rows are charged is a logical high, and the "another logic level" to which the additional row is precharged is ground. In operation, the OR condition of the AND rows is formed by discharging successive AND rows to ground via additional row R.sub.a, in effect rippling the logic level of additional row R.sub.a through the AND rows until it reaches row R.sub.0, to which the output column is coupled.

The present invention also provides a method for processing data in a logic array comprising the steps of precharing a plurality of AND rows to one logic level, precharging an additional row to another logic level, arranging a plurality of logic cells in each AND row to form on each respective AND row the AND condition of data from a plurality of data columns driving the logic cells in that AND row, coupling the AND rows and the additional row together through the logic cells, and rippling the logic level of the additional row through the logic cells to successive AND rows to form the OR condition of all of the AND rows on the AND row most remotely coupled to the additional row. The method can comprise the further step of reading the OR condition of the AND rows from an OR column coupled to the AND row which is most remotely coupled to the additional row. The additional row can be precharged to ground, and the AND rows precharged to a logical high.

FIG. 1 is a truth table for a two bit counter;

FIG. 2 is a Karnaugh map for the D.sub.0 term of the truth table of FIG. 1;

FIG. 3 is a Karnaugh map for the D.sub.1 term of the truth table of FIG. 1;

FIG. 4 is a schematic representation of a conventional programmable logic array implementing the truth table of FIG. 1;

FIG. 5 is a schematic representation implementing the truth table of FIG. 1 in accordance with the present invention;

FIG. 6 is a timing diagram of the two clocks used in the implementation shown in FIG. 5;

FIG. 7 is a simple example of a logical circuit array in accordance with the present invention; and

FIG. 8 is a logical representation of the array of FIG. 7.

The present invention will be described through the implementation of a two bit counter. A two bit counter is just one of the almost infinite number of different circuits which could be implemented in accordance with the present invention. However, in order to demonstrate the advantages and operation of the present invention, the simple two bit counter serves as a useful example.

The truth table for a two bit counter is shown in FIG. 1. The K and C signals are clear and count inputs to the counter, respectively. A.sub.1 and A.sub.0 are the present state of the two D type flip-flops in the counter. D.sub.1 and D.sub.2 are the next state D inputs to the counter.

In the design of digital systems, truth tables, such as that shown in FIG. 1, can be simplified and expressed as a logical expression. The form most desirable for circuit synthesis is the so-called "sum of products" form. In this form, the expression is given as a "sum" of terms, each of which is a simple "product" of variables or their complements. A sum of products expression can be further simplified to the "minimal" sum of products expression. By casting a truth table, such as that shown in FIG. 1, in a slightly different form, the minimal expression may be written by inspection. In particular, it is useful to rearrange the truth table in a two-dimensional form, called a Karnaugh map. Karnaugh maps for the D.sub.0 and D.sub.1 terms of the truth table of FIG. 1, are shown in FIGS. 2 and 3 respectively. Each square in a Karnaugh map corresponds to some particular combination of terms. Thus, each square in the map corresponds to a line in the truth table. In the Karnaugh map of FIG. 2, the terms K and C are stacked vertically, and the terms A.sub.1 and A.sub.0 appear horizontally. The corresponding D.sub.0 term appears within the map. D.sub.0 is "true" whenever a 1 appears in the map. The minimal sum of products expression is determined by grouping adjacent true terms in the map, as shown by the dotted lines in FIG. 2. As shown, D.sub.0 is true whenever K and C are both 0, and A.sub.0 is 1; or whenever K and A.sub.0 are 0, and C is 1. Thus, the minimal sum of products expression for term D.sub.0 is D.sub.0 =K C A.sub.0 +K C A.sub.0. Similarly, the minimal sum of products expression for the term D.sub.1 can be determined by examining the Karnaugh map of FIG. 3. As shown, D.sub.1 =K C A.sub.1 +K C A.sub.1 A.sub.0 +K A.sub.1 A.sub.0. In these equations, the symbol "+" means a logical "OR". Thus, one would read the equation for D.sub.0 as: "D.sub.0 equals not K and not C and A.sub.0 or not K and C and not A.sub.0."

After the minimal sum of products expressions have been determined for a truth table, a digital circuit to implement the truth table can be designed. FIG. 4 shows a design for the truth table of FIG. 1, which is implemented in a prior-art type programmable logic array ("PLA") structure. A full understanding of this prior art structure will enable the reader to appreciate the differences, and substantial advantages, of the structure of the present invention.

FIG. 4 shows a programmable logic array having a plurality of rows 50, 52, 54, 56 and 58 and a plurality of data columns 24, 26, 28, 30, 32, 34, 36, and 38. These data columns are associated with the AND plane of the array. Output columns 40 and 42, which are associated with the OR plane of the array, are also provided. Pullup resistors 10, 12, 14, 16, and 18, are connected between voltage source V.sub.DD and rows 50, 52, 54, 56, and 58 respectively. Each of the rows in the array carries out an AND function. The array shown in FIG. 4 has been arranged so that the top three rows, 50, 52, and 54, each perform one of the AND conditions of the minimal sum of products expression for D.sub.1 shown in FIG. 3. The last two rows in the array of FIG. 4, rows 56 and 58, each perform one of the AND conditions of the minimal sum of products expression for D.sub.0, shown in FIG. 2.

Column 24 of the array of FIG. 4 represents the K input of the truth table of FIG. 1. The K input is inverted by inverter 20, which causes the complement of the K input, or K to appear on data column 26. Similarly, input C appears on data column 28, and C, through the action of inverter 22, appears on data column 30.

D-type flip flops 44 and 46 correspond to the A.sub.1 and D.sub.1 terms, and the A.sub.0 and D.sub.0 terms, respectively. The present state of flip flop 44 will be present on outputs Q and Q of the flip flop, which, respectively, are equivalent to the A.sub.1 and A.sub.1 terms. Thus, A.sub.1 is represented by data column 32, and A.sub.1 is represented by data column 34. In the same manner, A.sub.0 is represented by data column 36, and A.sub.0 is represented by data column 38.

In order to implement the first AND condition, K C A.sub.1, of the minimal sum of products expression for D.sub.1, logic cells, comprising transistors 60, 62, and 64, are used in conjunction with row 50 of the array. The input electrodes of the transistors are coupled to data columns, and the output electrodes thereof are coupled between row 50 and ground. The input electrode of transistor 60 is coupled to data column 26, which is the K input. The input electrode of transistor 62 is coupled to data column 30, which is the C input. The input electrode of transistor 64 is connected to data column 32, which is the A.sub.1 term. Thus, row 50 of the array represents the AND condition K C A.sub.1.

In a similar manner, row 52 represents the AND condition K C A.sub.1 A.sub.0, row 54 represents the AND condition K A.sub.1 A.sub.0, row 56 represents the AND condition K C A.sub.0, and row 58 represents the AND condition K C A.sub.0. It will be noted that the input electrodes of all of the transistors in the AND plane of the array are oriented in the same direction.

In order to complete the design of the two bit counter, the OR conditions (designated "+") of the minimal sum of products expressions must be provided for. D.sub.1 comprises the OR condition of three AND conditions. The OR functions are provided by logical cells which comprise transistors 92, 94, and 96 connected to rows 50, 52, and 54 respectively. If any one of the three AND conditions of rows 50, 52, or 54 is true, than output column 42, coupled to D.sub.1, will be true.

The OR condition of rows 56 and 58 of the array will be reflected on output column 40, through the action of the logic cells comprising transistors 98 and 100 associated with rows 56 and 58, respectively. Output column 40 is coupled to the D.sub.0 input of flip flop 46.

It is important to note that the input electrodes of each of OR transistors 92, 94, 96, 98, and 100 are coupled to rows. Accordingly, the OR logic cells comprising these transistors are rotated by 90.degree. with respect to the AND logic cells which are present in the AND plane. The necessity of rotating the AND and OR logic cells by 90.degree. with respect to one another presents difficulty in fabricating programmable logic arrays, in the form of integrated circuits, without wasting space on the semiconductor chip. The present invention overcomes this substantial disadvantage.

An implementation of the same two bit counter, but using the structure of the present invention, is shown in FIG. 5. As is evident, the input electrodes of all of the logic cell transistors in this structure are connected to columns, and therefore, the transistors are all oriented such that their control electrodes extend horizontally. There is no 90.degree. rotation of transistors as there was in the prior art type programmable logic array shown in FIG. 4.

The AND rows 250, 252, 254, 256, and 258 in FIG. 5 correspond to AND rows 50, 52, 54, 56, and 58 in FIG. 4. The structure shown in FIG. 5 includes an additional row R.sub.a. The AND rows shown in FIG. 5 are precharged to one logic level, V.sub.DD, by p-type transistors 210, 212, 214, 216, and 218 which are clocked by clock signal .PHI..sub.1. The additional row R.sub.a is precharged to ground by n-type transistor 220, also clocked by clock signal .PHI..sub.1.

The K and K inputs appear on columns 224 and 226 respectively. The C and C inputs appear on columns 228 and 230 respectively. Memory element 244, which is a dynamic shift register, has its A.sub.1 output on data column 232 and its A.sub.1 output on data column 234. Memory element 246, also a dynamic shift register, has its A.sub.0 output on data column 236, and its A.sub.0 output on data column 238. Output D.sub.0 appears on output column 240, which is directly connected to row 258 of the array at contact 298. Similarly, output D.sub.1 appears on output column 242, which is directly connected to row 250 at contact 292.

In operation, each of the rows of the two bit counter array shown in FIG. 5 is precharged to voltage V.sub.DD when .PHI..sub.1 goes low at time t.sub.1, as shown in FIG. 6. At the same time, .PHI..sub.1 causes data to be shifted through memory element 244 by transistors 215, 217; through memory element 246 by transistors 219, 221; to data columns 228, 230 by transistors 223, 225; and to data columns 224, 226 by transistors 227, 229. During time t.sub.1, both clock signals .PHI..sub.1 and .PHI..sub.2 are low.

During time period t.sub.2, clock signal .PHI..sub.1 goes high, which causes transistor 220 to precharge additional row R.sub.a to ground. This will cause the OR condition of AND rows 250, 252, and 254 to be inherently transfered to row 250. Also during time t.sub.2, the OR condition of AND rows 256 and 258 will be transfered to row 258. At time t.sub.3, clock signal .PHI..sub.2 goes high, so that data can be read from the OR columns 242 and 240 into memory elements 244 and 246 via transistors 211, 213 and 207, 209, respectively. Thus, during time period t.sub.3, the OR conditions of the AND rows will be transfered into the memory elements. Time period t.sub.4, during which .PHI..sub.1 is high and .PHI..sub.2 is low, enables the transfer of data into the memory elements to cease prior to commencing the next precharge cycle of the AND rows.

The structure of the present invention operates, in effect, by selectively rippling the logic level of additional row R.sub.a through the logic cells associated with AND rows. A true signal on a data column will prevent any logic cell connected to that data column from becoming conductive. Thus, if any of the AND conditions are satisfied, the logic level from additional row R.sub.a will be prevented from rippling across the applicable AND row to the next successive AND row, and the AND row most remotely coupled to additional row R.sub.a will remain precharged, so that the output column connected thereto will remain high.

In order to more clearly explain the operation of the present invention, a simple logical circuit, in accordance with the invention, is shown in FIG. 7. FIG. 8 shows the logic diagram for the circuit of FIG. 7. In particular, the circuit provides the logical OR (through OR gate 332) of two NAND gates 328 and 330. In algebraic terms, the output of the circuit is exressed as AB+BC.

The array of FIG. 7 contains AND row 322, designated R.sub.0, and AND row 324, designated R.sub.n. An additional row 326, designated R.sub.a, is also provided. Data columns 316, 318, and 320 carry input signals A, B, and C respectively.

AND rows R.sub.0 and R.sub.n are precharged through transistors 300 and 302 respectively, to one logic level, V.sub.DD. Precharging occurs when a clock signal .PHI..sub.1 goes low. When clock signal .PHI..sub.1 goes high, additional row R.sub.a is precharged to another logic level, which in the example shown, is ground. If the logic level of either signals A and B or signals B and C is low, there will be no path through which the ground logic level from additional row R.sub.a can ripple through to AND row R.sub.0 Thus, row R.sub.0 will remain at voltage level V.sub.DD, and the OR output column 328, which is connected to row R.sub.0 at 314, will be high.

If, on the other hand, the logical expression AB+BC is not met, a path will exist, through some combination of the logic cells formed by transistors 306, 308, 310, and 312, which will ripple the ground potential of additional row R.sub.a through the circuit to row R.sub.0. For example, if signal B is high, transistors 308 and 310 will be turned on, thereby connecting additional row R.sub.a to AND row R.sub.0. If signals A and C are both high, additional row R.sub.a will be connected to AND row R.sub.0 through transistors 306 and 312, which will both be turned on.

It will now be appreciated that the present invention provides a dynamic, compact logical circuit array, where all of the logic cell transistors are oriented in the same direction. This is accomplished by providing a plurality of AND rows along with an additional row. The AND rows are precharged to one logic level, and the additional row is precharged to another logic level. If a predefined logical condition is not met, the logic cells, which read data off of data columns, will provide a path which connects the additional row to the first AND row, thereby rippling the logic level of the additional row through to the first AND row. The OR condition of the AND rows is formed on an output column connected to the first AND row.

In a complex logical circuit array built in accordance with the present invention, additional groups of AND rows with associated logic cells can be provided, with means for precharging the additional AND rows to one logic level. One or more additional rows, which are precharged to another logic level, will be provided so that the OR condition of each group of AND rows can be formed by rippling the logic level of the additional row or rows to an output column connected to the first AND row in each group.

Complex cells, other than those needed to perform the AND/OR products of a function, can be provided and may be inserted into the array at arbitrary locations. These include flip flops, inverters, loads, row and column connections, pass transistors, etc. The AND/OR cells are of unit size, one row high and one column wide, but the complex cells are composed of multiples of the rows and columns. The columns and rows of the array can be divided into any number of segments desired, allowing great design flexibility.

The implementation of the present invention shown in FIGS. 5 and 7 comprises dynamic CMOS. Those skilled in the art will appreciate that other technologies, such as NMOS, can also be used to implement an array in accordance with the present invention.

Although a preferred embodiment of the present invention has been disclosed for purposes herein, it is to be understood that many variations and modifications could be made thereto. It is intended to cover all of these variations and modifications which fall within the scope of the present invention, as set forth herein and defined by the appended claims.