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