Construction of linearly transformed planar BDD by Walsh coefficients

Abstract

In VLSI design, crossings of interconnections occupy space and cause delay. In particular, it is desirable to have planar networks for FPGA synthesis and sub-micron LSIs, since delays in the interconnections and crossings are comparable to the delays for logic circuits. Decision diagrams (DDs). provide a simple technology mapping, and planar DDs result in planar networks. In this paper, we present a deterministic method to construct planar Linearly Transformed Binary Decision Diagrams (BDDs) by Walsh transform spectral coefficients.