Computation of Probability Coefficients using Binary Decision Diagram and their Application in Test Vector Generation

Authors: Ashutosh Kumar Singh, Anand Mohan

Abstract:

This paper deals with efficient computation of probability coefficients which offers computational simplicity as compared to spectral coefficients. It eliminates the need of inner product evaluations in determination of signature of a combinational circuit realizing given Boolean function. The method for computation of probability coefficients using transform matrix, fast transform method and using BDD is given. Theoretical relations for achievable computational advantage in terms of required additions in computing all 2n probability coefficients of n variable function have been developed. It is shown that for n ≥ 5, only 50% additions are needed to compute all probability coefficients as compared to spectral coefficients. The fault detection techniques based on spectral signature can be used with probability signature also to offer computational advantage.

Keywords: Binary Decision Diagrams, Spectral Coefficients, Fault detection

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1080985

References:

[1] Ashutosh Kumar Singh and Anand Mohan, "A Theoretical Frame work for Probability Coefficients: A New Methodology for Fault Detection", IEEE Proc. International Conference on Computer and Electrical Engineering (iccee 2008), Phuket, Thailand, 19-21 December 2008.
[2] Osnat Keren, "Reduction of the Average Path Length in Binary Decision Diagrams by Spectral Methods," IEEE Trans. on Comput., vol. 57, no.4, pp. 520-531, April 2008.
[3] James Donald, Niraj K. Jha, "Reversible Logic Synthesis with Fredkin and Peres Gates", ACM Journal on Emerging Technologies in Computing Systems, vol. 4, pp. 1-19, March 2008.
[4] Abusaleh M. Jabir, Dhiraj K. Pradhan, Ashutosh K. Singh, Rajaprabhu T. L., "A Technique for Representing Multiple Output Binary Functions with Applications to Verification and Simulation", IEEE Trans. on Comput., vol. 56, No. 8, pp. 1133-1145, August 2007.
[5] D. M. Miller, "Spectral and Two-Place Decomposition Techniques in Reversible Logic", Proceeding of the IEEE Midwest Symposium on Circuits and Systems, vol. 2, pp. 493-496, 2002.
[6] D. M. Miller, R. Drechsler and M. A. Thornton, "Spectral Techniques in VLSI CAD" Kluwer Academic 2001.
[7] Dragan Jankovic, R. S. Stankovic, Rolf Drechsler Decision Diagram Method for Calculation of Pruned Walsh Transform", IEEE Trans. on Comput., vol. 50, Issue 2, pp. 147-157, Feb. 2001.
[8] R. Drechslor, B. Becker and N. Gockel, "Genetic Algorithm for Variable Ordering of OBDDs", IEE Proc. Comput. Digit. Tech., vol. 143, no. 6, pp. 364-368, 1996.
[9] M. A. Thornton and V. S. S. Nair, "Efficient calculation of spectral coefficients and their applications", IEEE Trans. on Comput., vol. 14, no.11, pp. 1328-1340, Nov. 1995.
[10] V. Chickermane, J. Lee, and J. H. Patel, "Addressing design for testability at the architectural level," IEEE Trans. on Comput., vol. 13, no.-7, pp. 920-934, Jul. 1994.
[11] S. H. Hosseini and N. Jamal, "Efficient distributed algorithms for self testing of multiple processor systems", IEEE Trans. on Comput., vol. 41, no.-11, pp. 1397-1409, Jul. 1992.
[12] R. E. Bryant, "Symbolic Boolean Manipulation with Ordered Binary- Decision Diagrams", ACM computing surveys vol. 24, no. 3, pp. 293- 318, 1992.
[13] Suman Purwar, "An Efficient Method of Computing Generalized Reed- Muller Expansions from Binary Decision Diagram", IEEE Trans. on Comput., vol. 40, issue 11, pp. 1298-1301, Nov. 1991.
[14] E. Eris and J. C. Muzio, "Spectral testing of circuit realizations based on linearisations", IEE Proc. Comput. Dig. Tech., vol. 133E, no.2. pp. 73- 78 March 1986.
[15] D. K. Pradhan, "Fault Tolerant Computing", Englewood Cliffs, New Jersey 07632 (U. S. A) 1986.
[16] S. L. Hurst, D. M. Miller and J. C. Mujio, "Spectral Techniques in Digital Logic", Academic Press (London) 1985.
[17] T. W. Williams and K. N. Parker, "Design for testability-A survey," IEEE Trans. on Comput., vol. C-31, no. 1, pp. 1-15, Jan. 1982.
[18] S. L Hurst, D. M. Miller and J. C. Muzio, "A spectral method of Boolean function complexity", Electron. Lett., 18, pp. 572-574, 1982.
[19] S. L. Hurst, "The logical processing of digital signals", Crane Russak, New York, 1978.
[20] S. B. Akers, "Binary Decision Diagrams", IEEE Trans. on Comput., vol. C-27, no. 6, pp. 509-516, 1978.
[21] B. J. Fino, and V. R. Algazi, "Unified matrix treatment of the fast Walsh-Hadamard transform", IEEE Trans. on Comput., vol. C-25, pp. 1142-1145, 1976.
[22] J. Shanks, "Computation of the fast Walsh-Fourier transform", IEEE Trans. on Comput., vol. EC-18, pp. 457-459, 1969.