Last time we took a look at linear feedback shift registers, or LFSRs, which produce pseudo random bits by shifting a buffer of them to the right, with the rightmost becoming both the output and the leftmost bit which being combined with a subset of the bits, known as taps, using an exclusive or operation.
We saw that despite looking completely different to the linear congruential generators that we covered a few posts ago they are in fact rather similar to them, albeit involving multiplication and remainder operations involving polynomials rather than integers.
Unfortunately, another thing that LFSRs have in common with linear congruential generators is that it is extremely difficult to set them up so that they generate sequences of bits that are as close to random as possible. Thankfully, there are those who've gone to the trouble of finding decent choices for the taps for us and so all that we need to concern ourselves with is implementing them, which we shall do in this post.
We saw that despite looking completely different to the linear congruential generators that we covered a few posts ago they are in fact rather similar to them, albeit involving multiplication and remainder operations involving polynomials rather than integers.
Unfortunately, another thing that LFSRs have in common with linear congruential generators is that it is extremely difficult to set them up so that they generate sequences of bits that are as close to random as possible. Thankfully, there are those who've gone to the trouble of finding decent choices for the taps for us and so all that we need to concern ourselves with is implementing them, which we shall do in this post.
Full text...