Bit Swapping LFSR and its Application to Fault Detection and Diagnosis Using FPGA

Bit Swapping LFSR and its Application to Fault Detection and Diagnosis Using FPGA

M.V.M.Lahari 1, M.Mani Kumari 2

1,2 Department of ECE, GVPCEOW,Visakhapatnam.

Abstract The increasing growth of sub-micron technology has resulted in the difficulty of VLSI testing. Test and design for testability are recognized today as critical to a successful design. Field Programmable Gate Arrays (FPGAs) have been used in many areas of digital design. Because FPGAs are reprogrammable, faults can be easily tolerated once fault sites are located. In this paper, we discuss about fault detection and fault diagnosis techniques using Built-in self test (BIST) and test pattern generators. The most of the discussion will be made using the test pattern generators. In order to generate testing pattern we aid Bit Swapping Linear Feedback Shift Register (BS-LFSR) and Low Transition- Random Test Pattern Generator (LT-RTPG). Fault detection and location will be carried out using pattern generators. VHDL is used as HDL language.

Keywords:- FPGA, BIST, BS-LFSR, LT-RTPG, VHDL.

1. INTRODUCTION

   In the digital system design implementation there may be a possibility of fault occurrence, to detect and minimize these faults in a design we use the fault detection and diagnosis techniques. We considered the FPGA digital system design to detect and reduce the faults. We can even correct these faults in a digital system design.

   Field Programmable Gate Arrays (FPGAs) have been used in many areas of digital design.

   FPGAs are Field programmable gate arrays that are regularly constructed with configurable logic blocks (CLBs) and input/output blocks (IOBs) communicated with interconnects and switches. FPGA can be configured to implement combinational or sequential logic functions. Several FPGA architectures have been developed for different applications. The most widely used type is the look up table (LUT) FPGA, in which the functional unit consists of several LUTs. This type of FPGA can be reprogrammed any number of times.

   Figure1: Generic FPGA architecture

   In the previous paper [1] they presented a methodology for the diagnosis of faulty CLBs in FPGA in which they used LFSR for test pattern generation and a comparator based Output Response Analyzer (ORA) for the Built in Self Test (BIST) Architecture. In this method all the testing is done within the FPGA which prevents the use of external hardware. The complexity of the fault detection using test pattern generators will increase in the worst case, and this problem will be studied in this project.

   The increasing growth of sub-micron technology has resulted in the difficulty of VLSI testing. Test and design for testability are recognized today as critical to a successful design.

   In order to reduce the difficulty in the complexity of test generation, one needs to model the actual defects that may occur in a chip with fault models at higher levels of abstraction. This process of fault modeling considerably reduces the burden of testing. This is due to the fact that many physical defects map to a single fault at the higher level. Faults may change the logic values at some internal lines in the integrated circuit, or they may result in a change in the voltage or current levels. They may also change the temporal behavior of the circuit. For this we detect and diagnose the faults in the design.

2. PREVIOUS WORKS

   In order to diagnose faults, there must first be a way to test modules in FPGAs. A candidate for this purpose is the built-in self-test (BIST). This structure reconfigures part of the functional circuit to be a test pattern generator (TPG), and some other to be an output response analyzer (ORA). The rest circuit consists of the circuit under test (CUT). The TPG is either a linear feedback shift register (LFSR) that generates pseudorandom test sequences, or simply a counter that provides an exhaustive test set.

   Figure 2: Connections between testing module and set of CLBs under test

3. BIT SWAPPING LFSR

   In recent years, the design for low power has become one of the greatest challenges in high performance very large scale integration (VLSI) design. As a consequence, many techniques have been introduced to minimize the power consumption of new VLSI systems. However, most of these methods focus on the power consumption during normal mode operation, while test mode operation has not normally been a predominant concern. However, it has been found that the power consumed during test mode operation is often much higher than during normal mode operation. This is because most of the consumed power results from the switching activity in the nodes of the circuit under test (CUT), which is much higher during test mode than during normal mode operation. Several techniques that have been developed to reduce the peak and average power dissipated during scan- based tests.[2] A direct technique to reduce power consumption is by running the test at a slower frequency than that in normal mode. This technique of reducing power consumption, while easy to implement, significantly increases the test

   The test inputs are fed to the CUT, while the output responses are collected and analyzed by the ORA. The ORA can be either a signature analyzer or a comparator-based analyzer. An FPGA is divided into disjoint sets of CLBs, where each set can be configured into a TPG and ORA as shown in figure 2. Such a set acts as a module in the PMC model since it is able to test another module and determine whether the CUT passes or fails the given test. All the CLBs under test are programmed in the same way; therefore, they perform the same logic function and could be given the same test patterns. Thus outputs of the TPG are fed to all CLBs in the set under test, and the results are analyzed by the ORA. Since each CLB can be programmed in many ways, it is not possible to test any CLB in a single test run. As a result, a complete test of all faults in a CLB usually requires several steps, and in each step a CLB is programmed in a particular way.

   application time. Furthermore, it fails in reducing peak-power consumption since it is independent of clock frequency. Another category of techniques used to reduce the power consumption in scan- based built-in self tests (BISTs) is by using scan chain- ordering techniques. These techniques aim to reduce the average-power consumption when scanning in test vectors and scanning out captured responses. Although these algorithms aim to reduce average-power consumption, they can reduce the peak power that may occur in the CUT during the scanning cycles, but not the capture power that may result during the test cycle (i.e., between launch and capture).The design of low transition test- pattern generators (TPGs) is one of the most common and efficient techniques for low-power tests. This project presents a new TPG, called the bit swapping linear feedback shift register (BS- LFSR), that is based on a simple bit swapping technique applied to the output sequence of a conventional LFSR and designed using a conventional LFSR and a 2×1 multiplexer. The introduced BS-LFSR reduces the average and instantaneous weighted switching activity (WSA) during test operation by reducing the number of transitions in the scan input of the CUT. The introduced BS-LFSR for test-per-scan BISTs is based upon some new observations concerning the

   number of transitions produced at the output of an LFSR.

   transitions in the primary inputs of the reduced by 25%.[3]

   Vol. 2 Issue 9, September – 2013

   CUT will be

   Figure 3: Swapping arrangement for an LFSR

   p>Figure 4: Bit swapping LFSR

   Important Properties of the BS-LFSR:

   There are some important features of the BSLFSR that make it equivalent to a conventional LFSR.

   The most important properties of the BS-LFSR are the following.

   1. The BS-LFSR generates the same number of 1s and 0s at the output of multiplexers after swapping of two adjacent cells; hence, the probabilities of having a 0 or 1 at a certain cell of the scan chain before applying the test vectors are equal. Hence, the proposed design retains an important feature of any random TPG. Furthermore, the output of the multiplexer depends on three different cells of the LFSR, each of which contains a pseudorandom value. Hence, the expected value at the output can also be considered to be a pseudorandom value.

   2. If the BS-LFSR is used to generate test patterns for either test per- clock BIST or for the primary inputs of a scan-based sequential circuit (assuming that they are directly accessible) as shown in Fig. 3, then consider the case that c1 will be swapped with c2 and c3 with c4, . . . , cn-2 with cn-1 according to the value of cn which is connected to the selection line of the multiplexers (see Figure. 4). In this case, we have the same exhaustive set of test vectors as would be generated by the conventional LFSR, but their order will be different and the overall

4. LOW TRANSITION RANDOM TEST PATTERN GENERATOR (LT-RTPG)

   This is a low hardware overhead test pattern generator (TPG) for scan-based BIST that can reduce switching activity in CUTs during BIST and also achieve very high fault coverage with a reasonable length of test sequence.[5] Since the correlation between consecutive vectors applied to a circuit during BIST is significantly lower, switching activity in the circuit can be significantly higher during BIST than that during its normal operation. Excessive switching activity during test application can damage CUTs during BIST. The LT-RTPG (Figure 5) reduces switching activity during BIST by reducing transitions at scan inputs.

   Figure 5: Architecture of LT-RTPG

   During scan shift operations. The LT- RTPG is comprised of an r-stage LFSR, a K-input AND gate, and a toggle flip-flop (T flip- flop). Hence, it can be implemented with very little hardware.[3] Each of K inputs of the AND gate is connected to either a normal or an inverting output of the r LFSR stages. If large k is used, large sets of neighboring state inputs will be assigned identical values in most test patterns, resulting in the decrease fault coverage or the increase in Test sequence length. LT-RTPGs with K=2 or 3 are used. Since a T flip-flop holds previous values until the input of the T flip-flop is assigned a 1, the same value v, where v {0,1} is repeatedly scanned into the scan chain until the value at the output of the AND gate becomes 1.[7]

   Hence, adjacent scan flip-flops are assigned identical Values in most test patterns and scan inputs have fewer transitions during scan shift operations. Since most switching activity during scan BIST occurs during scan shift operations, thus the LT-RTPG can reduce Heat dissipation during overall scan testing. It has been observed that many faults that escape random patterns are highly correlated with each other and can be detected by continuously complementing values of a few inputs from apparent test vectors.[4]

   This implies that RPRFs that escape LT-

   Where fi

   are the output values of thVol. 2 Issue 9, September – 2013

   e minterms

   e minterms

   RTPG test sequences can be effectively detected by fixing selected inputs to binary values specified in deterministic test cubes for these RPRFs and applying random patterns to the rest of inputs. The LT-RTPG can attain high fault coverage without excessive switching activity or large area overhead even for circuits that have large numbers of RPRFs.

5. REED – MULLER EXPANSION TECHNIQUE

   This technique can be used to realize any arbitrary n-variable Boolean function using AND and EX- OR gates only.[6]

   Properties:

   1. If the primary input leads are fault-free then at most (n+4) tests are required to detect all single stuck-at faults in the circuit.

   2. If there are faults on the primary input leads as well, then the number of tests required is (n+4)+2ne, where ne is the number of input variables that appear an even number of times in the product terms of the Reed-Muller expansion.

      Any combinational function of n-variables can be described by a Reed-Muller expansion of the form. f(x1,x2,xn) = C0 C1 1 C2 2 .. Cn n

      C C .. C n ..

      obtained from the truth table;

      Considered Boolean function

      f (W, X ,Y) = WX + Y +

      The Reed Muller expansion of the function is f (W, X ,Y) = 1 X W X W Y X Y

      Figure 6: Reed-Muller circuit for f=WX+WY+XY

6. SIMULATION RESULTS

   The following results are obtained using XILINX tool. Initially we designed front end model. For testing purpose we generated TPG using LT-RTPG and BS-LFSR. The test pattern results are shown in below figure 7 and 8. The outputs of BS-LFSR are fed to the Reed-Muller circuit for testing the faults through FPGA vertex-5. BS-LFSR and LT-RTPG

   n+1 1 2

   n+2

   1 3

   2 -1 1 2 n

   used here is of external type. By using this test

   where i is either xi or i but not both together, Ci is a binary constant 0 or 1 and is the modulo sum (exclusive- OR operation).

   For a three variable function, the Reed Muller expansion is

   f (W,X,Y) = C0 C1 W C2 X C3 Y C4 W

   X C5 W Y C6 X Y C7 W X Y

   The constants Ci for a three-variable Reed-Muller expansion may be computed using the following rules:

   C0 = f0

   C1 = f0 f4 C2 = f0 f2 C3 = f0 f1

   C4 = f0 f2 f4 f6 C5 = f0 f1 f4 f5 C6 = f0 f1 f2 f3

   C7 = f0 f1 f2 f3 f4 f5 f6 f7

   pattern we have tested the faults and the number of transitions and the switching activity in CUT are reduced.

   Figure 7: BS-LFSR Simulation Result

   Figure 8: LT-RTPG Simulation Result

7. CONCLUSION

REFERENCES

Vol. 2 Issue 9, September – 2013

In this paper we present a methodology for the diagnosis of faults through FPGA vertex-5. For generation of test pattern BS-LFSR and LT-RTPG are used. The main advantage of this method is testing time of the CUT (Reed-Muller circuit) mainly depends on number of faults rather than the chip size. Hence it yields more advantages while diagnosing the larger chips. Also the resolution of the fault diagnosis algorithm in interconnect testing is greatly dependent on the structure of the original application configuration. The complexity of the fault detection using test pattern generators will increase in the worst case, and this problem will be rectified using the weighted random test pattern generator (WR-TPG). It has been observed that many faults that escape random patterns are highly correlated with each other and can be detected by continuously complementing values of a few inputs from apparent test vectors. This implies that RPRFs that escape LT-RTPG test sequences can be effectively detected by fixing selected inputs to binary values specified in deterministic test cubes for these RPRFs and applying random patterns to the rest of inputs. This technique is used in the 3- weight WRBIST to achieve high fault coverage for random pattern resistant circuits. The LT-RTPG can attain high fault coverage without excessive switching activity or large area overhead even for circuits that have large numbers of RPRFs. All of the techniques described in this paper are based on the stuck-at fault model, which is most widely used fault model. Several approaches have been proposed for stuck-at fault model tests, fewer techniques of testing have been proposed despite its importance in todays system. Thus, further techniques and methodologies o address this problem should be considered in future research. Instant of LFSR we can use dual speed LFSR in future. It will generate pseudo random test patterns. It runs faster as compared to LFSR.

1. Fazal Noorbasha, K. Harikishore, Ch. Hemanth, A. Sivasairam, V. Vijaya Raju, (2012) LFSR Test Pattern For Fault Detection And Diagnosis For FPGA CLB Cells, IJAET, vol. 3, issue 1, pp. 240-246.

2. Atluri Jhansi rani, K.Harikishore, Fazal Noor Basha, J.Poornima, M.Jyothil, M.Sahithi, P.Srinivas, Fault Tolerance in bit swapping LFSR using FPGA Architecture, IJERA, Vol. 2, Issue 1,Jan-Feb 2012, pp.1080-1087.

3. C.Ravishankar Reddy, Shaik Zilani, V.Sumalatha, Low Power, Low-Transition Random Pattern Generator, IJERT, vol. 1, issue 5, July 2012, pp. 1-6.

4. Ramesh K S, Venkataramanan V, Switching Activity Reduction Using Scan Shift Operation, Journal of Computer Applications, vol. 5, Issue EICA2012-4, Feb 2012, pp. 409- 419.

5. Secongman Wang Faults diagnosis for using TPG low power dissipation and high fault coverage .IEEE Tranc. Vol.15 no.7, 2010.

6. Parag K.Lala Fault tolerant and fault testable hardware design Prentice-Hall, Inc. Upper Saddle River, NJ, USA 1985 ISBN:0-13- 308248-2.

7. S.Wang and S.K.Gupta, LT-RTPG: A New Test-Per-Scan BIST TPG for Low Switching Activity IEEE Trans. Computer-Aided Design In-tegr. Circuits Syst., Vol.25, no.8, pp. 1565-1574, 2006.