Gauss-elimination-based generation of multiple seed-polynomial pairs for LFSR

Li Ren Huang, Jing Yang Jou, Sy Yen Kuo

Research output: Contribution to journalArticlepeer-review

33 Scopus citations


This paper presents a new and efficient strategy of pseudorandom pattern generation (PRPG) for IC testing. It uses a general programmable LFSR (P-LFSR) to offer multiple-seed and multiple-polynomial PRPG. The deterministic pattern set generated by an ATPG tool or supplied by the designers is used to guide the generation of pseudorandom patterns. A novel application of the Gauss-elimination procedure is proposed to find the seeds as well as the polynomials. With an intelligent heuristic to further utilize the essential faults, this approach becomes very efficient, even for the random pattern resistant (RPR) circuits. Experiments are conducted on the ISCAS-85 benchmarks and the full scan version of the ISCAS-89 benchmarks. For all benchmark circuits, complete fault coverage is achieved with good balance on the hardware overhead and the test lengths as compared to other schemes.

Original languageEnglish
Pages (from-to)1015-1024
Number of pages10
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number9
StatePublished - 1997


  • BIST
  • LFSR
  • Mixed-mode testing
  • Pseudorandom pattern generation (prpg)


Dive into the research topics of 'Gauss-elimination-based generation of multiple seed-polynomial pairs for LFSR'. Together they form a unique fingerprint.

Cite this