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 h_{n}x^{n} + h_{n-1}x^{n-1} + . . . + h_{1}x + h_{0}, where the term h_{i}x^{i} refers to the i^{th} flop of the register. In standard form LFSR, if h_{i} = 1, then there is a feedback tap taken from this flop and in modular form LFSR, if h_{i} = 1, then there is a feedback to the output of this flop.

Note: h_{N} and h_{0} is always equals to 1 in a 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) = x^{8} + x^{5} + x^{2} + 1.

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, Q_{0} 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.