Binary Reflected Gray Code

May 2, 2014

An n-bit Gray sequence is a sequence of 2n values, starting from 0, in which each differs from its predecessor by a single bit. There are always 2n−1 n-bit Gray sequences; for instance, the two 2-bit Gray sequences are 0, 1, 3, 2 and 0, 2, 3, 1. It is easier to see the Gray sequences when they are written in binary; the two 2-bit Gray sequences written in binary are 00, 01, 11, 10 and 0,0 10, 11, 01, where it is clear that each element of the sequence differs from the previous one by only one bit.

Although there are many possible Gray sequences for any given number of bits, there is one Gray sequence, known as the binary reflected gray code BRGC, that is almost always the Gray sequence that is being discussed. Such sequences are generated recursively from the next-smaller sequence by reversing the sequence, prefixing the entries of the original sequence with a 0-bit, prefixing the entries of the reversed sequence with a 1-bit, then concatenating the two sequences. For instance, given the 2-bit Gray sequence 00, 01, 11, 10, its reversal is 10, 11, 01, 00, adding a 0-bit to the original gives 000, 001, 011, 010, adding a 1-bit to the reversal gives 110, 111, 101, 100, and concatenating the two gives 000, 001, 011, 010, 110, 111, 101, 100, which is 0, 1, 3, 2, 6, 7, 5, 4.

Your task is to write a function that generates an n-bit binary reflected Gray sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

My solution



In [16]:

    
%pylab inline









    



Populating the interactive namespace from numpy and matplotlib



In [28]:

    
def BRGC(n):
    # Returns type string
    if n == 1:
        return ['0', '1']
    else:
        return map(lambda x: str.__add__('0', x), BRGC(n-1)) + \
               map(lambda x: str.__add__('1', x), BRGC(n-1)[::-1])
def BCRG_int(n):
    # Returns type int
    return map(lambda x: int(x, 2), BRGC(n))



In [31]:

    
BCRG_int(4)









    Out[31]:





[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]



In [32]:

    
BRGC(4)









    Out[32]:





['0000',
 '0001',
 '0011',
 '0010',
 '0110',
 '0111',
 '0101',
 '0100',
 '1100',
 '1101',
 '1111',
 '1110',
 '1010',
 '1011',
 '1001',
 '1000']



In [33]:

    
# All unique values
a = BRGC(10)
len(set(a)) == len(a)









    Out[33]:





True

Solved on May 2, 2014

-- Giuseppe Venturini