Single stuck-at fault Diagnosing circuit of Reed-Muller canonical exclusive-or sum of product Boolean expressions

Journal of Computer Science, July, 2006 by P.N. Neelakantan, A. Ebenezer Jeyakumar

Abstract: A testable design with a universal test set for single stuck-at zero and stuck-at one faults of Reed-Muller canonical form of Exclusive-OR sum of product logic expressions is proposed. The test circuit detects almost all the single stuck-at faults and needs only simple modifications for variations in the circuit under test. The number of test vectors is also quite small compared with the classical method. The factor of un-identifiability is discussed and a new quantification parameter for the fault diagnosis has also been introduced. Results of Matlab simulations for a few logic functions are included.

Key words: Combinational circuits, exclusive-or sum of products, Reed-Muller canonical form, single stuck-at faults, testability realization, universal test set

INTRODUCTION

Any arbitrary binary logic function can be expressed as exclusive-or sum of product Reed-Muller canonical (ESOP RMC) form which results in minimal product terms as can be seen from Table 1 [1]. The SOP is the conventional sum of product form while the other forms are variations of Reed-Muller canonical (RMC) expressions. The PPRM is the positive-polarity RMC form, which does not allow any complemented variable to occur in the expression. For example, x1 [direct sum] x2x3 [direct sum] x4x5x6 is a PPRM expression, while x1' [direct sum] x2x3 is not. The FPRM allows negation of any variable, but throughout the expression the variable should appear only in the same form, either complemented or uncomplemented. Thus, x1' [direct sum] x2x3 [direct sum] x1'x4 is a FPRM expression since x1 is appearing as only complemented variable, whereas the expression x1 [direct sum] x2x3 [direct sum] x1'x4 is not FPRM as x1 is present in uncomplemented form in the first term and in complemented form in the third term. GRM is the abbreviation for Generalized Reed-Muller form. In this structure, a variable is free to appear as complemented or uncomplemented, but should should not result in same PPRM terms more than once. For instance, x1 [direct sum] x2x3 [direct sum] x2'x3' is not a GRM since the term x2'x3' results in x2x3 when converted into PPRM, which is already present as the second term. The Exclusive-Or Sum of Product (ESOP) form, on the other hand, does not impose any of the restrictions mentioned above and, in fact, is the most general form of RMC expressions. Such an expression is of the form f = [a.sub.0] [direct sum] [a.sub.1][x.sub.1]* [direct sum] [a.sub.2][x.sub.2]* ..... [direct sum] [a.sub.n][x.sub.n]* [direct sum] [a.sub.n 1][x.sub.1]*[x.sub.2]* [direct sum] ..... [direct sum] [a.sub.2n-1][x.sub.1]*[x.sub.2]* ... [x.sub.n]*, where [x.sub.n]* can be [x.sub.n] or its negation and [a.sub.n] is either 0 or 1. The main advantage of such a form, apart from minimal number of product terms, is that it enables a simple method of diagnosis [2-4]. They also provide a more efficient realization than conventional AND-OR functions in many applications such as linear circuits, arithmetic circuits and telecom networks [5]. Further, a more compact PLA implementation based on AND-EXOR form is achievable compared with the AND-OR circuits [6]. The basic disadvantage of slow speed and greater chip area of exclusive-or based implementations has become less prominent, with the abundant availability of FPGA's since the last decade [7]. A Reed-Muller canonical form of CMOS implementation can be easily tested for stuck-open faults with a universal test set [8]. Mixed polarity Reed-Muller expressions have also been useful in classification of Boolean functions [11]. In spite of the slow speed and larger chip area of RMC implementations compared to other others, some of the RMC forms require only a lesser area and also have been effectively used in the FPGA based modules of Xilinx, Actel [9].

Literature survey: A classical method of generating test patterns for very large and complex logic functions is Linear Feedback Shift Register (LFSR) based pseudo-exhaustive or pseudo-random type [1]. However, this does not work well with ESOP form as shown by Drechsler et al. [10]. A PPRM network for detection of stuck-at faults with a universal test of size n 4, n being the number of data inputs, was proposed by Reddy [2]. Though quite good for self-testing, the method is economical only for PPRM form, which obviously has more number of product terms than the other forms in most cases. Multiple stuck-at fault detection for ESOP circuits was carried out by Pradhan [11]. However since the cardinality is 2n 6 [SIGMA]nCe, e= 0 to j, the order of ESOP expression, the test set is not universal and also is too large to be practical for large input functions. Stuck-at and bridging faults with a universal test set for PPRM has also been reported [12]. Multiple fault detecting GRM realizations was propounded by Sasao [4]. It was shown that 2n s 3 test vectors, where s is the number of product terms in the logic function are required for single stuck-at fault detections in GRM circuit while 2n s vectors are required for detection of and/or bridging faults in GRM/ESOP circuits [13]. Here too, the test set is not universal as it depends on s, the number of product terms of the function. Kalay et al. [1] described an ESOP implementation with a universal test set of size n 6 for single faults. A robust and universal sequence has been proposed for stuck-open type of faults in GRM/ESOP cmos transistor implementations [14]. Zhongliang [15] demonstrated that the single stuck-at fault detection can be achieved with only n 5 test vectors. Apart from a small modification in his circuit, two methods, each with minor modifications in his scheme, are proposed in this paper and results of matlab simulations for a few specific functions comparing the detectability of the faults have been included. Further, the concept of indistiguishability index has also been introduced and compared for the illustrative functions.