Planarity in ROMDD's of multiple-valued symmetric functions

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.