I found an example below of a linear feedback shift register program on Wikipedia but I didn't understand it at all :
#include <stdint.h>
#include <stdio.h>
unsigned lfsr_fib()
{
uint16_t start_state = 0xACE1u; /* Any nonzero start state will work. */
uint16_t lfsr = start_state;
uint16_t bit; /* Must be 16-bit to allow bit<<15 later in the code */
unsigned period = 0;
do
{ /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) & 1u;
lfsr = (lfsr >> 1) | (bit << 15);
++period;
}
while (lfsr != start_state);
return period;
}
int main()
{
printf("%d\n", lfsr_fib());
return 0;
}
First, a tidbit about LFSRs. With an LFSR a rolling feedback is calculated that ultimately determines a single bit value. That value is then placed into the most-significant bit of the register after shifting the register down one bit. The two most important operations in the LFSR advance you posted are:
/* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) & 1u;
lfsr = (lfsr >> 1) | (bit << 15);
The bit shifts you see in the bit =
line correspond to the polynomial terms of corresponding exponents >= 1. Their series of pulls and XOR are what ultimately feed into the calculation of the final bit.
((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5))
16 14 13 11
That result is then fed into the lead bit by dropping it in after shifting the register down one bit:
lfsr = (lfsr >> 1) | (bit << 15);
When used with the proper primitive polynomial(s) (generation of which is beyond the scope of this text, but an intriguing investigation if you're up for it), this can generate a maximal period (all values are exhausted before the sequence begins repeating, save for zero, which is death to a basic LFSR, hopefully for obvious reasons). The code provided tests this by ensuring the original prime value does not occur again for 2^N-1, where N is the bit width of the LFSR. The example you provided uses a 16bit LFSR, and, when run, will print 65535, as expected. An eight bit version appears below:
unsigned lfsr_fib8()
{
uint8_t start_state = 0x01;
uint8_t lfsr = start_state;
uint8_t bit;
unsigned period = 0;
do
{ /* taps: 8 6 5 4 ; feedback polynomial: x^8 + x^6 + x^5 + x^4 + 1 */
bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 4)) & 1u;
lfsr = (lfsr >> 1) | (uint8_t)(bit << 7);
++period;
} while (lfsr != start_state);
return period;
}
This will produce 255, as expected. Finally, to your question, a 4 bit version. Here we have to get a little creative (but not much) since we have no intrinsic native type that is only 4 bits wide. That's ok. just make sure you only use the low nibble, and do NOT prime the start state with anything above 0x0F.
unsigned lfsr_fib4()
{
uint8_t start_state = 0x01;
uint8_t lfsr = start_state;
uint8_t bit;
unsigned period = 0;
do
{ /* taps: 4 1 ; feedback polynomial: x^4 + x + 1 */
bit = ((lfsr >> 0) ^ (lfsr >> 3)) & 1u;
lfsr = ((lfsr >> 1) | (uint8_t)(bit << 3)) & 0x0F;
++period;
} while (lfsr != start_state);
return period;
}
This will return 15, as expected.