# Patent

## Title
Compacting circuit responses

## Abstract

Circuit responses to a stimulus may be compacted, decreasing the number of pin outs, without increasing the circuit element length, using a compactor. In accordance with one embodiment of the present invention, errors may be detected in scan chains used for integrated circuit testing. The number of outputs applied to output pins or other connectors may be substantially decreased, resulting in cost savings.

## Background
CROSS-REFERENCE TO RELATED APPLICATIONS
This application is a continuation of U.S. patent application Ser. No. 10/107,628, filed on Mar. 27, 2002 now U.S. Pat. No. 7,185,253.


BACKGROUND
This invention relates generally to integrated circuits.
Integrated circuits include input pins for receiving signals from the outside world and output pins for providing signals to the outside world. Since integrated circuit packages are advantageously compact, increasing the number of pins means increasing the integrated circuit packaging size and cost.
For example, when testing integrated circuits, a number of modules or components may be scanned or analyzed for errors or defects. The more scan chains of modules to be analyzed, generally the more pins that are needed to receive signals from those scan chains. Conversely, the longer the scan chains, the slower the testing process. Either way, the costs may be aggravated.
Some of the major contributors to integrated circuit test cost include: available tester memory, available number of tester channels, test time, and number of pins available for scan-in and scan-out purposes. All these contributors to test cost have direct relationships with the scan chain lengths and the number of scan chains.
Therefore, there is a need for better ways to compact circuit outputs to reduce the number of circuit pins or connectors without increasing the size of the circuit elements.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a schematic depiction of one embodiment of the present invention;
FIG. 2 is a schematic depiction of one embodiment of the present invention;
FIG. 3 is applied to a hardware depiction of another embodiment of the present invention; and
FIG. 4 is a schematic depiction of another embodiment of the present invention.



DETAILED DESCRIPTION
Referring to FIG. 1, a response compactor 12 may receive inputs from a plurality of circuit elements 10. Each of the circuit elements 10 may be any of a variety of circuit elements, components or modules. Each circuit element 10 receives an input such as the inputs 1 to n and provides an output that may be provided to the response compactor 12. The response compactor 12, which may be a linear network containing combinational or sequential logic such as exclusive OR or AND OR gates, provides a series of outputs 1 to m. In accordance with one embodiment of the present invention, the number of outputs is substantially less than the number of circuit elements or the number of inputs provided to the response compactor 12 from those circuit elements 10.
Thus, in some embodiments of the present invention, the response compactor 12 may facilitate integrated circuit design by reducing the number of outputs and therefore the number of pins or other types of connectors that are needed to communicate with the circuit elements 10. In particular, in a variety of circumstances, it may be desirable to reduce the outputs from a plurality of circuit elements 10 to a smaller number of outputs. One example of a reason to reduce outputs is to decrease the number of pins or connectors on an integrated circuit. However, a variety of other reasons to reduce outputs may also exist.
In the ensuing discussion, examples are provided in connection with circuits for testing integrated circuits. In such cases, a scan chain may be analyzed by providing a stimulus to the scan chain and receiving its output. In many complex integrated circuits, a large number of scan chains may each be provided with a stimulus. The responses of those scan chains may be collected. In accordance with some embodiments of the present invention, the number of outputs that are provided to pins or other connectors may be reduced using a response compactor 12. However, the present invention is not limited to testing embodiments and is applicable to a wide variety of integrated circuits.
Referring to FIG. 2, a response compactor 12a may output scan-outs from 1 to m. The response compactor 12a may receive inputs from m scan chains 10a. Each of the scan chains 10a includes a scan-in, as indicated. In one embodiment of the present invention, the number of scan-outs is substantially less than the number of scan chains 10a that provide inputs to the response compactor 12a. In this way, in some embodiments, the number of necessary pins or connectors can be reduced without increasing the size of the scan chains.
For a design with n scan chains, scan chain outputs may be compacted to use significantly fewer than n scan-out pins. The number of scan-out pins (and tester channels for scan-outs) can be reduced to log2 n without requiring any information about the layout of the scan chains. For example, a design with 250 scan chains uses 10 scan-out pins without any information about how the scan chains have been inserted.
Let us suppose that we have a design with n scan chains. Hence, the compactor design will have n inputs. Suppose that the compactor has m outputs. A compactor design can be represented as a binary matrix (matrix with only zeros and ones) with n rows and m columns. Each row corresponds to a scan chain and each column corresponds to a compactor output. The entry in row i and column j of the binary matrix is 1, if the ith scan chain output is exclusive OR-ed to generate the jth output of the compactor; the matrix entry is 0 otherwise.
Referring to FIG. 3, a compactor 12a may include a number of exclusive OR (XOR) gates 14 coupled to eight scan chains 10a. The resulting 8×5 matrix is depicted below:




   
  
    [
    
      
        
          1
        
        
          1
        
        
          1
        
        
          0
        
        
          0
        
      
      
        
          1
        
        
          0
        
        
          1
        
        
          1
        
        
          0
        
      
      
        
          1
        
        
          1
        
        
          0
        
        
          0
        
        
          0
        
      
      
        
          0
        
        
          1
        
        
          1
        
        
          1
        
        
          0
        
      
      
        
          1
        
        
          1
        
        
          0
        
        
          0
        
        
          1
        
      
      
        
          0
        
        
          0
        
        
          1
        
        
          1
        
        
          1
        
      
      
        
          1
        
        
          0
        
        
          0
        
        
          1
        
        
          1
        
      
      
        
          1
        
        
          0
        
        
          0
        
        
          0
        
        
          1
        
      
    
    ]
  




The compactor of FIG. 3 has eight inputs (since there are eight scan chains) and five outputs. The entries in the first and second rows under the first column are one because the outputs of scan chains 1 and 2 are XOR-ed to obtain the first compactor output (scan-out 1) and the outputs of scan chains 3 and 4 are XOR-ed to obtain the second compactor output (scan-out 2). The example of FIG. 3 will detect simultaneous errors in two different scan-chains. As will be explained in more detail later, this is because all of the matrix rows are non-zero and different.
If a single scan chain produces an error at any scan-out cycle, the compactor outputs produce an error at that scan cycle if and only if no row of the compactor matrix contains all zeros. Therefore, no row of the compactor matrix contains all zeros in one embodiment.
As shown in FIG. 2, the exclusive OR gates 14 are arranged such that there is at least one exclusive OR gate 14 coupled between each input to the compactor 12a and at least one output from the compactor. Each input is also coupled to the outputs differently in accordance with one embodiment of the present invention. In other embodiments of the present invention, each input is coupled to an odd number of outputs through the exclusive OR gates 14. In still another embodiment of the present invention, the same number of inputs are coupled to each output.
If two scan chains produce errors at any scan-out cycle, the compactor outputs produce an error at that scan cycle if and only if no two rows of the compactor matrix are identical. Therefore, no two rows of the compactor matrix are identical in one embodiment. Since the compactor matrix has m columns, there are maximum 2m−1 distinct non-zero rows possible. Thus, the following condition may be satisfied: n≦2m−1, where n is the number of scan chains (which is equal to the number of rows of the compactor matrix). This means, m≧log2(n+1). Thus, the compactor can have log2(n+1) or more outputs when there are n scan chains. If there are 127 scan chains, for example, the compactor need only 7 scan-out pins instead of 127 scan-out pins.
When an odd number of scan chains produce errors at any scan-out cycle, the compactor outputs produce an error at that scan-out cycle if and only if the bit-wise exclusive-OR of any two rows of the compactor matrix is not equal to any other row of the compactor matrix. Therefore, the bit-wise exclusive-OR of any two rows of the compactor matrix is not equal to the bit-wise exclusive-OR of any other row of the matrix. Alternatively, every row of the compactor matrix contains an odd number of ones, in one embodiment.
Since the compactor matrix has m columns, a maximum of 2m-1 distinct non-zero rows with an odd number of ones are possible. Thus, the following condition may be satisfied: n≦2m-1, where n is the number of scan chains (equal to the number of rows of the compactor matrix). This means, m≧1+log2(n). If there are 127 scan chains, for example, we will need only 8 scan-out pins instead of 127 scan-out pins.
In some embodiments, only two errors in two scan chains can be detected. In other embodiments, errors in three scan chains may be detected. However, the present invention is applicable to embodiments involving errors in more than three scan chains, for example, using the concepts of BCH and Reed Solomon error detection and correction codes.
Some of the scan chains can produce logic values unknown during simulation (often called X-values) at the same scan-out cycle when some other scan chain produces an error. In that case, there is a chance that this error can get masked and the defect is not detected.
If a scan chain produces an error and another scan chain produces a logic value unknown during simulation at any scan-out cycle, the compactor outputs produce an error at that scan-out cycle if and only if no row of the compactor matrix contains all zeros. Thus, in one embodiment, no row of the matrix contains all zeros. If any two rows have ones in the same column, there must be two columns in which the same two rows have (0, 1) and (1, 0) in one embodiment. Every row of the compactor matrix is distinct, has equal numbers of ones and the numbers of ones in every row is odd, in one embodiment.
For example, let us suppose that we have a compactor matrix with 10 columns. Every row of this matrix has an equal number of ones, and the number of ones in every row must be odd. In this case, the number of rows is maximized if the number of ones in each row is 5; there are




  
    (
    
      
        
          10
        
      
      
        
          5
        
      
    
    )
  
  =
  252




such rows possible. In general, for a compactor matrix with 2k or 2k+1 columns, the number of rows is maximized if each row has k or k−1 ones depending on whether k is odd or even, respectively. Thus, the following relationships between n, the number of scan chains, and m, the number of compactor outputs, are satisfied:





  
    n
    ≤
    
      (
      
        
          
            m
            m
          
          2
        
        -
        1
      
      )
    
  
  ,




when m divisible by 4;





  
    n
    ≤
    
      (
      
        
          m
          m
        
        2
      
      )
    
  
  ,




when m divisible by 2 and not by 4;





  
    n
    ≤
    
      (
      
        
          
            m
            -
            
              1
              m
            
          
          2
        
        -
        1
      
      )
    
  
  ,




when m−1 divisible by 4;





  
    n
    ≤
    
      (
      
        
          
            m
            m
          
          -
          1
        
        2
      
      )
    
  
  ,




when m−1 divisible by 2 and not by 4.

The design of a compactor circuit may be illustrated using the following example. Suppose that we want to design a compactor circuit with 8 inputs (corresponding to 8 scan chains) and 5 outputs. The compactor matrix has 8 rows and 5 columns and is shown below.




   
  
    [
    
      
        
          1
        
        
          1
        
        
          1
        
        
          0
        
        
          0
        
      
      
        
          1
        
        
          0
        
        
          1
        
        
          1
        
        
          0
        
      
      
        
          1
        
        
          1
        
        
          0
        
        
          1
        
        
          0
        
      
      
        
          1
        
        
          1
        
        
          0
        
        
          0
        
        
          1
        
      
      
        
          1
        
        
          0
        
        
          1
        
        
          0
        
        
          1
        
      
      
        
          1
        
        
          0
        
        
          0
        
        
          1
        
        
          1
        
      
      
        
          0
        
        
          1
        
        
          0
        
        
          1
        
        
          1
        
      
      
        
          0
        
        
          0
        
        
          1
        
        
          1
        
        
          1
        
      
    
    ]
  




The compactor matrix is designed such that each row has three ones and all rows are distinct. Consider the scan chain corresponding to the first row of the compactor matrix. If this scan chain (referred to as scan chain 1) produces an unknown logic value, the outputs at the first three compactor outputs will be unknown and masked on the tester. However, if any other scan chain produces an error at the same scan-out cycle when scan chain 1 produces an unknown value, known as an x-value, one of the remaining two compactor outputs will be erroneous. For example, if scan chain 2 produces an error, the fourth compactor output will be erroneous. Also, it is not affected by the outputs from scan chain 1. This property holds for any scan chain producing an error at the same time any other scan chain producing an unknown value.
In one embodiment of the present invention, the presence of a single x-value in a scan chain can be detected. In other embodiments, more than one x-value can be detected.
The outputs of the compactor 12a can be applied to a signature analyzer 14 such as a Multiple Input Signature Register (MISR). The unknown logic values (X-values) at the compactor 12a outputs can be blocked or masked using X-blocking (or X-masking) logic. The X-blocking logic 16 may be used to fix the X-value at the compactor outputs to zeros or ones. Alternatively, signals can be sent so that the compactor 12a outputs are either collected in a signature analyzer 14 or observed on a tester depending on whether the outputs have any X-values. The inputs of this X-blocking logic 16 can be derived in several different ways, such as primary inputs or separate scan chains.
The design of the compactor 12 may be facilitated using the following principles:
1. If a single scan chain produces an error at any scan out, the compactor outputs produce an error at that scan cycle if, and only if, no row of the compactor matrix contains all zeros;
2. If two scan chains produce errors at any scan out cycle, the compactor outputs produce an error at that cycle if, and only if, no two rows of a compactor matrix are identical;
3. When three or an odd number of scan chains produce errors at any scan out cycle, the compactor outputs produce an error at that scan out cycle if, and only if, the bitwise exclusive-OR of any two rows of a compactor matrix is not equal to any other row of the compactor matrix;
4. Number three above is satisfied if every row of the compactor matrix contains an odd number of ones;
5. If a scan chain produces an error and another scan produces a logic value unknown during simulation at any scan out cycle, the compactor outputs produce an error at that scan out cycle if, and only if, no row of the compactor matrix contains all zeros, and if any two rows have ones at the same column there must be two columns in which the same rows have (0,1) and (1,0);
6. Number five above is satisfied if every row of the compactor matrix is distinct, has equal numbers of ones and the number ones in every row is odd;
7. Items number two and three above are satisfied for the compactor matrix satisfying item number six above;
8. One may differentiate the situation where a single scan chain produces an error at the scan out cycle and when two scan chains produce errors at the scan out cycle if, and only if, the compactor matrix satisfies item number three above; and
9. If the bitwise exclusive-OR of two rows of a compactor matrix is equal to the compactor error vector at the scan out cycle, then it is possible that the scan chains corresponding to these two rows produce errors at that scan out cycle.
There are many ways to access the contents of the scan chains during diagnosis. First, while scanning patterns out in the diagnosis mode, the scan chains can be configured into longer scan chains (by concatenating multiple scan chains) and the contents of these chains can be shifted out using the scan-out pins. Alternatively, in the diagnosis mode, we can apply select signals to scan-out one or more scan chain contents directly through the scan-out pins bypassing the compactor circuit.
However, for most practical cases, one can identify the failing scan chain and the failing flip-flop in the scan chain directly from the compactor outputs collected on the tester (also called tester data-log) without having to configure the scan chains in diagnosis mode. This is because the failing scan chain can be uniquely identified as long as only one scan chain produces error at any scan-out cycle. Once the scan chain is identified it is very easy to identify the failing flip-flop from the scan-out cycle information.
Thus, in accordance with some embodiments of the present invention, where no more than two scan chains produce errors, by making the matrix for the compactor have all non-zero rows that are different, all errors will be detected. Similarly, where three scan chains produce errors, by making the compactor with a matrix whose rows are non-zero, different, and have an odd number of ones, all errors can be detected. Finally, if one scan chain produces an error and one scan chain produces an indeterminate or unknown state during simulation, called an x-value, this may be detected if all rows are non-zero, different and have equal and odd numbers of ones in their matrices.
While the present invention has been described with respect to a limited number of embodiments, those skilled in the art will appreciate numerous modifications and variations therefrom. It is intended that the appended claims cover all such modifications and variations as fall within the true spirit and scope of this present invention.

## Claims

1. A method comprising:
forming a response compactor with a plurality of inputs and a plurality of outputs; and
coupling said inputs to said outputs such that every input is coupled to a unique set of at least two outputs.

2. The method of claim 1 including coupling each input to more than two outputs.

3. The method of claim 2 including coupling each input to multiple outputs so that any time an unknown value is received at an input, there are other connections to the output not covered by said unknown value.

4. The method of claim 1 including coupling each input to a different set of outputs than any other input.

5. The method of claim 1 including coupling each input to a plurality of outputs and each input to a different set of outputs than any other of said inputs.

6. The method of claim 1 including forming a compactor whose inputs are scan chains.

7. The method of claim 1 including forming fewer outputs than inputs.

8. The method of claim 1 including forming alternate input to output paths that do not collide with any unknown values received at an input.

9. A response compactor comprising:
a plurality of inputs and a plurality of outputs; and
said inputs coupled to said outputs such that every input is coupled to a unique set of at least two outputs.

10. The compactor of claim 9 wherein each input is coupled to more than two outputs.

11. The compactor of claim 10 wherein each input is coupled to multiple outputs so that any time an unknown value is received in an input, there are other connections to the output not covered by said unknown value.

12. The compactor of claim 9 wherein each input is coupled to a different set of outputs than any other input.

13. The compactor of claim 9 wherein each input is coupled to a plurality of outputs and each input is coupled to a different set of outputs than any other of said inputs.

14. The compactor of claim 9 wherein said inputs are scan chains.

15. The compactor of claim 9 including fewer outputs than inputs.

16. The compactor of claim 9 including alternate input to output paths that do not collide with any unknown values received at an input.