Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

DeBruijn Sequences From the Alternative Lfsr

IP.com Disclosure Number: IPCOM000119961D
Original Publication Date: 1991-Mar-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 2 page(s) / 56K

Publishing Venue

IBM

Related People

Bardell, PH: AUTHOR [+2]

Abstract

Disclosed is a means of inserting the all-zero state in the sequences from the alternative implementation of a linear feedback shift register (LFSR).

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

DeBruijn Sequences From the Alternative Lfsr

      Disclosed is a means of inserting the all-zero state in
the sequences from the alternative implementation of a linear
feedback shift register (LFSR).

      An n-stage LFSR implementing a primitive polynomial has a
sequence length m = 2n - 1 when initialized to a non-zero state.  The
8-stage LFSR implementing the polynomial x8 + x6 + x5 + x + 1 is
shown in Figure 1 (in which the block marked SRL represents a shift
register latch and XOR represents a modulo-2 adder).  The sequence
generated by this LFSR is called a "maximum length sequence" and is
of length 28 - 1 = 255.  The all-zero state is missing from this
sequence since the output of the register feedback is 0 when all of
its inputs are 0.

      It is well known (*) that the all-zero state can be included in
the sequence if the complements of the first n - 1 stages are ANDed
together and fed into the single exclusive-OR.  This inserts the all-
zero n-tuple between the 000...001 state and the 100...000 state.
Such a sequence is called a deBruijn sequence, for historical
reasons.

      An alternative implementation of the primitive polynomial x8 +
x6 + x5 + x + 1 is shown in Figure 2.  It also has
a sequence length of 28 - 1 = 255, with again the all-zero state
missing.

      The all-zero state can be included in the sequence by an
alternative implementation by ANDing together the complements of the
first n- 1 stages and feeding the AND output...