Dismiss
InnovationQ will be updated on Tuesday, September 18, from 8-9pm ET. You may experience brief service interruptions during this time. See here for details on our Australian patent collection updates.
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 [+1]

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...