Pseudo-Symmetric Binary Decision Diagrams (PSBDDs)

研究完全指定布尔函数的一种数据结构--伪对称二叉决策图(PSBDDs)。它基于有序二分决策图(OBDDS)和对称网络。完全对称函数的OBDD的结构被用作PSBDDS的模型。香农展开用于生成PSBDDs的顶点。存在将两个相邻顶点组合在一起的连接操作，使得函数被表示为伪对称网络而不是二叉树。研究包括：a)开发具有四种对称类型的PSBDD程序包；b)研究变量排序的最佳启发式，以及对称变量集的排序；c)比较PSBDD和BDDS之间大函数的映射结果；d)为不完全指定的功能开发有效生成PSBDD的策略；e)使用Davio I和Davio II展开来开发图；以及f)为设计自动化友好的细胞架构型FPGA建议新的体系结构。

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.