## Binary Arithmetic and Microchips

There is little doubt that the technology based on microchips keeps growing and getting better year after year. About 60 years ago the most advanced technologies, like radio, television and computers, were based on vacuum tubes. These were replaced by transistors, much smaller and more reliable. Because transistors were so much easier to use, they were used in many more ways than the vacuum tubes that they replaced. Along with this push to use the transistors in more places came a desire to make them smaller, so that they could be used for even more applications. This drive to make the transistors smaller eventually led to the development of microchips which contain entire circuits, including transistors, in spaces that can be microscopically small.

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 "states", either high voltage or low voltage. We say that the "register contains a 1 or 0." Each register is part of a circuit and the circuit could have current (let's call this an "impulse") or not. We will again use 0's and 1's to indicate whether the circuit does not or does have an impulse. When the circuit has an impulse, the state of the connected register will change, otherwise the state stays the same. This can all be summarized in the following table:

stateimpulsenew state
000
011
101
110
Now we can blur the distinction between states and impulses and use this table to define an "addition table" for the symbols 0 and 1:

 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.

## Linear Feedback Shift Registers

One task that we may design a microchip to carry out is to produce (output) a sequence of 0's and 1's that is as long as possible before it starts to repeat itself. We will consider what such a microchip can be used for in the next section.

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:

1. 00110011001100110011...
2. 01110011100111001110...
3. 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 :

This diagram shows three registers labeled r1, r2 and r3 (and these can contain only 0's and 1's). The big box at the top containing the "+" sign is called the Adder. It looks at (but does not change) what is in registers r1 and r3 and adds them (using binary arithmetic). This sum will be put into register r3. Here is how this "microchip" works. There is a clock working in the background which keeps everything working in the right order. We will describe what happens at each tick of the clock. Assume that the chip has been working for a while so that there are numbers in all the registers, in our example we will have a 1, 0 and 1 in the three registers respectively. At the tick of the clock, the adder adds the values in r1 and r3 (1 + 1 = 0). The sum (0) is pushed into r3 and the value that was in r3 (1) is pushed into r2. Similarly, what was in r2 (0) is pushed into r1 and what was in r1 (1) becomes part of the output. This looks like this:

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 LFSR. The LFSR in our example was already running so that all the registers would be filled. In practice, to start an LFSR we must supply the starting values for the registers. These starting values are called the "seed" and putting them into the registers is called "seeding the LFSR". Any set of values can be used as a seed, but if you use all 0's as a seed, the only output you will get is all 0's.

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

1. 001
2. 111
3. 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:

1. 101
2. 001
3. 110
4. 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 7th 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 2nd from the right.

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

1. 101
2. 0011
3. 11010
4. 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 = 23 dots and level 4 has 2 × (number of dots in level 3) = 2 × 8 = 16 = 24 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:

1. 5 registers
2. 6 registers
3. 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:

1. on level 4, 5th from the right
2. on level 5, 15th from the right
3. on level 4, 10th 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 (2number of registers - 1) then the LFSR will behave like LFSR-3B, otherwise like LFSR-3A.

Design your own LFSR with 4 registers and :

1. find one that behaves like LFSR-3B
2. find one that behaves like LFSR-3A

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:

1. 10 period 2
2. 0011 period 4
3. 1100 period 4
4. 1 period 1
1. 31
2. 63
3. 3
1. Level 3, 3rd from right
2. Level 4, 4th from right
3. Level 5, 21st from right
4. Level 3, 1st on right
1. 10 period 2
2. 0011 period 4
3. 1100 period 4
4. 1 period 1