linear feedback shift register pin sequence

The LFSR I decided to implement looks thus: The game will probably begin to feel degenerated after 15 minutes of gameplay or so.

The player will begin to see repetitions after 16 games with 50% probability, which isn't that great. So it must be fine I guess.Ĭomparing it to an 8 bit LFSR, the number of possible sequences is 256. Moreover, I personally get bored after 20 games at most, usually far less. That result is good enough for me - I don't suspect that any user will play that many game and also remember the sequence behind that. How long will it take until the player would play the same game twice? According to the birthday paradox, after about 256 games there is a 50% probability that some games had identical sequences.

It means that all the possibilities for the first 8 LEDs are possible (apart from 8 consecutive LEDS), but the ninth LED and beyond will be determined by these first 8 LEDs in a deterministic way. Are 16 bits enough?Īnyway, I've chosen to use an 16-bit LFSR, where each LED value is two consequent bits of the LFSR. Stein, whose 8th chapter offers a different look on the subject of such maximal bit sequences, concerning medieval indian poetry rhythms. If the taps are chosen in a certain way, one can get the longest stream possible, which for an LFSR of n bits is 2^n - 1 states.įor further read, I can recommend the book ' mathematics - the man made universe' by Sherman k. But when loaded with anything else, a sequence of 1s and 0s will flow out.Īn LFSR is a finite automaton, thus can only output a finite stream of bits before it repeats itself. All LFSRs output a constant stream of 0s when initially loaded with zeros. These bits are usually referred to as the LFSR taps.įor an LFSR, initial state matters. The idea is using a shift register of certain length, and shift in the XOR of several bits from the shift register itself (hence the feedback). One such algorithm is called a Linear Feedback Shift Register, or LFSR in short. Introducing pseudorandomness! We can generate a sequence that looks seemingly random to the unsuspecting eye, but is generated using some sort of deterministic algorithm. This is just a game, not some crazy bitcoin e-wallet that depends on true randomness to securely store all your money or something.

Generating real random values for the LEDs is possible, though may be somewhat cumbersome as it means constantly generating random variables and storing them. We need to create a random sequence to display to the player.

Linear feedback shift register pin sequence