Abu Khari Bin A’AIN, Ian GROUT, Norlina PARAMAN, Usman Ullah SHEIKH, Arbab ALAMGIR

Horizontal diversity in test generation for high fault coverage

Determination of the most appropriate test set is critical for high fault coverage in testing of digital integratedcircuits. Among black-box approaches, random testing is popular due to its simplicity and cost effectiveness. An extensionto random testing is antirandom that improves fault detection by maximizing the distance of every subsequent test patternfrom the set of previously applied test patterns. Antirandom testing uses total Hamming distance and total cartesiandistance as distance metrics to maximize diversity in the testing sequence. However, the algorithm for the antirandomtest set generation has two major issues. Firstly, there is no selection criteria defined when more than one test patterncandidates have the same maximum total Hamming distance and total cartesian distance. Secondly, determinationof total Hamming distance and total Cartesian distance is computational intensive as it is a summation of individualHamming distances and cartesian distances with all the previously selected test patterns. In this paper, two-dimensionalHamming distance is proposed to address the first issue. A novel concept of horizontal Hamming distance is introduced,which acts as a third criterion for test pattern selection. Fault simulations on ISCAS’85 and ISCAS’89 benchmarkcircuits have shown that employing horizontal Hamming distance improves the effectiveness of pure antirandom in termsof fault coverage. Additionally, an alternative method for total Hamming distance calculations is proposed to reduce thecomputational intensity. The proposed method avoids summation of individual Hamming distances by keeping track ofnumber of 0s and 1s applied at each inputs. As a result, up to 90% of the computations are reduced.

PDF

___

Venkatasubramanian M. Failure evasion: Statistically solving the NP complete problem of testing difficult-to-detect faults. PhD, Auburn University, Auburn, Alabama, USA, 2016.
Anand S, Burke EK, Chen TY, Clark J, Cohen MB, Grieskamp W, Harman M, Harrold MJ, Mcminn P, Bertolino A, Li JJ. An orchestrated survey of methodologies for automated software test case generation. J Syst Software 2013; 86: 1978-2001.
Rinitha R, Ponni R. Testing in VLSI: A survey. In: International Conference on Emerging Trends in Engineering, Technology and Science; 24 Feb 2016; Pudukottai, India: IEEE. pp. 1-6.
Venkatasubramanian M, Agrawal VD. Database Search and ATPG–Interdisciplinary Domains and Algorithms. In: 29th International Conference on VLSI Design; 4-8 Jan. 2016; Kolkata, India: IEEE. pp. 38-43.
Venkatasubramanian M, Agrawal VD. Quest for a quantum search algorithm for testing stuck-at faults in digital circuits. In: International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems; 12-14 Oct. 2015; Amherst, MA, USA: IEEE. pp. 128-133.
Venkatasubramanian M, Agrawal VD. Failures guide probabilistic search for a hard-to-find test. In: North Atlantic Test Workshop; 9-11 May, 2016; Providence, RI, USA: IEEE. pp. 18-23.
Venkatasubramanian M, Agrawal VD. A new test vector search algorithm for a single stuck-at fault using probabilistic correlation. In: North Atlantic Test Workshop; 14-16 May, 2014; NY, USA: IEEE. pp. 57-60.
Agrawal VD, Kime CR, Saluja KK. A tutorial on built-in self-test. I. Principles. IEEE Des Test Comput 1993; 10: 73-82.
Shiao CM, Lien WC, Lee KJ. A Test-per-cycle BIST architecture with low area overhead and no storage requirement. In: International Symposium on VLSI Design, Automation and Test; 25-27 April 2016; Hsinchu: IEEE. pp. 1-4.
Jutman A, Aleksejev I, Raik J. Design and Test Technology for Dependable Systems-on-Chip. Hershey, Pennsylvania, USA: IGI Global, 2011.
Joice DN, Saravanan S. Efficient Test Sequence Generator for Area Optimization in LFSR Reseeding. Ind J Sci Technol 2016; 9: 29.
Devika KN, Bhakthavatchalu R. Programmable MISR modules for logic BIST based VLSI testing. In: International Conference on Control, Instrumentation, Communication and Computational Technologies; 16-17 Dec. 2016; Kumaracoil, India: IEEE. pp. 699-703.
Novák O, Jenícek J, Rozkovec M. LFSR Reseeding Based Test Compression Respecting Different Controllability of Decompressor Outputs. In: International Symposium on Design and Diagnostics of Electronic Circuits & Systems; 22-24 April, 2015; Belgrade, Serbia: IEEE. pp. 9-14.
Mrugalski G, Rajski J, Rybak L, Solecki J, Tyszer J. Deterministic built-in self-test based on compressed test patterns stored on chip and their derivatives. United States Patent US 9933485, 2018.
McCluskey EJ. Built-in self-test techniques. IEEE Des Test Comput 1985; 2: 21-28.
Acharya S. Cellular automata pseudorandom sequence generation. MSc, University of Victoria, Victoria, Canada, 2017.
Xiang D, Wen X, Wang LT. Low-Power Scan-Based Built-In Self-Test Based on Weighted Pseudorandom Test Pattern Generation and Reseeding. IEEE T Vlsi Syst, 2017; 25: 942-953.
Lin X, Rajski J. Logic built-in self-test with high test coverage and low switching activity. United States patent US 9568552, 2017.
Wagner KD, Chin CK, McCluskey EJ. Pseudorandom testing. IEEE T Comput 1987; C-36: 332-343.
Rajski J, Tyszer J, Kassab M, Mukherjee N. Embedded deterministic test. IEEE T Comput Aid D 2004; 23: 776-792.
Krishna CV, Jas A, Touba NA. Test vector encoding using partial LFSR reseeding. In: Proceedings International Test Conference 2001; 1-1 Nov. 2001; Baltimore, MD, USA: IEEE. pp. 885-893.
K.Chakrabarty, B.T.Murray, V.Iyengar. Deterministic built-in test pattern generation for high-performance circuits using twisted-ring counters. IEEE T Vlsi Syst 2000; 8: 633-636.
Koneman B. LFSR-coded test patterns for scan designs. In: European Test Conference; 19-22 April 1993; Rotterdam, Netherlands: IEEE. pp. 237-242.
Lien WC, Lee KJ, Hsieh TY, Chakrabarty K. A new LFSR reseeding scheme via internal response feedback. In: Asian Test Symposium; 18-21 Nov. 2013; Yilan County, Taiwan: IEEE. pp. 97-102.
Rani DG, Meenakshi MM, Marina SA. Low hardware overhead implementation of 3-weight pattern generation technique for VLSI testing. In: International Conference on Devices, Circuits and Systems; 6-8 March 2014; Combiatore, India: IEEE. pp. 1-5.
Paschalis A, Voyiatzis I, Gizopoulos D. Accumulator based 3-weight pattern generation. IEEE T Vlsi Syst 2012; 20: 357-361.
Lien WC, Lee KJ, Hsieh TY, Chakrabarty K. Efficient LFSR reseeding based on internal-response feedback. J Electron Test 2014; 30: 673-685.
Liu T, Kuang J, Cai S, You Z. An effective logic BIST scheme based on LFSR-reseeding and TVAC. Int J Electron 2014; 101: 1217-1229.
Lien WC, Lee KJ, Hsieh TY. A test-per-clock LFSR reseeding algorithm for concurrent reduction on test sequence length and test data volume. In: Asian Test Symposium; 19-22 Nov. 2012; Nigata, Japan: IEEE. pp. 278-283.
Eggersglüß S, Krenz-Bååth R, Glowatz A, Hapke F, Drechsler R. A new SAT-based ATPG for generating highly compacted test sets. In: International symposium on Design and Diagnostics of Electronic Circuits & Systems; 18-20 Apr. 2012; Tallinn, Estonia: IEEE. pp. 230-235.
Wen K, Hu Y, Li X. Deterministic circular self test path. Tsinghua Sci Technol 2007; 12: 20-25.
Lien WC, Lee KJ, Hsieh TY, Ang WL. An efficient on-chip test generation scheme based on programmable and multiple twisted-ring counters. IEEE T Comput Aid D 2013; 32: 1254-1264.
Xu S. Orderly random testing for both hardware and software. In: Pacific Rim International Symposium on Dependable Computing; 15-17 Dec. 2008; Taipei: IEEE. pp. 160-167.
Wu SH, Jandhyala S, Malaiya YK, Jayasumana AP. Antirandom testing: a distance-based approach. VLSI Des 2008; 2008: 2.
Wu S, Malaiya YK, Jayasumana AP. Antirandom vs. pseudorandom testing. In: International Conference on Computer Design: VLSI in Computers and Processors; 5-7 Oct. 1998; Austin, Texas: IEEE. pp. 221-223.
Malaiya YK. Antirandom testing: getting the most out of black-box testing. In: International Symposium on Software Reliability Engineering; 24-27 Oct. 1995; Toulose, France: IEEE. pp. 86-95. [37] Mrozek I, Yarmolik V. Multiple Controlled Random Testing. Fund Inform 2016; 144: 23-43.
Mrozek I, Yarmolik V. Methods of Synthesis of Controlled Random Tests. In: International Conference on Computer Information systems and Industrial management; 14-16 Sep. 2016; Lithuania: Springer. pp. 429-440.
Xu S. Random-like testing of very large scale integration circuit. J Shanghai Univ 1998; 2: 279-283.
Chen T, Bai A, Hajjar A, Andrews AK, Anderson C. Fast anti-random (FAR) test generation to improve the quality of behavioral model verification. J Electron Test 2002; 18: 583-594.
Chen TY, Leung H, Mak IK. Adaptive random testing. In: Annual Asian Computing Science Conference; 8-10 Dec. 2004; Chiang Mai, Thailand: Springer. pp. 320-329.
Chan KP, Chen TY, Towey D. Normalized restricted random testing. In: International Conference on Reliable Software Technologies; 16-20 June 2003; Toulouse, France: Springer. pp. 368-381.
Chan KP, Chen TY, Towey D. Restricted random testing. In: European Confernece on Software Quality; 9-13 June 2002; Helsinki, Finland: Springer. pp. 321-330.
Yiunn DB, A’ain AK, Ghee J. Scalable test pattern generation (STPG). In: IEEE Symposium on Industrial Electronics & Applications; 3-5 Oct. 2010; Penang, Malaysia: IEEE. pp. 433-435.
Xu S, Xu P. A Quasi-best Random Testing. In: Asian Test Symposium; 1-4 Dec. 2010; Shanghai: IEEE. pp. 21-26.
Sahari MS, A’ain AK, Grout IA. Scalable antirandom testing (SAT). International Journal of Innovative Science and Modern Engineering (IJISME) 2015; 3: 33-35.
Mrozek I, Yarmolik VN. Iterative antirandom testing. J Electron Test 2012; 28: 301-315.
Yarmolik SV, Yarmolik VN. Controlled random tests. Automat Rem Contr+ 2012; 73: 1704-1714.
Mrozek I, Yarmolik V. Optimal Controlled Random Tests. In: International Conference on Computer Information systems and industrial management; 16-18 June 2017; Bialystok, Poland: Springer. pp. 27-38.
Bryan D. The ISCAS’85 benchmark circuits and netlist format. North Carolina State University 1985; 25.
Brglez F, Bryan D, Kozminski K. Combinational profiles of sequential benchmark circuits. In: IEEE International Symposium on Circuits and Systems; 8-11 May 1989; Portland, OR, USA: IEEE. pp. 1929-1934.
Mrozek I, Yarmolik V. Antirandom test vectors for BIST in hardware/software systems. Journal Fundamenta Informaticae 2012; 119: 163-185.