An Efficient Algorithm for Finding the K Longest Testable Paths Through Each Gate in a Combinational Circuit Conference Paper uri icon


  • Testing the K longest paths through each gate (KLPG) in a circuit detects the smallest local delay faults under process variation. In this work a novel automatic test pattern generation (ATPG) methodology to find the K longest testable paths through each gate in a combinational circuit is presented. Many techniques are used to significantly reduce the search space. The results on the ISCAS benchmark circuits show that this methodology is very efficient and able to handle circuits with an exponential number of paths, such as c6288.

published proceedings

  • IEEE International Test Conference (TC)

author list (cited authors)

  • Qiu, W., & Walker, D.

complete list of authors

  • Qiu, W||Walker, DMH

publication date

  • November 2003