DocumentCode :
292865
Title :
Fast spectrum computation for logic functions using binary decision diagrams
Author :
Fujita, Masahiro ; Yang, Jerry Chih-Yuan ; Clarke, Edmund M. ; Zhao, Xudong ; McGeer, Patrick
Author_Institution :
Fujitsu Lab. of America, USA
Volume :
1
fYear :
1994
fDate :
30 May-2 Jun 1994
Firstpage :
275
Abstract :
We show very efficient methods to compute Walsh spectrum for logic functions with large numbers of inputs (30 or more) using Binary Decision Diagrams. The BUD structure is extended to have any integer values as leaf (constant) nodes. The result is an efficient representation for integer vectors and integer matrices. The proposed procedure works directly on an extended BDD for the logic function, and computes the full Walsh spectrum in the form of an extended BDD. The algorithm presented is a more efficient version of the matrix-multiplication method. Our method embeds the Walsh transform matrix implicitly into program code with recursive calls, which results in a significant speed improvement. Our algorithm has the same complexity as the fastest known Walsh algorithm, and utilizes a much more efficient data structure than traditional truth tables. Furthermore, in cases where the complete set of spectra coefficient is either infeasible or impractical, we also present a method to compute subsets of Walsh coefficients. We present experimental results showing that logic functions having more than 60 inputs which cannot be processed by other published methods can be computed within 30 seconds on Sparc 2
Keywords :
Boolean functions; Walsh functions; logic design; BDD structure; Boolean functions; Sparc 2; Walsh spectrum; binary decision diagrams; data structure; fast spectrum computation; integer values; logic functions; logic synthesis; recursive calls; Binary decision diagrams; Boolean functions; Computer science; Data structures; Information analysis; Input variables; Laboratories; Logic functions;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Circuits and Systems, 1994. ISCAS '94., 1994 IEEE International Symposium on
Conference_Location :
London
Print_ISBN :
0-7803-1915-X
Type :
conf
DOI :
10.1109/ISCAS.1994.408808
Filename :
408808
Link To Document :
بازگشت