LFSR and Ring Generator

An n-bit Linear Feedback Shift Register (LFSR) consists of ‘n’ memory elements (or flops) and XOR gates. There are basically two types of LFSR –

   1.  Standard Form (also known as External Feedback LFSR)
  2.  Modular Form (also known as Internal Feedback LFSR)

LFSRs can be represented by its characteristics polynomial hnxn + hn-1xn-1 + . . . + h1x + h0, where the term hixi refers to the ith flop of the register. In standard form LFSR, if hi = 1, then there is a feedback tap taken from this flop and in modular form LFSR, if hi = 1, then there is a feedback to the output of this flop.

Note: hN and h0 is always equals to 1 in a LFSR.

Figure 1: Standard Form LFSR
Figure 2: Modular Form LFSR
Standard Form LFSR Modular Form LFSR
The modulo-2 sum of the selected stages indicated by the characteristics polynomial is fed back to the 1st stage of the LFSR. The output of the last stage of the LFSR is fed back to the stages indicated by the characteristics polynomial.
The speed is limited by the depth of the linear logic in its feedback path. Effected speed is determined by the number of XOR gates in the feedback path. Implementation involves a large fan-out on the output of the last stage. Theoretically up to ‘n’ fan-outs possible for a n-bit LFSR, which leads to timing challenges for large LFSRs.

To avoid these issues, EDT uses a Ring LFSR structure (called Ring Generator). This is a simple LFSR structure folded back on itself to form a ring with multiple tap points. Shown below is an example of a simple 8 bits Ring Generator implementing the polynomial, f(x) = x8 + x5 + x2 + 1.

Figure 3: Ring LFSR structure

A Ring LFSR has a smaller number of levels of logic than its corresponding external feedback LFSR and smaller fan-out than its corresponding internal feedback LFSR [As shown in Figure 4.1, Q0 is having 3 fan-outs but in its corresponding Ring LFSR implementation each flop can have maximum 2 fan-outs. The reduction is fan-outs is significant in large LFSRs]. Thus it minimizes XOR gates, has low fan-out and also has efficient physical implementation.

Ring LFSRs are obtained by transforming conventional LFSRs in such a way that many realizations having the same characteristic polynomial are generated. Shown below is an example of how a conventional LFSR is transformed into a Ring LFSR.

Figure 4.1: Modular LFSR structure f(x) = x8 + x5 + x2 + 1
Figure 4.2: Fold the LFSR to make it look like a Ring
Figure 4.3: Horizontally flip the Ring shown in Figure 4.2
Figure 4.4: Elementary Shift Left transformation (1)
The XOR position is shifted left by 2 positions [Q2 to Q4 and Q5 to Q7]
The feedback origin position is shifted left by 2 positions [Q0 to Q2]
Figure 4.5: Elementary Shift Left transformation (2)
The XOR position is shifted left by 1 position [Q4 to Q5]
The feedback origin position is shifted left by 1 position [Q2 to Q3]
%d bloggers like this: