## Chapter 4## Binary Numbers and the Standard Gray Code |

Back to List | Binary Numbers | The Standard Gray Code | The Tower of Hanoi

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.

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.

Let’s go the next stage. Start with the list:

- 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.

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.

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.

© 2000 by Addison Wesley Longman A division of Pearson Education |