IIHI'IIH I If!“ 3 129 MSU LIBRARIES .-_. {I I u IIIIIIII ” 094 3219 RETURNING MATERIALS: Place in book drop to remove this checkout from your record. FINES will be charged if book is returned after the date stamped below. AUG 1 0 2001 9116 03: THE DESIGN OF C-TESTABLE ARITHMETIC UNITS By Sin-Min Chang A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE Department of Electrical Engineering and Systems Science ABSTRACT THE DESIGN OF C-TESTABLE ARITHNIETIC UNITS By Sin-Min Chang Due to the regular and iterative structure of iterative logic arrays ([LAs), this thesis presents the C-testable designs that can be tested with a test set of constant length regardless of the circuit size. The concept of C-testability developed for ILAs is applied to the design of C-testable array multipliers and dividers. The results show that the proposed design of n-by-n C-testable multipliers can be fully tested with 16 test patterns, while the n-by-n restoring and nonrestoring array dividers can be tested with 40 and 20 test patterns respectively. Algorithms that generate the test patterns and expected outputs are also provided. Table of Contents LIST OF TABLES LIST OF FIGURES I. INTRODUCTION II. BACKGROUND 2.1. The Testing of Iterative Logic Array. 2.1.1. L-testable ILAs. 2.1.2. C-testable ILAs. 2.1.3. 2-D ILAs. 2.2. Previous Works. 2.2.1. Graph Labeling. 2.2.2. Design of C-testable CPM. 2.3. Problem Description. III. DESIGN AND TEST OF C-TESTABLE ARRAY MULTIPLIERS ..................... 3.1. Carry-Propagate Array Multiplier (CPM). 3.1.1. Graph Labeling. 3.1.2. Test Pattern Generation. 3.1.3. Design Evaluation. 3.2. Carry-Save Array Multiplier (CSM). iii 10 17 18 19 21 26 28 28 39 43 47 48 3.2.1. Graph Labeling. 3.2.2. Test Pattern Generation. 3.2.3. Design of an Alternative C-testable CSM. 3.3. Baugh-Wooley Array Multiplier (BWM). OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO ..... 3.3.1. Design of C-testable MBWM. 3.3.2. Test Pattern Generation. IV. Design of C-testable Array Dividers. 4.1. Non-Restoring Array Divider. 4.1.1. Graph Labeling. 4.1.2. Test Pattern Generation. 4.2. Restoring Array Divider. 4.2.1. Graph Labeling. 4.2.2. Design for C-testability 4.2.3. Test Pattern Generation V. Conclusions. LIST OF REFERENCES 64 64 69 77 77 77 85 9O 94 100 100 - 104 LIST OF TABLES 1. 1-D ILA with primary outputs Z,- and x’. 2. 1-D ILA with a primary output W. 3. (a) A Cell with Function of Table 2. (b) The Fault Pair Diagram of (a). 4. The testing of a ILA with input patterns (101) and (001). 5. A Fault Pair Diagram of Table l. 6. A 1-D ILA with primary outputs S,- and W. 7. A Schematic Circuit Diagram of 4—by-4 Carry-Propagate Array Multiplier [9]. 8(a). Labeling L for Carry-Propagate Array Multiplier [9]. 8(b). Labeling L’ for Carry-Propagate Array Multiplier [9]. 9. Four Basic Cells of a CPM. 10. Labeling for (a) a 4-by-4 CPM; (b) a 5-by-5 CPM; (c) A Schematic Diagram of a 4-by-4 modified CPM. 11. A 4-by-4 CSM : (a) Schematic Circuit Diagram; (b) Four Basic Cells; (c) Labeling; and (d) Modified CSM. 12. Schematic Circuit Diagram : (a) A 5-by-5 CSM_B [6]; and (b) A S-by-S Modified CSM_B. 15 16 22 23 24 3O 35 49 6O 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 26. . Eight Basic Cells of a MRSD. A Schematic Circuit Diagram of a 5-by-5 Baugh-Wooley Array Multiplier [6]. A Schematic Circuit Diagram of a S-by-S MCSM_C. - A Schematic Circuit Diagram of a S-by-S MBWM. The Bottom Row of MBWM in Figure 15. A Schematic Circuit Diagram of a 4-by-4 NRD [9]. The Basic building block of a NRD. Four Basic Cells of a NRD. The application of labels to a NRD. (a) D=1 (b) D=0 A Schematic Circuit Diagram of C-testable MNRD. A Schematic Circuit Diagram of Restoring Array Divider. A Basic Cell of a RSD. The Modified CS Cell of a MRSD. A Schematic Circuit Diagram of a 4-by-4 MRSD. iv 68 74 78 79 81 83 87 91 92 93 96 101 LIST OF FIGURES 1. 1-1) ILA with primary outputs 2“,. and x’. 2. 1-D ILA with a primary output W. 3. (a) A Cell with Function of Table 2. (b) The Fault Pair Diagram of (a). 4. The testing of a ILA with input patterns (101) and (001). 5. A Fault Pair Diagram of Table 1. 6. A 1-D ILA with primary outputs s;- and W. 7. A Schematic Circuit Diagram of 4-by-4 Carry-Propagate Array Multiplier [9]. 8(a). Labeling L for Carry-Propagate Array Multiplier [9]. 8(b). Labeling L’ for Carry-Propagate Array Multiplier [9]. -- -- 9. Four Basic Cells of a CPM. 10. Labeling for (a) a 4-by-4 CPM; (b) a 5-by-5 CPM; (c) A Schematic Diagram of a 4-by-4 modified CPM. 11. A 4-by-4 CSM : (a) Schematic Circuit Diagram; (b) Four Basic Cells; (c) Labeling; and (d) Modified CSM. 12. Schematic Circuit Diagram : (a) A 5-by-5 CSM_B [6]; and (b) A S-by-S Modified CSM_B. 13 15 16 22 23 24 30 35 49 60 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 26. . Eight Basic Cells of a MRSD. A Schematic Circuit Diagram of a OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO S-by-S Baugh-Wooley Array Multiplier [6]. A Schematic Circuit Diagram of a 5-by-5 MCSM_C. A Schematic Circuit Diagram of a 5-by-5 MBWM. The Bottom Row of MBWM in Figure 15. A Schematic Circuit Diagram of a 4-by-4 NRD [9]. The Basic building block of a NRD. Four Basic Cells of a NRD. The application of labels to a NRD. (a) D=1 (b) D=0 A Schematic Circuit Diagram of C-testable MNRD. A Schematic Circuit Diagram of Restoring Array Divider. A Basic Cell of a RSD. The Modified CS Cell of a MRSD. A Schematic Circuit Diagram of a 4~by-4 MRSD. 66 68 74 78 79 81 83 87 91 92 93 96 101 I. Introduction Rapid advances in semiconductor fabrication technology have made possible the implementation of digital circuits with a very large number of devices on a single chip. The complexity is coupled with an increase in the ratio of logic to pins which drastically reduces the controllability and observability of the logic on the chip [1]. As a result, testing of such high-complexity circuits is very difficult. One of the important issues associated with circuit testing is fault detection. In general, fault detection is carried out by applying a sequence of test inputs and observing the resulting outputs. The major cost of testing includes the generation of test sequences and their application. To reduce the cost of testing, it is necessary to minimize the length of the test sequence [2]. An Iterative logic array (ILA) consists of several identical cells with identical interconnections between cells. Due to its regular and iterative structure, designs of C—testable ILAs that can be examined with a test set of constant length irrespective of the circuit size, have been presented [3-5]. Recently, array multipliers of reason- able size have been implemented on a single VLSI (Very Large Scale Integrated) cir- cuit chip [6,7]. The concept of C-testability has been applied to the design of C- testable array multipliers [8]. The aim of this thesis is to present the designs of C-testable arithmetic units, such as array multipliers and array dividers, and their test generation procedures. In the next chapter, the testing of ILAs and previous work related to the C-testable designs are discussed. The inherent drawbacks in the previous work are also pointed out. In Chapter III and IV, the design and test generation of C-testable array multipliers and dividers are proposed. Finally, the conclusions and future research directions are given in Chapter V. IL Background 2.1. The Testing of Iterative Logic Array An iterative logic array (ILA) consists of several identical cells with identical interconnections between cells. This type of circuit configuration offers the advantages of structural regularity, like, ease of circuit and logic design, ease of placement and routing [10]. In a l-D ILA, the cells are organized in a row, such as ripple-carry adders, while in a 2-D ILA the cells are organized in a matrix of rows and columns, such as array multipliers. In each direction of signal flow, more than one signal line is allowed. As the complexity of the VLSI system increases, the reliability issue becomes more important than ever before. The method to make sure that a combinational circuit is functionally correct is to apply all the possible inputs and examine the corresponding output signals. However, it is impossible to do so on a large system. For example, if the number of input lines is 32, then the number of test patterns to detect the per- manent faults is 232 . This requires too much time for testing and too much memory space to store the test patterns. Moreover, the ILAs have the characteristics of unlim- ited expansion making the testing of ILAs highly interesting. The test procedure is to apply test patterns to the accessible input terminals of the array, referred to as primary inputs, and to observe the results at the accessible out- put terminals, refered to as primary outputs. The observed results are verified by com- paring them with the expected results. These accessible terminals are usually the boun- daries of the array. Faults in an ILA may occur either in the intercell connection, or in the array cells. The former is covered by either the input or output fault of the corresponding cell; the latter assumes that the faulty cell can change its truth table permanently in any arbitrary way as long as it remains a combinational circuit. However, it is assumed that there is no bridging fault between cells [8]. In practice, there are two fault-models at the my level [10]: Single Cell Fault Model (SCFM) and Multiple Cell Fault Model (MCFM). The former indicates only one cell out of the whole array can be faulty, and the latter means an arbitrary number of cells can be faulty. Basically, an ILA can be tested exhaustively using the truth table of a whole array. The size of the test set is exponential to the number of cells. In recent years, two categories of ILAs that simplify their testing have been studied: C-testable and L- testable ILAs. The former is an ILA which can be tested with a constant test size irrespective of the number of cells in the ILA, and the latter is an ILA that requires a test size linear to the number of cells. 2.1.1. L—testable ILAs. The test problems of ILAs under SCFM were first studied by Kautz [3]. Con- sider a 1-D ILA, as shown in Figure 1. Each cell receives an input .1: from its left-hand neighbor and an external input 2. It generates an external output 2 and transmits an output it to its right-hand neighbor. The controllable inputs of the array consist of the x-input to the leftmost cell and the z-inputs to all cells. All i-outputs and the f—output of the rightmost cell are observable. We assume that the z-input of cell i, or z,-, is independent to the z-input of cell j, or 2], for i r: j. Kautz [3] characterized the follow- ing necessary and sufficient conditions for L-testibility of a general ILA under SCFM. Condition 1: A complete set of test must be applied to the input terminals of any cells in the array. Condition 2: For each test, any effect of the fault must be propagated to an observ- able output. More specifically, consider the 1-D ILA of Figure 2. Each cell receives three inputs, x,- , z,- and, z,-’, and produces an output, W}. Suppose the cells are connected in such a way that the output of a cell is fed to its right as shown. Since the only primary output of such an ILA is the output of the rightmost cell, a fault may not be detected unless it can be propagated to the primary output. ..u Ea ..N 3:98 have a? <.= 9— ._ use". EN QM NM NM am am Ia q no. «a a N All]. c llllll v n N M _ N on .u «a «x ‘ r. VN RN NN ~N J—i .4 —->r fi __% .3 3&8 FEE . 53 5. a; .N 2:5 In general, the cell behavior can be described by a truth table. For example, Table 1(a), which is the carry output of a full adder, describes the cells in Figure 2. Table 1(a) consists of columns for input 1:,- and rows for_both z,- and zi’. Each entry represents the output of the cell operation. For notational simplicity, we denote WFW(x,-,z,-,z,-’), where xi = WM, i=1, 3, ...... , n, x=W0, and Wn=W. Suppose there is a faulty cell in this array and its function is changed so that W(0,0,0) becomes 1. This is illustrated in Table 1. Suppose the operation W(0,0,0) is examined. Table 1(a). Truth Table for Figure 2. 22 00 01 10 11 0—0000 D—IHh-Ao.‘ Table 1(b). Truth Table for a Faulty Cell in Figure 2. x 22’ 0 1 00 l O 01 0 1 10 0 1 11 l 1 Case 1: Cell #1 is faulty. Consider a test pattern of x=0, (zl, zl’)=(0,0), and (2}, zj')=(0,1), j=2,....,n. For a fault-free ILA, a logical 0 is expected at the primary output W. When the pattern is applied to the faulty Cell #1, its output is changed from 0 to 1. This incorrect output will be propagated from Cell #2 to the rightmost cell. As a result, a logical 1 will appear at the primary output and conflict with the correct output 0. This concludes that, if the above test pattern is applied to the ILA under SCFM, a logic 1 at the pri- mary output detects that one cell is faulty. Case 2: The Cell #i, i at 1, is faulty. Consider a test pattern of x=0, (zi, z;’)=(0,0), and (2], zj’)=(0,1), for lSan and jsti. Similar to Case 1, a logical 0 is expected at the primary output of a fault-free ILA. When the above pattern is applied to the array, a correct output 0 will be pr0pagated from the fault-free Cell #1 to #i—l and an incorrect output produced by the faulty Cell #i will be propagated to the primary output. This concludes that, if the test pattern is applied to the ILA under SCFM, a logical l at the primary output indicates that one cell is faulty. From above arguments, it is obvious that the examination of the operation W(0,0,0) requires n test patterns. Since it is necessary to examine all the possible operations of each cell, the number of test patterns required is thus proportional to n 10 (the length of the ILA). This concludes that the ILA of Figure 2 with cell function described by Table 1(a) is L-testable. 2.1.2. C-testable ILAs. The concept of C-testability was first defined by Friedman [4]. He provided the following necessary and sufficient conditions for the C-testability of a 1-D ILA under SCFM: Condition 1: In each test, all input combinations can be applied to every qth cell in the array by a single test. Condition 2: The input sequence should be able to propagate the effect of the fault to an observable output. According to Condition 1, the input patterns for each cell of an ILA must occur in a periodic manner. According to Condition 2, the function of the basic cell must be able to propagate the fault effect from its input to its output. These conditions can be studied more specifically with the following example. Consider the ILA of Fig- ure 2 with cell function described in Table 2, which is the summation of a full adder. 11 Table 2. Truth Table for Cells in a C-testable ILA. x 22’ 0 l 00 0 1 01 1 O 10 l 0 ll 0 1 Figure 3(b) shows a fault pair diagram generated from a cell of Figure 3(a) with a function in Table 2. The state j/k represents a fault that changes the correct data j into k, where j and k are either 1 or 0. The parentheses indicates the input pair (z,z’). If the current state is 1/0, and if the input pair (z,z’)=(0,1) is applied, from Table 2, the W-output becomes 1 (0) when x-input is 0 (1). This concludes that the next state is 0/ 1. On the other hand, if the current state is 1/0 and if the input pair (z,z’)=(0,0), from Table 2, the W—output becomes 0 (1) when x—input is 0 (1), i.e., the next state is 1/0, or the state is not changed. It is obvious that the fault pair diagram of Figure 3(b) is strongly connected. By [4], the ILA is C-testable. Alternatively, the C-testability can be also examined as follow. If a test pattern of x=1 and (z,-, z{)=(0,1) for all i, as shown in Figure 4(a), is applied to an ILA with cells of Figure 3(a), then the outputs of the odd and even num- bered cells are 0 and 1, respectively. Any single fault will generate an incorrect result 12 (a) (0!) (10) too) (00) (l l) m) (or) (10) (b) Figure 3. (a) A Cell with Fuction of Table 2; (b) The Fault Pair Diagram of (a). 13 .209 can So: ”Susan 39: .23 <\= a be 958. 95. .v Baum 5 3 14 at the primary output. For example, if a stuck-at-O fault occurs at the output of Cell #2, then an incorrect output 0 is produced at the output of Cell #2 and further pro- pagated to the primary output. This incorrect output conflicts with the expected output. In other words, the test pattern can simultaneously test any single stuck-at—O (or stuck- at-l) fault at the output of any even (odd) numbered cells. In fact, if an additional test pattern of 1:20 and (2,, zi’)=(0,1), as shown in Figure 4(b), is also applied, then we can completely test both operations W(0,0,1) and W(1,0,1) in each cell of the ILA. This concludes that only 2 test patterns are required to test the ILA for these two opera- tions, irrespective of the circuit size. If all the input combinations can be applied in this way, the ILA is thus C-testable. As mentioned before, the ILA of Figure 2 with the cell function described by Table 1 is not C-testable. This can be studied by its fault pair diagram in Figure 5. Since both states 0/1 and 1/0 can be changed to the state 0/0 for input (z,z’)=(0,0), or to the state In for input (z,z’)=(l,1), which are not distinguishable faults. As a result, the ILA is not C-testable. The problem arises as to whether or not the L-testable ILA of Figure 2 can be modified to be C-testable. Consider the ILA of Figure 6 which is modified from Figure 2. Each cell produces an additional output S, where the output S,- is described in Table 2. In fact, both functions described in Tables 1 and 2 are respectively the carry and sum outputs of a full adder (FA). Figure 6 is known as a ripple—carry adder 15 (or) (10) (or) (10) Figure 5. A Fault Pair Diagram of Table 1. 16 - o use”. .3 ea w 5&8 DEE es, 5. a _ < 17 (RCA). Since all the faults can be propagated out and observed from the additional primary outputs S}, the ILA of Figure 6 is thus C-testable. Therefore, Ripple carry adder is C-testable [9]. 2.1.3. 2—D ILAs. For 2-D ILA testing, various schemes have been recently proposed [10,11]. Basically, the 2-D ILA is partitioned into several l-D rows and each row is treated as a 1-D ILA. Therefore, the C-testability developed for 1-D ILAs can be applied to 2-D ILAs. Array multipliers and dividers are two special and simple forms of 2-D ILAs. It is known that an array multiplier is simply constructed by matrix of full adders with corresponding AND gates, the design methodology for C-testability of an array multi- plier would be similar to that of a RCA, i.e., applying all the possible input combina- tions to every cell. Unfortunately, some array multipliers may not allow for the appli- cation of the complete set of input patterns to its basic cells. The conventional Carry-Propagate Array Multipliers (CPM), Carry—Save Array Multipliers (CSM), and Baugh-Wooley Array Multipliers (BWM) are, therefore, not C-testable [8]. Similarly, because array dividers do not allow for the application of the com- plete set of test patterns, neither the restoring array divider, nor the non-restoring array divider, is C-testable [9]. 18 2.2. Previous Work. Recently, the concept of C-testability developed for ILAs has been applied to the design of C-testable array multipliers [8]. Shen and Ferguson have shown that the testing of an array multiplier must involve the exhaustive testing of every cell by applying all possible input patterns and observing the outputs. In other words, for each cell consisting of an AND gate and a full adder, all possible 24 input patterns must be applied. The significance of the design methodology of [8] is that they took advan- tage of the iterative structure in an array multiplier; the test sequence generated for exhaustively testing a cell can be applied to exhaustively test entire array. Conse- quently, the test length can be substantially reduced, and all cells can be simultane- ously tested because of the repetitive nature of hardware. However, the only draw- back in [8] is that no systematic test pattern generation procedure was provided. In order to systematically generate the test sequence for C-testable itera- tive array structures, Chatterjee and Abraham [9] have proposed a test generation methodology using graph labeling scheme. A data-flow graph based model is formu- lated in which labels representing binary vectors are assigned to the branches of the data-flow graph. The labels are shown to satisfy a set of constraints imposed by cell function and interconnection topology. As a result, complex test generation problems can be solved by manipulating a set of symbolic labels with ease and efficiency [9]. 19 2.2.1. Graph Labeling Consider two sets of labels illustrated in Table 3 [9], which represent different sequence of 1’s and 0’s. Table 3. Labels defined in [9]. v1 v2 V3 V4 C1 C2 C3 C4 0 o o o o o o o o o 1 1 1 1 o o o r o 1 1 o 1 o o 1 1 o 1 o o 1 1 o o 1 o 1 1 o 1 o 1 o o 1 o 1 1 1 o o o o 1 1 1 1 1 r 1 1 1 1 The combinations of the vectors V1, V2, and V3 contain all 23 possible binary 3-bit values. V4 is the bitwise sum of V1, V2, and V3 over GF(2). Two functions are defined as 8(vaj9 VD=V56VJ$ Vk ; ( 1 ) and flVianV0=VM+Vin+WVt (2) 20 The function g is the bitwise summation over GF(2) of the vectors Vi, V], and Vk, while the function f is the bitwise carry produced in the above summation. The Cm vectors are computed by evaluating f(V,-,VJ-,Vk) and the V", vectors are by 8(VbV j,V,,), where iatjatkwn, and l S ij,k,m S 4. Let A, B, C, X, and Y be vectors that represent any of 8 vectors Vl-V4, and C1-C4. A mapping VM is defined as VM(A,B,C)=XY if X=g(A,B,C) and =f(A,B,C). It is represented simply by ABC->YX. The vectors Vi’s and Cj’s are treated as labels. A data flow graph representation of the circuit is used. Each node of this graph represents a circuit module and interconnection between the modules is represented by directed arcs between the above nodes. The objective is to keep track of the data in each branch by the following way : 1) each branch is assigned an unique label; and 2) the labels on the input and output branches of a node are consistent with the corresponding cell function. 21 2.2.2. Design of a C-testable CPM. Consider the 4-by-4 Carry-Propagate array multiplier (CPM) [9], as shown in Figure 7. Each cell has 3 inputs, x, y, and z, and 2 outputs, sum bit u=x$y$z and carry bit v=xy+xz+yz. The input x is the AND aibj, where ai’s and bj’s are the multiplier and multiplicand bits, respectively. In [9], a label L consisting of two sets of vectors L1=(V1,C1,V4) and L2=(V4,C4,Vl) is applied to a CPM, as shown in Figure 8(a). The mapping, V1C1V4'->V4C4 , describes that a carry vector V4 is propagated from the rightmost cell to the leftmost cell of the first row. In order to reproduce the label L1 in the third row, an appropriate label L2 is chosen for the second row such that the carry assigned in the rightmost cell of the second row can be propagated to the leftmost cell and the labels L1 and L; are periodically reproduced in every other row. This is referred to as two-row periodic propagation (TRPP). Since the labels on the input and output branches of a graph node must be consistent with the corresponding cell function, the carry vector of the leftmost cell in the first row must be identical to the required vector in the y input of the leftmost cell in the second row. On the other hand, the sum output of each cell in the first row is 22 0 o 0 0 ‘39. “the “090 aibj 8 ’|%. . Figure 7. A Schematic Circuit Diagram of 4-by-4 Carry-Propagate Array Multiplier [9]. 23 V1 Figure 8(a). Labeling L for Carry-Propagate Array Multiplier [9]. Table 4(8). Application of L to CPM [9] 0 l l l l l 1 0 24 D 9 53 V1 O I Av cl. 0 e e. o .. Figure 8(b). Labeling L’ for Carry-Propagate Array Multiplier [9]. Table 40)). Application of L’ to CPM [9] fed to the y input of the corresponding cells in the second row. Therefore, the vectors must be chosen so that both carry and sum outputs have the same label. Unfor- tunately, producing such labels is virtually impossible for this application. However, with an additional XOR gate, the labels can be perfectly applied as shown in Figure 8. More specifically, the leftmost cell in the first row pro- duces the carry vector V4 and the sum vector C4. The carry vector is expected to be fed into the y input of the leftmost cell in the second row where an input vector C4 is expected. Although vectors V4 and C4 are not identical, C4 is bitwise complement of V4 except when (V1,V2,V3)=(000) and (111). Therefore, an additional two-input XOR gate can be used to make the applied label consistent, as shown in Figure 8, where an extra control signal TEST is needed. The signal TEST is set to a logical 0 during the normal operation and is set to 1 when the corresponding values of V4 and C4 are different during the test mode. The use of label L, however, is not enough to apply all possible input com- binations. As the application of L to array illustrated in Table 4(a), all input combina- tions are applied except (001) and (110) in Vector 1. Therefore, another label L’ consisting of L1’=(V1,C4,V4) and Lq’=(V4,C1,V1) is applied. This label is applied in the same manner as L except that the labels LI’ and L2’ are periodically reproduced in every other diagonal column, as shown in Figure 8(b) [9]. This is referred to as two-column periodic propagation (TCPP). 26 With the application of such labels, the modified Carry-propagate array multi- plier has been shown to be C-testable [9]. 2.3. Problem Description. In this thesis, the following three problems will be discussed. (1) Designs of C-testable Array Multipliers. (2) Although the C-testable CPM design of [9] can significantly reduce the time and cost of testing, it is not free of penalty. The extra XOR gates may slightly degrade the speed performance. Alleviating the performance degradation is desir- able. In addition, the graph labeling scheme for both CSM and BWM were not discussed in [9]. However, these array multipliers are the most commonly used. Therefore, the design of C-testable CSM and BWM is proposed. Designs of C-testable array dividers. An array divider design has been presented and claimed to be C-testable in [9]. However, due to the difficulty of fault propagation, the design of the non- restoring array divider proposed in [9] is, in fact, not C-testable. The design of C-testable array divider is studied. 27 (3) Design Methodologies. Since the methodology of generating test patterns and expected outputs has not been precisely stated and provided in the existing literature, the algorithms that generate test patterns and expected outputs for arithmetic units are thus investi- gated. III. Design and Test of C-testable Array Multipliers 3.1. Carry-Propagate Array Multipliers (CPM). According to graph labeling scheme, the following properties have been sum- marized [9]. Property 1: Any combination of three vectors V,Cij or CiVJCk, lSichs4, i¢j$k, does not contain the 3-bit combinations 010 and 101. Property 2: Th6 SCI Of VCCLOI'S ViCiVi (C iV‘C J) and IIS dual VJCiVi (C JV‘C i) together contain all possible combinations of 3-bit values. Property 3: The set of vectors Vii/jV,‘ and CiCJC,‘ where 1$ij,ks4 and i¢j¢k, cover all the possible 3-bit combinations. Our. goal is to find a set of labels that can completely apply all possible input combinations to each cell. While the labels in Property 1 cannot apply all input combinations, the labels in Property 2 will result a performance degradation. Therefore, we shall consider the labels that are comprised of either all vectors of {V1,V2,V3,V4}, 01' all VCCIOI'S {C1,C2,C3,C4}. 28 -29- 3.1.1. Graph Labeling. Consider the corresponding mappings, vij, -—> Cme ; and (3) C,C,C,, -—) VmCm , (4) where i¢j¢km, and l Sij,k,ms 4,'which represent the functions of the basic cell in a CPM. Consider also the application of the labels that are propagated in the fashion of combining TRPP and TCPP, i.e., two vectors are periodically propagated in one direction and the other two are in the other direction. More specifically, let Mi’s, i=1,..,4, represent the four basic cells of a CPM, as shown in Figure 9. Each cell is labeled by L;=(L,-1,LQ,L,3). The objective is to generate a set of labels so that they can be propagated to the entire array repetitively. According to their intercon- nection topology and the mappings (3) and (4), we shall solve the following mappings, ererLrs “9 523142 i (5) larlazlas "* Lrsloz ; (6) 161162163 *9 L431’22 ; and (7) L41L42L43 "" [’33le - (3) This results the following theorem. 3O Figure 9. Four Basic Cells of a CPM. 31 Theorem 1. The following set of labels is a solution of the mapping (5)-(8) : L1=(L11L12L13)=(V1:V2:V3); la=(larl22L23)=(C2,C1’C4)i (9) lg=(lorlozlos)=(c4»C3:C2)i L4=(L41’L42»L43)=(V3»V4:V1)- Lemmal. Consider four distinct indices i, j, k, and m, lSij,k,ms4, for labels V and C, and the mapping: xyz --> vu, where x, y, and z belong to either all V’s or all C’s, i.e., (x,y,z)=(V,-,Vj,V,,) or (Ci,CJ-,C,,), then we get the following properties. (a) The indices of the vectors for u and v are the same, i.e., iff u=V,,,, then v=C,,,, and ifi‘ u=C,,,, then v=Vm. (b) If any one of x, y, and z is Ck and u=C,,, or v=Vm, then the others belong to {Ci,CJ-}, and (b’) If any one of x, y, and z is V,‘ and u=Vm or v=C,,,, then the others belong to {Vng}. 32 (c) If one of x, y, and z is Vi, then u¢Vi, and v¢C,-, and (c’) If one of x, y, and z is C;, then u¢C,-, and v¢V,-. (d) If v=C,,, or u=V,,,, then none of x, y, and z is Vm, and (d’) If v=V,,, or u=C,,,, then none of x, y, and z is in Cm. Proof : The above results can be simply obtained from the mappings ViVJ-Vk——>Cmvm aha cock-411mg in (3) and (4). Proof of Theorem 1 : If Ll=(V1,V2,V3), by equations (3) and (5), we get L23=C4 and L42=V4. Further, by equation (8) and Lemma 1(a), L12=V2 results in L33=C2. Simi- larly, since L13=V3, by equation (6) and. Lemma 1(a), we conclude that lqz=C3. On the other hand, since L23=C4 and L13=V3, by equation (6) and Lemma 1(b), Lu and L2 are identical to Cl and C2. Similarly, since L12=V2 and L42=V4, by equation (8) and Lemma 1(b’), L41 and L43 are identical to V1 and V3. Moreover, by equation (7) and Lemma 1(c’), L33=C2 gives [InstCz and forces [Q2=C1 and L21=C2. Again equation (7) and Lemma 1(a), W1 implies L43=V1 and further forces L41=V3. Consequently, from the results, 15241, 162%,, and [43=C2, we conclude that L31=C4 by equation (7) and Lemma 1(b’). 33 Corollary 1.1. Given a label L1 consisting of either all V;, or all C, the rest of labels can be generated in the same fashion as discussed in Theorem 1. Proof : Consider an index set {1,2,3,4}. Given a label L1=(V,-,Vj,Vk). If we perrnute the indices ij,k, and m, i.e., assign i to 1, j to 2, k to 3, and m to 4, then we get the labels L1=(V,-,Vj,V,,), L,=(C-,C,-,C,,,), L,=(C,,,,C,,,Cj), and L4=(V,.,V,,,,V,,). (10) Similarly, If L1=(C i’Cj’Ck) then IQ=(VjstVm): lG=(anVbV:i)9 and L4=(Ci:CnvClt)° (11) Corollary 1.2. There exist 24 possible sets of such labels. Proof : Since label Ll takes three indices out from a set of four, this implies that there exist 12 possible sets. Furthermore, since L1 can take either all V,, or all C,-, this results in a total of 24 sets. In fact, each set of labels in Corollary 1.2 contains the same 8 combina- tions for the 3-bit input, but in a different sequence. 34 Figures 10(a) and 10(b) respectively illustrate the applications of label (9) to a 4-by-4 and a 5-by-5 CPM. The labels are perfectly applied and periodically pro- pagated through the cells of the entire array except those in the carry propagation stage, i.e., the leftmost cells of each row, referred to as left-boundary cells. Although the labels applied to the left-boundary cells are not exactly the same as expected, they have the same elements in the label but in different sequence. More specifically, the label of the leftmost cell in the second row of Figure 10(a) was expected to be (x,y,z)=(V3,V4,V1) and now is changed to (V4,V3,V1), referred to as Vector 6. Similarly, in the leftmost cell of the third row, the label (C2,C2,C4) is changed to (C1,C2,C4), referred to as Vector 5. Table 5 describes the input combina- tions of these four vectors. Each pair contains the all possible 8 input combinations in different sequence. Table 5. Input Combinations of Boundary Cells. Vector 4 Vector 6 Vector 2 Vector 5 (V3’V4’Vl) (V4’V3’Vl) (C2’C1’C4) (CI’CZ’C4) 1 000 000 000 000 2 110 110 110 110 3 010 100 010 100 4 100 010 011 101 5 011 101 100 010 6 101 011 101 011 7 001 001 001 001 8 111 111 111 111 35 C. v‘ cl V‘ V: QQQCW QQQz; QQQ:2 V: c, CI 15': C: QQQQfi QQQQ.3' QQQQH' '"QQQ.- (a) C| V: (b) Figure 10. Labeling for (a) a 4-by-4 CPM; (b) a 5-by-5 CPM; (c) A Schematic Diagram of a 4-by-4 modified CPM. 36 (c) ' QN 0:5 0* Figure 10. (Continued) 37 The problem arises as to whether or not the application of such labels meets the constraints, referred to as external constraints, imposed by cell functions and interconnection topology. As the interconnection topology shown in Figure 7, the x-direction input of each cell is the output of a 2-input AND gate. The inputs, a,- and bi of the AND gate, must meet the following constraints: all cells in the same diagonal column are required to apply the same ai, and all cells in the same row have the same bj. There- fore, both vectors 1 and 3 have the same value of a,-, so do vectors 2 and 4; and both vectors 1 and 2 have the same value of bj, so do vectors 3 and 4. More specifically, (ai,bj)=(1,l) if the output of AND gate is a logical 1; otherwise (ai,bj)=(0,0), (0,1), or (1,0) depending upon the external constraints and the corresponding data of L“. Table 6 describes the application of the labels of equation ( 9) to the array and get the suitable ai’s and bj’s. 38 Table 6. Application of Labels Li’s to the array. Vectorl Vector 2 Vector 3 Vector 4 aibj V1V2 V3 aibj C2C1C4 aibj- C4C3 C2 aibj V3 V4 V1 * 000 * 000 * 000 * 000 01001 11110 01001 11110 * 010 * 010 * 010 * 010 10011 10011 11100 11100 11100 11100 10011 10011 11101 11101 11101 11101 11110 01001 11110 01001 11111 11111 11111 11111 Remark: "*" denotes that aibj can be either 00, 01,or 10. From Table 6 and Table 5, we may find that both a,- and bj can be applied consistently to meet the external constraints for all cells in the array except those left-boundary cells. Since Vector 4 is substituted by Vector 6 and Vector 2 by Vector 5 for those boundary cells, applying the suitable ai and bi of Vector 4 to the corresponding left-boundary cells will produce a Vector (V3,V3,Vl) which is not Vector 6. Similarly, applying the suitable a,- and bi of Vector 2 to the corresponding left- boundary cells will not produce the Vector 5. Therefore, the problem can be solved by adding an XOR gate as shown in Figure 10(c) with a control signal. 39 In order to exhaustively test all the cells of a CPM, all the possible inputs should be examined. Table 7 describes the input combinations derived from Table 6. Table 7. Input Combinations for MCPM. Test__# Vectorl Vector 2 Vector 3 Vector 4 (abxy) (abxy) (abxy) (abxy) 1. 0000 0000 0000 0000 2. 0100 0100 0100 0100 3. 1000 1000 1000 1000 4. 0101 1110 0101 1110 5. 0010 0010 0010 0010 6. 0110 0110 0110 0110 7. 1010 1010 1010 1010 8. 1011 1011 1100 1100 9. 1100 1100 1011 1011 10. 1101 1101 1101' 1101 11. 1110 0101 1110 0101 12. 1111 1111 1111 1111 Table 7 shows that all input combinations are applied to the basic cell except (ai,bj,y,z)=0001, 1001, 0011, and 0111. As discussed in [8] and Lemma 2, the pat- terns (0001) and (1001) can never appear at the inputs to a cell under normal Opera- tion. Lemma 2. [8] The input vectors (1001) and (0001) can never appear at the input to any cell in the CPM. 40 Proof : Suppose that the input pattern (1001) is applied to the cell at the ith diagonal column and the jth row, say, Cell(i,;). ( 1001) represents that ai=1, bj=0 and the z-input is l. The z-input of Cell(ij) is nothing but the carry output u of Cell(i-l,i). Since the external constraint, bj=0, results in a zero at the x-input of Cell(i-1,i), both 2 and y-inputs must be 1 to produce the carry output u=1. Similarly, the z-input of Cell(k,1) must be 1 for all k, where ISkSi. However, the z-input of Cell(1,/) is fed a logical 0 as shown in Figure 7. Therefore, the input pattern (1001) will never appear during normal operation. Similarly, the pattern (0001) will never appear during normal operation. In order to apply all possible input combinations, the cell is modified in such a way that the carry output of the input (0001) is changed from logical 0 to 1 [8]. As a result, the use of the combination (0001) can apply the combinations (0011) and (0111) to the array. Therefore, the following input combinations are added to Table 7. Table 7(a). Input Combinations for MCPM. 13. 0001 0011 0001 0011 14. 0011 0001 0011 0001 15. 0001 0001 0111 0111 16. 0111 0111 0001 0001 41 According to Theorem 1, a set of test vectors can be obtained in Table 7, i.e., assign column a of Vector i to be Lil, column b of Vector i to be Liz, and LB can be generated by column y and z of Vector i. The entries in column y and z are input data. If the tester can apply those labels on the accessible inputs, then the test vectors in Table 7 can be propagated to the entire array repetitively. Therefore, the following theorem results. Theorem 2. The MCPM is C-testable with a test length of 16. Lemma 3. A Basic FA/AND cell of CPM shown in Figure 7 can be tested with 16 pat- terns. Proof : A 4-input circuit can be exhaustively tested by all its input combinations, i.e., 24:16 test patterns. Lemma 4. The four basic cells of CPM shown in Figure 9 can be tested with 16 patterns. Proof : From the generation of Table 7, each basic cell can be exhaustively tested by those 16 patterns. 42 Proof of Theorem 2 : The MCPM is C-testable if, for any size n, a n-by-n MCPM can be tested with 16 patterns. Let Mac be the four basic cells of CPM, as shown in Figure 9, and TS be the 16 test vectors of Table 7. A p-by-q MCPM represents a MCPM having p rows and q columns. Without loss of generality, both p and q are assumed to be even. Therefore, a p—by-q MCPM can be tessellated by Mac’s. Consider a 2-by-(2k) MCPM which is constructed by k MBC’s, say MR1, MR2, ..., MRb From Figure 9, the inputs of MR], j=2...k, are the same as those of MR1. Therefore, all MRJ- can be tested by the same test set TS. Simi- larly, a (2r)-by-2 MCPM can be constructed by r MBC’s, say MCI, MCZ, ..., MC, From Figure 9, the inputs of MC;, i=2...r, are the same as those of MCI. Therefore, all MC; can be tested by the same test set TS. Since, by Lemma 4, each Mac can be tested by the test set TS, a n-by-n MCPM that can be parti- tioned into m2 Mac’s, where n=2m, can then be tested by the same test set T8. 80, MCPM is C-testable with a test length of 16. 43 3.1.2. Test Pattern Generation. Consider a 4-by-4 modified carry propagate array multiplier (MCPM), as shown in Figure 10(c). The c’s and d’s inputs and control signals are connected to logical 0 during multiplication. However, it is assumed that during testing these inputs are available as primary inputs to the array. Two control signals TESTl and TEST2 are connected to the even and odd numbered rows, respectively. According to the input combinations of Table 7, Algorithm 1 describes the process of generating the test patterns and the corresponding expected outputs for a C-testable MCPM. The main idea of Algorithm 1 is that the test sequence designed by Theorem 1 for testing the four basic CPM cells can be applied to the entire array. Therefore, the test vectors that exhaustively test the four basic cells of CPM can be propagated to all the other cells. Algorithm 1 simply apply those test vec- tors in Table 7 into an MCPM repetitively. Algorithm 1: Vector_i=(ia,ib,ic,id), i=1,..,4. ia : a-input, ib : b-input, ic : y-input, id : z-input. The Test patterns to be generated are: a(i), b(i), c(i), d(i),i =0...n, TESTl, TEST2. The expected product p(i), i=0...2n+l. n is odd. *} tribunal-“:2 {* Step 1. (Test Patterns) *} For i=0 to n-l by 2 do Begin a(i):=1a; a(i+1):=2a; b(i):=-lb; b(i+1):=3b; c(i):=1c; c(i+1):=2c; d(i):=ld; d(i+1):=3d; End; {* (consider the leftmost cell of the second row) *} If ((ld XOR 4d)=lc) 'Ihen x_input:=0. Else x_input:=l; If (a(n)*b(1)=x_input) Then TEST1:=0 Else TEST 1:=1; {* (consider the leftmost cell of the third row) *} If ((4c XOR 2d)=3c) Then x_input:=0 Else x__input:=l; If (a(n)*b(2)=x_input) Then TEST2z=0 Else TEST2:=1; {* Step 2: (Expected Results) *} For i=0 to n-l By 2 do Begin p(i):=4c; p(i+l):=2c; End; For i=n+1 To 2n+l By 2 do Begin p(i):=2c; p(i+l):=1c; End; 45 The test patterns and expected outputs for a 4-by-4 MCPM are generated as shown in Table 8. Table 8. Test Patterns and Expected Outputs for a MCPM. TEST Expected Test_# a b c d 12 Output 1 0000 0000 0000 0000 00 00000000 2 0000 1111 0000 0000 00 00000000 3 1111 0000 0000 0000 00 00000000 4 1010 1111 1010 1111 0 0 10101111 5 0000 0000 1111 0000 11 01111111 6 0000 1111 1111 0000 11 01111111 7 1111 0000 1111 0000 11 01111111 8 1111 1010 1111 0101 1 1 01111010 9 1111 0101 0000 1010 1 1 10000101 10 1111 1111 0000 1111 11 10000000 11 0101 1111 0101 0000 0 0 01010000 12 1111 '1111 1111 1111 00 11111111 13 0000 0000 1010 1111 0 0 10101111 14 0000 0000 0101 1111 l 1 11010000 15 0000 1010 0000 1111 01 10000101 16 0000 0101 1111 1111 10 11111010 Remarks 3 3403020100) b=(b3bszbo) c=(03026160) d=(dod1dzds) By applying all the test patterns in Table 8, Table 9 illustrates that all the input combinations can be applied to each cell of the array. This shows that, the test patterns in Table 8 can detect any single fault that occurs at any place of the array. e1 e2 .3 05 07 000 000 000 110 100 100 100 010 000. 0100 110 0101 100 0010 100 0110 100 1010 101 1100 Table 9. Input Combinations for each cell in a 4-by-4 CPM. 33% 0100 0100 1000 1000 110 0101 1110 100 0010 0010 100 0110 0110 100 1010 1010 010 1011 1100 0000 0100 0100 0100 0100 1000 1000 1000 1000 1110 0101 1110 0101 0010 0010 0010 0010 0110 0110 0110 0110 1010 1010 1010 1010 1011 1100 1011 1100 0000 0000 0100 0100 0100 1000 1000 1000 0101 1110 0101 0010 0010 0010 0110 0110 0110 1010 1010 1010 1011 1100 1011 0000 0000 0100 0100 1000 1000 1110 0101 0010 0010 0110 0110 1010 1010 1011 1100 0000 0100 1000 0101 0010 0110 1010 1011 39 101 310 011 .11 001 .12 111 ’13 011 .16 111 .15 011 #16 111 010 1011 011 1101 001 1110 111 1111 011 0001 111 0011 111 0111 011 0001 101 1100 1011 011 1101 1101 001 1110 0101 111 1111 1111 011 0001 0011 111 0011 0001 011 0001 0111 111 0111 0001 1100 1011 1100 1011 1101 1101 1101 1101 0101 1110 0101 1110 1111 1111 1111 1111 0011 0001 -0011 0001 0001 0011 0001 0011 0001 0111 0001 0111 0111 0001 0111 0001 1100 1011 1100 1101 1101 1101 1110 0101 1110 1111 1111 1111 0001 0011 0001 0011 0001 0011 0001 0111 0001 0111 0001 0111 1100 1011 1101 1101 0101 1110 1111 1111 0011 0001 0001 0011 0001 0111 0111 0001 1100 1101 1110 1111 0001 0011 0001 0111 47 3.1.3. Design Evaluation. In the design of MCPM, the cells are modified as follows. Each left- boundary cell only consists of a full adder, i.e., the corresponding AND gate is separated from the cell and this AND gate is connected to an XOR gate with a con- trol signal. The remaining cells are designed in such a way that each cell retains the same operation as in the original design, but produces a logical I carry output when the input combination is (1000). The extra hardware in an n—by-n MCPM are those (n-l)’s XOR gates. Unlike the XOR gates located at the critical path in the design of MCPM in [9], the XOR gates in the proposed MCPM design will not degrade the speed performance. 48 3.2. Carry-Save Array Multipliers (CSM) A 4-by-4 Carry-Save array multiplier (CSM) is illustrated in Figure 11(a) [3]. It has been shown that the CSM is not C-testable [8]. Therefore, in this section, the design of C-testable CSM is studied and the graph labeling scheme is also applied to generate test patterns. 3.2.1. Graph labeling Consider the four basic cells, Mi, 1:1 to 4, as shown in Figure 11(b). According to the interconnection topology in Figure 11(b) and the mappings (3) and (4), we should solve the following mappings (12)-(15) for Lij’s, 1 Sijs 4. L11L12L13 —’ [42141 3 (12) [mimics -’ £42141 : (13) [61162163 "" [4121/21 ; and (14) L41L42L43 —" lalel - (15) Similar to Theorem 1, the following Theorem and Corollary result. (a) o o . o (b) Figure 11. A 4-by-4 CSM : (a) Schematic Circuit Diagram; (b) Four Basic Cells; (c) Labeling; and (d) Modified CSM. 50 V2 ct V3 Cl (C) Co C, do V! c; d‘ v c, ‘3 v . a. 6 .' O “b v 0* . 0A C.’ . a C C (d) . Cg' . - A C' O . . Cf . fl 0 o g, .V c c" . C C I ) O 51 Theorem 3. The following set of labels is a solution of the mappings (12)-(15) : L1=(L11,L12»L13)=(V1:V2»V3) 3 [441411’221’23F(C2»Cbc4) ; (16) lq=(lr31162163)=(C3»C4:C 1) 3 L4=(L41:L42,L43)=(V4»V3»V2) - Proof : Similar to the proof of Theorem 1, with the mappings (12)-( 15), we can obtain the labels at (16). Corollary 3.1. There exist 24 possible sets of such labels. Proof : Similar to Corollary 1.2, label L1 takes three indices out from a set of four, this implies that there exist 12 possible sets. Furthermore, since L1 can take either all V,-, or all Ci, this results in a total of 24 sets. 52 If the labels (16) are employed, they can be perfectly applied to the array without any extra hardware, as shown in Figure 11(c). Similar to the construction of Table 6, the application of such labels to CSM under the external constraints, is illus- trated in Table 10. Table 10. Application of Li’s to CSM. Vectorl Vector 2 Vector 3 Vector 4 V1V2V3 a,- bi C2C1C4 a,- bj C3 C4 C1 (1,- bj V4 V3 V2 a; bj 000 * 000 * 000 * 000 * 00111 11001 00111 11001 01010 01010 10111 10111 01111 01111 01111 01111 100 * 100 * 100 * 100'* 10111 10111 01010 0101 11001 00111 11001 00111 11111 11111 11111 11111 Like the design of MCPM, the carry output of (0100) can be changed to 1 in order to reproduce the patterns (1100) and (1110) internally because the input combi- nations (0100) and (0101) would never appear in the CSM. This can be proved by the following lemma. 53 Lemma 5. The input vectors (0100) and (0101) can never appear at the input to any cell in the CSM. Proof: By Lemma 2, the input vectors (1001) and (0001) can never appear in CPM. Since the input vector (c,d,a,b) in the CSM is equivalent to a vector (b,a,c,d) in the CPM, hence, by Lemma 2, (0101) and (0100) can never appear at the input to any cell in the CSM. Similar to Table 7, the input combinations for a MCSM derived from Table 10 are shown in Table 11. 54 Table 11. Input Combinations for a MCSM. Test_# Vectorl Vector 2 Vector 3 Vector 4 (cdab) (cdab) (cdab) (cdab) 1. 0000 0000 0000 0000 2. 0001 0001 0001 0001 3. 0010 0010 0010 0010 4. 0011 1101 0011 1101 5. 0110 0110 1011 1011 6. 0111 0111 0111 0111 7. 1000 1000 1000 1000 8. 1001 1001 1001 1001 9. 1010 1010 1010 1010 10. 1011 1011 0110 0110 11. 1101 0011 1101 0011 12. 1111 1111 1111 1111 13. 0100 1100 0100 1100 14. 1100 0100 1100 0100 15. 0100 1110 0100 1110 16. 1110 0100 1110 0100 In order to apply the test vectors in Table 10, those terminals assigned a logi- cal 0 in a CSM should become accessible. Figure 11(d) is a 4-by-4 modified CSM (MCSM). The following lemmas and theorem can be concluded. Lemma 6. The basic FA/AND cell of a CSM can be tested with 16 tests. Proof : A 4-input combinational circuit can be examined by all its input patterns, i.e., 16 tests. 55 Lemma 7. The basic CSM cells in Figure 11(b) can be tested with 16 tests. Proof : From the generation of Table 11, each basic cell can be exhaustively tested by those 16 patterns. Theorem 4. The MCSM is C-testable with a test length of 16. Proof : Similar to the proof of Theorem 2, if MBC is defined as the four basic cells of CSM and TS is the 16 test vectors in Table 11, then an n-by-n MCSM can be partitioned into m2 Mac’s, where n=2m. Since, by Lemma 7, each Mac can then be tested by the test set TS, an n-by-n MCSM can be tested by the same test set TS. So, the MCSM is C-testable with a test length of 16. 56 3.2.2. Test Pattern Generation. Consider the 4~by-4 modified Carry-Save array multiplier (MCSM), as shown in Figure 11(d). The c’, c, d, and e are connected to logical 0 during multiplication. However, it is assumed that during testing, these inputs are available as primary inputs to the array. Similar to Algorithm 1, Algorithm 2 generates both test patterns and expected outputs for a MCSM from Table 11. Table 12 illustrates the test patterns and expected outputs for a 4-by-4 MCSM. Algorithm 2: {* Vector_i=(ic,id,ia,ib), i=1,..,4. 57‘ * ic : c-input, id : d-input, ia : a—input, ib : b-input. * The Test patterns to be generated are: * a(i), b(i), c(i), c’(i), d(i), where i=0...n, e. n is an odd number. * The expected product is p(i), where i=0...2n+1. *} {* Step 1. (Test Patterns) For i=0 to n by 2 do Begin a(i):=1a; a(i+1):=2a; b(i):=1b; b(i+1):=3b; c’(i):=4c; c’(i+1):=2c; c(i):=1c; c(i+l):=2c; d(i):=ld; d(i+1):=2d; End; e:=a(0)"'b(0); {* Step 2: (Expected Results) For i=0 to 11 By 2 do Begin p(i):=4c; p(i+l):=2c; End; For i=n+1 To 2n+l By 2 do Begin p(i):=4c; p(i+l):=3c; End; *} If (Test_#=13 OR Test_#=15) Then For i=n+2 To 2n+1 do paw—(5; If (Test_#=14 OR Test_#=l6) Then For i=n+1 To 2n+1 do p(i):=p(_0; Test # 1° 9’?“ 9‘1“ P‘S” h’r‘ 1111 0101 1111 1111 1111 1111 1010 1111 0000 0000 1010 0101 Remark 2 a=(03020100) b=(b3b2blbo) C=(C3C2C1C0) C’=(C3’C2’C 1’C0’) d=(d3d2d1do) 0000 0000 1111 0101 0000 1111 1111 1111 1010 0000 1111 1111 0000 1111 0000 58 C 0000 0000 0000 1010 0000 0000 1111 1111 1111 1111 0101 1111 1010 0101 1010 0101 0101 1111 1111 1111 1111 1111 O OOOOHOHOOOHOHOOO Table 12. Test Patterns and Expected Outputs for MCSM. IExpecuxl Results 00000000 00000000 00000000 01011111 11110101 00000000 11111111 11111111 11111111 00001010 10100000 11111111 10011111 01000000 10011111 01000000 59 3.2.3. Design of an Alternative C-testable CSM. Consider an alternative Carry-Save Array Multiplier for multiplying two 5 - bit unsigned binary numbers, as shown in Figure 12(a) [4], referred to as CSM_B. The interconnection tapology shows that each a; is fed to the topmost cell and the cells in the next diagonal column. Each 17,- is fed to the cells in a row and the leftmost cell of its next row. Under the external constrains, the CSM_B is modified as shown in Figure 12(b). Control signals, d’s, SI, 52, S3, and e, are for producing the sequence of input combinations in Table 10. During normal multiplication, the signals d’s, SI, 52, S3, and e are all set to logical 0. Each cell in the t0p row constructed by two AND gates and a full-adder is now modified by inserting an XOR gate between the AND gate and the basic cell as shown in Figure 12(b). Either signal 51 or $2 is XORed with the output of this AND gate. The signal SI (52) is applied to the odd (even) numbered cells of the t0p row. The left-boundary cells are modified by adding an XOR gate with two inputs: S3 and bi. In addition, a signal e=aob1 is applied as the initial carry of the carry propagate stage. According to Table 11, Algorithm 3 generates both test patterns and expected outputs for a MCSM_B. Table 13 illustrates the generated test patterns and expected outputs for a S-by-S MCSM_B. Applying the test patterns of Table 13 to the MCSM_B allows us to conclude that the MCSM_B is C-testable with a test length of 16. 0 0 0 dibo o 405'} (a) 4.0, .7 ”400 O C (b) ' d. b. S.‘ x. “0 fl Q‘ 2. "0.1.1.... :1 “i ‘0 53 ‘1’0 23 2.. ’3 Q . 1- at..- i. l.J...... Figure 12. Schematic Circuit Diagram : (a) A S-by-S CSM_B [6]; ' and (b) A S-by-S Modified CSM_B. 61 Algorithm 3: {* Vector_i=(ic,id,ia,ib), i=1,..,4. * ic : c-input, id : d-input, ia : a-input, ib : b-input. * The test patterns to be generated are: * a(i), b(i), d(i), where i=0...n, e, 31, s2, s3. * The expected result is p(i), where i=1...2n+1. * n is even. *} {* Step 1. (Test Patterns) *} For i=0 to n by 2 do Begin d(i):=ld; d(i+1):=2d; a(i):=1a; a(i+1):=2a; b(i+1):=lb; b(i+2):=3b; End; e:=a(0)*b(1); If (2c=1 OR 4c=l) Then a(n):=1 Else a(n):=0; If (1a=1 AND 2a=0) Then a(n):=1; For k==0 to 1 do Begin b(0):=k; If (1a*b(0)=1c) Then s1:=0 Else sl:=l; If (2a*b(0)==1d) Then s2:=0 Else s2:=1; If (a(n)*b(1)=4c) Then s3:=0 Else s3:=1; If (a(n)*(b(0) XOR s3)=2c) Then k=1; End; If (1d=2d=1 AND 1a=0) Then b(0):=l; {* Step 2: (Expected Results) *} For i=0 to n By 2 do Begin p(i):=4c; p(i+l):=2c; End; For i=n+l to 2n+1 By 2 do Begin p(i):=4c; p(i+l):=3c; End; If (T est_#=13 OR Test_#=15) Then 62 For i=n+2 To 2n do p(i):=[7(_r)_; If (Test_#=14 OR Test_#= 16) Then— For i=n+1 To 2n do p(i):=p(r'); Table 13. Test Patterns and Expected Outputs for a 5-by-5 MCSM_B. Expected T881 # a b d S 1 52 S3 RCSUltS 1. 00000 00000 0000 0 0 0 0000000000 2. 00000 11110 0000 0 0 0 0000000000 3. 01111 00000 0000 0 0 0 0000000000 4. 10101 11111 1010 0 0 0 1010111110 5. 11111 10101 1111 1 1 1 0111101010 6. 01111 11110 1111 0 0 0 0000000000 7. 10000 00000 0000 1 1 1 0111111110 8. 10000 11111 0000 1 1 0 0111111110 9. 11111 00000 0000 1 1 1 0111111110 10. 11111 01010 0000 l 1 1 1000010100 11. 01010 11110 0101 1 0 0 0101000000 12. 11111 11111 1111 0 0 0 1111111110 13. 10000 00000 1111 0 l 1 1100111110 14. 00000 00001 1111 1 0 0 1010000000 15. 11010 00000 1111 0 l 1 1100111110 16. 10101 00000 1111 1 0 0 1010000000 Remark : a=(a4a3agalao) b=(b4b3bzbrbo) d=(d3d’2d1do) Theorem 5. The MCSM_B is C-testable with 16 test patterns. Proof : The only difference between the MCSM_B and MCSM is in their primary inputs of the boundary cells. For simplicity of discussion, the gates that pro- duce the outputs X5, 1’], and Zk, as shown in Figure 12, are denoted to as cell X5, Y1, and 2*, respectively. Since the control signals 51, S2 and S3 are set to 63 zero during the normal operation, the possible input combinations for the cells X3, Y1, and Z,‘ are: for X,- : (Sl,a,-,b0)=(000),(001),(010),(0ll); Y, : (Sznj.bo>=(000).(oo1).(010).(011); z, : (ambb53)=(000),(010),(100),(110). Since it has been shown that the MCSM is C-testable (Theorem 6), hence, the only problem remained is whether or not the above combinations can be included when the 16 patterns are applied. With the selected control signals, SI, 52, and S3, and the application of the test set in Table 11, the following table illustrates the combinations applied in the cells Xi, YJ- and Zk. The table shows that the above combinations are indeed included. Xi Yj Zo Z1,3... Z2,4... SI 0" b0 Sz aj b0 an b0 S3 an bk S3 an bk S3 1. 000 000 000 000 000 2. 000 000 000 010 010 3. 010 010 000 000 000 4. 001 011 110 110 110 5. 111 111 111 101 111 6. 010 010 000 010 010 7. 100 100 101 101 101 8. 101 101 110 110 110 9. 110 110 101 101 101 10. 110 110 101 111 101 11. 110 000 000 010 010 12. 011 011 110 110 110 13. 000 100 101 101 101 14. 101 001 010 000 000 15. 010 100 101 101 101 16. 100 010 100 100 100 3.3. Baugh-Wooley Array Multiplier (BWM) A S-by-S Baugh-Wooley Array Multiplier (BWM) is illustrated in Figure 13. It has been shown that the BWM is not C-testable [8]. 3.3.1. Design of C-testable MBWM A MCSM_C can be constructed from a MCSM_B if the cells in the second row from the bottom, or the (n-1)th row of an n-by-n MCSM_B, is modified as shown in Figure 14, where each a,‘ is replaced by an XOR gate having two inputs a,‘ and S4. When S4 is 0, the MCSM_C is functionally equivalent to a MCSM_B. Therefore, the test patterns of Table 13 can applied all the input combinations in Table 11 to every cell of the array and detect any single fault in MCSM_C. However, in order to detect the possible faults in the added XOR gates, the control signal S4 is assigned as shown in Table 14, where S4 is set to logical 0 except for Test_#l, #3, #5 and Test_#8. With the application of the test patterns of Table 14, it can be concluded that MCSM_C is C-testable. Lemma 8. MCSM_C is C-testable with a test length of 16. Proof : The MCSM_C is modified from MCSM_B as shown in Figure 14. Similar to the proof of Theorem 5, it is found that all the possible combinations of the ., b, sari-o. l.2.3nd(i.jl-M.41 05653 osiSJ 4.3. «be 9'» on. ‘o‘b ‘- 0 @‘Q’Q‘G’G‘Q -1. 1, v .. v Figure 13. A Schematic Circuit Diagram of a 5-by-5 Baugh-Wooley Array Multiplier [6]- xi (7‘ j I 2.4...“ i8 1.3.»... Figure 14. A Schematic Circuit Diagram of a 5-by-5 MCSM_C. cells on Wb are indeed included when the control signal 5,, is appropriately selected and applied. Since the MCSM_B is C-testable with a test length of 16, so is the MCSM_C. 67 W, : (b4,a,,,S4)=(001),(011),(101),(111), Table 14. Test Patterns and Expected Outputs for a MCSM_C. Expected Test_# a b d SI 52 S3 S4 Results 1. 00000 00000 0000 0 0 0 1 0000000000 2. 00000 11111 0000 0 0 0 0 0000000000 3. 01111 00000 0000 0 0 0 1 0000000000 4. 10101 11111 1010 0 0 0 0 1010111111 5. 11111 10101 1111 l 1 1 1 1111101011 6. 01111 11110 1111 0 0 0 0 1000000000 7. 10000 - 00000 0000 1 1 1 0 0111111110 8. 10000 11111 0000 l l 0 1 1111111110 9. 11111 00000 0000 1 1 1 0 0111111110 10. 11111 01010 0000 l l l 0 1000010100 11. 01010 11110 0101 l 0 0 0 0101000000 12. 11111 11111 1111 0 0 0 0 1111111111 13. 10000 00000 1111 0 1 l 0 1100111110 14. 00000 00000 1111 1 0 0 0 1010000000 15. 11010 00000 1111 0 1 l 0 1100111110 16. 00101 00000 1111 1 0 0 0 1010000000 Remark 3 a=(a4a3a2a1ao) b=(b4b3b2b1bo) d=(d3d2dldo) 'Ihe MCSM_C can be further modified by adding extra cells, as shown in Figure 15. During the normal operation, the control signals d, SI, 52, S3, 55, and S6 are 68 h " 30 0" b. 3! 7‘ X3 ’1 X. 2| O O O 1.0.12.— 2‘ _ O O O,,,, a. E 33 at. ‘I‘l'. OOW O O... s. l 0; O O O O O O' ., SS ‘0 so 54 t i Figure 15. A schematic Circuit Diagram of a 5-by-5 MBWM. 69- set to logical 0 and the signal 5,, is set to logical 1. It is obvious that, with the above assignments, the circuit of Figure 15 is functionally equivalent to the Baugh-Wooley Array Multiplier of Figure 13. This circuit is referred to as modified BWM, or MBWM. Theorem 6. The MBWM is C-testable with a test length of 16. Proof: The MBWM is modified from MCSM_C by adding extra cells as shown in Figure 15. With the appropriate selection of control signals, the 16 test pat- tern can be applied to test the extra cells. Therefore, the MBWM is C-testable with a test length of 16. 3.3.2. Test Pattern Generation. The testing problem of the MBWM can be separated into two parts, one is for the testing of MCSM and the other is for those additional cells. In order to reduce the number of test patterns, one may overlap the testing of the two parts together. Algorithm 4 generates both test patterns and expected outputs for a MBWM from Table 11. The method used here is to apply the 16 test vectors in Table 11 into this array by controlling the primary inputs. Also, the input patterns should cover all the possible input combinations of the boundary cells. Table 15 illustrates the test patterns and expected outputs for a 5-by-S MBWM. 70 Algorithm 4 : *ii-l-fl-i"; {31K Vector_i=(ic,id,ia,ib), i=1,..,4. ic : c-input, id : d-input, ia : a-input, ib : b-input. The Test patterns to be generated are: a(i), b(i), d(i), i=0,...,n, (s6,..,s1) The expected product is p(i), i=0,...,2n+1. The function inv(arg) returns a value which is the complement of "arg". n is even. *} Step 1. (Test Patterns) *} For i=0 to n by 2 do Begin a(i):=la; a(i+1):=2a; b(i+1):=1b; b(i+2):=3b; d(i):=ld; d(i+1):=2d; End; If (2c==1 OR 4c=1) Then a(n):=1 Else a(n):=0; If (la-1 AND 2a=0) Then a(n):=1; For k=0 to 1 do Begin b(0):=k; If (a(l)*b(0)=cl) Then sl:=0 Else sl:=1; If (a(2)*b(0)=c2) Then s2:=0 Else s2:=1; If (a(n)*b(1)=c4) Then s3:=0 Else 53z=1; If (a(n)*(b(0) XOR s3)=2c) Then k=1; End; If (1d=2d=l AND 1a=0 ) Then b(0):=1; s4:= 12W * 51' * .5 * E; If (d2¢a(n)) Then s5:=1 Else sS:=0; If (a2*b2 at b(n)) Then s6:=l Else s6:=0; If (sl*s2*s3=l AND 55:0) Then s4:=1; If (s1*s2*s5=l AND s3=0) Then s4:=1; 71 {* Step 2: (Expected Results) *} P(0)==a(0)*b(0); For i=1 to n-l by 2 do Begin p(i):=4c; p(i+ 1):=2¢; End; — For i=n to Zn by 2 do Begin p(i):=3c; p(i+l):=4c; End; If (a(n)¢2c OR b(n)¢2c) Then p(2n):=,7(2_n‘)‘; If (d2*a2*b2=l) Then p(2n+l):= inv(a(n))*inv(b(n)) Else If (2d=0 AND 2a*2b=0) Then p(2n+l):= inv(inv(a(n))*inv(b(n))) Else p(2n+l):=0; - If (Test_#=14,16) Then For i=0 to n-l do p(n+l+i):= p(n+l+z); If (Test_#=l3,15) Then For i=0 to n-l do p(n+2+i):= p(n+2+0; If (s4=l AND 35=0) Then Begin For i=n to 2n+l Do p(i):=0; End; If (54:1 AND s5=l) Then Begin p(n>==‘@;_ p(2n):=p(2n); p(2n+l):=p(2n+l); End; 72- Table 15. Test Patterns and Expected Outputs for a 5-by-5 MBWM. Expected Test # a b (1 SI - 56 Results 1. 00000 00000 0000 000100 0000000000 2. 00000 11110 0000 000001 1100000000 3. 01111 00000 0000 000100 0000000000 4. 10101 11111 1010 000001 0010101111 5. 11111 10101 1111 111101 0000001011 6. 01111 11110 1111 000010 0100000000 7. 10000 00000 0000 111010 1111111110 8. 10000 11111 0000 110111 0011101110 9. 11111 00000 0000 111010 1111111110 10. 11111 01010 0000 111011 0000000100 11. 01010 11110 0101 100000 0001010000 12. 11111 11111 1111 000000 0111111111 13. 10000 00000 1111 01100 0 0101001110 14. 00000 00001 1111 10 0 010 1010010000 15. 11010 00000 1111 01 10 0 0 0101001110 16. 10101 00000 1111 1 0 0 0 1 0 1010010000 Remark : a=(a4a3azalao) b=(b4b3b2b1bo) d=(d3d2dldo) Table 16 illustrates the input combinations for each cell in a 5-by-5 MBWM. It is obvious that, similar to the design of MCSM, all possible input combinations have been applied to each cell. However, the following combinations are not applied. Cell 1 : (000), (011), (101), (111) ; Cell 2 : (000), (001), (010), (011) ; Cell 3 : (010), (001). where Cell 1, Cell 2, and Cell 3 are the cells labeled in the Figure 16. 01 O4 101 05 101 06 101 O7 100 08 101 110 000 100 100 110 000 001 110 001 101 100 111 010 100 001 110 73 Table 16. Input Combinations for each cell in a 5-by—5 MBWM. 0000 0010 0010 000 000 0001 0001 0001 000 000 0010 0000 0000 000 000 1101 1101 0011 001 110 0110 1001 1001 101 101 0111 0111 0111 011 011 1000 1000 1000 100 100 1001 1011 1011 010 010 0000 0000 0010 000 0001 0001 0001 000 0010 0010 0000 000 1101 0011 1101 001 1011 0110 1001 101 0111 0111 0111 011 1000 1000 1000 100 1001 1001 1011 010 0000 0000 0000 0010 000 0001 0001 0001 0001 000 0010 0010 0010 0000 000 1101 0011 1101 0011 110 0110 1011 0110 1001 110 0111 0111 0111 0111 011 1000 1000 1000 1000 100 1001 1001 1001 1011 000 0000 0000 0000 0001 0001 0001 0010 0010 0010 0011 1101 0011 0110 1011 0110 0111 0111 0111 1000 1000 1000 1001 1001 1001 0000 0000 0001 0001 0010 0010 1101 0011 0110 1011 0111 0111 1000 1000 1001 1001 0000 0001 0010 0011 0110 0111 1000 1001 O9 100 #10 101 911 101 013 101 014 015 101 016 111 010 100 100 101 001 111 010 111 110 011 010 111 110 011 1010 100 0110 101 0011 110 1111 111 1100 011 0100 111 1110 011 0100 111 1010 1010 100 1011 0110 101 0011 1101 001 1111 1111 111 1100 0100 111 0100 1100 011 1110 0100 111 0100 1110 011 1010 1010 1010 100 0110 1011 0110 101 0011 1101 0011 110 1111 1111 1111 111 1100 0100 1100 011 0100 1100 0100 110 1110 0100 1110 011 0100 1110 0100 110 1010 1010 1010 1010 100 1011 0110 1011 0110 101 0011 1101 0011 1101 001 1111 1111 1111 1111 111 1100 0100 1100 0100 110 0100 1100 0100 1100 010 1110 0100 1110 0100 110 0100 1110 0100 1110 010 1010 1010 1010 1011 0110 1011 1101 0011 1101 1111 1111 1111 0100 1100 0100 1100 0100 1100 0100 1110 0100 1110 0100 1110 PH 00 Hrs 00 1011 0110 0011 1101 1111 1111 1100 0100 0100 1100 1110 0100 0100 1110 1011 1101 1111 0100 1100 0100 1110 74 '7 z; 00¢“ 1 e1 0 o o a 0 0' e2 Figure 16. The Bottom Row of MBWM in Figure 15. 75 Consider all the possible combinations of a4 and b4. 04 b4 Input Combinations 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0 1 l 0 0 1 Because of the external constrain, all the possible input combinations are demonstrated in the above table. Therefore, input combinations (000), (011), (101), and (111) do not occur in Cell 1 during the normal operation. Since the top input of Cell 2 is always 1 during normal operation, this implies that input combinations (000), (001), (010), and (011) do not occur in Cell 2 during the normal operation. Finally, consider the interconnection of Cell 3 as shown in Figure 16. Also consider the following truth table for the sum bit of Cell 1. a4 b4 sum 0 0 0 0 1 l 1 0 1 1 1 1 In other words, both 04 and b4 must be zeros if the sum bit of the Cell 1 is zero. Sup- pose that (010) can occur in Cell 3, Le. the top input of Cell 3, or the sum output of Cell 1, is logical 0. This results in both a4 and 17., being 0. Therefore, the inputs 26 and W3 of Figure 15 are also logical 0 and the cell would never produce a logical 1 in its carry-out bit. This implies that (010) does not occur in Cell 3 during normal operation. 76 Similarly, it can be easily found that (001) will never occur in Cell 3. The above arguments show that the possible input combinations of those extra cell are indeed included when the 16 test patterns are applied. IV. Design of C-testable Array Dividers 4.1. N on-Restoring Array Divider. A 4—by-4 Non-restoring array divider (NRD) is illustrated in Figure 17. This divider receives a 7-bit dividend, 4-bit divisor, and produces a 4-bit quotient and a 4- bit remainder. In this section, the design of C-testable NRD is presented. The graph labeling scheme is also applied to generate test patterns. The basic building block of a non-restoring divider is a controllable adder/subtractor (CAS) [6], as shown in Figure 18, where =X$YQZ$D, and P=(Y$D)X+ (YOD)Z+XZ. When D=0, the cell is merely a full adder, i.e., S is the sum of X, Y, and Z and P is the carry. On the other hand, when D=1, the cell becomes a full adder with inputs X, Z and 17. Consequently, the labeling scheme developed for full-adder—based array mul- tipliers is also suitable for NRD. 4.1.1. Graph Labeling. Because of the regularity of the NRD, the four basic CAS cells, M;, i=1 to 4, as shown in Figure 19 can be found. According to the interconnection topology of the 77 78 .5 9.2 13 a co semen :35 23538 < .5 2am 8 P E P A a: Elli a V_;n= an __y a: 79 Y x D x xx \ P < FA v S S=XOY$Z$D =(YoD)X+(YoD)Z+xz Figure 18. The Basic building block of a NRD. 80 four basic cells, the mappings L11L12L13 "" [13162 ; [41%3 —’ L13L42 ; (17) 141162163 “> L43L12 3 L41L42L43 "> [calm ; where 161:1’21’ L41=L11 : can be obtained. we shall solve the mappings for Lij’s, i=1,2,3,4 and j=1,2,3, where 2' indicates the cell type and j represents the input. Theorem 7. The following set of labels is a solution of mapping (17) : L1=(L11L12’L13)=(V19D:V2.V3) ; [n=(L211/22»I/23)=(C 19135254) ; (13) Ic=(l61162143)=(C19D»V4»C3) ; and L4=(L41L42»L43)=(V19D»C3:V4)~ Proof : Similar to the proof of Theorem 1, with the mappings (17), we can solve for the labels in (18). 81 141 bn L11 L12 D \ ! : : F——_¥___" M2 M1 L L13 [fi 13 < j‘ .15 \41 L42 [m £62 __J¢____ D ,T___>M__.T M4 M3 [6 ’43 L“ 3 < 1‘ JE Figure 19. Four Basic Cells of a NRD. 82 Figure 20 shows the application of the labels in (18) to a 4-by-4 NRD. In Table 17, the test#1-8 and test#1l-l8 illustrate the input combinations generated directly from the label set (18). They contain all possible input combinations except the patterns { (010),(101) } ( for D=0 ) and { (001),(110) } ( for D=1 ) in both L3 and L4. Therefore, the tests #9, #10, #19, and #20 are added. Tabel 17. Input combinations for an MNRD. Test# D L1 L2 L3 L4 0x2) (YXZ) (YXZ) (YXZ) l. 0 000 000 000 000 2. 0 001 110 110 001 3. 0 010 100 111 011 4. 0 011 101 100 000 5. 0 100 010 011 111 6. 0 101 011 000 100 7. 0 110 001 001 100 8. 0 111 111 111 111 9. 0 010 010 010 010 10. 0 101 101 101 101 11. l 100 100 100 100 12. 1 101 010 010 101 13. 1 110 000 011 111 14. 1 111 001 000 100 15. 1 000 110 111 011 16. 1 001 111 100 000 17. 1 010 101 101 000 18. 1 011 011 011 011 19. 1 001 001 001 001 20. 1 110 110 110 110 83 one so Dun 3 .92 a 9 232 do cousin.“ 2:. .8 2am H a v> MU v> MU it V all . —HQ HMO \ n01—fl «b v> —b «.0 —b v> ulM A/ m> VD n> VD . m> / fl: \ 7a . To v> G S no . 9 mil v To \7 7a 6 C7 9 ...M «U S as U n . n In: so as G a w 3 _ To . . u N>Vfl C» . NU\_I U ~>\_/ .3 ~rU\_/ —0 fl Q 84 82:89 .8 use» «S l\_/ mu . v; \_t n a o n l . 1, one . , one m0 _> «S .D / n9 5 «S .0 A! as , G n; G . § / _ m 'V no . ono as S no G as S G G g/ my 6 . . S no v; / V ”UH C» v> —.U MU ~\‘ v> ~U \fi n , 3v 1 . . . 11% 85 4.1.2. Test Pattern Generation. It has been shown in Table 17 that all possible input combinations can be applied to exhaustively test the four basic CAS cells of Figure 18. Since an NRD is constructed by these four basic cells, the labels (18) can be propagated to the entire NRD. However, Figures 20(a) and 20(b) show that the P-output of the leftmost cell in the first row is fed to the D-input of the leftmost cell in the second row, and then the D-output of the rightmost cell in the second row is fed to the Z-input of the same cell. This implies that the label applied to the P-output of the leftmost cell in the first row must be the same as the label applied to the Z-input of the rightmost cell in the second row. In practice, the application of labels (18) may not meet this requirement. There- fore, in order to consistently apply the labels two XOR gates are added to the NRD in each row, as shown in Figure 21. Two extra control lines, Testl and Test2, are needed in this design. During the normal operation, both Testl and Test2 are at logical 0. However, during the test mode, if the size of the divider is even, labels V3 (or 173) and V4 (or 174) are respectively assigned to Testl and Test2 for D=0 (or D=1). Theorem 8. The modified NRD of Figure 21 is C-testable with a test length of 20. Proof : Similar to the proof of Theorem 2, if Mac is defined as the four basic cells of NRD and TS is the 20 test vectors in Table 17, then an n-by-n MNRD can be partitioned into m2 MBC’s, where n=2m. Since each MBC can be tested by the 86 test set TS, an n-by-n MNRD can then be tested by the same test set TS. So, the MNRD is C-testable with a test length of 20. According to input combinations of Table 17, Algorithm 5 generates the test patterns and expected outputs for a MNRD. Table 18 shows the test patterns and expected outputs for a 4~by-4 MNRD. 87 .522 usage Co 82351330 32.2% < .3 2:5 E a Slang. -..Nlawb \l/ NV _. 30,—. cad. \JV 88 Algorithm 5: Consider the following four vectors: Vector i: (ia,ib,ic), i=1....4. ia : y-input, ib : x-input, ic : z-input. This algorithm is to generate the input test patterns during test mode. The test patterns to be generated are : n(i), d(i), i=0,...,2N+1, Testl, Test2, D The expect values are : q(i), r(i), i=0,...,N N+l is even *} *xx-x-x-x-x"; For i=0 to N do Begin Ifi is even Then Begin, n(N+i):=1a; n(N-i):=1a; d(N-i):=lb; q(N-i):=4c; r(N+i):=la; r(N-i):=la; End Else Begin n(N+i):=4a; n(N-i):=2a; d(N-i):=2b; q(N-i):=1c; r(N+i):=2a; r(N-i):=4a; End End; Testl:=(lc XOR D); Test2:=(4c XOR D); 89 Table 18. Test Patterns and Expected Outputs for a 4-by-4 MNRD. Thsflt Spmspwswwr 11. 12. l3. 14. 15. 16. 17. 18. 19. 20. n 0000000 1010000 0101111 0101010 1010101 1010000 0101010 1111111 1111111 0000000 0000000 1010000 0101111 0101010 1010101 1010000 0101010 1111111 0000000 1111111 d 0000 1010 1010 1010 0101 0101 0101 1111 0000 1111 1111 1111 0101 0101 1010 1010 1010 0000 0000 1111 Thstl HOOHOHOr—OHHOv—IOHOHOHO Tesfil HOOHHOHOOHHOHOOHOHHO r 0000000 0000101 1111010 0101010 1010101 0000101 0101010 1111111 1111111 0000000 0000000 0000101 1111010 0101010 1010101 0000101 0101010 1111111 0000000 1111111 Remark 3 n=(no "1 ”2 "3 "4 "5 "6) d=(do d1 dz d3) "=(’o ’1 "2 '3 "4 ’5 ’6) 4=(40 41 (12 43) 1111 0101 1010 0101 1010 1111 1111 1111 0101 1010 0101 1010 1111 1111 4.2. Restoring Array Divider. A Restoring Array Divider (RSD), as shown in Figure 22, is constructed by the identical building blocks, controllable subtractors (CSs) in Figure 23. The functions of each basic building block are =(xoYeZ)D'+XD ; and P=YZ+X_Z+)?Y . It is obvious that the RSD is not C-testable because when D=l, S=X, any fault that occurs at either inputs Y or Z cannot be propagated to its output. In order to propagate the fault, the basic CS cell is modified as shown in Figure 24, where the cell functions become S=(XOYOZ)D-+XD , P=YZ+Y2+fY, (19) and B=A$Y$Z . The modified CS (MCS) cell of Figure 24 receives an extra input A and pro- duces an extra output B. Any fault that occurs at either input Y or Z can be pro- pagated to the output B. 91 ...oEZD >82 watoaom he SPEED .385 28528 < .N~ ennui 92 v x D _ ... - ._ .._... _. _. .. cs P < 9—— Z \ Y s =(xoY02)5'+XD P=YZ+XZ+YY Figure 23. A Basic Cell of a RSD. 93 Y X A D _ _ - MCS P {—— <____._..__ z .4 s B Y S=X$YOZ$D P=(YOD)X+(Y$D)Z+XZ B=A$Y$Z Figure 24. The Modified CS Cell of a MRSD. 94 4.2.1. Graph Labeling. The MCS cell functions (19) can be described by the following mapping : YXAZD ---> PSB, (20) where P=f(f, Y, Z), S=D—g(X, Y. Z)+DX. and B=g(A, Y, Z). Consider the case of D=l, the mapping (20) can be simplified as YXAZ --.> PSB, ' (21) where P=f(}?, Y, Z), S=X, and B=g(A, Y, Z). The function of f and g have been defined in (1) and (2). 95 Consider also the eight MCS cells of Figure 25. Each cell is labeled by Li=(L,-1,LQ,L,~3,L,-4). Based on the topological interconnection of these cells, we shall solve for Lij’s from the following mappings : L11L12L13L14 ""> LuLssta: loll/22143524 ""> [44L82L83’ [41162143164 ""> Lott/721473, L41L42L43L44 “"> L54L62L63’ (22) L51L52L53L54 ----> Lulczlcs: L61L62L63L64 ----> 1,41,21,23. 141142143144 ““> [14L12L13’ Ls 1L32L33Ls4 “"> L14L42L43’ and Lu=L21=L31=L4p L51=L61=L71=L8l° 96 L54 M4 L 44 t I E \LGI‘La1L63 L31 143 1 <—-—1- l [mil/53 Figure 25. Eight Basic Cells of a MRSD. 97 Theorem 9. Proof : The set of labels, L1==(V1.52.C1$K.v2). L2=(Lz11/22l/z3144)=(V1J72:C4$K:V3). lo=(lcrlczr[/33,L34)=(V1fzfifiKyy): L4=(L41,L42,L43,L44)=(V1,17'2,V20K,V3), L5=(L51,L52’L53:L54)=(C1:52529K:C4)» L5=(L51L52A3L54)=(C1.172,V4$K,V1), [n=(L71L721’731/74)=(C1:C-3-2»C49K:C4)a and Ls== PSB, (23) where 1340?, Y, Z), S=g(X. Y. Z). and B=g(A, Y, Z). 98 The following Theorem can be concluded. Theorem 10. The set of labels, L1=la=(V1,@C39K,V4) . LZ=L4=(V1,I72,V2$K,V3) , L5=lo=(Cr:52:C29K»C4) , and L6=L8=(C1,‘7-4,V4$K2C3) a is a solution of the mapping (22) with the cell function (23), where K is either 1 or 0. Proof : Similar to the proof of Theorem 7, this can be simply proved by solving map- pings (22) under D=0. In summary, Theorems 11 and 12 describe the labels applied to a MRSD for both D=l and 0, respectively. Table 19 illustrates the input combinations of the MCS cells of Figure 25, where Li=(L,-1,L,~2,L,3,L,-4). In Table 19, while Test #1-#8 and #11- #18 are the input combinations derived directly from Theorem 12 for D=0, Test #21- #28 and #31-#38 are those derived from Theorem 11 for D=1. Similar to Table 17, in order to apply all possible input combinations, Tests #9, #10, #19 #20, #29, #30, #39, and#40areadded. Thsflt 199°:q P‘S*:“'?’F°:‘ 23. eeszssau: U U) seesaex. C1 u—ou-tHI-oI-bt—‘Hv-on-AI-‘v-ou-oHu-ot—srut—-MHHOOOOOOOOOOOCOOOOOCOO L1 (530» 0100 0101 0011 0100 1011 1100 1010 1011 0010 1101 0110 0111 0001 0110 1001 1110 1000 1001 1111 0100 0010 0111 1000 1101 1011 1111 0011 1110 0110 0101 1010 1111 1001 0010 1101 0001 1100 r, (bafip) 0100 0101 0010 0011 1100 1101 1010 1011 0010 1101 0110 0111 0000 0001 1110 1111 1000 1001 0000 1111 0100 0101 0000 1100 1010 1011 0000 1111 0001 1100 0110 0111 0010 1110 1000 1001 0010 1101 0011 1110 99 lg (bafip) 0100 0101 0011 0100 1011 1100 1010 1011 0010 1101 0110 0111 0001 0110 1001 1110 1000 1001 0000 1111 0100 0000 0111 1010 1111 1011 0000 1111 0011 1110 0110 0010 0101 1000 1101 1001 0010 1101 0001 1100 A mm) 0100 0101 0010 0011 1100 1101 1010 1011 0010 1101 0110 0111 0000 0001 1110 1111 1000 1001 0000 1111 0100 0101 0010 1100 1010 1011 0000 1111 0001 1100 0110 0111 0000 1110 1000 1001 0010 1101 0011 1110 L5 (bafin 0100 1010 1100 1101 0010 0011 0101 1011 0010 1101 0110 1000 1110 1111 0000 0001 0111 1001 0000 1111 0100 1010 1100 0010 0101 1011 0000 1111 0001 1100 0110 1000 1110 0000 0111 1001 0010 1101 0011 1110 Table 19. Input Combinations for MRSD. L6 (bafifi 0100 1010 1011 1100 0011 0100 0101 1011 0010 1101 0110 1000 1001 1110 0001 0110 0111 1001 0000 1111 0100 1110 1010 0111 0001 1011 0000 1111 0011 1110 0110 1100 1000 0101 0011 1001 0010 1101 0001 1100 1.7 (bafin '0100 1010 1100 1101 0010 0011 0101 1011 0010 1101 0110 1000 1110 1111 0001 0111 1001 1111 0100 1000 1100 0111 1011 1111 0001 1100 0110 1010 1110 0010 0101 1001 0010 1101 0011 1110 L3 (bafin 0100 1010 1011 1100 0011 0100 0101 1011 0010 1101 0110 1000 1001 1110 0001 0110 0111 1001 1111 0100 1110 1000 0111 0001 1011 1111 0011 1110 0110 1100 1010 0101 0011 1001 0010 1101 0001 1100 100 4.2.2. Design for C-testability. Figure 26 shows the Modified 4-by-4 Restoring Array Divider (MRSD). Simi- lar to Figure 21, additional XOR gates and control lines, Testl and Test2, are needed. During the normal operation, Testl, Test2 and 2’s are all assigned to logic 0, and ter- minals a’s, b’s and ro-rz are discarded. 4.2.3. Test Pattern Generation. According to Table 19, Algorithm 6 generates the test patterns and expected outputs for a MRSD. Table 20 illustrates the test patterns and expected outputs for a 4-by-4 MRSD. Therefore, the following Theorem results. Theorem 11. The MRSD of Figure 26 is C-testable with a test length of 40. Proof : Similar to the proof of Theorem 2, if Mac is defined as the eight basic cells of RSD and TS is the 40 test vectors in Table 19, then an n-by-n MRSD can be partitioned into pq Mac’s, where n=2p=4q. Since each Mac can be tested by the test set TS, an n-by-n MRSD can then be tested by the same test set TS. So, the MRSD is C-testable with a test length of 40. 101 .QmM—Z v-3-v a he 89.929 “385 oquozow < .8 2=mE a Q. ~ N a: a: E n E i 1 . i T 1 ~33. x /l , . _ / 1 n6 n: l l l. S a: _N n: 0A a: n «2 a: a» <2 3 _ ~ _ n no 9. mm «e N: .e .e a co 102 Algorithm 6 : {* Consider the following eight vectors: Mi: (ib,ia,if,ip), i=1....4 * ib : Y-input, ia : X-input, if : A-input, ip : Z-input. * The test patterns to be generated are : * a(i), d(i), i=0,...,2N, Testl, Test2 * The expect values are : * q(i), r(i), b(i), i=0,...2N * N+1 is the multiple of 4 *} For i=0 to N do Begin k = i mod 4 Case k 0: d(N-i):=4b; a(N-i):=4f; 1: d(N-i):=5b; a(N-i):=5f; 2: d(N-i):=4b; a(N-i):=4f; 3: d(N-i):=5b; a(N-i):=5f; End; — Test1=(4p XOR D); Test2=(3p XOR D); For i=0 to N do Begin 1: = i mod 4 Case k 0: b(N+i):=4f; r(N-i)==4a; 1: b(N+i):=5f; r(N—i):=1a; 2: b(N+i):=4f; r(N—i):=2a; 3: b(N+i):=5f; r(N-i):=3a; End; n(N-i):=4a; a(N+i):=4f; n(N-i):=5a; a(N+i):=3f; n(N-i):=4a; a(N+i):=2f; n(N-i):=5a; a(N+i):=1f; b(N-i):=4f; Q(N-i)==1p; b(N-i):=1f; <1(N-i)==2p; b(N-i):=2f; q(N-i):=3p; b(N-i):=3f; Q(N-i)==4p; n(N+i):=4a; z(i):=4p; n(N+i):=3a; z(i):=3p; n(N+i):=2a; z(i):=2p; n(N+i):=la; z(i):= 1 p; r(N+i):=4a; r(N+i):=5a; r(N+i):=4a; r(N+i):=5a; -i PP395‘5‘PPF‘E Mgr-IHO-‘I-‘HHO-‘I-‘HH .. . 3° 9° >'£’IE* 3* 9’19 r‘ F> 33.393039363133913. 32. 33. 35. 37. 38. 39. t-‘I-It-IHI-‘HI-it-lU-OU-it-‘l-II-IHI-OO-IO-lHHHOOOOOOOOOOOOOOOOOOOOU Table 20. Test Patterns and Expected Outputs of a 4-by-4 MRSD. n 1111111 0101111 1010000 1010101 0101010 0101111 1010000 0000000 0000000 1111111 1111111 0101111 1010000 1010101 0101010 0101111 1010000 0000000 0000000 1111111 1111111 0101010 1010101 0101010 1010101 0000000 0000000 1111111 0000000 1111111 1111111 0101010 1010101 0101010 1010101 0000000 0000000 1111111 0000000 1111111 d' 0000 1010 1010 1010 0101 0101 0101 1111 0000 1111 0000 1010 1010 1010 0101 0101 0101 1111 0000 1111 0000 1010 1010 0101 0101 1111 0000 1111 0000 1111 0000 1010 1010 0101 0101 1111 0000 1111 0000 1111 a 0000000 1010000 0101111 0101010 1010101 1010000 0101111 1111111 1111111 0000000 1111111 0101111 1010000 1010101 0101010 0101111 1010000 0000000 0000000 1111111 0000000 1010001 0101101 1010100 0101110 1111111 0000000 1111111 0000101 0000101 1111111 0101110 1010010 0101011 1010001 0000000 1111111 0000000 1111010 1111010 103 Z 1111 0101 1010 0101 1010 1111 1111 1111 0101 1010 0101 1010 1111 1111 1010 0101 0101 1111 1111 1111 0000 0000 1010 0101 0000 0101 1111 0000 1111 1111 0000 Testl 0 Hocwowr—HOHHQOh-OHu—HOv—nt—nOHOHQHQr—QU—Or—Or—OI—Or— Test2 0 Hook-aooh-OHr—HQOHOOHOHHHOHOQHOHHOHOu-aoor—Ov—r— r 1111111 1111010 0000101 1010101 0101010 1111010 0000101 0000000 0000000 1111111 1111111 1111010 0000101 1010101 0101010 1111010 0000101 0000000 0000000 1111111 1111111 0101010 1010101 0101010 1010101 0000000 0000000 1111111 0000000 1111111 1111111 0101010 1010101 0101010 1010101 0000000 0000000 1111111 0000000 1111111 Z-(Zo 21 12 z3)'=("o "1 '2 '3 '4 '5 '6) 4=(