Binary Numbers and the Standard Gray Code

Binary Numbers

Binary numbers, as you know, are representations of numbers in base 2. In base 10, our usual decimal system, we write 27835 to mean

while the binary number 11001 represents the number

or in base 10

.

In binary the first sixteen whole numbers (0, 1, …) may be written as

0
1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111

Binary numbers are often used in applications to represent a sequence of switches where a 1 or 0 indicates a switch is on or off respectively. Binary numbers are also used to describe a computer's internal representation of a numbers. Leading zeroes are often added to a list of binary numbers so that each representation has the same number of digits. Applying this convention to the list above gives the equivalent list

0000        0
0001        1
0010        2
0011        3
0100        4
0101        5
0110        6
0111        7
1000        8
1001        9
1010      10
1011      11
1100      12
1101      13
1110      14
1111      15

where the decimal equivalent is given to the right of each binary number.

The Standard Gray Code

There is a very handy mechanism for generating all the binary representations of numbers greater than or equal to zero. Specifically, this method gives the representations for numbers between 0 and 1, then between 0 and 3, then 0 and 7, 0 and 15 and so on. That is, the lists generated contain the binary numbers between 0 and one less than a power of 2 such as

but not in the order you think. Here’s how it works. Start with the numbers between 0 and 1

0
1

written in a column. This is the first stage.

To list the binary numbers between 0 and 3, first copy the column in reverse order underneath itself as shown below

0
1
1
0

Then add a 0 to the beginning of each entry in the first half of the list

00
01
1
0

and a 1 to the beginning of those in the bottom half

00
01
11
10

This list represents the numbers from 0 to 3 but not in the order 0, 1, 2, 3 rather

00        0
01        1
11        3
10        2

so the order of the numbers is 0, 1, 3, 2.

00
01
11
10

copy in reverse order:

00
01
11
10
10
11
01
00

add 0 to start the first half:

000
001
011
010
10
11
01
00

and add 1 to start the second half:

000
001
011
010
110
111
101
100

and this completes the list of binary strings. You can convince yourself this list corresponds to the decimal numbers 0, 1, 3, 2, 6, 7, 5, 4 in that order. You can also convince yourself the next stage would produce the list

0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000 .

Besides being easy to generate, lists created in this way have a very important property that is useful to engineers and computer scientists, among others. Consider the last list above. Suppose there are four switches in a row labeled 1, 2, 3, and 4 from left to right. With 0 representing "off" and 1 representing "on", the binary number

0000

can be interpreted as that state where all four switches are in the off position.

The number

1101

indicates that switches 1, 2 and 4 are on while switch 3 is off.

The specific list generated earlier

0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

not only represents every possible combination of switch on-off states but also has the property that each number on the list is obtained from the previous number by throwing exactly one switch.

For example, we can walk down the list above indicating which switch is thrown at each step.

0000 (All switches off)
0001 (Flip Switch 4 on)
0011 (Flip Switch 3 on)
0010 (Flip Switch 4 off)
0110 (Flip Switch 2 on)
0111 (Flip Switch 4 on)
0101 (Flip Switch 3 off)
0100 (Flip Switch 4 off)
1100 (Flip Switch 1 on)
1101 (Flip Switch 4 on)
1111 (Flip Switch 3 on)
1110 (Flip Switch 4 off)
1010 (Flip Switch 2 off)
1011 (Flip Switch 4 on)
1001 (Flip Switch 3 off)
1000 (Flip Switch 4 off)

If a complete set of binary numbers (all having the same number of digits) is arranged in such a way that each entry is determined by "throwing one switch" in the previous entry, we have what is called a Gray Code. The Gray Code generated by the method just outlined is called the Standard Gray Code. The Standard Gray Code is named after Frank Gray, a scientist at Bell Telephone Laboratories, who discovered the list and its formation.

The Tower of Hanoi

Gray Codes and the Standard Gray Code can be used as a tool in finding solutions to many classic problems. Let’s look at one problem in particular, the Tower of Hanoi. In this problem, a number of disks (think washers) of different sizes are stacked on one of three pegs in order of decreasing size with the largest on the bottom. The configuration with three disks is shown in the figure below.

The challenge is to move the stack one disk at a time so this pyramid of disks sits on a different peg from the starting position, again stacked from largest to smallest. The caveat is that each time you move a disk, you may place that peg only on an empty peg or on top of a disk that is larger than the disk being moved. That is, a disk may never sit on top of a smaller disk. Lastly, the goal is to move the stack in the fewest number of moves.

The sequence of moves shown below illustrates one solution of the three-disk version of the problem. Next to each picture is a statement of the particular move made to arrive in the pictured state where the pegs have been numbered I, II, III from left to right and the disks numbered 1, 2, 3 from smallest to largest.

Step 1: Starting position.

Step 2: Move disk 1 to peg III.

Step 3: Move disk 2 to peg II.

Step 4: Move disk 1 to peg II.

Step 5: Move disk 3 to peg III.

Step 6: Move disk 1 to peg I.

Step 7: Move disk 2 to peg III.

Step 8: Move disk 1 to peg III.

The stack has been successfully moved from peg I to peg III and at no point was a larger disk resting on a smaller one.

Next we list the moves in the solution next to the entries in the Standard Gray Code for binary numbers of 3 digits.

000 Starting position.

001 Move disk 1 to peg III.

011 Move disk 2 to peg II.

010 Move disk 1 to peg II.

110 Move disk 3 to peg III.

111 Move disk 1 to peg I.

101 Move disk 2 to peg III.

100 Move disk 1 to peg III.

Think of the three binary digits in any of the numbers listed as corresponding to disks 3,2,1 from left to right. Recall that each entry in the list of the Standard Gray Code differs from the previous entry by changing exactly one digit. The Standard Gray Code is related to the Tower of Hanoi solution by the following rule:

• The disk moved at each stage in the solution to the Tower of Hanoi problem corresponds to the position of the digit changed in that entry of the Standard Gray Code.

• For example, the starting position is represented by 000. The next entry in the Standard Gray Code is 001, formed by changing the digit corresponding to disk #1. Thus, disk #1 is the first disk moved in the solution. The entry following 001 is 011, indicating disk #2 is the next disk to be moved. You should verify this is the case for each step of the solution.

The use of the Standard Gray Code here is valid no matter how many disks you start out with provided you are using three pegs. If you have four disks, use the Standard Gray Code for 4-digit binary numbers to tell you which disk to move at each step. For five disks, use the 5-digit binary numbers, and so on.

There is still one point to be made when solving the Tower of Hanoi problem in this manner. Note that after completion of Step 3 above, the configuration of disks and pegs is

and the corresponding entry in the Standard Gray Code is 011. For Step 4 the Standard Gray Code entry is 010. The step from 011 to 010 indicates that at Step 4 we must move disk 1. However, we have a choice. Disk 1 could be placed on peg I atop disk 3 or on peg II atop disk 2 without violating the rules of movement. The Standard Gray Code tells us what disk to move but not necessarily where to move it.

The following rule comes into play when there is a choice of where to place a disk:

• When faced with a choice in placing a disk, always place an odd numbered disk on top of an even numbered disk. If an even numbered disk is not available, place the odd numbered disk on an empty peg. Similarly, place an even numbered disk on an odd disk, if available, or else on an empty peg.

• Armed with this rule and the Standard Gray Code, you can solve the Tower of Hanoi problem with three pegs and any number of disks.

Exercise

Consider the Tower of Hanoi problem where four disks are stacked on one of three pegs as in the picture below.

Number the pegs from left to right as I, II, and III . Number the disks 1 — 4 from smallest to largest. Using the Standard Gray Code with 4 digit binary numbers as a guide, describe a solution to this Tower of Hanoi problem. Specify the steps in a simple form such as "Move disk 1 to peg III" and indicate which binary number in the Standard Gray Code corresponds to each step in your solution.

 1

Consider the Tower of Hanoi problem where four disks are stacked on one of three pegs as in the picture below.

Number the pegs from left to right as I, II, and III . Number the disks 1 — 4 from smallest to largest. Using the Standard Gray Code with 4 digit binary numbers as a guide, describe a solution to this Tower of Hanoi problem. Specify the steps in a simple form such as "Move disk 1 to peg III" and indicate which binary number in the Standard Gray Code corresponds to each step in your solution.