Re: local bit flip Gray codes

From: Stephen D. Williams (sdw@lig.net)
Date: Mon Jun 12 2000 - 17:24:00 PDT

Eugene Leitl wrote:

> A somewhat unusual question, can someone point me towards resources on
> how to design local (only neighbouring bits change) bit flip Gray-ish
> codes, and how to design logics how to deal with them? Adders would be
> fine for starters.
>
> (This is about very long word and/or short clock arithmetics).

There is a standard Gray code, and it's compliment although I'm not sure how
standard it is. I've used Gray Code in a bulb-forming machine to encode the
shaft angle on the rotary body that moved the collets holding the quartz glass
tubes being formed by H-O2 torches and molds...

I've also seen code that converts between gray code and twos compliment,
here's one version:
http://fritter.phyast.pitt.edu/~jm/cprogs/bin2g.html
Binary to Gray conversion

This program takes a hexadecimal number which is binary and converts it
to a gray coded number. This program is designed to work for
numbers with fewer than 8 bits.

Sample compilation and output is below.

#include < stdio.h>

int main(int args, unsigned char *argc[]) {
unsigned char num, gnum;
int j, bit,numbits=8;

if (args!=2) {
printf("Usage: bin2g HexBinaryNumber\n");
return(-1);
}

if (args>2) {
printf("Second argument ignored\n");
}
num = (unsigned char ) strtoul(argc[1],(char **)NULL, 16);

/* bin2g is for numbers with bits fewer than 8, it works for any number
of bits, but the g2bin depends on the number of bits, currently, 8 */

if (num > 0xff) {
printf("Number must be smaller than 8 bits\n");
return(-1);
}

/* Calculate the grey code equivalent */

gnum = num ^ (num >> 0x01);

printf("Decimal binary num is %lu\n", num);
printf("Decimal grey equivalent is %lu\n", gnum);
printf("Binary Number Grey code number \n");
printf(" ");
bitDump(&num, &numbits);
printf("\t \t");
bitDump(&gnum, &numbits);
printf("\n");
return(0);
}

/* bitDump function takes the number and the number of bits and prints
the binary equivalent of the number */

int bitDump(unsigned char *num, int *numbts){
int j;
int bit;
for (j=0;j<*numbts;j++) {
bit =(mask & *num) ? 1 : 0;
printf("%d", bit);
}
return(0);
}

And g2b.c:
#include <stdio.h>

int main(int args, unsigned char *argc[]) {
unsigned char num, gnum;
int j, bit,numbits=8;
if (args!=2) {
printf("Usage: g2bin GreyCodeNumber\n");
return(-1);
}

gnum=(unsigned char) strtoul(argc[1], (char **)NULL, 16);

#ifdef DEBUG

printf("Grey number is 0x%02x\n", gnum);

#endif

if (gnum > 0xff) {
printf("Number must be smaller than 8 bits\n");
return(-1);
}
num = gnum ^ (gnum >> 0x01) ^ (gnum >> 0x02) ^ (gnum >> 0x03)
^ (gnum >> 0x04) ^ (gnum >> 0x05) ^ (gnum >> 0x06) ^ (gnum >> 0x07);

printf("Decimal binary num is %lu\n", num);
printf("Decimal grey equivalent is %lu\n", gnum);
printf("Grey code number Binary Number\n");
printf(" ");
bitDump(&gnum, &numbits);
printf("\t \t");
bitDump(&num, &numbits);
printf("\n");
return(0);
}
int bitDump(unsigned char *num, int *numbts){
int j;
int bit;
for (j=0;j<*numbts;j++) {
bit =(mask & *num) ? 1 : 0;
printf("%d", bit);
}
return(0);
}

Or another:
http://www.progsoc.uts.edu.au/~telford/reference/algorithm/grey_code.text
As lookup table:

Grey Bin Dec
0000 0000 0
0001 0001 1

0011 0010 2
0010 0011 3

0110 0100 4
0111 0101 5
0101 0110 6
0100 0111 7

1100 1000 8
1101 1001 9
1111 1010 10
1110 1011 11
1010 1100 12
1011 1101 13
1001 1110 14
1000 1111 15

1000 0000 16
1001 0001 17
1011 0010 18
1010 0011 19
1110 0100 20
1111 0101 21
1101 0110 22
1100 0111 23
1100 1000 24
1101 1001 25
1111 1010 26
1110 1011 27
1010 1100 28
1011 1101 29
1001 1110 30
1000 1111 31

As state transitions (or limit cycles):

((0 0)
(1 1)
(2 3 2)
(4 6 5 7 4)
(8 12 10 15 8)
(9 13 11 14 9)
(16 24 20 30 17 25 21 31 16)
(18 27 22 29 19 26 23 28 18))

/*
* binary to grey code converter
*/
void binprint( int x )
{
printf( "%c%c%c%c%c%c%c%c (%d)\n",
x & 0x0080 ? '1' : '0',
x & 0x0040 ? '1' : '0',
x & 0x0020 ? '1' : '0',
x & 0x0010 ? '1' : '0',
x & 0x0008 ? '1' : '0',
x & 0x0004 ? '1' : '0',
x & 0x0002 ? '1' : '0',
x & 0x0001 ? '1' : '0',
x );
}

int b2g( int b ) { return( b ^ ( b >> 1 )); }
int g2b( unsigned int b )
{
int i, g = 0;
for( i = 0; i < 32; i++ )
{
g ^= b;
b >>= 1;
}
return( g );
}

int main( int argc, char *argv[])
{
int i;

for( i = 1; i < argc; i++ )
{
char *p;
int n;

n = strtol( argv[ i ], &p, 0 );
if( p > argv[ i ])
{
printf( "Input=" );
binprint( n );
printf( "bin->grey=" );
binprint( b2g( n ));
printf( "grey->bin=" );
binprint( g2b( n ));
}
else
{
printf( "??? %s ???\n", argv[ i ]);
}
}
return( 1 );
}
2600 Driving controller used Gray Code:
http://www.videogames.org/2600Stuff/DrivingControllers
Micromachined:
http://itri.loyola.edu/mems/c6_s4.htm

http://www.isdmag.com/Editorial/2000/design0003.html

How about some VHDL to implement it? (I can only get a general idea from the
VHDL, but looks very interesting.)
http://www.xilinx.com/products/spartan2/recipes/rec009.htm

On rotary encoders:
```--