DSP Trick: Gray Code Conversion

From: Jerry Avins <jya@ieee.org>
Subject: Converting Between Binary and Gray Code
Date: 28 Sep 2000
Newsgroups: comp.dsp
THIS WORK IS PLACED IN THE PUBLIC DOMAIN

Name: Binary / Gray Code Conversion

Category: Algorithm

Application: Some sensors send information in Gray code. These must be converted to binary in order to do arithmetic with it. Occasionally, it is necessary to convert back.

Advantages: Higher speed or smaller code than other ways I've seen. (A neat way to do this is elusive enough that I've seen it done with a look-up table.)

Introduction: The by-the-book conversion of Gray to binary is O(N-1), where N is the word length. One of my algorithms is O(log(N)-1), where N is the word length rounded up to a power of two. The other is O(N-1) (including N-1 subroutine calls), but the code is very compact, especially if binary-to-Gray is also needed.

A Gray code is one in which adjacent numbers differ by one symbol. There are many Gray Codes, even in binary. They can be devised in any base. When Gray (or Gray code) is used without specifying which one, what is meant is reflected Binary Gray. To convert binary to Gray, it is only necessary to XOR the original unsigned binary with a copy of itself that has been right shifted one place. That is easy to do with common instructions. The cannonical way to convert Gray to binary is to XOR the bits one at a time, starting with the two highest bits, using the newly calculated bit in the next XOR. Ugh! I show two easier ways here. Robert Sherry wrote the actual C code. The function declarations make these shorts and the code assumes 16 bits; you can change that.

The Trick:

/*
        The purpose of this function is to convert an unsigned
        binary number to reflected binary Gray code.
*/
unsigned short binaryToGray(unsigned short num)
{
        return (num>>1) ^ num;
}
A tricky Trick: for up to 2^n bits, you can convert Gray to binary by
performing (2^n) - 1 binary-to Gray conversions. All you need is the
function above and a 'for' loop.
/*
        The purpose of this function is to convert a reflected binary
        Gray code number to a binary number.
*/
unsigned short grayToBinary(unsigned short num)
{
        unsigned short temp = num ^ (num>>8);
        temp ^= (temp>>4);
        temp ^= (temp>>2);
        temp ^= (temp>>1);
        return temp;
}