LFSR generation for high test coverage and low hardware overhead

LFSR generation for high test coverage and low hardware overhead

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Computers & Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.


    1. 1)
      • 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.
    2. 2)
      • 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. 7382.
    3. 3)
      • 3. Wang, L., Wu, C., Wen, X.: ‘VLSI test principles and architectures: design for testability’ (Elsevier, San Francisco, CA, USA, 2006).
    4. 4)
      • 4. Lee, W.F., Glaser, R.: ‘Learning from VLSI design experience’ (Springer, Basel, Switzerland, 2019).
    5. 5)
      • 5. McLaurin, T.: ‘Periodic online LBIST considerations for a multicore processor’. 2018 IEEE Int. Test Conf. Asia (ITC-Asia), Harbin, China, 2018, pp. 3742.
    6. 6)
      • 6. Wang, L.T.: ‘System-on-chip test architectures: nanometer design for testability’ (Morgan Kaufmann Publishers Inc., San Francisco, California, USA, 2008).
    7. 7)
      • 7. Shirvani, P.P., McCluskey, E.J.: ‘Fault-tolerant systems in a space environment: the CRC ARGOS project’, 1998.
    8. 8)
      • 8. Condo, C., Gross, W.J.: ‘Pseudorandom Gaussian distribution through optimised LFSR permutations’, Electron. Lett., 2015, 51, (25), pp. 20982100.
    9. 9)
      • 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. 97102.
    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. 1520.
    11. 11)
      • 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. 885893.
    12. 12)
      • 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. 685695.
    13. 13)
      • 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. 560565.
    14. 14)
      • 14. Koenemann, B.: ‘LFSR-coded test patterns for scan designs’. Proc. Second European Test Conf. ETC91, Munich, Germany, 1991, p. 237.
    15. 15)
      • 15. Berlekamp, E.: ‘Algebraic coding theory’ (World Scientific Publishing Co, River Edge, New Jersey, USA, 2015, Revised edn.).
    16. 16)
      • 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. 664669.
    17. 17)
      • 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.
    18. 18)
      • 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.
    19. 19)
      • 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. 98103.
    20. 20)
      • 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. 18.
    21. 21)
      • 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. 16.
    22. 22)
      • 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. 28.
    23. 23)
      • 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. 233238.
    24. 24)
      • 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. 95100.
    25. 25)
      • 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. 15501555.
    26. 26)
      • 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. 392395.
    27. 27)
      • 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. 16.

Related content

This is a required field
Please enter a valid email address