On the computation of LFSR characteristic polynomials for built-in deterministic test pattern generation
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 Smax+20, where Smax is the maximum number of specified bits in any test cube of t...
- Autores:
- Tipo de recurso:
- Fecha de publicación:
- 2016
- Institución:
- Universidad Tecnológica de Bolívar
- Repositorio:
- Repositorio Institucional UTB
- Idioma:
- eng
- OAI Identifier:
- oai:repositorio.utb.edu.co:20.500.12585/8992
- Acceso en línea:
- https://hdl.handle.net/20.500.12585/8992
- Palabra clave:
- Algorithm design and analysis
Linear systems
Mathematical model
Polynomials
Test pattern generators
Upper bound
Computation theory
Data compression
Geometry
Linear systems
Mathematical models
Algorithm design and analysis
Berlekamp-Massey algorithm
Characteristic polynomials
Deterministic test pattern
Polynomial degree
Test pattern generator
Test-set compression
Upper bound
Polynomials
- Rights
- restrictedAccess
- License
- http://creativecommons.org/licenses/by-nc-nd/4.0/
| Summary: | 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 Smax+20, where Smax 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' Smax+20 rule. Experimental results verify the advantages that the proposed methodology offers in terms of reduced polynomial degree and 100% coverage. © 1968-2012 IEEE. |
|---|