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

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.

Authors:

• Ashutosh Kumar Singh
• Anand Mohan

Keywords:

• Binary Decision Diagrams
• Spectral Coefficients
• Fault detection

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.