Design of Minimal Programmable Logic Arrays

321 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1983.The switching function minimization is very important for optimal and reliable PLA design. A number of different minimization procedures have appeared. However, until recently, the application of these minimization procedures has been limited to functions of a few variables. For the automated design of PLA's, we need computationally efficient procedures that can minimize functions of a large number of variables. For this type of function, the commonly used procedures cannot be applied either because they take too much computation time or because they require too much memory space. Part I of this thesis proposes a new minimization procedure requiring less computation time and less memory space. Part I also proposes the heuristic procedures for some functions which abolute minimization procedures cannot minimize within reasonable amount of time and memory space.A decoded-PLA consists of decoders, an AND array, and an OR array. It has been known that decoded-PLA's generally require smaller arrays than normal PLA's. However, no systematic procedure for the design of minimal decoded-PLA's has been known. Only heuristic procedures such as MINI developed by IBM are used for the design of decoded-PLA's, but they cannot guarantee minimality. Part II of this thesis proposes a systematic procedure for the design of minimal decoded-PLA's, where minimality is guaranteed.For functions with too many terms in their minimal sums, a single PLA scheme is not appropriate because the actual chip size is too big and the speed is too slow. A PLA network, i.e., a multiple PLA scheme, may be used to realize such big functions in an effective manner. Part III of this thesis proposes the partitioned-PLA method, which splits a large single PLA into several small sub-PLA's such that each of them can be realized with reasonable chip size and speed. Part III also proposes several other PLA networks and compares these networks in terms of sizes required for implementing various sample functions.U of I OnlyRestricted to the U of I community idenfinitely during batch ingest of legacy ETD