IBM Journal of Research and Development
IBM Skip to main content
  Home     Products & services     Support & downloads     My account  

  Select a country  
Journals Home  
  Systems Journal  
Journal of Research
and Development
    Current Issue  
    Recent Issues  
    Papers in Progress  
    Recent publications  
    Author's Guide  
  Contact Us  
  Related links:  
     IBM Research  

IBM Journal of Research and Development  
Volume 28, Number 2, Page 212 (1984)
Coding and Error Control
  Full article: arrowPDF   arrowCopyright info


Iterative Exhaustive Pattern Generation for Logic Testing

by D. T. Tang, C. L. Chen
Exhaustive pattern logic testing schemes provide all possible input patterns with respect to an output in the set of test patterns. This paper is concerned with the problem that arises when this is to be done simultaneously with respect to a number of outputs, using a single test set. More specifically, in this paper we describe an iterative procedure for generating a test set consisting of n-dimensional vectors which exhaustively covers all k-subspaces simultaneously, i.e., the projections of n-dimensional vectors in the test set onto any input subset of a specified size k contain all possible patterns of k-tuples. For any given k, we first find an appropriate N (N>k) and generate an efficient N-dimensional test set for exhaustive coverage of all k-subspaces. We next develop a constructive procedure to expand the corresponding test matrix (formed by taking test vectors as its rows) such that a test set of N2-dimensional vectors exhaustively covering the same k-subspaces is obtained. This procedure may be repeated to cover arbitrarily large n (n=N2i after i iterations), while keeping the same k. It is shown that the size of the test set obtained this way grows in size which becomes proportional to (log n) raised to the power of [log (q+1)], where q is a function of k only, and is approximated (bounded closely below) by k2/4 in binary cases. This approach applies to nonbinary cases as well except that the value of q in an r-ary case is approximated by a number lying between k2/4 and k2/2.
Related Subjects: Error control and recovery; Logic design and technology; Test-pattern generation