How to use LFSR to generate random numbers as per this Xilinx application note?

Question

The Xilinx App note XAPP052 "Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators" shows a method on how to use LFSRs to get random bit sequence of maximum length. I expected this to be a chain of registers similar to one used for CRC checks where we use feedback XOR gates to generate the random bit sequence. However, this appears different.
There are few things that I am trying to understand here:

How are they implementing a 32-bit LFSR using 2 16x1 SRAMs and 4 DFFs? Shouldn't it be 32 DFFs with some taps using feedback? The inclusion of Synchronous RAM blocks is confusing.
What would be the structure to implement 12 bit and 16 bit random bit sequence?
In Table 3 it gives the "XNOR form" and the length of the chain used to generate the random bit sequence. Is there a way that I might carry out simulation using this information in C language or otherwise?

The mixture of DFFs and Synchronous RAM blocks is confusing me as it does not match a simple shift register chain with XOR gates in feedback as used with CRC checking hardware. The reason I expect this to match CRC hardware is that both have concept of a polynomial that decides where we tap to get the feedback bits.
Edit:
I would be grateful if someone can clarify the relationship between Tables 1 & 2 and the Table 3. Why are there only 4 DFFs each time and they are providing address into some RAM blocks? That is now how shift registers work.

Justme · Answer

That is just an example how to parallelize 1-bit wide and 32-bit deep shift register into an implementation that suits better for programmable logic devices, in this case 2-bit wide and 16-bit deep as an example, and then extends it to many bits wide and many bits deep register.

For 12-bit shift register, there's 144 different tap configurations to achieve a maximal length output, and for 16-bit shift register, there's 2048 different tap configurations to achieve a maximal length output. Just select a configuration from a list, the Xilinx appnote has examples for which taps to use. Each configuration of taps generates a different sequence. However, 12-bit and 16-bit configurations are not that widely used, as they require four feedback taps. 11-bit, 15-bit and 17-bit registers only need two taps for feedback.

Of course, it's exactly the same code as calculating a CRC, except you are feeding no data in and let the shift register feed itself back. It seems that the XNOR configuration has exact same taps as the usual Galois configuration, where you just XOR with the polynomial. A 32-bit integer is a 32-bit shift register, so even if you use code for CRC32 algorithm, you will get a maximal length pseudorandom bitstream with 2^32-1 bits. As long as the shift register is initialized to something that is non-zero.

Don't think about the RAM blocks, unless you must implement this on a PLD of some sort.

How to use LFSR to generate random numbers as per this Xilinx application note?

One Answer

Add your own answers!

Ask a Question