[Exercise] Gray code

geek

Implement a Gray code encoder and decoder, e.g., gray_encode(5) = 7 and gray_decode(5) = 6.

Joe

I wrote this function that generates the gray code recursively for n-bits. It is based on the algorithm defined in the wikipedia article:

def gray_code(n, numlist=[""]):

    if n == 0:
        return numlist

    _tmpnumlist = numlist[:]
    _tmpnumlist.reverse()

    a = [ "0" + i for i in numlist]
    b = [ "1" + i for i in _tmpnumlist]

    return gray_code(n-1, a+b)

print gray_code(3) # prints a 3-bit Gray code

output:

['000', '001', '011', '010', '110', '111', '101', '100']

mesa177

There's a really cool way of finding the gray code of a decimal number:

1) Convert the decimal number in to its binary representation
2) Starting from the MSB, add 0 to the MSB then mod it by 2; the result is the MSB of the gray code
3) Similar to step 1, and moving from the MSB to LSB, add each nth bit to the (n-1)th bit, mod it by 2, and the result is the nth bit of the gray code.

Examples:

1) If we have the decimal value 15, the binary representation is 1111.
Starting from MSB, ie bit 1, add to 0, it's 1. 1 mod 2 is 1, so the MSB of the gray code is 1.
Second bit is 1, add to previous bit ie 1, result is 0. 0 mod 2 is 0, so the second MSB of the gray code is 0.
Similarly the 3rd bit is 1, add to previous bit ie 1, result is 0. 0 mod 2 is 0, so the third MSB of the gray
code is 0.
Finally the 4th bit ie LSB is 1, add to previous bit ie 1, result is 0. 0 mod 2 is 0, so the LSB of the gray code
is 0.

Hence, the gray code of 1111 is 1000 => gray code of 15 is 8.

1) If we have the decimal value 9, the binary representation is 1001.
Starting from MSB, ie bit 1, add to 0, it's 1. 1 mod 2 is 1, so the MSB of the gray code is 1.
Second bit is 0, add to previous bit ie 1, result is 1. 1 mod 2 is 1, so the second MSB of the gray code is 1.
Similarly the 3rd bit is 0, add to previous bit ie 0, result is 0. 0 mod 2 is 0, so the third MSB of the gray
code is 0.
Finally the 4th bit ie LSB is 1, add to previous bit ie 0, result is 1. 1 mod 2 is 1, so the LSB of the gray code
is 1.
Hence, gray code of 1001 is 1101 => gray code of 9 is 13.

Right now I'm tired from a long day at work, so code will have to wait a while.

mesa177

I didn't think this through enough when I was taking logic design, but now I do: 0 mod 2 is always 0, and 1 mod 2 is always 1. The input is identical to the output, so we can just skip the whole process.

[Edit] Since the addition is a one-bit based addition, and we don't need the carry, we can simply use a xor for the process [/Edit].

The new algorithm would be:
1) Convert the decimal number in to its binary representation
2) Starting from the MSB, Xor 0 to the MSB; the result is the MSB of the gray code
3) Similar to step 1, and moving from the MSB to LSB, Xor each nth bit to the (n-1)th bit, and the
result is the nth bit of the gray code.
4) Convert the result binary number to its decimal form, et voila the gray code.

This exercise needs a VHDL code >)

mesa177

Code in Matlab/Octaviz:

A = 1; % Dummy value assigned to input variable
while (~isempty(A))
      A = input('Please enter a value (to exit, click enter): ');
      if (~isempty(A))
          A_bin_str = dec2bin(A);
          for i = 1:size(A_bin_str,2)
              A_bin(i) = str2double(A_bin_str(i));
          end
          A_bin_shft_rght = horzcat(0,A_bin);
          A_bin_shft_lft = horzcat(A_bin,0);
          temp_gray = xor(A_bin_shft_rght,A_bin_shft_lft);
          % The gray code of the entered value lies within the first n-1
          % bits of the result from Xoring process
          A_gray_code = bin2dec(num2str(temp_gray(1:size(temp_gray,2)-1)));
          fprintf('The gray code of the entered value %d is %d\n\n',A,A_gray_code);
          % Clearing the variables ensures that there will be no conflict
          % in handling matrix dimensions from one entry to another
          clear A_bin_str A_bin A_bin_shft_rght A_bin_shft_lft temp_gray
          clear A_gray_code  
      else
          disp('Exiting program...');
      end
end

Example:

Please enter a value (to exit, click enter): 5
The gray code of the entered value 5 is 7

Please enter a value (to exit, click enter): 14
The gray code of the entered value 14 is 9

Please enter a value (to exit, click enter): 9
The gray code of the entered value 9 is 13

Please enter a value (to exit, click enter): 123
The gray code of the entered value 123 is 70

Please enter a value (to exit, click enter): 
Exiting program...

Joe

mesa177, I couldn't come up with anything geeky enough for your bday, so I decided to implement your algorithm (your "trick" really. It reminded me of this trick we were taught to convert bin to hex...) in Python.

For what it's worth, it shows how expressive Python's syntax is. Reading it will feel like pseudo-code describing the simplest approach :)

The thing I enjoy most about this code is the implementation of XOR in function graypos.

def binpos (decnum, position):
    if (decnum % 2**position) >= (2**(position-1)):
        return 1
    else:
        return 0

def graypos (decnum, position):
    ''' return binpos(a) XOR binpos(a+1)
    '''
    if binpos(decnum, position) != binpos(decnum, position+1):
        return 1
    else:
        return 0

def graysize (decnum):
    i=0
    while decnum >= 2**i:
        i += 1
    return i

def gray (decnum):
    if decnum == 0:
        return "0"

    gray_list = []
    for idx in range(graysize(decnum)):
        gray_list.append(str(graypos(decnum, idx+1)))
    gray_list.reverse()
    return "".join(gray_list)

You can test it like this:

>>> for i in range(10):
print gray(i)

0
1
11
10
110
111
101
100
1100
1101