ColMatch - BIST Designer

Main Features of ColMatch 1.0

  • High speed
  • Low memory demands
  • Easy to use
  • Usable for problems of very high dimensions
  • Test set can be presented in the compacted form or with don't cares. The test don't cares often significantly reduce the amount of output decoder logic
  • Built-in test compaction
  • Repetitive column matching enables to reach better results
  • Exact or heuristic column matching
  • Output file compatible with Berkeley PLA format
  • Needs Win32, Pentium or compatible processor


ColMatch is an easy-to-use tool for generating test-per-clock BIST (built-in self-test) for combinational or full-scan circuits.
The general structure of the proposed BIST is shown in the following figure:

The test pattern generator (TPG) produces test patterns that are fed into the circuit under test (CUT) in parallel.
This TPG consists of two parts: the pseudo-random pattern generator (PRPG), which is mostly a LFSR or a cellular automaton.
The plain PRPG often does not produce patterns that ensure satisfactory fault coverage, hence they must be modified by some additional circuitry - namely the Output decoder.

In our method the output decoder is a combinational block transforming the PRPG code words into deterministic test patterns pre-computed by some ATPG tool (Automatic Test Patterns Genarator). Our aim is to design the output decoder to be as small as possible.

In Colmatch v.2 we have introduced support of the mixed-mode testing. Here the test is divided into two disjoint phases: the pseudorandom and the deterministic. In the first phase the circuit is tested by unmodified LFSR patterns, to detect the easy-to-detect faults. In the deterministic phase the yet undetected faults are tested by test vectors generated by an APTG.
The structure is shown in the following figure:

The Switch is an array of multiplexers switching between the two phases.

ColMatch is based on a column matching BIST design approach. The solution is based on a novel search algorithm, which identifies the matches between the pairs of columns of the two sets of patterns. After that as many outputs as possible are directly matched to the inputs, which minimizes the combinational logic.
For the mixed-mode BIST, the simple column match implies no Decoder logic, however the Switch multiplexer has to be present. In Colmatch v.2 we prefer matches where columns with equal indexes (positions) are matched. After that, such a match implies no MUX at the output as well. We call it a Direct match.
An example is shown in the following figures. The 5-bit LFSR is run for 5 cycles first and the easily testable faults are detected. Then we run the fault simulation to find the undetected faults, for which the test vectors are generated by an ATPG. At the end the decoder logic is synthesized for these tests and the succeeding LFSR patterns.

There have been two direct column matches found (y0 - x0, y1 - x1), one negative direct match (y2 - x2') and one indirect column match (y3 - x1).

The inputs of the ColMatch program are two sets of patterns: the PRPG patterns and the test patterns. The output of the algorithm is a PLA file describing the output decoder transforming the two patterns.