An algebraic technique for generating optimal CMOS circuitry in linear time

The authors explore a method for quickly generating optimal CMOS functional circuits. The method is based upon an algebra they 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 transversal, and is generated in time proportional to the number of input signals. After describing the required concepts from graph theory and CMOS layout practices, the authors introduce an alternative symbolism for describing parallel-series graphs. They develop, with these symbols, a composition algebra, and demonstrate that the properties in the alternative domain hold in the original. The authors then use the algebra to implement a linear-time algorithm for generating CMOS functional cells.