Browse Prior Art Database

Improved Random Sequence Generator for Very Large Scale Integration Test

IP.com Disclosure Number: IPCOM000114766D
Original Publication Date: 1995-Jan-01
Included in the Prior Art Database: 2005-Mar-29
Document File: 2 page(s) / 59K

Publishing Venue

IBM

Related People

Hanna, PE: AUTHOR

Abstract

The manufacture and test of thermal conduction modules and other Very Large Scale Integration (VLSI) components involve use of pseudorandom sequence generators. The most common technique used to generate these sequences is a Linear Feedback Shift Register (LFSR), which involves repeated division by an appropriate irreducible polynomial.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Improved Random Sequence Generator for Very Large Scale Integration
Test

      The manufacture and test of thermal conduction modules and
other Very Large Scale Integration (VLSI) components involve use of
pseudorandom sequence generators.  The most common technique used to
generate these sequences is a Linear Feedback Shift Register (LFSR),
which involves repeated division by an appropriate irreducible
polynomial.

      The main drawback of the LFSR technique is that the sequences
it generates exhibit linear dependence.  That is, although the bit
patterns it produces pass certain statistical tests for randomness,
the order in which they are produced may allow certain classes of
faults to elude detection.

      Described is a method of generating pseudorandom bit sequences
without linear dependence.  (*) describes an algorithm for generating
a pseudorandom sequence that has no repeated patterns at all.

      If e1, e2, ..., en is any sequence of 0's and 1's, find the
longest final segment that occurs earlier in the sequence.  If the
last occurrence of that sequence was followed by a 1, then generate
an 0 as the next bit in the sequence, otherwise generate a 1.  In
this way, no pattern will ever be repeated, which makes Mycielski
sequences ideal for pseudorandom VLSI test sequences.

Unfortunately, this method has two drawbacks that render it
impractical.
  1.  It requires the entire sequence to be retained in memory.
  2.  The time required to generate each bit increased in proportion
to
       the square of the length of the...