## Want to keep learning?

This content is taken from the Davidson Institute of Science Education at the Weizmann Institute of Science's online course, Maths Puzzles: Cryptarithms, Symbologies and Secret Codes. Join the course to learn more.
2.17

## Davidson Institute of Science Education at the Weizmann Institute of Science

Skip to 0 minutes and 0 seconds When we look at the binary numbers that are ordered from 1 and up we see an interesting phenomenon. Each time we reach a power of 2, all the bits (digits) change! Here is the binary table from 0 to 16. When advancing from 0 to 1… from 1 to 2, we go from 01 in binary code to 10, and when advancing from 3 to 4 we change 011 to 100, and so on. You can see that whenever we change from 0 to 1, from 1 to 2, from 3 to 4, from 7 to 8 or from 15 to 16, all the bits change. In digital devices that count things, like the speedometer in a car, this property may be a problem.

Skip to 0 minutes and 49 seconds In any electronic device, there is always a risk that something will malfunction, especially when changes are made, such as when one bit is changed into another. If all the bits are changed at once, the risk is much bigger. This problem exists even in meters that are based on the decimal system – like a row of cogwheels where each one has the digits 0 to 9 (in old-fashioned speedometers). When the number changes from 9999 to 10000, all the wheels rotate at once, and this raises the risk of a technical malfunction. This was exactly the motivation for Frank Gray, an American Physicist, to invent a symbology in which in every move between two consecutive numbers, only one digit is changed.

Skip to 1 minute and 30 seconds Gray’s method is appropriate for any counting system (decimal, binary, etc.), and when it is used in the binary system, it is called “Gray Code”. Here is a table of the numbers 0 to 15 in Gray Code. Only one digit is changed when advancing from one number to the number after it. Note that one bit changes between every single consecutive line. From decimal zero to one - the furthest right hand bit changes. From 1 to 2, the second bit from the right changes and so on. A surprising fact is that there is more than one Gray Code that fulfils these demands! This means that this here is not the only table we can come up with.

Skip to 2 minutes and 18 seconds There are many other “Gray code” tables for the numbers between 0 to 15, for example, here are 2 different binary Gray codes for the numbers 0 to 7. In this example, all the numbers except zero are encoded differently. Take the number 7 for instance. Here it is encoded 0100 and here 0010. However in both tables these values, 0100 and 0010 are both one bit different from the bit representation in the line above. So, How many different Gray encodings are there for a given range of numbers? The number of possible Gray Codes for different numbers is enormous - extremely large.

Skip to 3 minutes and 31 seconds There are 91,392 possible Gray Codes just for coding the numbers 0 to 15, and to find the number of possible Gray Codes for the numbers 0 to 255, you will probably need to wait for a very long time. This is an “open” problem in math – a problem that has not yet been solved! Even a very powerful computer can’t calculate this number but maybe it will be possible in the future. The recreational mathematician Martin Gardner writes about Gray Codes in his book “Knotted Doughnuts and Other Mathematical Entertainments”. He shows that all the possible Gray Codes for a given number of bits, can be generated from a drawing of the corresponding n-cube.

Skip to 4 minutes and 21 seconds This means that you can generate all the possible 2-bit Gray codes by drawing a square, all the possible 3-bit Gray codes by drawing a cube, all the possible 4-bit Gray codes by drawing a 4-dimensional hypercube and so on. Let’s see how this is done for the 2-bit case. We’ll generate two (for example) of the eight possible Gray codes for the numbers zero to three. So, draw a square, and label each vertex with binary numbers so that there is only one different bit between any two adjacent vertices. So we’ll draw our square and label it clockwise 00, 01,11 and 10. Every vertex is just one bit different from the two adjacent vertices.

Skip to 5 minutes and 17 seconds Now, we trace the square starting from one vertex and traveling along all its sides, passing through each vertex exactly once. A path like this, one that visits all the vertices in a graph exactly once, is known as a “Hamiltonian Path”, after the famous, late, Irish mathematician, William Rowan Hamilton. If we start at the vertex labeled “00” and trace the square clockwise, we get the sequence 00, 01, 11 and 10.

Skip to 5 minutes and 53 seconds This is one possibility for a Gray Code for the numbers zero to three: with 00 = 0, 01 = 1, 11 = 2 and 10 = 3. There is another way to generate a Gray code - to start with the vertex “10”, for example, and trace the square counter- clockwise. In this case, we get the sequence 10, 11, 01 and 00, and the Gray Code will be 10 = 0, 11 = 1, 01 = 2 and 00 = 3. Since we can start with any of the four vertices, there are 4 times 2 equals 8 2-bit Gray codes. Doing the same thing on a cube will generate the 144 different 3-bit Gray codes for the numbers 0-7.

Skip to 6 minutes and 40 seconds One main disadvantage of Gray codes is that there is no straightforward way to convert them from binary code to Gray Code. In order to solve this problem, mathematicians found a way to convert a binary number into one specific kind of Gray Code. This Gray Code is called “reflected” Gray Code. Here is how to change a binary number to binary reflected Gray code. Let’s take an example the number twelve - in binary - 1100.

Skip to 7 minutes and 11 seconds Go over the digits of the binary number from right to left: 0, 0, 1, 1. If the digit to the left of the digit you are looking at is 0, as is the case in the example, leave the digit alone. Otherwise reverse the digit you are looking at. o, we leave this 0 alone because the digit to its left is 0, this 0 we reverse or flip, because the digit to its left is 1. So we change it to 1. This 1 has a 1 to the left of it so we reverse it and it becomes 0. This 1 has a 0 to it, the leading zero, so its left alone.

Skip to 7 minutes and 56 seconds The binary number 1100 is equal to 1010 in reflected Gray Code. Now let’s do the other direction and convert from reflected Gray Code to binary. Here’s how we do this. We’ll change the number 1010 which is in Gray back into binary. So, go over the digits of the number in reflected Gray Code from right to left. If the sum of the digits that are to the left of the digit you are looking at is an even number, leave the digit alone. Otherwise reverse it. The sum of the digits to the left of this zero is 2 which is even, so we leave this 0 alone.

Skip to 8 minutes and 37 seconds The sum of the digits to the left of this 1 is 1 which is odd, so we flip it and it becomes a 0. This 0 also has a sum of 1 to the left of it so we reverse it and it becomes 1. This 1 has a 0 to the left of it, the leading zero, this is odd so its left alone. The binary-reflected Gray code number 1010 is equal to 1100 in binary. And that’s a bit about Gray Codes - note the pun…

# What are Gray codes?

When we look at the binary numbers in order we see an interesting phenomenon. Each time we reach a power of 2, all the bits change! When advancing from 1 to 2, we go from 01 in binary code to 10, and when advancing from 3 to 4 we change 011 to 100, and so on.

In digital devices that count things, like the speedometer in a car, this property may be a problem. In any electronic device, there is always a risk that something will malfunction, especially when changes are made, such as when one bit is changed into another. If all the bits are changed at once, the risk is much bigger.

This problem exists also in meters that are based on the decimal system – like a row of cogwheels where each one has the digits 0 to 9 (in old-fashioned speedometers). When the number changes from 9999 to 10000, all the wheels rotate at once, and this raises the risk of a technical malfunction.

This was exactly the motivation for Frank Gray, an American Physicist, to invent a symbology in which in every move between two consecutive numbers, only one digit is changed. Gray’s method is appropriate for any counting system (decimal, binary, etc.), and when it is used in the binary system, it is called “Gray Code”. This of course means that the positions of the bits in the number no longer represent powers of two, so we need to use a table or other means to translate Gray code back into decimal. Watch this video to learn about Gray codes.