Browse Prior Art Database

Variable Length Linear Feedback Shift Registers

IP.com Disclosure Number: IPCOM000035283D
Original Publication Date: 1989-Jul-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 3 page(s) / 29K

Publishing Venue

IBM

Related People

Bardell, PH: AUTHOR

Abstract

Disclosed is a linear feedback shift register (LFSR) that can be configured in a varying number of stages. Each of these configurations yields a maximal length sequence for its number of stages without need to change the feedback taps for each configuration.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Variable Length Linear Feedback Shift Registers

Disclosed is a linear feedback shift register (LFSR) that can be configured in a varying number of stages. Each of these configurations yields a maximal length sequence for its number of stages without need to change the feedback taps for each configuration.

The sequence that an LFSR produces depends on the feedback taps and the placement of these taps is defined by the characteristic polynomial of the LFSR
1. Consider the following primitive polynomials: P1(x) = x8 + x5 + x3 + x2 + 1 P2(x) = x9 + x5 + x3 + x2 + 1 P3(x) = x10 + x5 + x3 + x2 + 1 P4(x) = x11 + x5 + x3 + x2 + 1

Polynomial P1(x) defines the feedback taps of an 8 stage LFSR which has a sequence of length 1023 (28-1). The sequence defined by P2(x) is 2047 bits long while the other two are 4095 and 8191 bits in length. Since the terms of the polynomials are the same except for the high- order term, a simple structure can be used to implement them such that any one sequence can be selected by a multiplexer. The figure shows such a circuit. The same polynomials can be used to implement the divider form of an LFSR [1] to minimize delay. There are many groups of primitive polynomials that have the same minor terms. Any of these groups can be used to implement variable length LFSRs. Not only polynomials with adjacent degrees as above, but ones with non-contiguous degrees, can be used to construct such LFSRs. An example is the triplet: Pa(x) = x31 + x6 + x2 + x + 1 Pb(x) = x41 + x6 + x2 + x + 1 Pc(x) = x53 + x6 + x2 + x + 1

When used to implement an LFSR in the manner shown in the figure, with the appropriate number of stages between the MUX inputs, maximal length sequences of degree 31, 41 or 53 are generated.

Both of the LFSR implementations describe...