Abstract:
Spectral methods for analysis and design of digital logic circuits have been proposed and developed for several years. The widespread use of these techniques has suffered...Show MoreMetadata
Abstract:
Spectral methods for analysis and design of digital logic circuits have been proposed and developed for several years. The widespread use of these techniques has suffered due to the associated computational complexity. This paper presents a new approach for the computation of spectral coefficients with polynomial complexity. Usually, the computation of the spectral coefficients involves the evaluation of inner products of vectors of exponential length. In the new approach, it is not necessary to compute inner products, rather, each spectral coefficient is expressed in terms of a measure of correlation between two Boolean functions. This formulation coupled with compact BDD representations of the functions reduces the overall complexity. Further, some computer aided design applications are presented that can make use of the new spectrum evaluation approach. In particular, the basis for a synthesis method that allows spectral coefficients to be computed in an iterative manner is outlined. The proposed synthesis approach has the advantage that it can accommodate a wide variety of constituent gates, including XOR gates, and complex subfunctions for realizing the circuits.<>
Published in: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems ( Volume: 14, Issue: 11, November 1995)
DOI: 10.1109/43.469660
Citations are not available for this document.
Cites in Papers - |
Cites in Papers - IEEE (19)
Select All
1.
Helena Astola, Stanislav Stankovic, Jaakko T. Astola, "Error-Correcting Decision Diagrams for Multiple-Valued Functions", 2011 41st IEEE International Symposium on Multiple-Valued Logic, pp.38-43, 2011.
2.
Ashutosh Kumar Singh, Anand Mohan, "A Theoretical Framework for Probability Coefficients: A New Methodology for Fault Detection", 2008 International Conference on Computer and Electrical Engineering, pp.261-265, 2008.
3.
Y. Iguchi, T. Sasao, "Hardware to compute Walsh coefficients", 35th International Symposium on Multiple-Valued Logic (ISMVL'05), pp.75-81, 2005.
4.
J.E. Rice, J.C. Muzio, "A characterization of antisymmetry in Boolean and multi-valued functions", 35th International Symposium on Multiple-Valued Logic (ISMVL'05), pp.270-275, 2005.
5.
Lei Zhang, Zhenhui Lin, Zongwei Lv, "Technology mapping and Hadamard transform", IEEE 2002 International Conference on Communications, Circuits and Systems and West Sino Expositions, vol.2, pp.1381-1385 vol.2, 2002.
6.
B.J. Falkowski, S. Kannurao, "Mutual relations and properties of symmetric functions in Walsh spectral domain", 2002 IEEE International Symposium on Circuits and Systems. Proceedings (Cat. No.02CH37353), vol.4, pp.IV-IV, 2002.
7.
J.E. Rice, J.C. Muzio, "Antisymmetries in the realization of Boolean functions", 2002 IEEE International Symposium on Circuits and Systems. Proceedings (Cat. No.02CH37353), vol.4, pp.IV-IV, 2002.
8.
S. Kannurao, B.J. Falkowski, "Identification of complement single variable symmetry in Boolean functions through Walsh transform", 2002 IEEE International Symposium on Circuits and Systems. Proceedings (Cat. No.02CH37353), vol.5, pp.V-V, 2002.
9.
W.J. Townsend, M.A. Thornton, "Walsh spectrum computations using Cayley graphs", Proceedings of the 44th IEEE 2001 Midwest Symposium on Circuits and Systems. MWSCAS 2001 (Cat. No.01CH37257), vol.1, pp.110-113 vol.1, 2001.
10.
D. Jankovic, R.S. Stankovic, R. Drechsler, "Decision diagram method for calculation of pruned Walsh transform", IEEE Transactions on Computers, vol.50, no.2, pp.147-157, 2001.
11.
B.J. Falkowski, S. KannuRao, "Skew symmetry detection using the Walsh spectral coefficients", 2000 IEEE International Symposium on Circuits and Systems (ISCAS), vol.2, pp.321-324 vol.2, 2000.
12.
R. Drechsler, M. Thornton, "Computation of spectral information from logic netlists", Proceedings 30th IEEE International Symposium on Multiple-Valued Logic (ISMVL 2000), pp.53-58, 2000.
13.
B.J. Falkowski, S. Kannurao, "Spectral theory of disjunctive decomposition for balanced Boolean functions", VLSI Design 2000. Wireless and Digital Imaging in the Millennium. Proceedings of 13th International Conference on VLSI Design, pp.506-511, 2000.
14.
Yingtao Jiang, Yihui Tang, Yuke Wang, Y. Savaria, "Evaluating the output probability of Boolean functions without floating point operations", Engineering Solutions for the Next Millennium. 1999 IEEE Canadian Conference on Electrical and Computer Engineering (Cat. No.99TH8411), vol.1, pp.433-437 vol.1, 1999.
15.
D.M. Miller, "An improved method for computing a generalized spectral coefficient", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.17, no.3, pp.233-238, 1998.
16.
B.J. Falkowski, Chip-Hong Chang, "Forward and inverse transformations between Haar spectra and ordered binary decision diagrams of Boolean functions", IEEE Transactions on Computers, vol.46, no.11, pp.1272-1279, 1997.
17.
M.A. Thornton, "Modified Haar transform calculation using digital circuit output probabilities", Proceedings of ICICS, 1997 International Conference on Information, Communications and Signal Processing. Theme: Trends in Information Systems Engineering and Wireless Multimedia Communications (Cat. , vol.1, pp.52-58 vol.1, 1997.
18.
M.A. Thornton, R.P. Moore, J.C. Cordova, "Applications of circuit probability computation using decision diagrams", 1997 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, PACRIM. 10 Years Networking the Pacific Rim, 1987-1997, vol.2, pp.683-687 vol.2, 1997.
19.
D.M. Wessels, "Efficient approximation of spectral and autocorrelation coefficients", Proceedings of Digital Processing Applications (TENCON '96), vol.1, pp.247-251 vol.1, 1996.
Cites in Papers - Other Publishers (14)
1.
Anastasios Kyrillidis, Anshumali Shrivastava, Moshe Y. Vardi, Zhiwei Zhang, "Solving Hybrid Boolean Constraints in Continuous Space via Multilinear Fourier Expansions", Artificial Intelligence, pp.103559, 2021.
2.
Ping Xu, Bingqiang Chen, Lingyun Xue, Jingcheng Zhang, Lei Zhu, "A Prediction-Based Spatial-Spectral Adaptive Hyperspectral Compressive Sensing Algorithm", Sensors, vol.18, no.10, pp.3289, 2018.
3.
S.N. Yanushkevich, S. Kasai, G. Tangim, A.H. Tran, T. Mohamed, V.P. Shmerko, "Introduction to Noise-Resilient Computing", Synthesis Lectures on Digital Circuits and Systems, vol.8, no.1, pp.1, 2013.
4.
Helena Astola, Stanislav Stankovic, Jaakko T. Astola, Computer Aided Systems Theory ? EUROCAST 2011, vol.6928, pp.319, 2012.
5.
J. E. Rice, J. C. Muzio, N. Anderson, "New Considerations for Spectral Classification of Boolean Switching Functions", VLSI Design, vol.2011, pp.1, 2011.
6.
B.J. Falkowski, T. Sasao, "Unified algorithm to generate Walsh functions in four different orderings and its programmable hardware implementations", IEE Proceedings - Vision, Image and Signal Processing, vol.152, no.6, pp.819-826, 2005.
7.
Denis V. Popel, Artificial Intelligence in Logic Design, pp.259, 2004.
8.
Yingtao Jiang, Yuke Wang, Xiaoyu Song, Y. Savaria, "Computation of signal output probability for Boolean functions represented by OBDD", Computers & Mathematics with Applications, vol.47, no.12, pp.1865, 2004.
9.
B.J. Falkowski, "Compact representations of logic functions for lossless compression of grey-scale images", IEE Proceedings - Computers and Digital Techniques, vol.151, no.3, pp.221-230, 2004.
10.
Bogdan J. Falkowski, Sudha Kannurao, "Generation of sign Walsh spectra from disjoint cubes of Boolean functions", Computers & Electrical Engineering, vol.28, no.6, pp.631, 2002.
11.
B.J. Falkowski, S. Kannurao, "Analysis of disjoint decomposition of balanced Boolean functions through the Walsh spectrum", IEE Proceedings - Computers and Digital Techniques, vol.148, no.2, pp.71-78, 2001.
12.
B.J. Falkowski, S. Kannurao, "Algorithm for identifying skew symmetries through Walsh transform", Electronics Letters, vol.36, no.5, pp.401-402, 2000.
13.
M. A. Thornton, V. S. S. Nair, "Behavioral synthesis of combinational logic using spectral-based heuristics", ACM Transactions on Design Automation of Electronic Systems (TODAES), vol.4, no.2, pp.219, 1999.
14.
B.J. Falkowski, "Family of generalised multi-polarity complex Hadamard transforms", IEE Proceedings - Vision, Image and Signal Processing, vol.145, no.6, pp.371-378, 1998.
