gray_code.ipynb

Kernel: SageMath 9.4

Fun with the Gray Code

This function returns the $k$th $n$ bit gray code string, $0 \leq k \lt 2^k$.

def gray(n,k):
    if k<0 or k>=2^n:
        print("error")
        return []
    elif n==1:
        return [k]
    else:
        if k<2^(n-1):
            return [0]+gray(n-1,k)
        else:
            return ([1]+gray(n-1,2^n-1-k))

gray(10,5)

[0, 0, 0, 0, 0, 0, 0, 1, 1, 1]

gray(10,5000)

error

[]

[gray(4,k) for k in range(2^4)]

[[0, 0, 0, 0],
 [0, 0, 0, 1],
 [0, 0, 1, 1],
 [0, 0, 1, 0],
 [0, 1, 1, 0],
 [0, 1, 1, 1],
 [0, 1, 0, 1],
 [0, 1, 0, 0],
 [1, 1, 0, 0],
 [1, 1, 0, 1],
 [1, 1, 1, 1],
 [1, 1, 1, 0],
 [1, 0, 1, 0],
 [1, 0, 1, 1],
 [1, 0, 0, 1],
 [1, 0, 0, 0]]

Given an $n$ bit sequence, this function returns its position in the n bit Gray code, expressed as a sequence of binary digits.

def gray_decoder(seq):
    p=[]
    state=0
    for bit in seq:
        if state==0:
            state=bit
            p=p+[bit]
        else:
            state=1-bit
            p=p+[1-bit]
    return p

for l in map(lambda s:gray_decoder(s),[gray(3,k) for k in range(8)]): print(l)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-8-0ebb3f9d5225> in <module>
----> 1 for l in map(lambda s:gray_decoder(s),[gray(Integer(3),k) for k in range(Integer(8))]): print(l)

<ipython-input-8-0ebb3f9d5225> in <lambda>(s)
----> 1 for l in map(lambda s:gray_decoder(s),[gray(Integer(3),k) for k in range(Integer(8))]): print(l)

NameError: name 'gray_decoder' is not defined

p=gray_decoder([1,0,1,1,0])

SageMath doesn't seem to have a function that converts a list of digits to a number, so here is the definiton of one that coverts a list using a specified base.

def list_to_number(list,base): 
    if len(list)==1:
        return list[0]
    else:
        return list_to_number(list[:-1],base)*base + list[-1]

list_to_number([1,1,1],2)

7

This verifies that the [removed]gray_decoder does invert [removed]gray.

[list_to_number(row,2) for row in map(lambda s:gray_decoder(s),[gray(3,k) for k in range(8)])]

[0, 1, 2, 3, 4, 5, 6, 7]

four=map(lambda s:gray_decoder(s),[gray(3,k) for k in range(8)])

four

[[0, 0, 0],
 [0, 0, 1],
 [0, 1, 0],
 [0, 1, 1],
 [1, 0, 0],
 [1, 0, 1],
 [1, 1, 0],
 [1, 1, 1]]