EFFICIENT REALIZATION OF BOOLEAN FUNCTIONS BY PRUNING NAND(NOR) TREES

Abstract

A combinatorial tree structure composed entirely of NAND(NOR) blocks is pruned in a non-exhaustive fashion to yield minimal or near-minimal networks. It is assumed that complemented variables are not available and that there are no fan-in or fan-out limitations. The cost of a network is taken as being primarily determined by the number of logic blocks with the number of inputs and logic levels as secondary factors. The pruning algorithm lends itself to both hand methods and machine computation, although the synthesis procedure has not been programmed. Of the 68 nondegenerate functional equivalence classes of 3 variables, the minimum number of blocks results in 63 cases; only one more block in excess of the minimum is required in each of the other 5 cases.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 02, 1969
Accession Number
AD0693565

Entities

People

  • Brian E. White

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Human Systems
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Boolean Algebra
  • Classification
  • Computations
  • Computers
  • Construction
  • Digital Computers
  • Electrical Engineering
  • Engineering
  • Logic
  • Massachusetts
  • Network Science
  • Notation
  • Redundancy
  • Security

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Operations Research