Accession Number : ADA309273

Title :   Planarity in ROMDD's of Multiple-Valued Symmetric Functions.

Descriptive Note : Master's thesis,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s) : Nowlin, Jeffrey L.

PDF Url : ADA309273

Report Date : MAR 1996

Pagination or Media Count : 67

Abstract : An important consideration in the design of digital circuits is delay. A major source of delay in VLSI is interconnect. Crossings among interconnect require via's which cause resistance and additional delay. This thesis focuses on circuit design based on the reduced ordered multiple-valued decision diagram (ROMDD), a graph representation of a logic function. Crossings among edges in the ROMDD result in crossings in the circuit. Thus, ROMDD's without crossings reduce delay. Since symmetric functions are important in the design of logic circuits, they are considered here. It is shown that a multiple-valued symmetric function has a planar ROMDD if and only if it is a pseudo-voting n+r function. Additionally, multiple-valued Fibonacci functions are examined and conditions for planarity in their ROMDD representations are established.

Descriptors :   *VERY LARGE SCALE INTEGRATION, *LOGIC CIRCUITS, *CIRCUIT ANALYSIS, MATHEMATICAL MODELS, DIGITAL SYSTEMS, OPTIMIZATION, COMPUTER AIDED DESIGN, THRESHOLD EFFECTS, THESES, CHIPS(ELECTRONICS), NODES, DECISION THEORY, CIRCUIT INTERCONNECTIONS, SYSTEMS ANALYSIS, DELAY CIRCUITS, SWITCHING CIRCUITS.

Subject Categories : Electrical and Electronic Equipment
      Electricity and Magnetism

Distribution Statement : APPROVED FOR PUBLIC RELEASE