SYNTHESIS OF LOGIC FUNCTIONS ON AN ARRAY OF INTEGRATED CIRCUITS,
L. M. Spandorfer, Murphy,J. V. · Defense Technical Information Center (DTIC) · 1963
The problem is considered of synthesizing largescale logic on an array of microcircuits with particular attention to topological aspects arising from the interconnection and crossover problems. The results are applicable to semiconductor, thin-film, and hybrid microcircuits. A model is described and assumptions delineated. A theorem is presented which shows that all switching functions can be synthesized by means of a collection of logic elements and interconnecting paths in a manner such that no logic paths intersect or cross over one another. Specific techniques are presented for synthesizing functions in planar, i.e., crossoverless, form. A divergent approach is taken where algorithms are given for synthesizing any logic function on at most two layers of interconnections. The assumptions are: (1) that any logic element can be connected only to its neighbors in the array and (2) that each interconnecting line, or path, can be assigned to either layer 1 or layer 2 by means of a very simple rule. A study is also presented of the algorithms can be modified to handle faulty logic elements, thus establishing a re-routing capability. (Author)