Chipress

In digital design, we quite often need to generate random numbers. However, it is impossible to achieve true randomness in the digital world. Therefore, design engineers use LFSR (Linear Feedback Shift Register) to generate pseudo-random sequences.

Why Randomness is Needed in Digital Design?

Randomness is everywhere in digital design, for example, cryptography, BIST (Built-in Self-test) test pattern generator, counter implementation (with fewer gates than binary counters) and PCIe physical layer data scrambler / descrambler.

PCIe physical layer hardware, in particular, has a data scrambler on the data transmission side, and a data descrambler on the data receiving side. The scrambling and descrambling help to achieve a desirable balance of 0s and 1s in the data stream, and improve the overall data integrity during data transmission, since the noises among all frequencies are flattened and high crosstalk noises at a certain frequency are mitigated. Because the scrambling algorithm / hardware is known, the data can be recovered on the receiving side by applying the same algorithm and using the same hardware.

How does a LFSR Work?

There are two types of LFSRs: external feedback and internal feedback. All LFSRs consist of a few flops plus a few XOR gates, and they are defined by their characteristic polynomials.

The characteristic polynomials essentially define XOR gates position in the shift registers. For example, the diagram below shows LFSR with polynomial P(x) = x⁴ + x³ + x +1.

The degree of the LFSR polynomial defines the number of flops in the LFSR. The coefficient of xⁱ term defines the XOR feedback connection to flop i:

1. Coefficient = 0 means no connection
2. Coefficient = 1 means connection exits
3. Xⁿ term, or polynomial degree term, always presents in the polynomial, and it represents the primary feedback
4. X⁰ term always presents in the polynomial, and it represents the principal input to the shift registers

External feedback LFSR is also called many-to-one LFSR, while internal feedback LFSR is also called one-to-many LFSR. External feedback LFSR has a XOR gate tree outside of the shift register chain, thus, compared to internal feedback LFSR, if the polynomial degree is higher, external feedback LFSR is harder for timing closure and can run at lower frequency.

At the start of the operation, the LFSR must be initialized to some non-zero values, or non-zero seeds, otherwise it will be stuck at all 0 values.

An LFSR generates a periodic sequence, and the maximum length of an LFSR sequence is (2ⁿ-1). Note, not all LFSRs generate a maximum-length sequence, and the characteristic polynomial of an LFSR generating a maximum-length sequence is a primitive polynomial. This wikipedia page about LFSR summarizes primitive polynomials.

In addition, external and internal feedback LFSR with the same primitive polynomial do not generate the same sequence, only the same length. Interested readers or interviewees are encouraged to try this out.

Reference

1. https://en.wikipedia.org/wiki/PCI_Express
2. https://en.wikipedia.org/wiki/Linear-feedback_shift_register