Re: local bit flip Gray codes
- To: Eugene Leitl <Eugene.Leitl@xxxxxxxxxxxxxxxxxxx>
- Subject: Re: local bit flip Gray codes
- From: <eugene.leitl@xxxxxxxxxxxxxxxxxxx>
- Date: Mon, 12 Jun 2000 20:24:00 -0400
- CC: fork@xxxxxxxx
- Organization: Insta.com, Inc.
- References: <14661.24510.116531.922865@lrz.uni-muenchen.de>
- Resent-Date: Mon, 12 Jun 2000 16:27:53 -0700 (PDT)
- Resent-From: Eugene Leitl <eugene.leitl@xxxxxxxxxxxxxxxxxxx>
- Resent-Message-ID: <14661.29177.354358.865029@lrz.uni-muenchen.de>
- Resent-To: <transhumantech@xxxxxxxxxxxxx>, <transhumantech@xxxxxxxxxxx>, <MISC>
From: "Stephen D. Williams" <sdw@lig.net>
Ok, overkill answer here:
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;
unsigned int mask ;
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;
unsigned long int mask;
int bit;
mask = 0x80;
for (j=0;j<*numbts;j++) {
bit =(mask & *num) ? 1 : 0;
printf("%d", bit);
mask >>=1;
}
return(0);
}
And g2b.c:
#include <stdio.h>
int main(int args, unsigned char *argc[]) {
unsigned char num, gnum;
int j, bit,numbits=8;
unsigned int mask ;
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;
unsigned long int mask;
int bit;
mask = 0x80;
for (j=0;j<*numbts;j++) {
bit =(mask & *num) ? 1 : 0;
printf("%d", bit);
mask >>=1;
}
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
Cool article about async clocks and Grey Code addressing:
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:
http://www.ubasics.com/adam/electronics/doc/rotryenc.shtml
sdw
--
Insta.com - Revolutionary E-Business Communication
sdw@insta.com Stephen D. Williams Senior Consultant/Architect http://sdw.st
43392 Wayside Cir,Ashburn,VA 20147-4622 703-724-0118W 703-995-0407Fax Jan2000
