Lego computer science: Gray code

Continuing a series of blogs on what to do with all that lego scattered over the floor: learn some computer science…how might we represent numbers using only two symbols?

We build numbers out of 10 different symbols: our digits 0-9. Charles Babbage’s victorian computer design represented numbers using the same decimal system (see Part 4: Lego Computer Science: representing numbers using position). That was probably an obvious choice for Babbage, but as we have already seen, there are lots of different ways numbers could be represented.

Modern computers use a different representation. The reason is they are based on a technology of electrical signals that are either there or not, switches that are on or off. Those two choices are used as two symbols to represent data. It is as though all data will be built of two lego coloured blocks: red and blue, say.

A naive way of using two different symbols (red and blue blocks) to represent numbers.

How might that then be done? There are still lots of ways that could be chosen.

Count the red blocks

One really obvious way would be to just pick one of the two coloured bricks (say red) to mean 1 and then to represent a number like 2 say you would have 2 of that colour block, filling the other spaces allocated for the number with the other colour. So if you were representing numbers with storage space for three blocks, two of them would be red and one would be blue for the number 2. All would be red for the number 3.

This is actually just a variation of unary, that we have seen earlier, just with a fixed amount of storage. It isn’t a very good representation as you need lots of storage space to represent large numbers because it is not using all possible combinations of the two symbols. In particular, far more numbers can be represented with a better representation. In the above example, 3 places are available on the lego base to put the blocks we are using and we have been able to represent 4 different numbers (0 to 3). However, information theory tells us we should be able to store up to 8 different numbers in the space, given two symbols and using them the right way, with the right representation.

A random code for numbers

How do we use all 8 possibilities? Just allocate a different combination to each pattern with blocks either red or blue, and allocate a different number to each pattern. Here is one random way of doing it.

A code for numbers chosen at random

Having a random allocation of patterns to numbers isn’t a very good representation though as it doesn’t even let us count easily. There is no natural order. There is no simple way to know what comes next other than learning the sequence. It also doesn’t easily expand to larger numbers. A good representation is one that makes the operations we are trying to do easy. This doesn’t.

Gray Code

Before we get to the actual binary representation computers use, another representation of numbers has been used in the past that isn’t just random. Called Gray code it is a good example of choosing a representation to make a specific task easier. In particular, it is really good if you want to create an electronic gadget that counts through a sequence.

Also called a a reflected binary code, Gray code is a sequence where you change only one bit (so the colour of one lego block) at a time as you move to the next number.

If you are creating an electronic circuit to count, perhaps as an actual counter or just to step through different states of a device (eg cycling through different modes like stopwatch, countdown timer, normal watch), then numbers would essentially be represented by electronic switches being on or off. A difficulty with this is that it is highly unlikely that two switches would change at exactly the same time. If you have a representation like our random one above, or actual binary, to move between some numbers you have to change lots of digits.

You can see the problem with lego. For example, to move from 0 to 1 in our sequence above you have to change all three lego blocks for new ones of the other colour. Similarly, to go from 1 to 2 you need to change two blocks. Now, if you swap one block from the number first and then the other, there is a point in time when you actually have a different (so wrong) number! To change the number 1 to 2, for example, we must swap the first and third bricks. Suppose we swap the first brick first and then the third brick. For a short time we are actually holding the number 3. Only when we change the last brick do we get to the real next number 2. We have actually counted 1, 3, 2, not 1, 2 as we wanted to. We have briefly been in the wrong state, which could trigger the electronics to do things associated with that state we do not want (like display the wrong number in a counter).

Mistaken counting using our random representation. To get from 1 to 2 we need to swap the first and third brick. If we change the first brick first, there is a brief time when our number has become three, before the third brick is changed. We have counted 1, 3, 2 by mistake.

Just as it is hard to swap several blocks at precisely the same time, electronic switches do not switch at exactly the same time, meaning that our gadget could end up doing the wrong thing, because it briefly jumps to the wrong state. This led to the idea of having a representation that used a sequence of numbers where only one bit of the number needs to be changed to get to the next number.

A Gray code in lego bricks. To move from one number in the sequence to the next, you only need to change one lego brick.

There are lots of ways to do this and the version above is the one introduced by physicist Frank Gray. Gray codes of this kind have been used in all sorts of situations: a Gray code sequence was used to represent characters in Émile Baudot’s telegraph communication system, for example. More recently they have been used to make it easier to correct errors in streams of data in digital TV.

Computers do not need to worry about this timing problem of when things change as they use clocks to determine when values are valid. Data is only read when the tick of the clock signal says it is safe too. This is slower, but gives time for all the digital switches to settle into their final state before the values are read, meaning faulty intermediate values are ignored. That means computers are free to use other representations of numbers and in particular use a binary system equivalent to our decimal system. That is important as while Gray code is good for counting, and stepping through states, amongst other things, it is not very convenient for doing more complicated arithmetic.

This post was funded by UKRI, through grant EP/K040251/2 held by Professor Ursula Martin, and forms part of a broader project on the development and impact of computing.

Lego Computer Science

Part of a series featuring featuring pixel puzzles,
compression algorithms, number representation,
gray code, binaryand computation.

Lego Computer Science

Part 1: Lego Computer Science: pixel picture

Part 2: Lego Computer Science: compression algorithms

Part 3: Lego Computer Science: representing numbers

Part 4: Lego Computer Science: representing numbers using position

Part 5: Lego Computer Science: Gray code

Part 6: Lego Computer Science: Binary

Part 7: Lego Computer Science: What is computation (simple cellular automata)?

6 thoughts on “Lego computer science: Gray code

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s