Thursday, May 8, 2014

Generating Gray codes

Gray code is a sequence of n-bit binary code where each pattern differs with the previous pattern by only one bit.

For example 2-bit gray code is shown below.

00
01
11
10

Now we have two write a program to generate such a sequence for the given value (n). One algorithm to generate gray code is explained below. An n-bit gray code can be generated from (n-1) bit gray code as follows.

1-bit gray code is obvious; it is 0,1.
2-bit gray code can be generated as follows. 
  • Expand the sequence by adding it's elements in reverse order (in this case 1, 0).
  • Prepend zeros to the first half and Ones to the second Half

 0  0
 0  1
 -----
 1  1
 1  0

3-bit gray code can be generated similarly.

0  00
0  01
0  11
0  10
------
1  10
1  11
1  01
1  00

Below is the implementation of this algorithm in C++.