Title :
Technology decomposition using optimal alphabetic trees
Author :
Pedram, Massoud ; Vaishnav, Hirendu
Author_Institution :
Dept. of Electr. Eng.-Syst., Univ. of Southern California, Los Angeles, CA, USA
Abstract :
A technique for converting an arbitrary sum-of-products expression into a subnetwork of two-input NAND gates such that, given a fixed linear order on the inputs to the expression, the signal arrival time at the output of the subnetwork is minimum, is presented. The procedure, which is based on an algorithm for constructing optimal binary trees for alphabetic codes, is optimal for complex nodes with sum-of-products expressions having noncrossing literal support. This procedure has been said to recursively NAND-decompose a Boolean network based on the input ordering information derived from a companion placement solution resulting in reduced chip area and improved performance after technology mapping, placement and routing
Keywords :
Boolean functions; circuit layout CAD; circuit optimisation; logic CAD; logic gates; minimisation of switching nets; multivalued logic circuits; network routing; trees (mathematics); Boolean network; arbitrary sum-of-products expression; complex nodes; improved performance; multilevel logic synthesis; optimal alphabetic trees; optimal binary trees; placement; recursively NAND-decompose; reduced chip area; routing; subnetwork; technology decomposition; technology mapping; two-input NAND gates; Binary trees; Circuit synthesis; Computational complexity; Costs; Ear; Logic circuits; Network synthesis; Prototypes; Routing; Timing;
Conference_Titel :
Design Automation, 1993, with the European Event in ASIC Design. Proceedings. [4th] European Conference on
Conference_Location :
Paris
Print_ISBN :
0-8186-3410-3
DOI :
10.1109/EDAC.1993.386414
