What goes on inside a microchip is something an electrical engineer would be interested in, but we only need to know that there are places in the microchip where the voltage of the electrical current can be measured (crudely) as either being high or low. When talking about what is happening in a microchip it is convenient to talk about 1's and 0's standing for high and low voltages respectively. Actually we use 1's and 0's to stand for more than one thing ... let me explain. A place in the microchip where the voltage can be measured is called a * register*, and the register can be in one of two "

state | impulse | new state |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

0 + 0 = 0 |

0 + 1 = 1 |

1 + 0 = 1 |

1 + 1 = 0 |

If we use these addition rules and the usual rules for multiplication of 0 and 1, we get what is called * binary arithmetic* (or mod 2 arithmetic). I should point out that while we use the symbols 0 and 1 according to these rules to describe what is happening in a microchip, we are not trying to describe what is physically happening in the microchip. There no objects moving around in the microchip that correspond to 0's and 1's. This is just an easy way to think about the way the microchips work which doesn't give wrong answers. An electrical engineer would laugh at my descriptions in the next section because what I describe is so far from what really happens, but that doesn't really matter. What does matter is the fact that the descriptions I give will work to help me answer the questions about what (but not how) the microchip is doing what it does.
Microchips are designed so that they do something (often very complicated things). In order to see how binary arithmetic is used in describing what a microchip does, we need to examine a particular task that a microchip can be designed to do.

Look at the sequences 011011011011... and 01010110101011... . In the first sequence we see that after the first 011 we get another repeat of 011 and yet another one after that and so on. Not every sequence of 0's and 1's has to have a repeating part, but for those that do we call the length of the smallest repeating part the ** period** of the sequence. The first sequence has period 3. The second sequence starts out with 01 then 01 and then 01, so we might think that 01 is the repeating part and the sequence has period 2 - but this would not be right since the next term of the sequence is a 1 and so could not be the start of another 01. In fact, 0101011 is the repeating part here and the period is 7.

Find the smallest repeating part and the period for the following sequences:

- 00110011001100110011...
- 01110011100111001110...
- 10011001100110011001...

There are two sequences with period 1, namely 000000... and 111111... . There are also two sequences with period 2, we have 01010101... and 10101010... There are six sequences of period 3 (001001001..., 010010010010..., 100100100..., 011011011..., 101101101..., and 110110110...). How many sequences of period 4 do you think there are? (Hint, be careful not to count sequences which have a smaller period than 4 even though you made them up to have period 4) [*answer*].

As I have already said, not every sequence has to repeat, but every sequence that is produced by a computer does have to repeat. This is a fundamental limitation of computers and can not be gotten around by new designs and fancier programming. This is unfortunate since there are many applications and computations for which a non-ending supply of 0's and 1's having no repeating pattern is needed. The best that we can do for these applications is to construct microchips which produce sequences of 0's and 1's which have a very, very large period. We will look at one simple way to design such a microchip and figure out what the period of the output sequence is.

Consider this schematic diagram :

At the next tick of the clock the whole process is repeated:

If we let this go for a couple of more ticks of the clock the output would look like ...1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 ... and this sequence has repeating part 1 0 1 0 0 1 1 and so period 7.

When we take this schematic diagram and make an actual microchip which does what the diagram does, we call the microchip a "* Linear Feedback Shift Register*". This mouthful will often be abbreviated to

Find the first 22 values of the output of the LFSR when you start with the following seeds (starting values for the registers):

- 001
- 111
- 110

Looking at the answers of Exercise 2, you might observe that while they all had different repeating parts, each had the same period (7). Now look at the long string of output right under the last set of diagrams. You find the repeating part of the answers to Exercise 2 inside this long string.

1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 |

1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 |

1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 |

1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 |

In fact, there are seven possible seeds (we are not counting 0 0 0 as a seed) and each of them gives a repeating part of size 7 as in Exercise 2, and each of these repeating parts can be found in the long string above. In the table below I have shown the seeds in red and the repeating parts in color (red and blue).

1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 |

1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 |

1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 |

1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 |

1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 |

1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 |

1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 |

Not all LFSR's behave this way. Let's call the LFSR that we have been dealing with "**LFSR-3A**", and now we'll construct another one which we will call "**LFSR-3B**". This one also has 3 registers but it's adder adds up what is contained in all three registers. Schematically, LFSR-3B looks like this:

Find the period and the repeating part of the output of LFSR-3B when you start with the following seeds:

- 101
- 001
- 110
- 111

The difference between LFSR-3A and LFSR-3B is that for LFSR-3A, you get the same output string (or as we sometimes like to say, * output stream*) no matter what the seed is - it just starts in a different place depending on the seed, while LFSR-3B produces three different output streams, namely, ...1 0 1 0 1 0 1 0 1 0..., and ...1 0 0 1 1 0 0 1 1 0 0 1 ... and ... 1 1 1 1 1 1 1 1 ... . These streams have period 2, period 4 and period 1 respectively. You know that these are all you can get because each of the 7 possible seeds can be found in one and only one of these three streams. [See if you can find each of them in some stream.]

The two examples that we have looked at both had three registers, but we could have as many registers as we like and also, we can decide to have the adder look at as many or as few (but at least two and always including the first) registers as we desire. These are the decisions we make when we design a microchip. We would like to design more microchips that behave like LFSR-3A since these would have the longest periods. But before we get into that, we need to consider how many seeds we have and what they are when there are more than three registers.

To find out what the seeds are (and how many there are) for different numbers of registers, we'll look at a "* binary bush*". This bush has several levels and in the diagram below we will only draw 5 levels, but the bush can grow larger if you like. The bush consists of a lot of "branches" each of which is labeled with either a 0 or a 1. In going from one level to the next higher level, each branch gives rise to two branches, one labeled with a 1 and the other labeled with a 0 (and I have always put the 0 label on the left branch). The very bottom of the bush (level zero) is a "root" and there are just two branches coming from it (one with a 0 and the other with a 1). This is what our bush looks like:

Each "dot" in the bush (except the root) represents a seed. To see which seed is represented, start at the dot and follow the branches, always going down until you get to the root. As you follow this path of branches read the labels, in order, on the branches and this is the seed. For instance, look at the dot in the 7^{th} position from the right on level 4. The branch going down from this dot is labeled 1. From the dot on level 3 that this branch went to, you go down again with a branch labeled 0. Then another branch labeled 0 and finally a branch labeled 1 to get to the root. The seed represented by the original dot is thus **1001** (this is a seed for 4 registers). It is also true that every possible seed is represented by a single dot in the bush. If you have a seed you can find the dot that represents it by starting at the root and following the branches upward using the labels that you get from the seed - ** by reading from right to left**. So, for the seed 011, start at the root and go up the branch labeled 1, then the branch labeled 1 and finally the branch labeled 0. This will get us to the dot on level 3 that is 2

Find the dots in the binary bush which represent the following seeds:

- 101
- 0011
- 11010
- 111

Now that we know that seeds are represented by dots in the binary bush, we can count seeds by counting dots. Any seed for, say 5 registers, is going to be represented by a dot on level 5 (think about how you find the dot by looking at the seed). So, all the dots on a particular level represent seeds for a number of registers equal to the level number. Thus, a seed for 7 registers will be represented by a dot on level 7. There is only one thing to be careful about in this relationship between dots and seeds. The dots at the left end of each level represent "seeds" that consist only of 0's, and we don't consider these to be proper seeds. [If you were wondering, we don't just erase these dots from the bush because we need them to get to higher dots which are not representing all 0 seeds.] We can now count the number of seeds in each level. We see that there are two dots in level 1 and 4 dots in level 2. In fact, whenever we go up one level we double the number of dots. So, level 3 has 2 × (number of dots in level 2) = 2 × 4 = 8 = 2^{3} dots and level 4 has 2 × (number of dots in level 3) = 2 × 8 = 16 = 2^{4} dots. The number of dots which represent seeds on each level is one less than the number of dots on that level, so the number of seeds of 3 registers = number of seeds represented on level 3 of the binary bush = 8 - 1 = 7.

How many seeds are there for a LFSR which has:

- 5 registers
- 6 registers
- 2 registers

To write down all the seeds for a given number of registers, go to the level of the binary bush of the number of registers and for each dot on that level except for the leftmost one, read the seed for that dot. Go to level 3 in the diagram of the binary bush and read off the 7 seeds.

Find the seeds which are represented by the dot which is:

- on level 4, 5
^{th}from the right - on level 5, 15
^{th}from the right - on level 4, 10
^{th}from the right

When we looked at LFSR-3A we noticed that only one output stream was produced and it was a sequence with period 7, the largest period that we found with 3 registers. But 7 is also the total number of proper seeds for three registers. For any number of registers (not just 3), if the period of the output stream is the maximum number of proper seeds for that number of registers, then there can only be one output stream and you can not have any larger period no matter which registers the adder looks at. Since the output stream is completely determined for a given seed, each seed that you can find which starts in a repeating part of the stream will give the same output stream. The number of these seeds is the period of the sequence. If the period is smaller than the number of seeds then there will be some seeds that are not found in the output streams of the others. These, in turn, can be used to start different output streams, so we will get more than one output stream, and this looks like the behavior of LFSR-3B.

Now you can design your own LFSR's and see how they perform. First, decide how many registers you want to use. Then, pick which registers the adder is going to look at. For this choice you must pick at least two registers, and one of the choices must be the first register. There is a way to decide whether such a LFSR will act like LFSR-3A or LFSR-3B, but this involves some advanced technical mathematics that I can't go into. However, we can just design a LFSR and then pick any seed to start. If the period of the output stream for this seed is less than the maximum (2^{number of registers} - 1) then the LFSR will behave like LFSR-3B, otherwise like LFSR-3A.

Design your own LFSR with 4 registers and :

- find one that behaves like LFSR-3B
- find one that behaves like LFSR-3A

Answer to question

There will be 12. They are 0001, 0010, 0011, 0100, 0110, 0111, 1000, 1001, 1011, 1100, 1101, and 1110.

Answers to Exercise 7 There will be many answers to these questions, here are two:

Answers to Exercise 6

- 10 period 2
- 0011 period 4
- 1100 period 4
- 1 period 1

Answers to Exercise 5

- 31
- 63
- 3

Answers to Exercise 4

- Level 3, 3
^{rd}from right - Level 4, 4
^{th}from right - Level 5, 21
^{st}from right - Level 3, 1
^{st}on right

Answers to Exercise 3

- 10 period 2
- 0011 period 4
- 1100 period 4
- 1 period 1

Answers to Exercise 2

- 0011101001110100111010
- 1110100111010011101001
- 1101001110100111010011

Answers to Exercise 1

- 0011 period 4
- 01110 period 5
- 1001 period 4