Gray Code
Gray Code was actually invented by Bell Telephone Laboratories researcher George Stibitz in 1941.1 In a later patent application (1947), Frank Gray, also working for Bell Labs, named the coding scheme “reflected binary code.” 2 Today, the resulting code system is often called Gray Code.
Video Lecture
Motivation
During the middle part of the 20th century, the first automated telephone systems made use of electromechanical computers. The electromechanical switches in these systems had some manufacturing and implementation variability, which resulted in the switches flipping at different times. If the state of the switches was read prior to the switches all flipping, an incorrect value would be obtained.
Researchers at Bell Labs, including George Stibitz and Frank Gray, devised methods for implementing a sufficiently reliable telephone switching system using electromechanical computers. Stibitz described a method for working around the switch flip timing issue by encoding data in such a way that only 1 switch would be flipped when moving from one value to the next.
2-bit Gray Code
| Decimal | Gray |
|---|---|
| 0 | 00 |
| 1 | 01 |
| 2 | 11 |
| 3 | 10 |
As shown in Table 1, a 2-bit Gray Code follows the pattern 00, 01, 11, 10. After the number 3 is reached with this code, the overflow back to 0 is handled by flipping the first bit back to zero. In this way, only 1 switch is flipped to move from one number to the next.
4-bit Gray Code
To encode values higher than 3, it is necessary to use additional switches. Doubling to 4 switches permits representation of values up to 15:
| Decimal | Gray |
|---|---|
| 0 | 0000 |
| 1 | 0001 |
| 2 | 0011 |
| 3 | 0010 |
| 4 | 0110 |
| 5 | 0111 |
| 6 | 0101 |
| 7 | 0100 |
| 8 | 1100 |
| 9 | 1101 |
| 10 | 1111 |
| 11 | 1110 |
| 12 | 1010 |
| 13 | 1011 |
| 14 | 1001 |
| 15 | 1000 |
Once the 4-bit Gray Code (Table 2) overflows after 15, the coding returns to 0 by flipping off the first switch. Note that the first two digits of the 4-bit Gray Code change in the same order as the 2-bit Gray Code. The last two digits in the 4-bit Gray Code follow the 2-bit Gray Code by counting up and then back down, following the 2-bit Gray Code forward and then in reverse: 00, 01, 11, 10, 10, 11, 01, 00, and so forth. Gray Code can be written for numbers represented with a greater number of bits by following a similar approach.
Applications
Gray Code is still in use for some applications, even though electromechanical computers have been rendered generally obsolete by fully electronic ones. One use of Gray Code occurs in a circuit analysis technique known as a Karnaugh Map, which will be described in the next lesson.
References and Further Reading
-
George R. Stibitz. United States Patent 2307868: “Binary Counter.” Google Patents Reference ↩
-
Frank Gray. United States Patent 2632058: “Pulse Code Communication.” Google Patents Reference ↩
