Model of the Month

BIST Circuits, Part Two

Previously, in Part One, three designs were presented. The maximal_length_lfsr enables the generation of PRBS data in order to stimulate a design.

The signature_register enables data to be captured from a design being tested and for a check to be made to see if the design being tested is faulty or not. To determine if the circuit is faulty, we compare the value stored in the signature register against the known good value. If they are equal, the design is OK, if not, the circuit has a fault.

Note that although we can create general-purpose PRBS generators and signature registers, the signature will depend upon the circuit being examined. It is possible to derive the signature simply by simulating the circuit in a testbench consisting of the PRBS generator for stimulus and examining the SISR after 2ⁿ-1 cycles to capture the signature. However, how would one know whether the SISR had been correctly designed in the first place, or even the LFSR?

Well, for the LFSR we can create a testbench to check that for the first 2ⁿ-1 cycles, all 2ⁿ-1 generated values are unique and that the next 2ⁿ-1 cycles are simply a repeat of the first 2ⁿ-1 cycles. As we shall see later, the actual bit pattern produced by the PRBS generator is irrelevant providing that statistically, 50% of bits are 0 and 50% are 1. Because the LFSR cannot generate the all-zeroes pattern, strictly speaking the figures are 50%-1 for 0 but apart from this the PRBS generated data stream is essentially random. The P (P for pseudo) in PRBS denotes that the data stream isn't perfectly random. In using the binary data stream for signature analysis, all that matters is that we know the bit pattern of the data stream input to the SISR.

For the SISR, it's a little more involved and we have to indulge in some mathematics. However, once we have shown that the SISR has been designed correctly, we can create testbenches for different designs and simply run simulations to determine the signature. So we only gotta do the maths once!

This means that we must run a simulation whereby we feed the parallel output of the PRBS generator into a sample circuit (not faulty) with one output and that output fed directly into the serial input of the SISR to test the SISR and to generate the signature. This will enable us to determine the known good value. We then check the signature derived from the simulation against that which can be derived from the maths. This will guard against simply assuming the simulation-derived signature is correct. If we make a mistake in coding up the SISR, we could easily end up with a signature that is invalid, causing us to to reject all perfectly good circuits (hopefully we'd suss out that something was wrong!) and keeping some bad ones - aaarrrgghhh!

What we have to do is to derive the known good signature from a mathematical analysis of the input stream, the SISR structure and the output stream from the SISR.

Mathematically, the trick is to treat binary data streams and modulo-2 division as polynomials.

First of all we need to convert from the binary form of a data stream to a maths perspective. We have two binary data streams — the input to the SISR and the output from the SISR. It is worth remembering that the register contents of the SISR can be regarded as a polynomial, as the register contents are also a binary pattern.

The input stream to the signature register becomes the input polynomial, which I will denote as I(x), apologies to the mathematicians amongst you if this is not standard notation. So, a binary data stream such as:

10110101 = B5_(hex) becomes 1 + x² + x³ + x⁵ + x⁷, so

I(x) = 1 + x² + x³ + x⁵ + x⁷

Equation 1. Binary data stream as a polynomial

The reason for the leading 1 is that x⁰=1 (do you remember that anything to the power 0 = 1?).

It is actually quite straightforward, isn't it? Whenever you see a '1' in the binary data stream, you put an x in the polynomial and raise it to the power of the bit position of the 1 in the input stream.

Now, I suspect that it doesn't matter (mathematically) which way round you view the input polynomial but I reckon it helps to put some pegs in the ground, so the '5' of B5(hex) binary stream corresponds to x5 + x7. The only odd thing (perhaps) is that we number the bit positions starting from the left hand bit of the binary data stream.

So we have some input data described as a polynomial. Let's perform modulo-2 division on the I(x) data and generate a quotient again expressed as a polynomial, Q(x). So, mathematically,

I(x)	=	Q(x)	+	R(x)
C(x)				C(x)

Equation 2. Mathematical Relationship of Polynomials

where C(x) is the ‘transfer function’ of the modulo-2 division...

Figure 1. Dataflow Relationship of Polynomials

... and R(x) is the remainder. R(x)/C(x) is not the remainder, it's the ‘fractional’ part of the division. The remainder R(x) is resident in the modulo-2 division circuit at the point in time at which the quotient has been output (remember we’re working with serial data here). A little algebra yields,

I(x) = C(x)Q(x) + R(x)

Equation 3. Calculation of I(x)

C(x) is often known as the characteristic polynomial. So, we can multiply the characteristic polynomial of our modulo-2 division circuit by the quotient, add the remainder and we should (should!) create the original input polynomial. We can use this approach to show that the modulo-2 division circuit works correctly.

So to summarise, in hardware terms, I(x) is the binary data stream to our modulo-2 division circuit, Q(x) is the binary data stream produced at the output of our modulo-2 division circuit and R(x) is the remainder left behind in our modulo-2 division circuit.

And what is this modulo-2 division circuit? Yes, it's the SISR! The characteristic polynomial of the SISR is C(x).

Thus we should be able to simulate the SISR with the output from the circuit under test, this is I(x). After 2ⁿ-1 cycles, the SISR should contain the signature, this is R(x). The output of the SISR produced during the 2ⁿ-1 cycles is Q(x). The characteristic polynomial of the SISR itself is C(x). Note that for the first few cycles, the first few bits output from the SISR will be the original state of the SISR, these are not part of Q(x). It is customary to set the initial SISR state to all zeroes.

Independently, using equation 2, we must divide C(x) into I(x) (using long division) and record Q(x) and R(x). One is not expected to do this by hand, various software packages can be used to obtain the results. You could even create a separate VHDL testbench to generate Q(x) and R(x), just so long as you take a completely different approach from that used in the SISR simulation — you could create a modulo-2 long_division function to mimic the SISR behaviour.

Now, to present the principles of deriving the known good signature, let's see how it's done with a much smaller example than our original 10-bit SISR. Otherwise we're going to have to express I(x) as a 1024-bit polynomial for this 10-bit design and derive the signature, which just takes too long to explain.

Figure 2. Hardware Implementation of Polynomials

So for a 3-bit LFSR sequence, from the output of a simple faulty circuit, the polynomial is:

I(x) = x⁶ + x⁵ + x³ + x¹ + 1

this corresponds to a binary stream of 1101011 (remember that the MSB of the binary stream is clocked into the SISR first), thus,

              SISR     
   I(x)    contents  output  
1101011   000         
 110101   100         
  11010   110         
   1101   111         
    110   111    1    
     11   011    11   
      1   101    111  
          010    1111 
          R(x)     Q(x) 

and so,

C(x) = x³ + x¹ + 1

Q(x) = x³ + x² + x¹ + 1

R(x) = x¹

Is C(x)Q(x) + R(x) = I(x) ?

An easy way to check is to convert the polynomials back to binary streams both for the C(x)Q(x) multiplication and the R(x) addition, as follows:

         1111 x  
         1011    
         ----    
         1111    
        1111     
       ....      
      1111       
      -------    
      1101001    

Remember that the addition of the partial products is modulo-2. And finally add R(x),

      1101001 +  
          010    
      -------    
      1101011    

Is this I(x)? Yes. So R(x) is the contents of the signature register.

So that's the maths, hope you were able to follow it. Please note that this is not a rigorous treatment of the subject matter, simply enough detail so that you can derive your own approaches to checking the signature for your own BIST circuits. Onto the VHDL now...

An inherent limitation of this approach is that only one output can be tested at a time. Ideally, we would like to extend the signature register in order to handle multiple inputs. The good news is that we can.

The MISR code given below implements a multiple-input signature register.

library IEEE;
use IEEE.std_logic_1164.all;

entity misr is
port (
  clock         : std_ulogic;
  reset         : std_ulogic;
  signature_in  : in std_ulogic_vector(9 downto 0);
  signature_out : out std_ulogic_vector(9 downto 0)
);
end misr;

architecture modular of misr is

  signal sig_reg : std_ulogic_vector(9 downto 0);

begin

  process (clock)
    variable lfsr_tap : std_ulogic;
  begin
    if clock'EVENT and clock='1' then
      if reset = '1' then
        sig_reg <= (others => '0');
      else
        lfsr_tap := sig_reg(6) xor sig_reg(9);
        sig_reg(9 downto 1) <= sig_reg(8 downto 0) xor signature_in(9 downto 1);
        sig_reg(0) <= lfsr_tap xor signature_in(0);
      end if;
    end if;
  end process;
  
  signature_out <= sig_reg;
  
end modular;

Next month it is intended that we apply these BIST circuits to a real design, so that you can see how to incorporate BIST in your own designs.

You are welcome to use the source code we provide but you must keep the copyright notice with the code (see the Acknowledgements page for more details).

To download the VHDL source code for this month's
Model of the Month, click here.

Source code for other Models of the Month
can be downloaded from here.