Minimization methods for cellular logic arrays
Harold Gregory Schmitz · Montana State University ScholarWorks (Montana State University) · 1969
This thesis is concerned with the development of minimization techniques for the efficient synthesis of cellular logic networks.The main results can he summarized as follows: First, an algorithm is presented which obtains a realization for an arbitrary switching function using a minimal size two-dimensional cellular logic array in which each cell is capable of producing all two-input one-output unate functions and in which the interconnection structure is constrained to be "nearest neighbor."Also, the number of equivalence classes of unate cascade realizable functions is determined, and a necessary condition and improved test for determining unate cascade realizability is given.Second, a solution to a classical minimization problem involving the Reed-Muller canonic forms is provided and minimization techniques for two-dimensional cellular arrays based on the Reed Muller forms are developed.Third, an essential step in the cellular array minimization algorithms is formulated as a graph theoretic problem whose solution requires finding the cliques of a linear nondirected graph.For this, a new algorithm for detecting the cliques of a linear nondirected graph is developed.