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:

  1. 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.
  2. What would be the structure to implement 12 bit and 16 bit random bit sequence?
  3. 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.


1 Answer 1

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

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

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

  • \$\begingroup\$ Could you kindly elaborate on what you mean by paralellize in (1)? I shall be implementing this on an FPGA. \$\endgroup\$
    – gyuunyuu
    Jul 22, 2020 at 19:56
  • 1
    \$\begingroup\$ Well, I am not an expert on this, but if you do a 1-bit wide LFSR, and want a new random byte out, you must give the LFSR 8 clock cycles to generate 8 random bits for the byte. It is possible to rewrite the algorithm so that you get all 8 bits out in one clock cycle. Basically, same as using a lookup table in software to update a CRC value for single byte input, instead of updating the CRC value for one bit a time for all 8 bits of a byte. \$\endgroup\$
    – Justme
    Jul 22, 2020 at 20:05
  • \$\begingroup\$ Ok, the use of RAMs makes more sense now. Is there reason for having exactly 4 DFFs each time and also, why do these DFFs provide an address of all things? The RAMs should be merely implementing shift registers and shift registers do not need address input. \$\endgroup\$
    – gyuunyuu
    Jul 23, 2020 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.