# On the Use of an Algebraic Signature Analyzer for Mixed-Signal Systems Testing

Authors: Vadim Geurkov; Lev Kirischian
Journal: VLSI Design
 (2014)

---

## Abstract

We propose an approach to design of an algebraic signature analyzer that can be used for mixed-signal systems testing. The analyzer does not contain carry propagating circuitry, which improves its performance as well as fault tolerance. The common design technique of a signature analyzer for mixed-signal systems is based on the rules of an arithmetic finite field. The application of this technique to the systems with an arbitrary radix is a challenging task and the devices designed possess high hardware complexity. The proposed technique is simple and applicable to systems of any size and radix. The hardware complexity is low. The technique can also be used in arithmetic/algebraic coding and cryptography.


---

## Body

## 1. Introduction

Signature analysis has been widely used for digital and mixed-signal systems testing [1–12]. Mixed-signal systems consist of both digital and analog circuits; however the signature analysis method is only applicable to the subset of these systems that have digital outputs (such as analog-to-digital converters, measurement instruments, etc.). Signature analysis can be employed as an external test solution or can be embedded into the system under test. In the built-in implementation, a circuit under test (CUT) of digital or mixed-signal nature is fed by test stimuli, while the output responses are compacted by a signature analyzer (SA), as illustrated in Figure 1. The actual signature is compared against the fault-free circuit’s signature and a pass/fail decision is made. A signature of a fault-free circuit is referred to as a reference signature. If the CUT is of a digital nature, the SA essentially constitutes a circuit that computes analgebraic remainder. The reference signature has only one,punctual value, and the decision making circuit consists of a simple digital comparator. If the CUT is of a mixed-signal nature, the SA computes anarithmetic residue. In this case, the reference signature becomes aninterval value and the decision making circuit uses a window comparator.Figure 1
Built-in signature analysis of a circuit under test.Design methods for an algebraic signature analyzer have been well developed in error-control coding [13]. A remainder calculating circuit for an arbitrary base (binary or nonbinary) can be readily designed for a digital CUT of any size. In contrast, it is much harder to design a residue calculating circuit, specifically for a nonbinary base [14]. Furthermore, due to the presence of carry propagating circuitry, the implementation complexity and error vulnerability of the residue calculating circuit are higher compared to the remainder calculating circuit.We propose an approach to design of an algebraic signature analyzer that can be used for mixed-signal systems testing. Due to an algebraic nature, the analyzer does not contain carry propagating circuitry. This helps to improve its error immunity, as well as performance.


## 2. A Conventional Signature Analyzer

An algebraic signature analyzer is designed on the basis of a polynomial division circuit, as shown in Figure2 [3, 13, 15]. This circuit divides the incoming sequence of nonbinary symbols (digits), am-1,…,a1,a0, treated as a polynomial:
(1)ay=am-1ym-1+⋯+a1y+a0
by the polynomial
(2)py=ptyt+⋯+p1y+p0,t≪m.
The remainder
(3)sy=st-1yt-1+⋯+s1y+s0
constitutes a CUTsignature.Figure 2
At-stage polynomial division circuit.Each digit,ai, 0≤i≤m-1, consists n bits and is considered to be an element of the field GF(2n). The degree of the polynomial (2), or the number of stages, t, in Figure 2, depends on the desired probability of undetected error in the sequence of incoming digits. For long sequences with independent errors, this probability is estimated as Pnd≈2-tn. In practice, n≥8 and even for the one-stage circuit, Pnd≤2-(1×8)=0.0039, which is quite low. Therefore, a multiple-input signature analyzer normally contains only one stage. Such an analyzer is presented in Figure 3 [14], where α is a primitive element of the field GF(2n), that is, a root of a primitive polynomial gx=gn-1xn-1+⋯+g1x+g0. Each element of the field can be represented by a power of α. Let αi be the incoming digit and αj the content of the analyzer. Then, each operational cycle of the analyzer is described by the expression
(4)αjα⊕αi=αk.Figure 3
A symbolic presentation of a one-stage algebraic signature analyzer.Without a loss of generality, we will consider a 3-bit signature register (n=3), with α being a primitive element of GF(23), in particular a root of a primitive polynomial g(x)=x3+x+1. Then, a symbolic scheme of Figure 3 will transfer to the logic level circuit of Figure 4, where
(5)αl=a2(l)x2+a1lx+a0l,ail∈0,1,0≤i≤2,0≤l≤6.Figure 4
A logic level presentation of the algebraic 3-input signature analyzer.This expression indicates the relationship between the power and vector representations of a field element, as reflected in Table1 (where x=α).Table 1
Three representations for the elements ofGF(23) generated by g(x)=x3+x+1. Here g(α)=0.
Power
Polynomial
Vector
representation
representation
representation
α
l
a
2
(
l
)
α
2
+
a
1
(
l
)
α
1
+
a
0
(
l
)
α
0
a
2
(
l
)
a
1
(
l
)
a
0
(
l
)
0
0
000
α
0
α
0
001
α
1
α
1
010
α
2
α
2
100
α
3
α
1
+
α
0
011
α
4
α
2
+
α
1
110
α
5
α
2
+
α
1
+
α
0
111
α
6
α
2
+
α
0
101If the preliminary “cleared” analyzer receives, for example, the following sequence of 3-bit output responses from a digital CUT,α5, α6, α4, α2, α1, α0, then after the 6th shift its content will become
(6)0·α+α5α+α6α+α4α+α2α+α1α+α0=α.The power representation of the field element,α, corresponds to the vector representation, 010, which is the actual signature of the CUT.In contrast to a digital CUT, the output responses of a mixed-signal CUT are distorted even in a fault-free case. Small permissible variations in the responses cause a significant deviation of the final signature. For example, if in the above sequence of output responses the least significant bit in the first response changes from 1 to 0 (i.e., the vector 111 changes to 110, or powerα5 changes to α4), then the actual signature will change from 010 to 101 (or from α to α6 in power form).Apparently, the conventional SA represented in Figures3 and 4 cannot be employed for mixed-signal circuits testing.In the known methods, output responses of mixed-signal circuits are compacted by a circuit referred to as a modulo adder (or accumulator, or digital integrator) [4–8]. It should be noted that a modulo adder is a special case of aresidue computing circuit [14]. A residue computing circuit is represented in Figure 5. Here aj is the current content of the register, ai is the incoming (arithmetic) symbol, and b is the base of the system. This circuit divides the incoming sequence of symbols, am-1,…,a1,a0, treated as a number:
(7)a=am-1bm-1+⋯+a1b+a0
by the modulus
(8)p=pt-1bt-1+⋯+p1b+p0,t≪m.Figure 5
A symbolic presentation of a one-stage arithmetic signature analyzer.As in the case with the algebraic SA, we consider a single-stage device; that is,t=1, p=p0<b=2n, where n is the number of bits occupied by the symbol. The residue, s0, constitutes a signature.An operational cycle of the circuit in Figure5 can be described by the expression
(9)ajb+ai=aj+mod⁡p.Although the circuits of Figures3 and 5 look similar, their implementation is quite different. In general case, the designing procedure for the arithmetic circuits is more complicated and their hardware complexity is greater.As an example, Figure6 represents the circuit that computes a modulo 5 residue of the incoming sequence of 3-bit symbols treated as an octal number [14]. Here ai is the incoming octal digit and C is a combinational circuit which generates the following next state signals:
(10)c2=a0ja1j¯a0ia1ia2i+a1ja0ja1i⊕a2i+a0ja0ia2i¯,c1=a2ja2i¯(a0i¯+a1i¯)+a2j¯a2i(a0j¯a0i+a1j¯a1i)+a1ja0j¯+a2i¯+a0ja1i⊕a2i,c0=a0ja1i(a1j⊕a2i¯)+a1ja2i¯(a0j¯+a0i¯a1i¯)+a2j+a1j¯a2ia0j¯a1i+a0ia1i¯+a0ja0i¯.Figure 6
A 3-input arithmetic compactor.Each shift of this circuit implements the operationaj×8+ai (mod 5).In addition to high hardware complexity, the arithmetic compactor contains carry propagating circuitry (shown in red color in Figure6) that delays the operation and aggravates the effect of a single fault.Below, we design an algebraic circuit that can be employed for mixed-signal data compaction. It does not contain carry propagating circuitry.


## 3. A Novel Approach

Polynomial (1) in conjunction with the reference signature can be considered as a code word of the code whose minimal distance is defined by the g(x). The distance here is the Hamming distance. This distance characterizes algebraic error-detecting properties of the code and is not convenient for arithmetic errors that occur in mixed-signal systems. Indeed, a small permissible deviation of the data to be compacted causes the reference signature to span the entire space. Under these conditions, the decision making circuit in Figure 1 must be able to compare the actual signature with the entire set of possible reference signatures. This increases the analyzer complexity.To decrease the complexity, an arithmetic SA treats the sequence of output responses from a mixed-signal circuit as a number (7). In conjunction with the reference residue, this is considered as a code word of an arithmetic error-control code. The properties of this code depend on the arithmetic minimal distance which in turn depends on the modulus p. The arithmetic residue calculating analyzer does not search the entire space, since the space of arithmetic reference signatures is now contiguous. To make a decision, it employs a window comparator. This simplifies the circuitry. However, the hardware complexity of the arithmetic SA can still be quite high, as it was illustrated above.In the rest of this paper, we will show how to design an algebraic SA, which generates a contiguous space of algebraic reference signatures.In order to be contiguous, the space of signatures must be ordered. A signature can be represented in the vector or power forms. We will use the power exponent as the criterion for ordering the signature set. The distance between two vectors (signatures) will be evaluated as the arithmetic difference between the corresponding exponents. For example, the distance between the signatures 010 and 101 will be 5, because the exponents of powersα6 and α differ by 5. We can interpret these exponents as output responses of a mixed-signal CUT, since they possess arithmetic properties. At the same time, the corresponding vectors (signatures) possess algebraic properties. Therefore, arithmetic data is mapped into algebraic data. Figure 7 represents the circuit which performs the mapping and computes an algebraic signature.Figure 7
A symbolic form of an algebraic SA for a mixed-signal CUT.The circuit of Figure7 can be obtained from the circuit of Figure 3 by the following transform:
(11)αjαi=(αjα)αi-1=(αjα)(1+αk)︷αi-1=αjα+αj+1+k=αjα+αl.Since the finite fieldGF(2n) is closed and errors are independent, this mapping will not change the probability of undetected error.The logic level implementation of the circuit of Figure7 is more complex compared to the circuit of Figure 3, but it is less complex than that of the circuit of Figure 5.Prior to designing the circuit, we have to make a few observations.Thefirst observation is that
(12)αjαi=⋯αjαjααjααj⋯α︸i.Let us denote an output response from a mixed-signal CUT byi. Thesecond observation is that the response i can be considered as an exponent of the power, that is, αi. Essentially, this means that the arithmetic values i are mapped into algebraic values αi.Based on these observations, we can design a signature analyzer in the way shown in Figure8. Here α is a primitive element of a finite field GF(2n); n coincides with the bit-length of the output responses. The lower and upper inputs of the multiplexer in Figure 8 are connected together, since α2n-1=α0 in GF(2n).Figure 8
A more detailed symbolic form of the SA.Considering the case when the analyzer is fed by 3-bit data, its more detailed implementation will have the form of Figure9.Figure 9
A register transfer level implementation of the SA.Here the buses consist of 3 lines, as indicated by the appropriate number. The initial content of the SA before the shift isαj, or a2x2+a1x+a0 in the polynomial form (we have omitted the superscripts for the sake of simplicity). The notations ak and ak+, where index k can be one of 0, 1, and 2, indicate the present and next states, respectively.A multiplier byα in GF(23) is realized bearing in mind that g(x)=x3+x+1, α corresponds to x, and
(13)(a2x2+a1x+a0)xmod⁡g(x)=(a2x3+a1x2+a0x)mod⁡g(x)=a2(x+1)+a1x2+a0x=a1x2+(a2+a0)x+a2.This operation is shown by crosslines in Figure9. The multiplexer inputs “0” and “7” are tied together, because α7=α0 in the field GF(23).In order to demonstrate how to use this analyzer, we will assume that it receives only two values from a CUT, in particularj and i. Since the CUT is of a mixed-signal nature, there is an unavoidable (and thereby permitted) deviation of these values by ±1 (the greater tolerances can also be considered). The analyzer will map the received data into αj±1 and αi±1, respectively. If we assume that the initial content of the SA is 001 (versus 000 for a conventional SA), then after the first shift the content becomes α0αj±1=αj±1. After the second shift, it changes to αj±1αi±1=αj+i±2. This expression is derived using the interval arithmetic rules. It states that for the fault-free CUT the actual result must match one of the values from the interval [αj+i-2,αj+i+2], that is, one of the following:
(14)αj+i-2,αj+i-1,αj+i,αj+i+1,αj+i+2.To further simplify the SA operation, we will assume that instead ofα0 (i.e., 001) the initial SA content is α-(j+i). We will refer to this value as theseed value. Then, by the same reasoning, the SA content after two shifts will match one of the following powers:
(15)α-2,α-1,α0,α1,α2.Due to the closure property of the fieldGF(23), this power set is equivalent to
(16)α5,α6,α0,α1,α2.Consequently, the decision making circuit in Figure3 will work as follows. If the actual signature does not match any value from set (16), the CUT is considered to be faulty. Since these values are ordered (and surround the power α0), the decision making circuit can employ a comparator, thereby reducing the hardware complexity of the SA.As in any signature analyzer, some errors in the CUT output responses may escape detection. The aliasing rate can be estimated as described in [16] and will coincide with the aliasing rate of the conventional analyzer.Example. Let us consider a 3-bit CUT, which is fed by two input stimuli. Under the fault-free operation, the CUT produces the output responses j=101±1 and i=110±1. Therefore, the seed value will be α-(j+i)=α-(5+6)=α-11=α3, or 011 in the vector form. If the CUT is fault-free, then after 2 shifts the SA content must match one of the elements in set (16). For example, if the actual responses are 101+1=110 (or α6) and 110+1=111 (or α7) (i.e., the variations are within the tolerance bounds), the signature will be α3α6α7=α2 which belongs to set (16). And the decision making circuit will generate apass signal. The validity of such a decision is determined by the aliasing rate.Let us assume that a fault in the CUT has made the following changes in the output responses:110→011 (α6→α3) and 111→100 (α7→α4). Then the actual signature will become α3α3α4=α3. This element does not belong to set (16), so the fault is detected.There are two distinct ways of designing the decision making circuit depending on the optimization criteria (time or hardware overhead).Hardware Overhead. If performance is paramount and time overhead is not desirable, the following approach can be employed. Let m be the number of output responses. All of the 2m+1  α-multiplier outputs (see Figure 8) that belong to set (16) are connected to the first inputs of the 2m+1 comparators of a similar type. The second inputs of these comparators are shared and fed by the vector 0⋯01. If the CUT is fault-free, one of the comparators will produce a logic “1” signal. The logic OR of the comparator outputs will constitute apass/fail signal.The above procedure is based on the fact that the fault-free CUT produces one of the signatures from set (16). If the actual signature is α0, the comparator connected directly to the signature register produces a logic “1,” thus indicating that the CUT is fault-free. If the actual signature is α6, then the product α6α, generated at the output of the first α-multiplier, equals 1, which is detected by the next comparator. The same reasoning applies to the rest of the signatures from set (16). The logic diagram of the n-bit comparator is shown in Figure 10.Figure 10
Ann-bit comparator.Time Overhead. If time overhead is allowed, the hardware complexity can be further reduced. In terms of implementation, it is more convenient to use the following seed value: α-(j+i+m+1), where m is the number of output responses. For the above example, α-(11+3)=α0, and set (16) will transform to
(17)α2,α3,α4,α5,α6.After the last output response has been shifted in, the SA continues to shift its content2m+1 more times, while the input i is forced to 1. This ensures that the SA content is multiplied by α with each shift. For the above example, 2m+1=5. If, within this time, the match with an element of set (17) has been determined, the CUT is considered to be fault-free. Otherwise, it is faulty.If the CUT is fault-free and its output responses have not exceeded their tolerances, then while cycling through the states during the extra2m+1 shifts, the output of the multiplexer in Figure 8 will go through the power α0 or vector 0⋯01. The match with the vector 0⋯01 is detected by the comparator of Figure 10 connected to the multiplexor’s output. The comparator output is actually producing apass/fail signal.The implementation complexity of the circuit of Figure8 increases significantly with the growth of the data width, n. Therefore, this circuit can only be implemented for the output responses with relatively low values of n. For greater values of n, we will modify the circuit of Figure 8 to the one shown in Figure 11. The modified circuit contains binary-weighted stages and is more economical in terms of hardware. The complexity of the multiplier ×αi is comparable with that of the multiplier ×α, whereas the number of multipliers drops from 2n to n. The economy increases with the growth of n.Figure 11
A binary-weighted version of the SA.For the case of 3-bit data, the circuit of Figure11 transfers to the one shown in Figure 12. This circuit operates much in the same way. The αi-multipliers structure is determined from the following expressions:
(18)x(a2x2+a1x+a0)mod⁡g(x)=a1x2+(a2+a0)x+a2,x2(a2x2+a1x+a0)mod⁡g(x)=(a2+a0)x2+(a2+a1)x+a1,x4(a2x2+a1x+a0)mod⁡g(x)=a2+a1+a0x2+a1+a0x+a2+a1.Figure 12
A register transfer level implementation of the 3-bit SA.


## 4. Experimental Results

The experimental setup to test the proposed method of signature analysis is shown in Figure13. The setup includes the microcontroller system board Adapt9S12D (Technological Arts Inc.) based on Freescale’s 9S12DG128 microcontroller and the Altera DE2 Development board based on the Cyclone II EP2C35F672C6 field-programmable gate-array (FPGA) device. We have selected 16 input test stimuli (voltages Vin) equally distributed over the range (0~5.12)V and applied them to the analog-to-digital converter (ADC) of the 9S12 microcontroller (which served as a mixed-signal system). Each input voltage, Vin, was measured by a high-precision voltmeter and regarded as a nominal test input value.Figure 13
The experimental setup.The circuit in Figure13 operates as follows. Every time the switch Sω is closed, the system performs 8 measurements of the same test signal and averages the result by accumulating the sum of the eight 8-bit measurements and shifting it right three times, which eliminates noise. The ADC transfer characteristic is presented in Figure 14 [17]. According to this characteristic, each conversion result for a properly operating device can deviate from the nominal value by ±1, which is an implication of the fact that the permissible differential nonlinearity can range from -0.5 to +0.5 LSB (see shadowed boxes in Figure 14). For example, if Vin=40 mV, the conversion result can be $01, $02, or $03 (in the worst case, the points a and b coincide). Therefore, each of the thirty-two 8-bit average results contains an error of at most ±1 count. The test stimuli have been selected equal to the midpoints of the quantization bins, thereby increasing the uncertainty and worsening the probability of undetected error. If the test stimuli would have been selected at the transition points of the characteristic, the probability of undetected error (aliasing rate) would improve. This follows from the observation that each conversion would result in 2 possible values as opposed to 3 possible values in the previous case.Figure 14
9S12 ADC transfer function.As soon as average values of the conversion results are computed by the microcontroller, they are transferred to the DE2 board. The transfer of each datum is accompanied by a high-to-low transition of the strobe signalStr. The Str signal serves as aclock for the state machine that implements the signature analyzer (in its 8-bit configuration). The signature, D, is displayed on a two-digit 7-segment display in hexadecimal form.The first experiment was performed on the properly operating device. In the second experiment, the average results were corrupted digitally in the microcontroller (thereby simulating random faults in the ADC) and sent to the analyzer. The analyzer has correctly identified the faulty device.The relationship between input voltages and output codes is presented in Table2. Based on this table and taking into consideration that g(x)=x8+x4+x3+x2+1, the seed value is calculated as follows:
(19)4+20+⋯+244=1984=199mod⁡(28-1)=199,α-199=α56=01011101,SeedValue=α56α-16=α40=01101010=106.Table 2
Relationship between input test stimuli and output responses.
Input voltage
Output code
mV
Min
Nom.
Max
No fault
Fault
80
3
4
5
3
3
400
19
20
21
21
21
720
35
36
37
37
37
1040
51
52
53
53
53
1360
67
68
69
68
70
1680
83
84
85
85
85
2000
99
100
101
99
99
2320
115
116
117
117
117
2640
131
132
133
133
133
2960
147
148
149
148
150
3280
163
164
165
165
165
3600
179
180
181
179
179
3920
195
196
197
197
197
4240
211
212
213
212
240
4560
227
228
229
229
230
4880
243
244
245
244
244In addition to test experiments, the operation of the analyzer (the DE2 part of the test setup) was simulated using Altera Quartus II software. Based on the two experiments represented in Table2, the signatures that correspond to fault-free and faulty ADCs are, respectively, 233 and 201 (in decimal form). The process of calculation of these signatures is demonstrated in Figures 15 and 16. Figures 17 and 18 represent the fault detection process. The actual final signatures are shifted additionally 32 times. If the value 1 appears in the analyzer during these shifts, the system is fault-free. Otherwise it is faulty.Figure 15
All output code deviations are within the tolerance bounds.Figure 16
Some of the output code deviations exceed the tolerance bounds.Figure 17
The combination “1” is detected: ADC is operating properly.Figure 18
The combination “1” is not detected: ADC is faulty.The simulation results matched the experimental results.


## 5. Conclusion

We examined an algebraic signature analysis method that can be employed for mixed-signal circuits testing. We demonstrated how to design the appropriate device. This device does not produce arithmetic carries and is therefore less prone to errors. The absence of carry propagating circuitry also contributes to the higher performance of the device.The proposed scheme can also be used in arithmetic and algebraic error-control coding, as well as cryptography.



---

*Source: 465907-2014-11-16.xml*