{'fraction_non_alphanumeric': 0.03343843345502821, 'fraction_numerical': 0.0075506140059741125, 'mean_word_length': 4.580092592592592, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Simulation Experiment on a Built-In Self Test Equipped with Pseudorandom Test Pattern Generator and Multi-Input Shift Register (MISR)

This paper investigates the impact of the changes of the characteristic polynomials and initial loadings, on behaviour of aliasing errors of parallel signature analyzer (Multi-Input Shift Register), used in an LFSR based digital circuit testing technique. The investigation is carried-out through an extensive simulation study of the effectiveness of the LFSR based digital circuit testing technique. The results of the study show that when the identical characteristic polynomials of order n are used in both pseudo-random test-pattern generator, as well as in Multi-Input Shift Register (MISR) signature analyzer (parallel type) then the probability of aliasing errors remains unchanged due to the changes in the initial loadings of the pseudo-random test-pattern generator.


INTRODUCTION
Reliability is one of the main considerations in any circuit design. It involves a correct and predictable behaviour of the circuit according to design specifications over a sufficiently long period of time. To achieve this goal, the logic-circuit design is aimed at an error-free circuit operation. Unfortunately, in spite of all possible care being bestowed on design and simulation, hardware faults resulting from physical defects (e.g. mask defects, manufacturing process flaws) will occur in the hardware implementation of the logic circuit. Hence, when a fault occurs anyway, one must be able to detect the presence of the fault and, if desired to pinpoint its location. This task is accomplished by testing the circuit. System maintenance draws heavily upon the testing capability of the logic system [1], [2]. Digital circuit manufacturers are well aware of the need to incorporate testability features early in the design stage, or otherwise they have to incur higher testing costs, subsequently. An empirical relationship, that have been used for estimating the cost of finding a faulty chip, indicates that the cost increases by a factor of 10, as fault finding advances from one level to the next [3] - [7]. However, recent studies have shown that the cost of testing and fault finding, at system and field level, is higher than this factor of 10 and increases exponentially [7] - [9]. Thus, if a fault can be detected at chip or board level, then significantly larger costs per fault can be avoided. This is the prime reason that attention has now focused on providing testability at chip, module or even at board level.
Any test methodology usually consists of (i) A test strategy for generating the test-stimuli, (ii) A strategy for evaluating output responses, and (iii) Implementation mechanisms to realize the appropriate strategies in test-generation and response evaluation. Present day philosophy to achieve economical and cost effective testing of Very Large Scale Integration (VLSI) components and systems is to provide on-chip testing. Though these techniques involve additional chip area for the added test circuitry, they have provided reasonable testability levels. In fact it has been reported that, for about 20% additional silicon area required, more than 98% of the chip design can be checked using structured Design For Testability (DFT) approaches [7] - [11]. As a natural outcome of the structured design approach for DFT, built-in testing has drawn considerable attention. Usually a built-in test methodology is defined as the one that incorporates both test-pattern generation and response data compression mechanisms internally in the chip itself. If this methodology is self-sufficient in detecting the faults of its internal test circuitry also, then such a methodology is referred to as Built-In Self-Test (BIST) in test literature. The main emphasis in BIST designs is that to provide close to one hundred percent testing of combinational circuits [10], [12]. In particular, pseudo-random test-pattern generation followed by the compression of response data by signature analysis has become a standard form of testing in BIST environment. Linear Feedback Shift Registers (LFSRs) have been proposed as an integral part of a sequential logic design, such that they can be used to both generate and compact the results of a test. Undoubtedly, an LFSR based pseudo-random test-pattern generation is an extremely simple tool for generating desired sequence as well as the length of the test-stimuli. Many estimation schemes are readily available for computing the length of test patterns where the desired sequence of the test-patterns can be obtained by the predetermined seed of the LFSRs. Further, the effective testing of large circuits uses the concept of 'pseudoexhaustive testing' where the principle of divide and conquer is applied [13] - [19]. Difficulty arises when the resulting response data obtained from the Circuit Under Test (CUT) is compressed into small signatures using Signature Analyzer (SAZ). Although, this scheme of SAZ is easily implemented by an LFSR either in the form of Single Input Shift Register (SISR) -serial SAZ or MISR-parallel SAZ . But this leads to loss of information, due to the erroneous response patterns that get compressed into the same signature as the fault-free signature of the CUT. Thus, some of the faults might go undetected due to this masking phenomenon. This compression can further reduce the fault-coverage in the BIST scheme. This problem of error masking is called aliasing [20] - [25]. Methods to determine the extent of fault escape caused by a response compressor are not readily available. However, various attempts have been made to analyze and improve the basic SAZ's realization methods [26] - [33]. The end goal of the above schemes, individually, or with a combination of these, is to reduce the deception volume [26]. Methods that consider both, the test pattern generator and response data compressor factors in totality and simultaneously, in analyzing the aliasing behaviour of the circuit, are not available. There is a growing need for such an approach, which comprehensively looks at aliasing problems with respect to both test pattern generator and response data compressor and reflects the true aliasing characteristics. This is the prime justification of the research work in this area. Therefore, towards this direction a research work have been done [34], [35]. Through these papers, different studies were carried out to investigate the roles of characteristic polynomials used in Pseudo-Random Test-Pattern Generator (PRTPG) as well as in SAZ, and initial loading of PRTPG with the behaviour of aliasing errors of SAZ. The work contained in the papers [34], [35] used separate different structures (internal and external exclusive-OR types) of LFSRs. However, both the papers considered SISR type of SAZ. This paper is an extension of the previous research where MISR type of SAZ is used. In this work external exclusive-OR type and internal exclusive-OR type LFSR is used in PRTPG and MISR respectively. The results of the study show that the probability of aliasing errors remains unchanged due to the change in the initial loading when the id (MIS dentical char SR type).
racteristic po olynomials o of order n are e used in both PRTPG, a as well as in n SAZ

M MATHEM MATICAL C CHARACT TERIZATI ION OF LF FSR
From the structure of the type of the LFSR shown in Figure 2, it can be seen that if the current state of the j th flip-flop is a q-j , for j = 1, 2 , ... , n , then by the recurrence relation e MISR (i.e., the sequence r = r n + r n-1 + ………… + r 2 + r 1 ) can be represented by the state polynomial s(λ) = r n λ n-1 + r n-1 λ n-2 + ………… + r 2 λ+ r 1 (14) Similarly, an n-bit input sequence (d = D n + D n-1 + ………… + D 2 + D 1 ) can be represented by the input polynomial. d(λ) = D n λ n-1 + D n-1 λ n-2 + ………… + D 2 λ+ D 1 (15) The signature obtained by SAZ (any SISR or MISR) is defined as the final state of the register after the input sequence d has been entered into the register. Then the MISR signature can be given as Thus, the theory behind the use of the LFSR for SAZ is based on the concept of polynomial division process, where the remainder left in the register after the last bit of input data is sampled, corresponds to the final signature. Whereas, the output sequence from the n th bit of the LFSR defines the quotient, QO of the division. In general, the shift register is initialized by the reset or by parallel load function of the register, at a time of fault-free evaluation as well as every time when a new fault is injected in the CUT. Assume that the CUT is of combinational nature with n primary inputs and k primary outputs. If the initial state of the LFSR is all 0's, let the final state of the LFSR be represented by the polynomial s(λ). Then it can be shown that these polynomials are related by the equation where, P(λ) is the characteristic polynomial of the LFSR structure used in MISR-SAZ. Hence an LFSR carries out polynomial division on the input data stream by the characteristic polynomial, producing an output stream corresponding to the quotient QO(λ) and remainder s(λ).

SIMULATION STUDY
The testing model employed in the simulation study for PRTPG and MISR is as described in section 2 and shown in Figures 1 and 2. Various combinational circuits have been simulated using the manufacturer's logical diagrams with gate level description. A single stuck-at fault model is assumed. Where, s-a-0 and s-a-1 faults are postulated on each individual, N L , branches of the each CUT. In the case of each n-input CUT, identical all possible characteristic polynomials of order n are individually applied to PRTPG and MISR-SAZ as well. All possible initial loading of PRTPG, 2 n -1, are exhausted to monitor the aliasing error behaviour of MISR-SAZ. These characteristic polynomials are generated using the algorithms developed and reported in papers [2], [40] and [41]. To make it more readable the simulation procedure used to study the aliasing behaviour is described below.

Simulation procedure
Begin (For an n-input CUT) NL = total number of branches in the CUT; NP = total number of possible characteristic polynomial of order n, over GF(2); L i = is the periodicity of i th characteristic polynomial of order n; NS = total number of possible initial loading {NS = 2 n -1, excluding S =[000. The above procedure is used to observe the effect of the characteristic polynomials used in PRTPG as well as in MISR-SAZ along with the initial loading of PRTPG on aliasing counts of MISR-SAZ. The aliasing counts for the circuits of Table 1 were monitored for the sets of all NP and NS of order n. The observed results demonstrates that when the identical characteristic polynomials are used in both the PRTPG and MISR-SAZ, then any change in initial loading of PRTPG does not change the value of aliasing count. Due the complexity of the result sets and space only a candidate of result for circuits summarized in Table 1 are shown in Tables 2 to 4. In Tables 2 -4 the aliasing count is shown. These values of aliasing counts remain unchanged for all the possible changes of initial loading of PRTPG.

CONCLUSIONS
It has been demonstrated through this simulation study that the change of the initial loading of PRTPG does not have any impact on the effectiveness of an LFSR based digital circuit testing technique that uses identical characteristic polynomials in both the PRTPG and MISR-SAZ as well. Thus, this result restricts the outright use of the results of findings; that the effectiveness of LFSR based digital circuit testing techniques can be improved by changing the initial loading of PRTPG. Thus, for effective use of initial loading of PRTPG of LFSR based digital circuit testing technique, it is essential to analyze the role of characteristic polynomials used in PRTPG as well as in MISR-SAZ. Although, our investigation is limited with small sizes of circuits but the trend of results suggests for further through analytical investigation.