Publication:
Planarity in ROMDD's of multiple-valued symmetric functions

Loading...
Thumbnail Image
Authors
Nowlin, Jeffrey L.
Subjects
Advisors
Butler, Jon T.
Date of Issue
1996-03
Date
March, 1996
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
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.
Type
Thesis
Description
Series/Report No
Department
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
53 p.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
Collections