Welcome, guest | Sign In | My Account | Store | Cart

Please refer to: http://en.wikipedia.org/wiki/Gray_code

The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one digit.

The reflected binary code was originally designed to prevent spurious output from electromechanical switches. Today, Gray codes are widely used to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.

Example Gray Codes: 2-bit Gray code 00 01 11 10

3-bit Gray code 000 001 011 010 110 111 101 100

4-bit Gray code 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

Python, 75 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
def isOdd(integer):
    #assert isinstance(integer, int)
    return integer % 2 == 1

def isEven(integer):
    #assert isinstance(integer, int)
    return integer % 2 == 0

def _list_to_string(li):
    return ''.join(map(str, li))

class GrayCode(object):
    def __init__(self, nbits):
        self._nbits = nbits
        self._grayCode = []
        self.__generate()

    def __getitem__(self, i):
        return self._grayCode[i]

    def __str__(self):
        return str(self._grayCode)

    __repr__ = __str__

    def __iter__(self):            
        return self._grayCode.__iter__()

    def __generate(self):
        li = [0 for i in xrange(self._nbits)]
        self._grayCode.append(_list_to_string(li))

        for term in xrange(2, (1<<self._nbits)+1):
            if isOdd(term):                
                for i in xrange(-1,-(self._nbits),-1):
                    if li[i]==1:                        
                        li[i-1]=li[i-1]^1                        
                        break
                    
            if isEven(term):
                li[-1]=li[-1]^1

            self._grayCode.append(_list_to_string(li))

class GrayCodeIterator(object):
    def __init__(self, nbits):
        self._nbits = nbits

    def __iter__(self):
        li = [0 for i in xrange(self._nbits)]
        yield _list_to_string(li)

        for term in xrange(2, (1<<self._nbits)+1):
            if isOdd(term):                
                for i in xrange(-1,-(self._nbits),-1):
                    if li[i]==1:                        
                        li[i-1]=li[i-1]^1                        
                        break
                    
            if isEven(term):
                li[-1]=li[-1]^1

            yield _list_to_string(li)


if __name__=='__main__':
    d = 4
    codes=GrayCode(d)
    print '%d digits gray codes:' % d
    print codes
    print 'Using Iterator:'
    #for c in GrayCode(20):  
    #    print c
    for c in GrayCodeIterator(20):
        print c

In the implementation, GrayCode returns a list of gray codes given by the number of bits, and GrayCodeIterator returns an iterator, with much higher memory efficiency.

4 comments

greg p 12 years, 11 months ago  # | flag

Cool deal, I made it into an online utility here so people can try it out.

Aaron Gallagher 12 years, 11 months ago  # | flag

I'm assuming you're using the ugly reduce hack because sum complained at you? The right way to do it is like so, where li is your list: s = ''.join(str(i) for i in li) Lines 21-22 can be replaced with '__repr__ = __str__' if you put it after the def __str__ block. I'm not sure why you don't just generate the list of strings instead of converting it every time, or why you don't use a generator expression instead of returning the iter() of a list from a list comprehension, or why you're doing the isinstance assertion in isEven and isOdd. You can also rename the 'next' method of GrayCodeIterator to __iter__ and remove the old __iter__.

Aaron Gallagher 12 years, 11 months ago  # | flag

Ack, figures that it came out wrong because I didn't preview it. I forgot I had to have two newlines before and after code samples.

s = ''.join(str(i) for i in li)
Shao-chuan Wang (author) 12 years, 11 months ago  # | flag

Hi, Aaron Gallagher. Thank you for your excellent suggesions. I have made some modifications, and it should look much more elegant right now. :)

Created by Shao-chuan Wang on Sun, 21 Dec 2008 (MIT)
Python recipes (4591)
Shao-chuan Wang's recipes (22)

Required Modules

  • (none specified)

Other Information and Tasks