Journal of Computer Science and Technology ›› 1986, Vol. 1 ›› Issue (1): 35-45.

Previous Articles     Next Articles

An Efficient Algorithm for Calculating Boolean Difference

Wei Daozheng   

  1. The Institute of Computing Technology, Academia Sinica, Beijing, China
  • Received:1985-07-03 Online:1986-01-10 Published:2022-01-20

In this paper we have proposed a method of computing Boolean difference by means of transition operators. This method considerably simplifies the computational complexity. Particularly, when the method is used in the test generation of digital circuits, the Boolean difference can be calculated iteratively from the outputs of gates to their inputs level by level, no matter whether there are reconvergent fanout lines or not. When there are m different paths from a given fault line to the primary output of the circuit, using traditional Boolean difference methods, the result formula will contain 2m?1 product terms, whereas using the method presented in this paper, the result formula will contain onlym product terms. On the other hand, the m product terms are connected by “OR” operators, therefore it is very convenient to generate partial test patterns. We also introduce a method in which partial test patterns along a given path can be generated. The method discussed in this paper have been used in the test generation of the PCBs of several computers and the results were quite satisfactory.

[1] I. S. Reed, A class of multiple-error-correcting codes and the decoding scheme.IRE Trans. PGIT-4 (1954), 38–49.
[2] S. B. Akers, Jr. On a theory of Boolean functions,J. Soc. Indust. Appl. Math.,7:4 (1959), 487–489.
[3] F. F. Sellers, Jr, M. Y. Hsiao and L. W. Bearnson, Analyzing errors with the Boolean difference,IEEE Trans. Computers, C-17 (1968), 676–683.
[4] S. S. Yau and Y. S. Tang, An efficient algorithm for generating complete test sets for combinational logic circuits,IEEE Trans. Computers,C-20 (1971), 1245–1251.
[5] C. T. Ku and G. M. Masson, The Boolean difference and multiple fault analysis,IEEE Trans. Computers C-24 (1975), 62–71.
[6] M. Y. Hsiao and D. K. Chia, Boolean difference for fault detection in asychronous sequential machines,IEEE Trans. Computers, C-20 (1971), 1356–1361.
[7] A. Thayse and M. Davio, Boolean differential calculus and its application to switching theory,IEEE Trans. Computers, C-22, (1973), 409–420.
[8] M. A. Breuer and A. D. Friedman, Diagnosis and reliable design of digital systems, Computer Science Press, Inc. 1976.
[9] A. L. C. Chiang, I. S. Reed and A. V. Banes, Path sensitization, partial Boolean difference and automated fault diagnosis,IEEE Trans. Computers, C-21 (1972), 189–194.
[10] Zhang Mian and Qu Yan-wen, The multiple-variable Boolean differences and the theorem of sensitizing multiple paths,Chinese Journal of Computers,3: 2(1980), 182–190.
[11] Wei Dao-zheng, Test pattern generation for large combinational logic circuits,Chinese Journal of Computers,1: 2(1978), 93–98.
[12] J. P. Roth, Diagnosis of automata failures: a calculus and a method,IBM J. Research and Develop,10: 4(1966), 278–291.
No related articles found!
Full text



No Suggested Reading articles found!

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
  Copyright ©2015 JCST, All Rights Reserved