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.
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.
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.
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).
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.
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.
Continuing a series of blogs on what to do with all that lego scattered over the floor: learn some computer science…how do we represent numbers and how is it related to the representation Charles Babbage used in his design for a Victorian steam-powered computer?
We’ve seen there are lots of ways that human societies have represented numbers and that there are many ways we could represent numbers even just using lego. Computers store numbers using a different representation again called binary. Before we get to that though we need to understand how we represent bigger numbers ourselves and why it is so useful.
Our number system was invented in India somewhere before the 4th century. It then spread, including to the west, via muslim scholars in Persia by the 9th century, so is called the Hindu-Arabic numeral system. Its most famous advocate was Muḥammad ibn Mūsā al-Khwārizmī. The word algorithm comes from the latin version of his name because of his book on algorithms for doing arithmetic with Hindu-arabic numbers.
The really clever thing about it is the core idea that a digit can have a different value depending on its position. In the number 555, for example, the digit 5 is representing the number five hundred, the number fifty and the number five. Those three numbers are added together to give the actual number being represented. Digit in the ‘ones’ column keep their value, those in the ‘tens’ column are ten times bigger, those in the ‘hundreds column a hundred times bigger than the digit, and so on. This was revolutionary differing from most previous systems where a different symbol was used for bigger number, and each symbol always meant the same thing. For example, in Roman numerals X is used to mean 10 and always means 10 wherever it occurs in a number. This kind of positional system wasn’t totally unique as the Babylonians had used a less sophisticated version and Archimedes also came up with a similar idea, those these systems didn’t get used elsewhere.
In the lego representations of numbers we have seen so far, to represent big numbers we would need ever more coloured blocks, or ever more different kinds of brick or ever bigger piles of bricks, to give a representation of those bigger numbers. It just doesn’t scale. However, this idea of position-valued numbers can be applied whatever the representation of digits used, not just with digits 0 to 9. So we can use the place number system to represent ever bigger numbers using our different versions of the way digits could be represented in lego. We only need symbols for the different digits, not for every number, of for every bigger numbers.
For example, if we have ten different colours of bricks to represent the 10 digits of our decimal system, we can build any number by just placing them in the right position, placing coloured bricks on a base piece.
Numbers could be variable sized or fixed size. If as above we have a base plate, and so storage space, for four digits then we can’t represent larger numbers than 9999. This is what happens with the way computers store numbers. A fixed amount of space is allocated for each number in the computer’s memory, and if a number needs more digits then we get an “overflow error” as it can’t be stored. Rockets worth millions of pounds have exploded on take-off in the past because a programmer made the mistake of trying to store numbers too big for the space allocated for them. If we want bigger numbers, we need a representation (and algorithms) that extend the size of the number if we run out of space. In lego that means our algorithm for dealing with numbers would have to include extending the grey base plate by adding a new piece when needed (and removing it when no longer needed). That then would allow us to add new digits.
Unlike when we write numbers, where we write just as many digits as we need, with fixed-sized numbers like this, we need to add zeros on the end to fill the space. There is no such thing as an empty piece of storage in a computer. Something is always there! So the number 123 is actually stored as 0123 in a fixed 4-digit representation like our lego one.
Charles Babbage made use of this idea when inventing his Victorian machines for doing computation: had they been built would have been the first computers. Driven by steam power his difference engine and analytical engine were to have digits represented by wheels with the numbers 0-9 written round the edge, linked to the positions of cog-like teeth that turned them.
Wheels were to be stacked on top of each other to represent larger numbers in a vertical rather than horizontal position system. The equivalent lego version to Babbage’s would therefore not have blocks on a base plate but blocks stacked on top of each other.
In Babbage’s machines different numbers were represented by their own column of wheels. He envisioned the analytical engine to have a room sized data store full of such columns of wheels.
So Babbage’s idea was just to use our decimal system with digits represented with wheels. Modern computers instead use binary … bit that is for next time.
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.
Continuing a series of blogs on what to do with all that lego scattered over the floor: learn some computer science…what does number representation mean?
We’ve seen some different ways to represent images and how ultimately they can be represented as numbers but how about numbers themselves. We talk as though computers can store numbers as numbers but even they are represented in terms of simpler things in computers.
But first what do we mean by a number and a representation of a number? If I told you to make the numbers 0 to 9 in lego (go on have a go) you may well make something like this…
But those symbols 0, 1, 2, … are just that. They are symbols representing numbers not the numbers themselves. They are arbitrary choices. Different cultures past and present use different symbols to mean the same thing. For example, the ancient Egyptian way of writing the number 1000 was a hieroglyph of a water lily. (Perhaps you can make that in lego!)
What really are numbers? What is the symbol 2 standing for? It represents the abstract idea of twoness ie any collection, group or pile of two things: 2 pieces of lego, 2 ducks, 2 sprouts, … and what is twoness? … it is oneness with one more thing added to the pile. So if you want to get closer to the actual numbers then a closer representation using lego might be a single brick, two bricks, three bricks, … put together in any way you like.
Another way would to use different sizes of bricks for them. Use a lego brick with a single stud for 1, a 2-stud brick for two and so on (combining bricks where you don’t have a single piece with the right number of studs). In these versions 0 is the absence of anything just like the real zero.
Once we do it in bricks it is just another representation though – a symbol of the actual thing. You can actually use any symbols as long as you decide the meaning in advance, there doesn’t actually have to be any element of twoness in the symbol for two. What other ways can you think of representing numbers 0 to 9 in lego? Make them…
A more abstract set of symbols would be to use different coloured bricks – red for 1, blue for 2 and so on. Now 0 can have a direct symbol like a black brick. Now as long as it is the right colour any brick would do. Any sized red brick can still mean 1 (if we want it to). Notice we are now doing the opposite of what we did with images. Instead of representing a colour with a number, we are representing a number with a colour.
Here is a different representation. A one stud brick means 1, a 2-stud brick means 2, a square 4 stud brick means 3, a rectangular 6 stud brick means 4 and so on. As long as we agreed that is what they mean it is fine. Whatever representation we choose it is just a convention that we have to then be consistent about and agree with others.
What has this to do with computing? Well if we are going to write algorithms to work with numbers, we need a way to store and so represent numbers. More fundamentally though, computation (and so at its core computer science) really is all about symbol manipulation. That is what computational devices (like computers) do. They just manipulate symbols using algorithms. We will see this more clearly when we get to creating a simple computer (a Turing Machine) out of lego (but that is for later).
We interpret the symbols in the inputs of computers and the symbols in the outputs with meanings and as a result they tell us things we wanted to know. So if we key the symbols 12+13= into a calculator or computer and it gives us back 25, what has happened is just that it has followed some rules (an algorithm for addition) that manipulated those input symbols and made it spew out the output symbols. It has no idea what they mean as it is just blindly following its rules about how to manipulate symbols. We also could have used absolutely any symbols for the numbers and operators as long as they were the ones the computer was programmed to manipulate. We are the ones that add the intelligence and give those symbols meanings of numbers and addition and the result of doing an addition.
This is why representations are important – we need to choose a representation for things that makes the symbol manipulation we intend to do easy. We already saw this with images. If we want to send a large image to someone else then a representation of images like run-length encoding that shrinks the amount of data is a good idea.
When designing computers we need to provide them with a representation of numbers so they can manipulate those numbers. We have seen that there are lots of representations we could choose for numbers and any in theory would do, but when we choose a representation of numbers for use to do computation, we want to pick one that makes the operations we are interested in doing easy. Charles Babbage for example chose to use cog-like wheels turned to particular positions to represent numbers as he had worked out how to create a mechanism to do calculation with them. But that is something for another time…
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.
Continuing a series of blogs on what to do with all that lego scattered over the floor: learn some computer science…
We saw in the last post how images are stored as pixels – the equivalent of square or round lego blocks of different colours laid out in a grid like a mosaic. By giving each colour a number and drawing out a gird of numbers we give ourself a map to recreate the picture from. Turning that grid of numbers into a list (and knowing the size of the rectangle that is the image) we can store the image as a file of numbers, and send it to someone else to recreate.
Of course, we didn’t really need that grid of numbers at all as it is the list we really need. A different (possibly quicker) way to create the list of numbers is work through the picture a brick at a time, row by row and find a brick of the same colour. Then make a long line of those bricks matching the ones in the lego image, keeping them in the same order as in the image. That long line of bricks is a different representation of the image as a list instead of as a grid. As long as we keep the bricks in order we can regenerate the image. By writing down the number of the colour of each brick we can turn the list of bricks into another representation – the list of numbers. Again the original lego image can be recreated from the numbers.
The trouble with this is for any decent size image it is a long list of numbers – made very obvious by the very long line of lego bricks now covering your living room floor. There is an easy thing to do to make them take less space. Often you will see that there is a run of the same coloured lego bricks in the line. So when putting them out, stack adjacent bricks of the same colour together in a pile, only starting a new pile if the bricks change colour. If eventually we get to more bricks of the original colour, they start their own new pile. This allows the line of bricks to take up far less space on the floor. (We have essentially compressed our image – made it take less storage space, at least here less floor space).
Now when we create the list of numbers (so we can share the image, or pack all the lego away but still be able to recreate the image), we count how many bricks are in each pile. We can then write out a list to represent the numbers something like 7 blue, 1 green, … Of course we can replace the colours by numbers that represent them too using our key that gives a number to each colour (as above).
If we are using 1 to mean blue and the line of bricks starts with a pile of seven black bricks then write down a pair of numbers 7 1 to mean “a pile of seven blue bricks”. If this is followed by 1 green bricks with 3 being used for green then we next write down 1 3, to mean a pile of 1 green bricks and so on. As long as there are lots of runs of bricks (pixels) of the same colour then this will use far less numbers to store than the original:
7 1 1 3 6 1 2 3 1 1 1 2 3 1 2 3 2 2 3 1 2 3 …
We have compressed our image file and it will now be much quicker to send to a friend. The picture can still be rebuilt though as we have not lost any information at all in doing this (it is called a lossless data compression algorithm). The actual algorithm we have been following is called run-length encoding.
Of course, for some images, it may take more not less numbers if the picture changes colour nearly every brick (as in the middle of our giraffe picture). However, as long as there are large patches of similar colours then it will do better.
There are always tweaks you can do to algorithms that may improve the algorithm in some circumstances. For example in the above we jumped back to the start of the row when we got to the end. An alternative would be to snake down the image, working along the adjacent rows in opposite directions. That could improve run-length encoding for some images because patches of colour are likely the same as the row below, so this may allow us to continue some runs. Perhaps you can come up with other ways to make a better image compression algorithm
Run-length encoding is a very simple compression algorithm but it shows how the same information can be stored using a different representation in a way that takes up less space (so can be shared more quickly) – and that is what compression is all about. Other more complex compression algorithms use this algorithm as one element of the full algorithm.
Make this picture in lego (or colouring in on squared paper or in a spreadsheet if you don’t have the lego). Then convert it to a representation consisting of a line of piles of bricks and then create the compressed numbered list.
Make your own lego images, encode and compress them and send the list of numbers to a friend to recreate.
It is now after Christmas. You are stuffed full of turkey, and the floor is covered with lego. It must be time to get back to having some computer science fun, but could the lego help? As we will see you can explore digital images, cryptography, steganography, data compression, models of computing, machine learning and more with lego (and all without getting an expensive robot set which is the more obvious way to learn computer science with lego though you do need lots of lego). Actually you could also do it all with other things that were in your stocking like a bead necklace making set and probably with all that chocolate, too.
First we are going to look at understanding digital images using lego (or beads or …)
Digital images come in two types: raster (or bitmap) images and vector images. They are different kinds of image representation. Lego is good for experimenting with the former through pixel puzzles. The idea is to make mosaic-like pictures out of a grid of small coloured lego. Lego have recently introduced a whole line of sets called Lego Art should you want to buy rather amazing versions of this idea, and you can buy an “Art Project” set that gives you all the bits you need to make your own raster images. You can (in theory at least) make it from bits and pieces of normal lego too. You do need quite a lot though.
Raster images are the basic kind of digital image as used by digital cameras. A digital image is split into a regular grid of small squares, called pixels. Each pixel is a different colour.
To do it yourself with normal lego you need, for starters, to collect lots of the small circle or square pieces of different colours. You then need a base to put them on. Either use a flat plate piece if you have one or make a square base of lego pieces that is 16 by 16. Then, filling the base completely with coloured pieces to make a mosaic-like picture. That is all a digital image really is at heart. Each piece of lego is a pixel. Computer images just have very tiny pieces, so tiny that they all merge together.
Here is one of our designs of a ladybird.
The more small squares you have to make the picture, the higher the resolution of the image With only 16 x 16 pixels we have a low resolution image. If you only have enough lego for an 8×8 picture then you have lower resolution images. If you are lucky enough to have a vast supply of lego then you will be able to make higher resolution, so more accurate looking images.
Computers do not actually store colours (or lego for that matter). Everything is just numbers. So the image is stored in the computer as a grid of numbers. It is only when the image is displayed it is converted to actual colours. How does that work. Well you first of all need a key that maps colours to numbers: 0 for black, 1 for red and so on. The number of colours you have is called the colour depth – the more numbers and linked colours in your key, the higher the colour depth. So the more different coloured lego pieces you were able to collect the larger your colour depth can be. Then you write the numbers out on squared paper with each number corresponding to the colour at that point in your picture. Below is a version for our ladybird…
Now if you know this is a 16×16 picture then you can write it out (so store it) as just a list of numbers, listed one row after another instead: [5,5,4,4,…5,5,0,4,…4,4,7,2] rather than bothering with squared paper. To be really clear you could even make the first two numbers the size of the grid: [16,16,5,5,4,4,…5,5,0,4,…4,4,7,2]
That along with the key is enough to recreate the picture which has to be either agreed in advance or sent as part of the list of numbers.
You can store that list of numbers and then rebuild the picture anytime you wish. That is all computers are doing when they store images where the file storing the numbers is called an image file.
A computer display (or camera display or digital tv for that matter) is just doing the equivalent of building a lego picture from the list of numbers every time it displays an image, or changes an old one for something new. Computers are very fast at doing this and the speed they do so is called the frame rate – how many new pictures or frames they can show every second. If a computer has a frame rate of 50 frames per second, then it as though it can do the equivalent of make a new lego image from scratch 50 times every second! Of course it is a bit easier for a computer as it is just sending instructions to a display to change the colour shown in each pixels position rather than actually putting coloured lego bricks in place.
Better still you can give that list of numbers to a friend and they will be able to rebuild the picture from their own lego (assuming they have enough lego of the right colours of course). Having shared your list of numbers, you have just done the equivalent of sending an image over the internet from one computer to another. That is all that is happening when images are shared, one computer sends the list of numbers to another computer, allowing it to recreate a copy of the original. You of course still have your original, so have not given up any lego.
So lego can help you understand simple raster computer images, but there is lots more you can learn about computer science with simple lego bricks as we will see…
Each day we published a blog post about computing with the theme suggested by the picture on the advent calendar’s ‘door’. Our first picture was a woolly jumper so the accompanying post was about the links between knitting and coding, the door with a picture of a ‘pair of mittens’ on led to a post about pair programming and gestural gloves, a patterned bauble to an article about printed circuit boards, and so on. It was fun coming up with ideas and links and we hope it was fun to read too.
We hope you enjoyed the series of posts (scroll to the end to see them all) and that you have a very Merry Christmas. Don’t forget that if you’re awake and reading this at the time it’s published (6.30am Christmas Day) and it’s not cloudy, you may be able to see Father Christmas passing overhead at 6.48am. He’s just behind the International Space Station…
And on to today’s post which is accompanied by a picture of a Christmas Tree, so it’ll be a fairly botanically-themed post. The suggestion for this post came from Prof Ursula Martin of Oxford University, who told us about the ‘wood computer’.
The Wood Computer
by Jo Brodie, QMUL.
Other than asking someone “do you know what this tree is?” as you’re out enjoying a nice walk and coming across an unfamiliar tree, the way of working out what that tree is would usually involve some sort of key, with a set of questions that help you distinguish between the different possibilities. You can see an example of the sorts of features you might want to consider in the Woodland Trust’s page on “How to identify trees“.
Depending on the time of year you might consider its leaves – do they have stalks or not, do they sit opposite from each other on a twig or are they diagonally placed etc. You can work your way through leaf colour, shape, number of lobes on the leaf and also answer questions about the bark and other features of your tree. Eventually you narrow things down to a handful of possibilities.
What happens if the tree is cut up into timber and your job is to check if you’re buying the right wood for your project. If you’re not a botanist the job is a little harder and you’d need to consider things like the pattern of the grain, the hardness, the colour and any scent from the tree’s oils.
Historically, one way of working out which piece of timber was in front of you was to use a ‘wood computer’ or wood identification kit. This was prepared (programmed!) from a series of index cards with various wood features printed on all the cards – there might be over 60 different features.
Every card had the same set of features on it and a hole punched next to every feature. You can see an example of a ‘blank’ card below, which has a row of regularly placed holes around the edge. This one happens to be being used as a library card rather than a wood computer (though if we consider what books are made of…).
I bet you can imagine inserting a thin knitting needle into any of those holes and lifting that card up – in fact that’s exactly how you’d use the wood computer. In the tweet below you can see several cards that made up the wood computer.
This is a practical 'wood identification kit'.
The manual multi-access key is poked through different holes on the identification cards, which represent specific characteristics of the wood, to help determine which one you’re handling. pic.twitter.com/CLNkFyRlMJ
One card was for one tree or type of wood and the programmer would add notch the hole next to features that particularly defined that type. For example you’d notch ‘has apples’ for the apple tree card but leave it as an intact hole on the pear tree card. If a particular type of timber had fine grained wood they’d add the notch to the hole next to “fine-grained”. The cards were known, not too surprisingly, as edge-notched cards.
You can see what one looks like here with some notches cut into it. You might have spotted how knitting needles can help you in telling different woods apart.
Holes and notches
Each card would end up with a slightly different pattern of notched holes, and you’d end up with lots of cards that are slightly different from each other.
How it works
Your wood computer is basically a stack of cards, all lined up and that knitting needle. You pick a feature that your tree or piece of wood has and put your needle through that hole, and lift. All of the cards that don’t have that feature notched will have an un-notched hole and will continue to hang from your knitting needle. All of the cards that contain wood that do have that feature have now been sorted from your pile of cards and are sitting on the table.
You can repeat the process several times to whittle (sorry!) your cards down by choosing a different feature to sort them on.
The advantage of the cards is that they are incredibly low tech, requiring no electricity or phone signal and they’re very easy to use without needing specialist botanical knowledge.
We are nearly coming to the end of our CS4FN Christmas Computing Advent Calendar with one more post to come tomorrow. If you’ve missed any you can catch up by scrolling to the end where there’s a complete list so far.
Today’s advent calendar window shows Father Christmas’ sleigh with a sack full of presents ready for delivery. Today’s theme is about the many different online ways that you can now ‘track’ his movements around the world. This follows on from yesterday’s bonus post about how you can actually see (cloud permitting) his sleigh ‘in person’ as it flies overhead at 6:48am on Christmas Day. In reality it’s International Space Station whizzing past – but other interpretations are available.
In 1955, so the story goes, an American department store published a newspaper advert with a phone number for children to call so that they could speak to Father Christmas. Unfortunately a misprint meant that the wrong number was given and instead people found they were talking to the US military’s Air Defense Command (now called North America Air Defense Command or NORAD).
Realising the mistake, but also spotting a great public relations opportunity, the team capitalised on this and began to make an annual event of it.
NORAD uses radar and geosynchronous* satellites to monitor Father Christmas. The satellites are able to detect infrared (heat) radiation and apparently Rudolph’s red nose gives quite a strong signal. This data is then shared with everyone via their website, though they don’t know in advance what route he’ll take.
If you’re visiting the website hover over the different bits of the picture as there are linked activities and extra information too.
*geo = Earth, synchronous = matching / following (like when you sync devices), the satellite follows the Earth’s orbit and is always above the same spot, so effectively (from the Earth’s point of view) the satellite appears not to move (it is moving but it follows the Earth’s rotation).
FlightRadar24 is a great website for telling you the answer to “what was that aircraft that’s just flown by?” It tracks the flight of aircraft all over the globe in real time, using a signal transmitted by the aircraft’s beacon (called a transponder) which announces where it is. Father Christmas’ sleigh has its own transponder too which is transmitting its location to receivers around the world.
An aircraft, or Santa’s sleigh, gets information about where it is from a GPS satellite (very similar to using a maps app on a smartphone and it telling you where you are and whether you should go left or right) and it then transmits this location info, along with other data, through its transponder.
There are thousands of receivers here on Earth, many of them in people’s homes and gardens (you can even apply to host a receiver antenna, or build your own with a Raspberry Pi) and whenever Santa’s sleigh passes over one of these ‘ground stations’ its signal is picked up and collected by FlightRadar24. The receivers are in different places so they are receiving the same signal at slightly different times and this information can be used to work out (by triangulation) how fast the sleigh is moving and in what direction.
Dave Holmes, a developer who works at Google and who works on the Santa Tracker project says “Santa Tracker launched in 2004, and has been an important project at Google ever since. While there’s a small core team dedicated to Santa, up to 20 or so Googlers volunteer to help make it happen every year, and it’s become a true community effort. It’s also a way for our developers to try things and see what Google products can do … I like to say that everything I’ve learned at Google, I learned from Santa.”
Back in the early 1990s email was very new but right from the start people used it to send each other amusing things. One of them was a rather literal consideration of the physics of a sleigh that is laden with gifts and a traditionally overweight Santa, led by a team of reindeer moving at unlikely speeds (after all Father Christmas has to get around the entire world to deliver presents, in just one day). The author (unknown) began –
“No known species of reindeer can fly. BUT there are 300,000 species of living organisms yet to be classified, and while most of these are insects and germs, this does not COMPLETELY rule out flying reindeer which only Santa has ever seen.”
But then goes on to point out that such a gift-delivery system would be working far beyond normal levels and would probably end in disaster, suggesting that –
“In short, they will burst into flame almost instantaneously, exposing the reindeer behind them, and create deafening sonic booms in their wake. The entire reindeer team will be vaporized within 4.26 thousandths of a second. Santa, meanwhile, will be subjected to centrifugal forces 17,500.06 times greater than gravity. A 250-pound Santa (which seems ludicrously slim) would be pinned to the back of his sleigh by 4,315,015 pounds of force.”
Fortunately Father Christmas has his own magic, meaning that we don’t need to worry too much about him disobeying the laws of physics. But he and his reindeer really deserve those cookies, milk and carrots!
Our CS4FN Christmas Computing Advent Calendar has now been running for 23 days! That’s one post every single day, matching a computing-themed blog post to the image on the front of the advent calendar. If you’d like to see how well we’ve managed this please scroll to the end where you can find all of our previous Advent Calendar posts.
Today’s picture is of Father Christmas who, we’ll assume, is re-checking his list and packing his sleigh ready for a long flight around the world, where he’ll be collecting cookies as he goes.
As the song implies, he takes particular care over his list checking it twice to make sure there are no mistakes. In that respect he’s a little like computer scientists who put systems in place to make sure that when they send data to someone else that person can tell quickly if it’s arrived correctly. Today’s post is about reducing errors (and trying to avoid introducing errors). (We don’t know what data collection methods Father Christmas used though.)
1. Reducing errors: check digits
Once I’d reached the age of about 12 my parents started to let me go by myself to my friend’s house which was about a 15 minute walk away. When I arrived I would use my friend’s parents’ landline phone (with permission) to “give 3 rings” to my parents. This meant that I rang my parents’ number – but they didn’t answer, instead they let the phone ring three times and then I hung up. That way they knew the call was from me (our pre-agreed code) but no-one was charged to make or receive a call and they knew I’d arrived safely. (Obviously if the phone rang for longer they’d know it was probably from someone else and answer it).
Computer scientists also use an agreed code when sending data to another person or computer over a network – they want to make sure their data arrived safely too. Data is* sent as binary 1s and 0s and sometimes there’s a scrambling error in the transmission resulting in a 1 arriving as a 0, or a 0 arriving as a 1. A neat way to find out if this might have happened is to double-check what it was supposed to be, by using something called a parity bit (parity means ‘equal’) or check digit. This digit is added to each block of data you’re sending and computer scientists came up with this to let you check if the arriving data looks correct.
Here’s how it works
Suppose you want to send a message consisting of the numbers 6, 13, 2 and 12. These numbers can be converted into binary for data transmission: for example 6 in binary is 0110, 13 is 1101, 2 is 0010 and 12 is 1100. In the 5-row table below these are written in black (the top line is 6 and the fourth row is 12 – we’ll come to the red numbers in a moment).
We’ll now add a parity bit to each row, according to a rule, to make them five digits long.
The rule is that if the binary number has an odd number of 0s we even it up by adding another 0. If there’s an even number of 0s we just add a 1.
In the 1st row 0110 has an even number of zeroes so a 1 is added, 1101 has an odd number of zeroes so an extra 0 is added. Once we’ve checked all four rows we end up with a new parity column (shown in red on the right to make it stand out) on the right. We can also add a new parity row at the bottom as well, by doing the same thing for each of the numbers but read as a column. The first column has an even number of zeroes so we add a 1, the next just has one odd zero so we add a 0 there and so on.
We’ve added extra data to be sent, but this redundancy check (the extra info isn’t part of the message itself but helps support it) makes it easier for the person receiving the information to know if it’s OK or where any problem is.
Let’s pretend you’ve just pressed send and your 1s and 0s are winging their way to your friend.
Unfortunately there was a small error in transmission and one of the numbers has ‘flipped’. Will your friend be able to tell which one it is? (Remember they don’t know what your message actually said, they can only see what’s arrived).
Here’s the (slightly scrambled) data that they receive.
They can use the parity bit information to check each row and column. The first row looks fine – two zeroes (even) and the parity bit one says 1 so that’s right. The second row looks wrong though – there’s an even number of zeroes so you’d expect a 1 in the parity bit – but it says 0, so you know there’s a mistake somewhere in row 2, but your friend won’t know where yet. They need to check the columns too.
Column 1 looks good, there are two zeroes and the parity bit says 1 so that’s correct. Column 2 has an even number of zeroes so you’d expect the parity bit to be 1, but it’s 0. So we know the problem is in Row 2 and Column 2. If we look at where they intersect we can see that a 1 has flipped to a 0, shown below in bold and blue. Your friend can correct the data and translate the binary back into the original numbers.
You could try this with a friend or family member. Think up any 4 numbers between 0 (binary 0000) and 15 (binary 1111) then transmit your binary code with one error and see if they can work out which data bit flipped. Or… you can do it as a magic trick with a pack of cards (see the activity at the end).
*are, for the pedants 🙂
Writing together: Clarence ‘Skip’ Ellis – about Clarence Ellis who used his knowledge of computing to bypass parity checks. The company he worked for was running out of punched cards (we’ll look at these in more depth later in the week) which the company’s computer used to store data. He was able to find a way for his colleagues to re-use the cards they already had, without triggering parity check problems – in doing so the payroll program could be run and everyone could get paid.
2. Trying not to introduce errors: when spellcheck goes worng
Another thing Father Christmas needs to do is check that he has the correct names of all the good children he’ll be giving presents to. He might use a spellchecker for this – this is something that reads the words in a document and compares them to a pre-set list. If a word is spelled in an unusual way the computer will alert you and ask if you want to change it to the one in the list or if you want to add it as a new spelling to the list. It would spot that I spelled ‘wrong’ wrongly in the heading for this section and ask if I meant ‘wrong’ instead of ‘worng’.
Find and replace
Sometimes people want to change a word in their document that appears many times. For example you might put TBA (which can mean ‘to be agreed’ or ‘to be arranged’) as a temporary placemarker in a Word document and later decide that every time the document says ‘TBA’ you’d prefer it to say “to be determined” instead. You don’t have to manually delete and retype every single instance of ‘TBA’, you can ‘automate’ the process using the Find and Replace option. Word will then find every ‘TBA’ automatically and change it to ‘to be determined’.
Sometimes this doesn’t go quite as expected.
In the UK the word ‘ass’ just means donkey but in the US it’s a slightly less polite word for bottom. A slightly more polite word might be ‘butt’ so you – being polite – want to make sure that any time the word ‘ass’ appears in a particular document it’s replaced with the word ‘butt’. This is unfortunate though if you happen to be the editor of a book about donkeys, which is now suddenly about bottoms.
It’s much worse if your document talks about your class at school (clbutt?). Or perhaps it’s some homework about the assassination of an American president (buttbuttination?). Or maybe you need a new password (pbuttword), or even a new passport (pbuttport). Your document is now absolute gibberish and you would not pbutt any exams with that. Where’s spellcheck when you need it?
These types of mistakes are not that uncommon, I’ve even done it myself with the addresses of schools where I send copies of our CS4FN magazine to teachers.
I had a column in my address database which said things like UK, U.K. or United Kingdom and I decided I wanted them all to match and say “United Kingdom”. So… I used find and replace and asked my computer to turn every mention of ‘UK’ or ‘U.K.’ into United Kingdom. It worked beautifully… but I didn’t check the other columns.
I discovered my mistake when ‘Luke’ at a school on ‘Duke Road’ didn’t get his copy of the magazine and it was returned to me by the Post Office as the address was unreadable. I then had to correct both Lunited Kingdome’s name and his DUnited Kingdome Road address 😉 Oops.
Here are some other examples
Trivial Pursuit makers change all mentions of "km" to "kilometres" as a universal find and change. Can't see what could go wrong there. pic.twitter.com/956hYeJw3B
and here’s what happened when someone changed TBA to ‘to be determined’ without noticing that the string of letters also appears in the word basketball.
Once universally replaced mentions of "TBA" in a course guide with "to be determined." Result: a "basketobedeterminedll" course.
— Truly 'Triple Vaccinated for Extra Creaminess' S. (@hotincleveland) January 5, 2017
3. Magic trick activity: parity check with playing cards
You could demonstrate the parity checking (that we did above with 1s and 0s) as a card trick – you just need an assistant and an audience. If you look closely at the pattern of cards in the picture above, and the pattern of 1s and 0s further up in this post you might notice a similarity…
Give a pack of shuffled cards to an audience member and ask them to deal out 16 cards in four rows either face up or face down (their choice). An example is shown in the left of the picture above. Tell them that in a moment you’re going to ask them to turn over a card while you’re not looking and later, you’ll tell them which card they flipped over. Announce that your assistant is going to make it ‘even harder’ by adding an extra column and row (I bet you can see where this is going). Of course, your assistant is adding a parity bit to the rows and columns (but your audience doesn’t know that) – an example is shown in the middle picture above.
Now avert your eyes (or get someone to blindfold you) and ask the audience member to turn over one card from the grid without telling you which. (Example in the picture on the right, above).
When you look at the grid you can quickly work out which one has been turned over, using exactly the same method we used with the 1s and 0s above.
This trick is a variation of one invented by New Zealand computer scientist, Tim Bell, and you can find more information about it and detailed instructions (as well as ideas to make it seem like you’re really a magician) in our free booklet called The Magic of Computer Science: card tricks special. The trick is called ‘The Out of Body Experience‘ and you can find it on pages 24-31 (pages 13 – 16 of the 33 page PDF).
Every day from the 1st to the 25th of December this blog will publish a Christmas Computing post, as part of our CS4FN Christmas Computing Advent Calendar. On the front of the calendar for each day is a festive cartoon which suggests the post’s theme – today’s is a star, so today’s post is about finding your way: navigation.
In modern cities looking up at the night sky is perhaps not as dramatic as it might have been in the past, or in a place with less light pollution. For centuries people have used stars and the patterns they form to help them find their way.
There are many ways our explorations of space have led to new technologies, though satellites have perhaps had the most obvious effect on our daily lives. Early uses were just for communication, allowing live news reports from the other side of the world, with networks that span the globe. More recently GPS – the Global Positioning System has led to new applications and now we generally just use our phones or satnav to point us in the right direction.
Victorian engineer Charles Babbage designed, though never built the first mechanical computer. The first computers had actually existed for a long time before he had his idea, though. The British superiority at sea and ultimately the Empire was already dependent on them. They were used to calculate books of numbers that British sailors relied on to navigate the globe. The original meaning of the word computer was actually a person who did these calculations. The first computers were humans.
Babbage became interested in the idea of creating a mechanical computer in part because of computing work he did himself, calculating accurate versions of numbers needed for a special book: ‘The Nautical Almanac’. It was a book of astronomical tables, the result of an idea of Astronomer Royal, Nevil Maskelyne. It was the earliest way ships had to reliably work out their longitudinal (i.e., east-west) position at sea. Without them, to cross the Atlantic, you just set off and kept going until you hit land, just as Columbus did. The Nautical Almanac gave a way to work out how far west you were all the time.
Maskelyne’s idea was based on the fact that the angle from the moon’ to a person on the Earth and back to a star was the same at the same time wherever that person was looking from (as long as they could see both the star and moon at once). This angle was called the lunar distance.
The lunar distance could be used to work out where you were because as time passed its value changed but in a predictable way based on Newton’s Laws of motion applied to the planets. For a given place, Greenwich say, you could calculate what that lunar distance would be for different stars at any time in the future. This is essentially what the Almanac recorded.
Now the time changes as you move East or West: Dawn gradually arrives later the further west you go, for example, as the Earth rotates the sun comes into view at different times round the planet). That is why we have different time zones. The time in the USA is hours behind that in Britain which itself is behind that in China. Now suppose you know your local time, which you can check regularly from the position of the sun or moon, and you know the lunar distance. You can look up in the Almanac the time in Greenwich that the lunar distance occurs and that gives you the current time in Greenwich. The greater the difference that time is to your local time, the further West (or East) you are. It is because Greenwich was used as the fixed point for working the lunar distances out, that we now use Greenwich Mean Time as UK time. The time in Greenwich was the one that mattered!
This was all wonderful. Sailors just had to take astronomical readings, do some fairly simple calculations and a look up in the Almanac to work out where they were. However, there was a big snag. it relied on all those numbers in the tables having been accurately calculated in advance. That took some serious computing power. Maskelyne therefore employed teams of human ‘computers’ across the country, paying them to do the calculations for him. These men and women were the first industrial computers.
Before pocket calculators were invented in the 1970s the easiest way to do calculations whether big multiplication, division, powers or square roots was to use logarithms(not to be confused with algorithm). The logarithm of a number is just the number of times you can divide it by 10 before you get to 1. Complicated calculations can be turned in to simple ones using logarithms. Therefore the equivalent of the pocket calculator was a book containing a table of logarithms. Log tables were the basis of all other calculations including maritime ones. Babbage himself became a human computer, doing calculations for the Nautical Almanac. He calculated the most accurate book of log tables then available for the British Admiralty.
The mechanical computer came about because Babbage was also interested in finding the most profitable ways to mechanise work in factories. He realised a machine could do more than weave cloth but might also do calculations. More to the point such a machine would be able to do them with a guaranteed accuracy, unlike people. He therefore spent his life designing and then trying to build such a machine. It was a revolutionary idea and while his design worked, the level of precision engineering needed was beyond what could be done. It was another hundred years before the first electronic computer was invented – again to replace human computers working in the national interest…but this time at Bletchley Park doing the calculations needed to crack the German military codes and so win the World War II.
The creation of 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.
Each day throughout December (until Christmas Day) we’ll be publishing a computing-themed blog post suggested by the picture on the front of our Advent Calendar. Today’s image on the door of the CS4FN Christmas Computing Advent Calendar is a Christmas wreath which made me think of wires and of weaving.
You might remember that our first advent calendar post was about the links between coding and knitting. Today’s post looks at an even more literal version of that: core rope memory.
1. Core rope memory: the Apollo space mission’s woven computer memory
by Jo Brodie, QMUL.
Firstly it looks like this.
Secondly it got us to the Moon!
Probably the world’s first portable computer
Core rope memory was made up of small ‘eyelets’ or beads of metal called ferrite that can be magnetised (these ring-shaped magnets were known as magnetic cores) and copper wire which was woven through some of the eyelets but not others. An electrical current passing through the wires made the whole thing work. A wire that passed through an eyelet would be read as a binary 1 when the current was on but if it passed around one then it would be read as 0. This meant that a computer program, made up of sequences of 1s and 0s, could be permanently stored by the pattern that was woven.
This type of memory was woven in the 1960s for NASA’s Apollo moon mission by women who were skilled textile workers. They would work in pairs and use a special hollow needle to thread the copper wire through one magnetic core and then the other person would thread it back through a different one, following instructions from another program which indicated which of the eyelets to use.
That program was first developed on a computer (the sort that took up a whole room back then) and then translated into instructions for a machine which helped the weavers get the wire threads into the correct position. It was very difficult to undo a mistake so a great deal of care was taken to get things right the first time, especially as it could take up to two months to complete one block of memory. Some of the rope weavers were overseen by Margaret Hamilton, one of the women who developed the software used on board the spacecraft.
Several of these pre-programmed core rope memory units were combined and installed in the guidance computers of the Apollo mission spacecraft, to fly astronauts safely to the Moon and back.
NASA needed on-board guidance systems to control the spacecraft independently of Mission Control back on Earth. They needed something that didn’t take up too much room or weigh too much, that could survive the shaking and juddering of take-off and background radiation – core rope memory fitted the bill perfectly.
It packed a lot* of information into a small space and was very robust as it could only break if a wire came loose or one of the ferrite eyelets was damaged (which didn’t happen). To make sure though, the guidance computer’s electronics were protected by being sealed from the atmosphere. They survived and worked well, guiding the Landing Modules safely onto the Moon.
*well, not by modern standards! The guidance computer contained only around 70 kilobytes of read only memory.
2. A brief history of the digital revolution, part 1: from birth to the moon
The Royal Institution Christmas Lectures 2008 invited you on a high tech trek to build the ultimate computer. The Christmas Lectures talk a lot about the current cutting-edge of computer technology, but what were things like in the early days of the digital revolution? The researcher for the 2008 Christmas Lectures, Lewis Dartnell, takes us through the story.
Electronic computers have come a long way since their birth only 50 years ago. One of the very first digital computers was built at the University of Manchester, a prototype called Manchester Mark I. The machine was revolutionary, with its complex processing circuits and storage memory to hold both the program being run and the data it was working on. The Mark I was first run on 21 June 1948 and paved the way as a universal computer that is truly versatile and can be reprogrammed at will, rather than being hard-wired for a single particular task.
These earliest computers used technology called vacuum tubes, which were essentially just like filament light bulbs. Because they get so hot, such vacuum tubes were really power hungry and not very reliable. Typically, computers like the Manchester Mark I, processing using vacuum tubes, could only be run for a few hours at a time before one of the vacuum tubes broke and had to be replaced. The biggest break-through in modern computing came with the invention of the transistor, a small electronic component that can perform the same function as a vacuum tube, but is much more energy efficient and reliable. The beauty of the transistor is that computer scientists found ways of making them smaller and smaller, and to connect a number of them together into a single miniaturized processing board called an integrated circuit. These came to be known as microchips, and form the basis of all the computers made today.
A major drive for the development of microchip technology was the Apollo programme, begun in 1961 to land humans on the Moon. Although the vast majority of the complex calculations to do with plotting the trajectory and navigating to the moon were performed by enormous banks of computers back on Earth, it was crucial for the spacecraft to have their own on-board computer system. This was called the Apollo Guidance Computer (AGC), and both the command module and the lunar module, which actually made the descent to the surface of the moon, had one each. These ground-breaking computers provided the astronauts with crucial flight information, helped them make course corrections and to touch-down gently on the moon’s surface. Because it’s absolutely crucial to reduce the amount of mass and power usage on a spacecraft as far as possible, developing these guidance computers really pushed the technology in miniaturising integrated circuits.
The Apollo Guidance Computer not only helped drive the early development of microchips, but it also suffered one of the most infamous computer crashes in history. During the descent down to the Moon’s surface the AGC started displaying two error messages that the two astronauts, Neil Armstrong and Buzz Aldrin, weren’t familiar with. Engineers back at mission control on Earth quickly tried to identify the error code, and what it might mean for the lunar landing. Something that had never happened in any of the training simulations was now overloading the flow of data into the computer, the first time it had ever been used for real. Time was running out with only a limited amount of rocket fuel on-board and the Moon rushing up towards them. Luckily the computer entered a fail-safe mode, aborting low-priority calculations but able to continue with the critical tasks for the landing.
It wasn’t until the investigation afterwards that it was realized just how lucky Neil Armstrong and Buzz Aldrin had really been. The root of the problem was that the real attempt at the Moon landing was the first time an important radar system had been plugged into the computer, sending data into the AGC that wasn’t needed for the landing. This almost totally overloaded the computer, but by amazing luck, the amount of spare processing power built into the system for safety was almost exactly the amount being wasted by the un-needed radar, and the AGC didn’t crash completely.
The story of the digital revolution continues in part 2.
3. Activity 1 – make your own core rope memory
A nice craft activity is to create a cut-down version with beads and coloured threads. You string 8 beads (with a gap between them) on one thread to form a single ‘byte’ (of 8 binary bits). You then take other threads and pass them through when you want that bead to read 1, or over, when you want that bead to read 0. One way of deciding whether it’s 1 or 0 is to pick a word (or maybe your name) and use enough threads so you have one for each letter.
Using binary encoding for each letter (so capital letter A would be 01000001 if you’re following this conversion from binary to letters table) and put that letter’s thread through or over each of the 8 beads to ‘spell’ out the letter in binary.
My name’s Jo so mine would have only three threads (one to hold the 8 beads and two to spell my name). One thread would go over, through, over, over, through, over, through, over to spell the capital letter J (01001010) and over, through, through, over, through, through, through, through to spell lowercase o (01101111). Let’s hope you have a slightly longer name!
4. Activity 2 – create an origami laurel wreath
Not only do we have a wreath-themed activity in our back catalogue (!) but in a delightful coincidence this story also relates to Apollo (the Greek god). If you’re wondering what origami might have to do with computing it’s just another way of looking at algorithms and instructions. Also, decomposition (breaking a problem into smaller parts) because you can re-use the instructions needed for the laurel wreath to make other origami items. We like using ‘unplugged’ activities like this to demonstrate computing concepts.