## Re: [stella] Pitfall! LFSR

 Subject: Re: [stella] Pitfall! LFSR From: Chris Wilkson Date: Mon, 3 Sep 2001 21:49:54 -0400 (EDT)
```On Mon, 30 Jul 2001, nj bloodline wrote:

> What is "random scene generation" when all the scenes are in a certain
> order?! There's full maps out on the net to Pifall!, so I'm assuming the
> screens are always in the same order.

A Linear Feedback Shift Register (LFSR) is a type of pseudo-random number
generator.  Most pseudo-random number generators take a starting value,
called a "seed" and will produce a sequence of numbers based on an algorithm
and that number.

For instance, if I had a 3-bit register that always shifted to the right
and loaded the XOR of bit 1 and bit 0 into bit 2, the following sequence
results:

OLD -> NEW
---    ---
0       0
1       4
2       5
3       1
4       2
5       6
6       7
7       3

If I preload the register with a given seed number the following sequences
result:

SEED  SEQUENCE
----  --------
1     1, 4, 2, 5, 6, 7, 3, 1 (repeats)
6     6, 7, 3, 1, 4, 2, 5, 6 (repeats)
3     3, 1, 4, 2, 5, 6, 7, 3 (repeats)

The sequence is always the same and it always repeats. It just starts in
a different position each time.  The one special case is zero.  If the
LFSR is loaded with zero, its output will be zero forever.

This is a pretty simple example.  It isn't reversible (try it and see
what happens) but the sequence looks random (until it starts repeating).

Hope that helps!

-Chris

-
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/

```