What is Gray Code?

Gray code is basically a binary number system in which the successive binary numbers differ by exactly one bit. We can write a sequence of binary numbers for any K bits as a grey code sequence. For example, the sequence of 3-bit binary numbers is 000,001,011,010,110,111,101,100 where each consecutive numbers differ by exactly one bit.

Unlike binary numbers, a gray code is not weighted i.e. the bits of the gray code do not have any weight associated with them according to their position. For example, in the binary system, the least significant bit has a weight $2^0 = 1$, the second bit from the right has a weight $2^1$, and so on. The bits in the gray code are positional but are not weighted like in binary code, They are numeric representations of a cyclic encoding scheme and they will repeat after a certain interval.

How to Construct an n-bit Gray Code?

Reflect and Prefix method:

It is a recursive method to generate the n-bit gray code. The steps to generate a gray code are as follows:

1. Base case is that we generate for n = 1, the codes generated as 0 and 1.
2. Take the list of previous codes and add the reversed list of the same codes into it i.e. add sequence 1, 0 in 0, 1 and the final one is 0, 1, 1, 0.
3. Now, we add prefix 0 to the original list i.e. first half, and add prefix 1 to the reversed list i.e. second half: 00,01,11,10.

The above process is shown in the image below:

In this way, gray codes can be generated.

What are the Types of Gray Codes?

There are mainly three types of gray codes.

1) N-ary Gray code: These codes are also called non-boolean gray codes because they use non-boolean values in their encoding. A 4-array gray code contains values 0,1,2,3 in its encoding and it is called quaternary. 00, 01, 02, 03, 13, 12, 11, 10, 20, 21, 22, 23, 33, 32, 31, 30 It can be seen that there is exactly a 1-bit difference between any two consecutive gray codes.

2) Two-dimensional gray codes (n,k):

Two-dimensional gray codes are used in location identification schemes and are used in communication to remove the number of bits errors in QAM (quadrature amplitude modulation). In two-dimensional gray code encoding, the horizontally and vertically adjacent bits differ by 1-bit and the diagonally adjacent bits differ by 2-bits.

3) Balanced Gray codes: A balanced gray code is a gray code in which the bit changes are equally distributed among the bit positions up to a high possibility. It can be shown that n-bit balanced gray code can be constructed for all integers n.

What are the uses of Gray codes?

1) Error detection: Due to the property of gray codes that only a single bit is different between two consecutive numbers, it is used to detect errors and is used for digital communication mediums like cable TV.

2) Genetics: Gray codes are used in genetic algorithm theory.

3) Tower of Hanoi problem: Gray code is used to solve the tower of Hanoi problem.

4) Position encoders: Gray codes are used in position encoders in preference over weighted binary encoding.

5) Boolean circuit Minimization: Gray codes are used to minimize the boolean circuits by labeling the axes of karnaugh maps.

Examples of Gray codes

Let's see an example of a 4-bit gray code and its corresponding binary code:

We can see that any two consecutive numbers in the gray code sequence differ by 1-bit while this is not the case in binary code.

Learn more about Data Structures

To learn more about data structures go to the data structures