access icon free LFSR generation for high test coverage and low hardware overhead

© The Institution of Engineering and Technology
Received 06/02/2019, Accepted 21/08/2019, Revised 10/07/2019, Published 21/08/2019

Safety-critical technology rests on optimised and effective testing techniques for every embedded system involved in the equipment. Pattern generator (PG) such as linear feedback shift register (LFSR) is used for fault detection and useful for reliability and online test. This study presents an analysis of the LFSR, using a known automatic test PG (ATPG) test set. Two techniques are undertaken to target difficult-to-detect faults with their respective trade-off analysis. This is achieved using Berlekamp–Massey (BM) algorithm with optimisations to reduce area overhead. The first technique (concatenated) combines all test sets generating a single polynomial that covers complete ATPG set (baseline-C). Improvements are found in Algorithm 1 reducing polynomial size through Xs assignment. The second technique uses non-concatenated test sets and provides a group of LFSRs using BM without including any optimisation (baseline-N). This algorithm is further optimised by selecting full mapping and independent polynomial expressions. Results are generated using 32 benchmarks and 65 nm technology. The concatenated technique provides reductions on area overhead for 90.6% cases with a best case of 57 and 39% means. The remaining 9.4% of cases, non-concatenated technique provides the best reduction of 37 with 1.4% means, whilst achieving 100% test mapping in both cases.

Inspec keywords: automatic test pattern generation; fault diagnosis; polynomials; integrated circuit testing; logic testing; shift registers

Other keywords: low hardware overhead; fault detection; Berlekamp–Massey algorithm; high test coverage; polynomial size; linear feedback shift register; safety-critical technology; automatic test PG test set; area overhead; complete ATPG set; LFSR generation; concatenated technique; embedded system; size 65.0 nm; test mapping; difficult-to-detect faults; nonconcatenated test sets; pattern generator; nonconcatenated technique; independent polynomial expressions

Subjects: Logic and switching circuits; Logic design methods; Interpolation and function approximation (numerical analysis); Interpolation and function approximation (numerical analysis); Logic circuits; Digital circuit design, modelling and testing

References

    1. 1)
      • 2. Agrawal, V.D., Kime, C.R., Saluja, K.K.: ‘A tutorial on built-in self-test. I. Principles’, IEEE Des. Test Comput., 1993, 10, (1), pp. 73–82.
    2. 2)
      • 19. Jha, S., Chandrasekar, K., Wu, W., et al: ‘A cube-aware compaction method for scan ATPG’. 2014 27th Int. Conf. on VLSI Design and 2014 13th Int. Conf. on Embedded Systems, Mumbai, India, 2014, pp. 98–103.
    3. 3)
      • 6. Wang, L.T.: ‘System-on-chip test architectures: nanometer design for testability’ (Morgan Kaufmann Publishers Inc., San Francisco, California, USA, 2008).
    4. 4)
      • 20. Pomeranz, I.: ‘POSTT: path-oriented static test compaction for transition faults in scan circuits’. 2017 IEEE Int. Test Conf. (ITC), Fort Worth, TX, USA, 2017, pp. 1–8.
    5. 5)
      • 24. Jeswani, J., Rose, J., Schwarz, T.: ‘Using algebraic signatures to compress built-in self-test on a chip’. 2017 2nd Int. Conf. on Communication Systems, Computing and IT Applications (CSCITA), Mumbai, India, 2017, pp. 95–100.
    6. 6)
      • 22. Touba, N.A., McCluskey, E.J.: ‘Test point insertion based on path tracing’. Proc. 14th VLSI Test Symp., Princeton, NJ, USA, USA, 1996, pp. 2–8.
    7. 7)
      • 21. He, M.T., Contreras, G.K., Tehranipoor, M., et al: ‘Test-point insertion efficiency analysis for LBIST applications’. 2016 IEEE 34th VLSI Test Symp. (VTS), Las Vegas, NV, USA, 2016, pp. 1–6.
    8. 8)
      • 14. Koenemann, B.: ‘LFSR-coded test patterns for scan designs’. Proc. Second European Test Conf. ETC91, Munich, Germany, 1991, p. 237.
    9. 9)
      • 25. Anderson, J.H., Hara-Azumi, Y., Yamashita, S.: ‘Effect of LFSR seeding, scrambling and feedback polynomial on stochastic computing accuracy’. 2016 Design, Automation & Test in Europe Conference & Exhibition, Dresden, Germany, 2016, pp. 1550–1555.
    10. 10)
      • 10. Chakraborty, R., Chowdhury, D.R.: ‘A novel seed selection algorithm for test time reduction in BIST’. 2009 Asian Test Symp., Taichung, Taiwan, 2009, pp. 15–20.
    11. 11)
      • 5. McLaurin, T.: ‘Periodic online LBIST considerations for a multicore processor’. 2018 IEEE Int. Test Conf. Asia (ITC-Asia), Harbin, China, 2018, pp. 37–42.
    12. 12)
      • 17. Hellebrand, S., Tarnick, S., Courtois, B., et al: ‘Generation of vector patterns through reseeding of multiple-polynomial linear feedback shift register’, Proc. IEEE Int. Test Conf., Baltimore, Maryland, USA, 1995, p. 120.
    13. 13)
      • 23. Acevedo, O., Kagaris, D.: ‘Using the Berlekamp–Massey algorithm to obtain LFSR characteristic polynomials for TPG’. 2012 IEEE Int. Symp. Defect and Fault Tolerance in VLSI and Nanotechnology Systems DFT 2012, Austin, TX, USA, 3 October 2012–5 October 2012, pp. 233–238.
    14. 14)
      • 12. Yuan, H., Zhou, C., Sun, X., et al: ‘LFSR reseeding-oriented low-power test-compression architecture for scan designs’, J. Electron. Test., 2018, 34, (6), pp. 685–695.
    15. 15)
      • 15. Berlekamp, E.: ‘Algebraic coding theory’ (World Scientific Publishing Co, River Edge, New Jersey, USA, 2015, Revised edn.).
    16. 16)
      • 8. Condo, C., Gross, W.J.: ‘Pseudorandom Gaussian distribution through optimised LFSR permutations’, Electron. Lett., 2015, 51, (25), pp. 2098–2100.
    17. 17)
      • 3. Wang, L., Wu, C., Wen, X.: ‘VLSI test principles and architectures: design for testability’ (Elsevier, San Francisco, CA, USA, 2006).
    18. 18)
      • 27. Sidorenko, V.R., Bossert, M.: ‘Synthesizing all linearized shift-registers of the minimal or required length’. 2010 Int. ITG Conf. Source and Channel Coding (SCC), Siegen, Germany, 2010, pp. 1–6.
    19. 19)
      • 13. Al-Yamani, A.A., McCluskey, E.J.: ‘Seed encoding with LFSRs and cellular automata’. Proc. 2003 Design Automation Conf. (IEEE Cat. no. 03CH37451), Anaheim, CA, USA, 2003, pp. 560–565.
    20. 20)
      • 9. Lien, W.C., Lee, K.J., Hsieh, T.Y., et al: ‘A new LFSR reseeding scheme via internal response feedback’. 2013 22nd Asian Test Symp., Jiaosi Township, Taiwan, 2013, pp. 97–102.
    21. 21)
      • 1. BSI Standards Limited: ‘Road vehicles — functional safety, part 10: guideline on ISO 26262’ (BSI Standards Publication, UK, 2012, BSI Standards Limited edn.) BSI Standards Limited, Ed., BSI Standards Limited.
    22. 22)
      • 7. Shirvani, P.P., McCluskey, E.J.: ‘Fault-tolerant systems in a space environment: the CRC ARGOS project’, 1998.
    23. 23)
      • 4. Lee, W.F., Glaser, R.: ‘Learning from VLSI design experience’ (Springer, Basel, Switzerland, 2019).
    24. 24)
      • 11. Krishna, C.V., Jas, A., Touba, N.A.: ‘Test vector encoding using partial LFSR reseeding’. Proc. Int. Test Conf. 2001 (Cat. no. 01CH37260), Baltimore, MD, USA, 2001, pp. 885–893.
    25. 25)
      • 26. Miyase, K., Kajihara, S., Reddy, S.M.: ‘A method of static test compaction based on don't care identification’. Proc. First IEEE Int. Workshop on Electronic Design, Test and Applications 2002, Christchurch, New Zealand, New Zealand, 2002, pp. 392–395.
    26. 26)
      • 18. Liu, Y., Mukherjee, N., Rajski, J., et al: ‘Deterministic stellar BIST for in-system automotive test’. Int. Test Conf. Int. Symp. Test & Failure Analysis 2018, USA, 2018.
    27. 27)
      • 16. Acevedo, O., Kagaris, D.: ‘On the computation of LFSR characteristic polynomials for built-in deterministic test pattern generation’, IEEE Trans. Comput., 2016, 65, (2), pp. 664–669.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2019.0042
Loading

Related content

content/journals/10.1049/iet-cdt.2019.0042
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading