How to program LFSR in C programming langugage?
I wanted to build something to learn. I know theory of LFSR. So, I wanted to build https://www.cs.princeton.edu/courses/archive/spr19...
this program. But, I am totally confused/overwhelmed on this information. I have already read bit by bit, but still I can't connect those to the working of LFSR; especially the last part of generate(k). How do I make my brain more capable for doing programming?
- Robert JLv 72 months agoFavorite Answer
The LFSR routine just needs to take the XOR of the bits used for the shift register "taps" and feed that result back in to the register when it is shifted.
To my view, they are over-complicating it by using string; an unsigned int, long or double would normally be used
eg. Based the example in the link, you can extract the tap bits using bitwise AND:
unsigned int lfsr, a, b, r;
For each iteration; written for clarity not speed...
a = b = 0;
if(lfsr & 0x0400) // Test bit 11
a = 1;
if(lfsr & 0x0100) // Test bit 9
b = 1;
r = a ^ b; // Exclusive OR the two tap bits
lfsr <<= 1; // Shift the register one bit left
lfsr |= r; // OR the result of the xor, which is either 0 (no effect) or 1, which sets the low bit.
More complicated LFSRs such as used with CRC-16 and CRC-32 may exor the whole register with a value relating to the polynomial in use, and/or may use lookup tables to handle a byte or word at a time, rather than the very slow one-bit-at-a-time needed with a pure shift-register method.