The present invention relates to arrays for performing logic functions and more particularly it is related to increasing the number of logic functions performed in an array without increasing the size of the array.
The performing of logic in matrices 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. It is also well known that the standardization of logic circuit layouts stemming from the use of logic matrices or arrays results in the simplification and acceleration of the design and manufacture of monolithic chips containing logic performing circuits. However, up until now the use of the logic arrays has been limited. A major cause in this limited use has been that only a small percentage of the intersections in an array turn out to be usable in performing logic functions. This percentage of useful intersections in the arrays results in inefficient use of the surface area of the monolithic chips on which the arrays are fabricated. It turns out that, for most applications, the design and manufacturing efficiencies of logic arrays are outweighed economically by their inefficient use of chip area and it is less expensive to spend additional time and effort to design and manufacture logic chips with highly customized layouts that are less orderly than logic arrays but perform far more logic functions in a given area of a monolithic chip.
The small percentage of usable logic circuits in a logic array is a result of the orderliness of the array. Once input and output lines are used to perform a given logic function they cannot be used in performing other unrelated logic functions without hopelessly unbalancing the logic. As a result, large areas of the array contain intersections of input and output lines that are barren of usable circuits.
A number of schemes have been devised to reduce the sparseness of the logic on logic array chips. One such scheme is to use a plurality of decoders to feed input variables to the input lines of a single array allowing a number of very powerful logic functions to be efficiently performed in a single array. Another scheme used to reduce sparseness involves using compound arrangement of arrays called programmable array logic chips (PLA's). These involve feeding the output of a first array called a product term generator, or an AND array, to a second array called the sum of a product term generator, or an OR array, so as to increase the number of functions that can be performed without geometrically increasing the number of array intersections needed to perform those functions. While these modifications increase the number of useful logic circuits that can be placed in an array logic chip, they do not solve the problem of the unusable portions of the input and output lines that is discussed above.
It has been suggested in pending patent application Ser. No. 637,261 of Howley, Jones and Logue, "Reconfigurable Logic Array", filed Dec. 3, 1975 and assigned to the assignee of this invention and in pending patent application Ser. No. 534,944 of Muehldorf, "Time Split Array Logic Element And Method Of Operation", filed Dec. 20, 1974 and assigned to the assignee of this invention that the arrays be time shared by enabling and disabling the logic performing elements or gates in the arrays during different time periods. In particular, in patent application Ser. No. 534,944, the gates are each either enabled or disabled by data stored in one stage of a shift register. Each time a zero is stored in that stage the gate is not operable while each time a one is stored in that stage the gate is operable. By shifting the data in the shift registers different gates can be enabled during different time periods.