Depth Oriented Design for NAND Networks.
Abstract
The design of high speed digital systems requires careful effort to minimize the propagation delay through combinational logic networks. For technological reasons these networks are often most desirably constructed from either NAND or NOR gates with various fan-in limits. It is simpler for the designer to write Boolean expressions which define the desired network behavior in terms of the general class of binary Boolean operators (henceforth referred to as B2) instead of multiple input NAND or NOR operators. The main objective of this paper is to provide a methodology for convenient design of combinational networks. The techniques provided here are not merely existence proofs but are constructive and could, for example, be implemented in the form of computer programs to convert expressions with very large numbers of literals to networks meeting the indicated bounds, leaving only small (eg. 3 to 5 literals) networks to be constructed by hand or through table search. All bounds and constructions in this paper are based upon the size of the input expressions where for any expression E the size of E is represented by abs. val. (E) and is equal to the number of literals in E. The techniques presented treat each literal as distinct (eg. AB+AC has 4 literals). Thus, these techniques are most useful when the size of the expression is large and the number of repetitions of variable names is relatively small. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1978
- Accession Number
- ADA069765
Entities
People
- James Paul Rutledge
Organizations
- University of Illinois Urbana–Champaign