OK you can click on almost anything. The main things to click on are the little circles underneath the boxes. These are the multipliers and you need to have some of them turned on before the shift register will do anything. Next, make sure you click on at least one of the square boxes along the top (the cells). You need to have some of them turned on too. The "begin" button initializes all the variables to the values that you have chosen. Click on it before you start. The "step" button runs the thing one step at a time, which is the best way to learn how it works. But you can click on the "run" button to have it work automatically. This is more fun if you change the "size" to about 14 pixels, and change the "length" to about 50 and change the "speed" to about 50 and then hit run. The machine works quickly and the output box fills up with pseudo-random bits, and it's all free! For a different experience, click on the FCSR button to change it into a feedback with carry shift register, and try to figure out what it's doing by clicking on the "step" button again and again. It's not hard (and it's explained below).

A linear feedback shift register (LFSR) consists of cells and multipliers. The cells (square boxes) are lined up in a row across the top; each cell is connected to a multiplier (circle) beneath it. Normally the contents of each cell or multiplier is 0 or 1. In this applet, a 1 is represented by a red dot, and a 0 is represented by an empty cell (or multiplier). You can change the contents of any cell or multiplier by clicking on it.

Typically you choose the multipliers according to a carefully worked out scheme, but almost anything will give an interesting result. Then you choose an initial state for the cells (by clicking on them). To run the shift register, click on the "step" button repeatedly.

Here is what happens. The big long box along the bottom is an adder. It multiplies the contents of each cell (0 or 1) with the contents of the multiplier (0 or 1) beneath it and adds these numbers up. If the result is even it keeps a 0 (no red dot); if the result is odd then it keeps a 1 (red dot in long box). Then, when the "step" button is clicked, the contents of every cell moves to the right by one step, the contents of the long adder box on the bottom is moved into the leftmost cell, and a new value for the adder is determined. That's it!

You can change the number of cells by clicking on "length", clearing out the text frame, and putting in your new number. (The applet is set to start with 10 cells.) You can change the size of the cells by clicking on the "size" button. The initial size is 40 pixels per box. It is possible to set up a shift register with 100 cells and watch it work by making the box size around 7 pixels.

The feedback with carry register (FCSR) works in almost the same way, except there is a new box on the left, the "memory" box. The memory box contains an integer which is not necessarily just a 0 or a 1. In this machine, the adder works a little differently. The contents of each cell is multiplied with the multiplier beneath it and these numbers are added up, as before. However, the contents of the memory is also added, and the resulting sum is displayed in the long adder box on the bottom. At any given moment, this is what you will see in the FCSR: the contents of the adder at the bottom should be equal to the memory + the sum of the products (cells)*(multipliers).

When the "step" button is pressed, all cell contents move one step to the right. The contents of the adder now determines the new contents of the leftmost cell and the memory as follows. The leftmost cell receives the "sum" modulo 2. (That is, it receives a 0 if this sum was even; a 1 if this sum was odd.) Next, the "sum" is divided by 2 (throwing away any remainder) and this new value is placed in the memory. Finally, the next value of the "sum" is calculated as before: memory + (cells)*(multipliers).

It is initially set to 0, but you can change the memory by clicking on the memory box itself (in the SWING version) or by clicking on the "memory" button (in the JAVA 1.1 version). There is a theorem that says the "memory" never exceeds the number of nonzero multipliers. Or maybe twice this; I've forgotten at the moment. Even if you start with a huge memory value, say, by putting 100 into the memory box, it will quickly drop and then hover around between 0 and the number of nonzero multipliers.

The amazing thing about these gadgets is that such a simple rule of operation can result in extremely complex behavior. Moreover their behavior can be analyzed, but the analysis of the two machines (LFSR and FCSR) is completely different. It is not difficult to come up with similar architectures that are almost impossible to analyze. If you would like to read more, you can check out the paper I wrote with Andy Klapper,