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)?

CS4FN Advent – Day 6 – patterned bauble: tracing patterns in computing – printed circuit boards, spotting links and a puzzle for tourists

Welcome to Day 6 of the CS4FN Christmas Computing Advent Calendar – every day until Christmas we’ll post a little something about computer science. Some of it will even relate (…vaguely) to the picture on the advent calendar’s door.

Today’s picture is of a festive bauble with a pattern engraved on it. That obviously made us think of printed circuit boards. Read on to see why.

A brightly coloured (pink!) Christmas bauble, ready to go on a tree.

At the very end of this article you can see a list of all the previous Advent Calendar posts.

Printed Circuit Boards

Yesterday we looked at computers made of water, in which the flow of water (and where it ends up) let people do some quite advanced calculations. Today it’s the electrons that are doing the flowing… through tiny little copper channels.

Printed Circuit Boards (aka PCBs) contain and connect the bits that computers and electronic devices need to run properly. PCBs have two main functions: to act as a sort of ‘bookshelf’ for all the electronic components (such as transistors, sensors etc), but also to support electrical connections between those components so that electricity can flow through them and the device can work. Some of the components are soldered directly to the board, others are connected by being clipped into sockets that have previously been attached. A circuit board is generally only a few inches long with smaller ones for smaller (or simpler) devices – they have to fit inside after all.

They look like the image above and generally consist of a stiff flat board (which itself does not conduct electricity) and on that there’s a coating of copper foil which has had a pattern etched into it. Etching uses chemicals to ‘delete’ all the bits of copper that aren’t needed, leaving behind only the pattern that forms the correct connecting circuits.

Complete circuit

This next article was originally published on the CS4FN website.

Follow the circuit…

1. Kirchhoff’s famous circuit laws describe the conservation of charge and energy in electrical circuits. They form the basis for circuit design as well, leading to many a homework assignment working out the current at different places in a circuit. Their creator, physicist Gustav Kirchhoff, was born in the town of Koenigsberg in what is now Russia.

2. Koenigsberg sits on several islands originally connected by seven bridges. It was this town plan that helped mathematician Leonhard Euler to pose and solve the famous Seven Bridges of Koenigsberg Problem. It helped develop the useful mathematical area called graph theory.

3. Graph theory is used by engineers when building mobile phone networks. Your mobile phone finds the nearest base station and locks onto it to send and receive information. Researchers recently revealed a midget drone plane called WASP, built on the cheap with parts bought on the Internet. It could fly unseen over a city mimicking a ‘local tower’ to intercept phone messages and wi-fi data.

4. Wi-fi is a set of agreed standards that allow radio links between all manner of electronic gadgets. These worldwide rules are based around the idea of ‘frames’. Frames contain the data that is to be sent or received in a particular format. Devices have to know these rules of conversation to talk to each other. They range from asking nicely in the ‘association request frame’ if the receiver is ready, willing and able to connect, to the ‘association response frame’ where the receiver answers “yes” or “no”.

5. Yes or no is an example of a binary encoding: only two options exist. Many electronic devices these days use binary coding. The signal has only two possible values. That makes turning them mathematically into numbers and the subsequent calculations easier and more accurate. Analogue electronics, where voltage and currents can vary across a range of values are more difficult to design but are still useful in some applications. They can have surprising advantages. For example, before digital radio took over it was possible to build a working ‘crystal radio set’ using analogue techniques with simple household items like wire and a rusty nail. This radio was powered by the radio waves and didn’t need batteries.

6. Batteries store energy and many see them as a big unsolved problem of electronics. They are heavy, need space and charging, and when they run out your gadget stops. Researchers are now looking at using common everyday stuff like plastics and concrete to store the energy we need. Another idea is to use energy from our walking on the go. Whatever way energy is created and stored in the future, it will still swirl round the circuit obeying Kirchhoff’s laws.

GO TO 1!

Today’s puzzle

Instead of an electron whizzing around a circuit board imagine you’re a tourist guide looking after some guests visiting London. Your task is to get your group to visit each one of the visitor attractions listed in the printed circuit ‘map’ below, once (without revisiting it). Can you plan a route that does this? (The answer will be in tomorrow’s advent calendar ‘door’).

Note for parents and teachers: we have a classroom activity that features this puzzle and teachers can use this to talk about things like an introduction to algorithmic thinking, sequences, graphs / nodes / edges, representation and abstraction. Access The Tour Guide activity here (the image above comes from the free PDF which you can download on that page).

Answer to yesterday’s puzzle

Yesterday’s puzzle was about compressing information and the answer is a line from Charles Dickens’ A Christmas Carol – “When Scrooge awoke, it was so dark, that looking out of bed, he could scarcely distinguish the transparent window from the opaque walls of his chamber” which we shortened to “NG1 AMH5 IBEC2 84F6JKO 7JDLC93”. You can read the whole book here at Project Gutenberg.

Previous Advent Calendar posts