Call for Paper

CAE solicits original research papers for the December 2021 Edition. Last date of manuscript submission is November 30, 2021.

Read More

New Test Pattern Generators for the BIST Pseudo-Exhaustive Testing based on Coding Theory Principles

Mohamed H. El-Mahlawy, Winston Waller. Published in Software Engineering.

Communications on Applied Electronics
Year of Publication: 2016
Publisher: Foundation of Computer Science (FCS), NY, USA
Authors: Mohamed H. El-Mahlawy, Winston Waller
10.5120/cae2016652148

Mohamed H El-Mahlawy and Winston Waller. Article: New Test Pattern Generators for the BIST Pseudo-Exhaustive Testing based on Coding Theory Principles. Communications on Applied Electronics 4(8):30-45, April 2016. Published by Foundation of Computer Science (FCS), NY, USA. BibTeX

@article{key:article,
	author = {Mohamed H. El-Mahlawy and Winston Waller},
	title = {Article: New Test Pattern Generators for the BIST Pseudo-Exhaustive Testing based on Coding Theory Principles},
	journal = {Communications on Applied Electronics},
	year = {2016},
	volume = {4},
	number = {8},
	pages = {30-45},
	month = {April},
	note = {Published by Foundation of Computer Science (FCS), NY, USA}
}

Abstract

In this paper, an efficient algorithm to design convolved LFSR/SR (Linear Feedback Shift Register / Shift Register) for the pseudo-exhaustive testing (PET) is presented as far as the lengths of the test set and hardware overhead are concerning. In this algorithm, an efficient search to reduce the constraint in the size of the shift register (SR) segment and makes an efficient search to restrict on the number of feed forward stages into two stages at most and no restriction on the size of the SR segment. The residues are assigned such that minimum hardware overhead is achieved. This search generates several possible solutions for each case, from which the minimal hardware solutions may be chosen. In addition, a new test pattern generator (TPG) for the PET that bridges the gap between convolved LFSR/SR and permuted LFSR/SR is presented. It is considered to be the optimal pseudo-exhaustive test pattern generator (PETPG) as far as the lengths of the test set and hardware overhead are concerning. An efficient residue assignment for the inputs of the CUT to reduce the hardware overhead is presented. With small number of permutations in the assigned residues, the chance of obtaining efficient solutions may be increased. The presented generator in this paper is considered the general form of the PETPG. The simple LFSR/SR, the permuted LFSR/SR, and convolved LFSR/SR are considered the special case. The experimental results for all combinational benchmark circuits [1] indicate the superiority of the presented approach with respect to previous published works.

References

  1. F. Brglez and H. Fujiwara. 1985. A neutral netlist on ten combinational benchmark circuits and a target translator in FORTRAN. In Proceedings of the International Symposium on circuits and systems (June, 1985).
  2. Mohamed H. El-Mahlawy. 1995. Automatic Measurement of Digital Circuits. M.Sc. Thesis. Military Technical College, Egypt.
  3. M. El Said Gohniemy, S. Fadel Bahgat, Mohamed H. El-Mahlawy, and E. E. M. Zouelfoukkar. 1996. A Novel Microcomputer Based Digital Automatic Testing Equipment using Signature Analysis. In Proceedings of the IEEE conference on Industrial Applications in Power Systems Computer Science and Telecommunications (13-16 May 1996), 140-144.
  4. M. H. El-Mahlawy. 2000. Pseudo-Exhaustive Built-In Self-Test for Boundary Scan. Ph.D. Thesis. Kent University, U.K.
  5. Paul H. Bardell, Willian H. McAnney, Jacob Savir. 1987. Built-In test for VLSI: pseudorandom techniques. John Wiley and Sons.
  6. S. W. Golomb. 1982. Shift Register Sequences. Laguna Hills CA: Aegean Park Press.
  7. Mohamed H. El-Mahlawy. 2015. Signature Multi-Mode Hardware-Based Self-Test Architecture for Digital Integrated Circuits. In Proceedings of the IEEE International Conference on Electronics, Circuits, & Systems (6-9 Dec. 2015), 437-441.
  8. Sherif I. Morsy, Mohamed H. El-Mahlawy, Gouda I. Mohamed. 2013. Hybrid based Self-Test Solution for Embedded System on Chip. International Journal of Computer Applications, Vol. 84, No. 12, (Dec. 2013), 7- 14.
  9. Mohamed H. El-Mahlawy and A. Seddik. 2007. Design and Implementation of New Automatic Testing System for Digital Circuits Based on the Signature Analysis. In Proceedings of the 12th International Conference on Aerospace Sciences & Aviation Technology (ASAT-12) (May 2007), CRS-9-1 - CRS-9-12, Egypt.
  10. Mohamed H. El-Mahlawy, A. Abd El-Wahab, and A.S. Ragab. 2008. FPGA Implementation of The Portable Automatic Testing System for Digital Circuits. In Proceedings of the 6th International Conference of the Electrical Engineering (ICEENG-6) (May 2008), EE126-1 - EE126-24, Egypt.
  11. Parag K. Lala. 1997. Digital circuit testing and testability. Academic Press.
  12. Angela Krstic, and Kwang-Ting (Tim) Cheng. 1998. Delay Fault Testing for VLSI Circuits. Kluwer Academic Publishers.
  13. Mukund Sivaraman, and Andrzej J. Strojwas. 1998. A unified Approach for Timing Verification and delay Fault Testing. Kluwer Academic Publishers.
  14. Alexander Miczo. 2003. Digital Logic Testing and Simulation. John Wiley & Sons.
  15. Mohamed H. El-Mahlawy, and Winston Waller. 2000. An efficient algorithm to design convolved LFSR/SR. In Proceedings of the 17th National Radio Science Conference (22-24 Feb. 2000), C23 (1-10), Egypt.
  16. Mohamed H. El-Mahlawy, and Winston Waller. 2000. An efficient algorithm to partition the combinational circuits for pseudoexhaustive testing. In Proceedings of the 17th National Radio Science Conference, (22-24 Feb. 2000), C24 (1-11), Egypt.
  17. E. J. McCluskey and S. Bozorgui-Nesbat. 1981. Design for autonomous test. IEEE transaction on computers Vol. C-30, No. 11, (Nov. 1981), 866-875.
  18. E. J. McCluskey. 1984. Verification testing-A pseudoexhaustive test technique. IEEE transaction on computers Vol. C-33, No. 6 (June 1984), 541-546.
  19. Zeev Barzilai, Jacob Savir, George Markowsky, and Merlin G. Smith. 1981. The weighted syndrome sums approach to VLSI testing. IEEE Transactions on Computers, Vol. C-30, No. 12 (Dec. 1981), 996-1000.
  20. D. T. Tang and L. S. Woo. 1983. Exhaustive test pattern generation with constant weight vectors. IEEE transaction on computers, Vol. C-32, No. 12 (Dec. 1983), 1145-1150.
  21. L. -T. Wang and E. J. McCluskey. 1986. Condensed linear feedfack shift register (LFSR) testing - A pseudo-exhaustive test technique. IEEE transaction on computers Vol. C-35, No. 4 (April 1986), 367-370.
  22. L. -T. Wang and E. J. McCluskey. 1988. Circuits for pseudoexhaustive test pattern generation. IEEE transaction on computer-aided design, Vol. 7, No. 10, (Oct. 1988) 1068- 1080.
  23. S. B. Akers. 1985. On the use of linear sums in exhaustive testing. Digest of papers, 15th Annual International on Fault Tolerant Computing Symposium (1985), 148-153.
  24. N. Vasanthavada, P. N. Marinos. 1985. An operationally efficient scheme for exhaustive test-pattern generation using linear codes. In Proceedings of the International Test Conference (Nov. 1985), 476-482.
  25. Zeev Barzilai, Don Coppersmith, and Arnold L. Rosenberg. 1983. Exhaustive generation of bit patterns with applications to VLSI self-testing. IEEE Transactions on Computers, Vol. C-32, NO. 2 (Feb. 1983), 190-194.
  26. Dimitrios Kagaris and Spyros Tragoudas. 1993. Cost-effective LFSR synthesis for optimal pseudoexhaustive BIST test sets. IEEE transactions on very large scale integration systems, Vol. 1, NO. 4 (Dec. 1993), 526-536.
  27. Srinivasan, R., S. K. Gupta, and M. A. Breuer. 1993. Novel test pattern generators for pseudoexhaustive testing. In Proceedings of the International Test Conference (1993), 1041-1050.
  28. Srinivasan, R., S. K. Gupta, and M. A. Breuer. 2000. Novel test pattern generators for pseudoexhaustive testing. IEEE transaction on computers Vol. 49, No. 11 (Nov. 2000), 1228-1239.
  29. Z. Barzilai, D. Coppersmith, and A. Rosenberg. 1983. Exhaustive Bit Pattern Generation in Discontiguous Positions with Applications to VLSI Testing. IEEE Transaction on Computers, Vol. 32, No. 2 (Feb. 1983), 190-194.
  30. Mohamed H. El-Mahlawy, and Winston Waller. 2004. A New Segmentation Approach for Pseudoexhaustive Testing of Combinational Circuits. In Proceeding of the 4th International Conference of the Electrical Engineering (ICEENG-4) (Nov. 2004), 251-265, Egypt.

Keywords

Design for testability of VLSI design, pseudo-exhaustive testing, pseudo-exhaustive test pattern generator, LFSR/SR, permuted LFSR/SR, convolved LFSR/SR.