On The Computation of LFSR Characteristic Polynomials for Built-In Deterministic Test Pattern Generation
| Autor: | Dimitri Kagaris, Oscar Acevedo |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Computation theory
Polynomial Test-set compression 0211 other engineering and technologies Geometry Linear systems 02 engineering and technology Polynomials Upper and lower bounds Test pattern generator Berlekamp-Massey algorithm Theoretical Computer Science Combinatorics Mathematical model Deterministic test pattern Algorithm design and analysis 0202 electrical engineering electronic engineering information engineering Degree of a polynomial Polynomial degree 021106 design practice & management Mathematics Characteristic polynomial Discrete mathematics Mathematical models Degree (graph theory) Test pattern generators 020202 computer hardware & architecture Computational Theory and Mathematics Hardware and Architecture Data compression Test set Fault coverage Characteristic polynomials Upper bound Software Generator (mathematics) |
| Zdroj: | IEEE Transactions on Computers. 65:664-669 |
| ISSN: | 0018-9340 |
| DOI: | 10.1109/tc.2015.2428697 |
| Popis: | In built-in test pattern generation and test set compression, an LFSR is usually employed as the on-chip generator with an arbitrarily selected characteristic polynomial of degree equal, according to a popular rule, to $S_\mathrm{ max}+20$ , where $S_\mathrm{ max}$ is the maximum number of specified bits in any test cube of the test set. By fixing the polynomial a priori a linear system only needs to be solved to compute the required LFSR initial states (seeds) to generate the target test cubes, but the disadvantage is that the polynomial degree (length of the LFSR and seed bit size) may be too large and the fault coverage cannot be guaranteed. In this paper we address the problem of computing a polynomial of small degree directly from the given test set without having to solve multiple non-linear systems and fixing a priori the polynomial degree. The proposed method uses an adaptation of the Berlekamp-Massey algorithm and the Sidorenko-Bossert theorem to perform the computation. In addition, the method guarantees (by design) that all the test cubes in the given test set are generated, thereby achieving 100% coverage, which cannot be guaranteed under the “trial-and-error” $S_\mathrm{ max}+20$ rule. Experimental results verify the advantages that the proposed methodology offers in terms of reduced polynomial degree and 100% coverage. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|