Close

Linear-feedback shift register instead of Linear congruential generator

A project log for Simon game with ATtiny13

Full-featured clone of a famous “Simon” game for training your visual and acoustic memory. Electronic kit simple enough for beginners.

VojtakVojtak 01/01/2017 at 19:320 Comments

In a discussion below the project review [RÖB] asked if a linear congruential generator is better that a linear feedback shift register or how are they different.

So I have tried an example for the 16-bit maximal-period Galois LFSR from Wikipedia. The result is really not bad as you can see in the pictured data (only a subtle vertical pattern can be noticed):

The Wikipedia example was slightly modified to work with seed = 0 (period of this LFSR is only 65535):

uint8_t simple_random4() { // using LFSR instead of LCG
  for (uint8_t i = 0; i < 2; i++) { // we need two random bits
    uint8_t lsb = ctx & 1; // Get LSB (i.e., the output bit)
    ctx >>= 1; // Shift register
    if (lsb || !ctx) { // output bit is 1 or ctx = 0
      ctx ^= 0xB400; // apply toggle mask
    }
  }
  return ctx & 0b00000011; // remainder after division by 4
}

Because ATtiny13 can't use MUL instruction but linear congruential generator uses a multiplication, the linear-feedback shift register is more effective and uses 22 bytes less space in flash memory (modified source and HEX file are in the download section). So maybe I can add some additional feature in the future.

Discussions