Gray Code

Monday, January 22nd, 2018 - Digital Electronics

The Gray code was designed by Frank Gray at Bell Labs and patented in 1953. It is an unweighted binary code in which two successive values differ only by 1 bit. Owing to this feature, the maximum error that can creep into a system using the binary Gray code to encode data is much less than the worst-case error encountered in the case of straight binary encoding. Table gray code lists the binary and Gray code equivalents of decimal numbers 0–15. An examination of the four-bit Gray code numbers, as listed in Table below, shows that the last entry rolls over to the first entry. That is, the last and the first entry also differ by only 1 bit. This is known as the cyclic property of the Gray code. Although there can be more than one Gray code for a given word length, the term was first applied to a specific binary code for non-negative integers and called the binary-reflected Gray code or simply the Gray code.

There are various ways by which Gray codes with a given number of bits can be remembered. One such way is to remember that the least significant bit follows a repetitive pattern of ‘2’ (11, 00, 11,…), the next higher adjacent bit follows a pattern of ‘4’ (1111, 0000, 1111,…) and so on. We can also generate the n-bit Gray code recursively by prefixing a ‘0’ to the Gray code for n−1 bits to obtain the first 2n−1 numbers, and then prefixing ‘1’ to the reflected Gray code for n−1 bits to obtain the remaining 2n−1 numbers. The reflected Gray code is nothing but the code written in reverse order. The process of generation of higher-bit Gray codes using the reflectand-prefix method is illustrated in table below. The columns of bits between those representing the Gray codes give the intermediate step of writing the code followed by the same written in reverse order.

Gray Code

Gray code

Generation Of Higher-Bit Gray Code Numbers

Generation of higher-bit Gray code numbers

Binary–Gray Code Conversion

A given binary number can be converted into its Gray code equivalent by going through the following steps:

  1. Begin with the most significant bit (MSB) of the binary number. The MSB of the Gray code equivalent is the same as the MSB of the given binary number.
  2. The second most significant bit, adjacent to the MSB, in the Gray code number is obtained by adding the MSB and the second MSB of the binary number and ignoring the carry, if any. That is, if the MSB and the bit adjacent to it are both ‘1’, then the corresponding Gray code bit would be a ‘0’.
  3. The third most significant bit, adjacent to the second MSB, in the Gray code number is obtained by adding the second MSB and the third MSB in the binary number and ignoring the carry, if any.
  4. The process continues until we obtain the LSB of the Gray code number by the addition of the LSB and the next higher adjacent bit of the binary number.

The conversion process is further illustrated with the help of an example showing step-by-step conversion of (1011)2 into its Gray code equivalent:

Binary            1011
Gray code   1- – –
Binary            1011
Gray code   11- –
Binary            1011
Gray code   111-
Binary            1011
Gray code   1110

Gray Code–Binary Conversion

A given Gray code number can be converted into its binary equivalent by going through the following steps:

  1. Begin with the most significant bit (MSB). The MSB of the binary number is the same as the MSB of the Gray code number.
  2. The bit next to the MSB (the second MSB) in the binary number is obtained by adding the MSB in the binary number to the second MSB in the Gray code number and disregarding the carry, if any.
  3. The third MSB in the binary number is obtained by adding the second MSB in the binary number to the third MSB in the Gray code number. Again, carry, if any, is to be ignored.
  4. The process continues until we obtain the LSB of the binary number.

The conversion process is further illustrated with the help of an example showing step-by-step conversion of the Gray code number 1110 into its binary equivalent:

Gray code     1110
Binary         1- – –
Gray code     1110
Binary         10 – –
Gray code     1110
Binary         101
Gray code     1110
Binary         1011

n-ary Gray Code

The binary-reflected Gray code described above is invariably referred to as the ‘Gray code’. However, over the years, mathematicians have discovered other types of Gray code. One such code is the n-ary Gray code, also called the non-Boolean Gray code owing to the use of non-Boolean symbols for encoding. The generalized representation of the code is the (n, k-Gray code, where n is the number of independent digits used and k is the word length. A ternary Gray code (n=3) uses the values 0, 1 and 2, and the sequence of numbers in the two-digit word length would be (00, 01, 02, 12, 11, 10, 20, 21, 22). In the quaternary (n=4) code, using 0, 1, 2 and 3 as independent digits and a two-digit word length, the sequence of numbers would be (00, 01, 02, 03, 13, 12, 11, 10, 20, 21, 22, 23, 33, 32, 31, 30). It is important to note here that an (n, k-Gray code with an odd n does not exhibit the cyclic property of the binary Gray code, while in case of an even n it does have the cyclic property.

The (n, k-Gray code may be constructed recursively, like the binary-reflected Gray code, or may be constructed iteratively. The process of generating larger word-length ternary Gray codes is illustrated in table below. The columns between those representing the ternary Gray codes give the intermediate steps.

Gray Code Applications

  1. The Gray code is used in the transmission of digital signals as it minimizes the occurrence of errors.
  2. The Gray code is preferred over the straight binary code in angle-measuring devices. Generation of a larger word-length ternary Gray code
    Generation of a larger word-length ternary Gray code

    Use of the Gray code almost eliminates the possibility of an angle misread, which is likely if the angle is represented in straight binary. The cyclic property of the Gray code is a plus in this application.
  3. The Gray code is used for labelling the axes of Karnaugh maps, a graphical technique used for minimization of Boolean expressions.
  4. The use of Gray codes to address program memory in computers minimizes power consumption. This is due to fewer address lines changing state with advances in the program counter.
  5. Gray codes are also very useful in genetic algorithms since mutations in the code allow for mostly incremental changes. However, occasionally a one-bit change can result in a big leap, thus leading to new properties with Gray code.

You may also like, related Gray Code