An algebraic technique for generating optimal CMOS circuitry in linear time

We explore a method for quickly generating optimal CMOS functional circuits. The method is based upon an algebra we have derived that describes the composition of parallel-series graphs and their duals simultaneously, and as such, exactly describes the layout of CMOS functional circuits. The method is constructive; it creates the smallest components first, putting them together until the final circuit is realized. The constructed layout is representative of an unordered tree traversal, and is generated in time proportional to the number of input signals. After describing the required concepts from graph theory and CMOS layout practices, we introduce an alternative symbolism for describing parallel-series graphs. We develop, with these symbols, a composition algebra, and demonstrate that the properties in the alternative domain hold in the original. We then use the algebra to implement a linear-time algorithm for generating CMOS functional cells.

Duke Scholars

Author John H. Reif Computer Science