COMBINATIONAL LOGIC DESIGN USING UNIVERSAL LOGIC MODULES

Abstract

With the spectacular advances in the Integrated Circuit (IC) Technology, the circuit designer has now IC packages at his disposal rather than the discrete components. The objective of a combinational or sequential logic circuit with minimum number of logic gates (AND, OR, NOT, NAND, NOR etc.), as practiced in the past,has no relevance today. The current motivation is to design a circuit with simple layout and with minimum IC packages. The problem taken for Ph.D. dissertation, deals with the designing a combinational logic circuit, described by single- or multi-output,completely or incompletely specified logic function(s), using Universal Logic Modules (ULM) which are commercially available as multiplexers. The logic circuit is realized in the form of a ULM tree network, which is a structure obtained as a consequence of the application of Shannon's Expansion Theorem to the given logic function. Two objectives are kept in mind while designing the methods presented in the thesis. The tree structure makes it possible for the final design to have a geometrically regular pattern for the buses feeding data to the control and input terminals of the ULM tree. This pattern is generally called Input Bus Structure (IBS). The objectives to be achieved are either to obtain a (1) Simple IBS or (2) Minimal ULM tree with/without a simple IBS. where minimal means the use of minimum number of ULMs. Further, since the cost of an IC package depends upon the number of its pins, an effort has been made to get a final design with IC packages having smaller number of pins. The existing methods of designing a ULM network for a combinational function, in the light of the two objectives mentioned earlier, are reviewed first. When the design is complete, the input terminals of the ULM tree must be assigned the values (logical) of the input data. This assignment presents a formidable problem when the given function contains large number of variables. The methods, existing in the available literature, to solve this problem, are then reviewed and classified in five categories. At least three of these methods have been extensively modified and reformulated to make their applications simpler and more suitable to the ULM tree structure. Further, systematic procedures are given to reduce a given ULM tree to a smaller tree and to convert a tree using n-ULMs (that is, the ULMs which realize any function of n variables) to a tree using (n-l)-ULMs, (n-2)-ULMs and so on. The application of these methods results in a ULM tree with smaller pin-count. Five different methods are then presented to design a given combinational logic function (single- or multi-output/ completely or incompletely specified) using identical n-ULMs. The use of identical ULMs make the applications of these methods and the final reduction conversion of the ULM tree easier. All the five methods are oriented towards the use of the computer simulation, when the circuit to be designed becomes complex. These methods have been illustrated by several examples of a single-output, completely specified functions, and two examples of multi-output incompletely specified functions i.e. 2l+21-to-BCD Code Converter and Seven Segment Display Generator. The first design method utilizes the Boolean Matrix representation of the given function. A *pair-fun ction' is introduced here which helps in the selection of the data variable leading to a ULM tree with simple IBS. Given a function, an empirical formula is then presented to decide the number and type of the ULMs necessary to realize the function. The second method uses the Rademacher-Walsh transform to get the spectrum (consisting of spectral coefficients), by inspection of which the final design of the ULM tree with simple IBS is obtained. The next three methods are designed to achieve a minimal ULM tree with a comparatively simple LBS. The first of these methods makes partial use of the Quine-McClusky algorithm for function simplification from which the data variables for the ULM tree are chosen using the theorems stated alongwith its description. If the given function is in irreducible canonical sum-of-products form, then the second (iv) of these methods utilizes the concept of cubical complex representation. Two theorems are stated to select the various data variables. The final method takes a probabilistic view of the design problem, when the function contains large number of minterms, each minterm being a function of large number of variables. It is shown that a small set of design-options is obtained, one of which yields a minimal ULM tree. Two theorems are stated to simplify the developed procedure. When the number of minterms approach 2T, n being the number of function-variables, it is then shown how an approximate method described therein, may lead to a minimal or nearly minimal ULM tree. Finally, the five methods are critically compared from the points of view of computational efforts, simplicity of the final design and the situations in which a particular method may yield results quickly.