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
References is not available for this document.
Select All
1.
S. B. Akers, "Binary decision diagrams", IEEE Trans. Comput., vol. C-27, pp. 509-516, June 1978.
2.
R. L. Ashenhurst, "The decomposition of switching functions", Proc. Int. Symp. Theory Switching, pp. 74-116, 1957-Apr.
3.
D. Bryan, "The ISCAS85 benchmark circuits and netlist format", OnLine Documentation, 1988.
4.
R. E. Bryant, "Graph-based algorithms for Boolean function manipulation", IEEE Trans. Comput., vol. C-35, pp. 667-691, Aug. 1986.
5.
C. K. Chow, "On the characterization of threshold functions", IEEE Special Pub. S.134, pp. 34-38, 1961.
6.
E. M. Clarke, K. L. McMillian, X. Zhao and M. Fujita, "Spectral transforms for extremely large Boolean function", Proc. IFIP WG 10.5 Workshop Appl. Reed-Muller Expansion in Circuit Design, pp. 86-90, 1993-Sept.
7.
E. M. Clarke, K. L. McMillan, X. Zhao, M. Fujita and J. Yang, "Spectral transformations for large Boolean functions with applications to technology mapping", Proc. ACM/IEEE Design Automat. Conf., pp. 54-60, 1993.
8.
E. M. Clarke, X. Zhao, M. Fujita, Y. Matsunaga, R. McGeer and J. Yan, "Fast Walsh transform computation with binary decision diagram", Proc. IFIP WG 10.5 Workshop Appl. Reed-Muller Expansion in Circuit Design, pp. 82-85, 1993-Sept.
9.
J. W. Cooley and J. W. Tukey, "An algorithm for the machine calculation of complex Fourier series", Math Computat., vol. 19, pp. 297-301, 1965.
10.
T. Damarla, "Generalized transforms for multiple valued circuits and their fault detection", IEEE Trans. Comput., vol. 41, pp. 1101-1109, Sept. 1992.
11.
M. Davio, J.-P. Deschamps and A. Thayse, Discrete and Switching Functions, New York:McGraw-Hill, 1978.
12.
C. R. Edwards, "The application of the Rademacher-Walsh transform to Boolean function classification and threshold logic synthesis", IEEE Trans. Comput., vol. C-24, pp. 48-62, 1975.
13.
C. R. Edwards, "The design of easily tested circuits using mapping and spectral techniques", Radio Electron. Eng., vol. 47, no. 7, pp. 321-342, 1977.
14.
B. J. Falkowski, I. Schafer and M. A. Perkowski, "Calculation of the Rademacher-Walsh spectrum from a reduced representation of Boolean functions", Proc. Europ. Design Automat. Conf., pp. 181-186, 1992-Sept.
15.
M. Fujita, H. Fujisawa and N. Kawato, "Evaluation and improvements of Boolean comparison method based on binary decision diagrams", Proc. ICCAD, pp. 2-5, 1988.
16.
M. Fujita, J. Yang, E. M. Clarke, X. Zhao and P. McGeer, "Fast spectrum computation for logic functions using binary decision diagrams", Proc. Int. Conf. Circuits Syst., 1994.
17.
D. Green, Modern Logic Design, MA, Reading:Addison-Wesley, 1986.
18.
T. C. Hsiao and S. C. Seth, "An analysis of the use of Rademacher-Walsh spectrum in compact testing", IEEE Trans. Comput., vol. C-33, pp. 934-937, Oct. 1984.
19.
S. L Hurst, "The application of chow parameters and Rademacher-Walsh matrices in the synthesis of binary functions", Comput. J., vol. 16, no. 2, 1973.
20.
S. L. Hurst, D. M. Miller and J. C. Muzio, Spectral Techniques in Digital Logic, FL, Orlando:Academic Press, 1985.
21.
J. Jain, J. Bitner, D. S. Fussel and J. A. Abraham, Probabilistic design verification, Apr. 1991.
22.
M. G. Karpovsky, Finite Orthogonal Series in the Design of Digital Devices, New York:Wiley, 1976.
23.
S. K. Kumar and M. A. Breuer, "Probabilistic aspects of Boolean switching functions via a new transform", Journal ACM, vol. 28, no. 3, pp. 502-520, July 1981.
24.
R. Lechner, "Harmonic analysis of switching functions", In Recent Developments in Switching Theory, pp. 121-228, 1971.
25.
C. Y. Lee, "Representation of switching circuits by binary-decision programs", Bell Syst. Tech. J., vol. 38, pp. 985-999, July 1959.
26.
A. M. Lloyd, "A consideration of orthogonal matrices other than the Rademacher-Walsh types for the synthesis of digital networks", J. Electron., vol. 47, no. 3, pp. 205-212, 1979.
27.
M. Mano, Digital Design, NJ, Englewood Cliffs:Prentice-Hall, 1984.
28.
S. Milak, A. R. Wang, R. K. Brayton and A. Sangiovanni-Vincentelli, "Logic verification using binary decision diagrams in a logic synthesis environment", Proc. ICCAD, pp. 6-9, 1988.
29.
D. M. Miller and J. C. Muzio, "Spectral fault signatures for single stuck-at faults in combinational networks", IEEE Trans. Comput., vol. C-33, pp. 765-768, Aug. 1984.
30.
K. P. Parker and E. J. McCluskey, "Probabilistic treatment of general combinational networks", IEEE Trans. Comput., vol. C-24, pp. 668-670, June 1975.
