SYNTHESIS OF LOGIC FUNCTIONS ON AN ARRAY OF INTEGRATED CIRCUITS,
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 31, 1963
- Accession Number
- AD0431017
Entities
People
- J. V. Murphy
- L. M. Spandorfer