Spectral Transform Decision Diagrams
Spectral Transform Decision Diagrams
复制标题
谱变换决策图
DOI：
10.1007/978-1-4613-1385-4_3
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
C. Moraga
中科院分区：
文献类型：
--
作者：
R. Stankovic;Tsutomu Sasao;C. Moraga
本章提出了谱决策图（STDD），它是开关函数和整数值函数的谱变换的图形表示。二元决策图（Binary Decision Diagram，BDD）和功能决策图（Functional Decision Diagram，FDD）分别是开关函数及其Reed-Muller变换的图形表示。多端判决图（MTBDD）、算术变换判决图（ACDD）和沃尔什变换判决图（WDD）分别是整数值函数、其算术变换和其沃尔什变换的图形表示。本章说明STDD同时表示函数及其谱变换。对于n位加法器，ACDD和WDD需要O（n）个节点，而MTBDD需要O（2n）个节点。对于n位乘法器，ACDD和WDD需要O（n2）个节点，MTBDD需要O（4 n）个节点。
This chapter proposes spectral decision diagrams (STDDs), that are graphical representations of spectral transforms of switching functions and integer-valued functions. Binary decision diagrams (BDDs) and functional decision diagrams (FDDs) are graphical representations for switching functions and their Reed-Muller transforms, respectively. Multi-terminal decision diagrams (MTBDDs), arithmetic transform decision diagrams (ACDDs), and Walsh transform decision diagrams (WDDs) are graphical representations for integer-valued functions, their arithmetic transforms, and their Walsh transforms, respectively. This chapter shows that an STDD represents a function and its spectral transform at the same time. As forn-bit adders, ACDDs and WDDs requireO(n) nodes while MTBDDs requireO(2n) nodes. As forn-bit multipliers, ACDDs and WDDs requireO(n2) nodes while MTBDDs requireO(4n) nodes.