Pseudo-Symmetric Binary Decision Diagrams (PSBDDs)

点击翻译按钮获取中文摘要

This research is on a data structure, Pseudo-Symmetric Binary Decision Diagrams (PSBDDs), for completely specified Boolean functions. It is based on Ordered Binary Decision Diagrams (OBDDs) and symmetric networks. The structure of an OBDD for a totally symmetric function is used as a model for PSBDDs. The Shannon expansion is used to generate the vertices of PSBDDs. There is a join operation which combines two adjacent vertices such that the function is represented as a pseudo-symmetric network instead of a binary tree. The research consists of: a) developing a PSBDD package with four types of symmetry; b) investigating the best heuristic for variable ordering, and ordering sets of symmetric variables; c) comparing mapping results for large functions between PSBDDs and BDDs; d) developing strategies for efficient generation of PSBDDs for incompletely specified functions; e) developing diagrams using Davio I and Davio II expansions; and f) suggesting new architectures for Cellular-Architecture type FPGAs which are design-automation friendly.