AND/EXOR-based regular function representation

We propose a new data structure, pseudo-symmetric functional decision diagrams (PSFDDs), for completely specified Boolean functions. The new diagrams are based on functional decision diagrams (FDDs) and pseudo-symmetric binary decision diagrams (PSBDDs). As in FDDs, we use Davio expansions to generate the vertices of PSFDDs, but in addition we introduce a new Join-EXOR operation which combines two adjacent vertices such that the function is represented as a regular pseudo-symmetric network (two-dimensional array) instead of a binary tree. The regular structure can be directly mapped to a plane and therefore interconnection length is known from the logic representation. This allows us to accurately predict post-layout delays before the layout is completed. These structures are especially well suited for design technologies where the delay of interconnections limits device performance.