Gray-Codes

quote:

---

Original post by Ridcully.

I have to write a work for school about the gray code and it''s fields of application.

---

Grey code? As in electronics? If so email me and i''ll help. If i''m way of topic then sorry.

Dave



Regards,
David Stubbs

As software programmers, we are well accustomed to the binary (base 2) number system. Starting at 0000, we count upwards to 0001, 0010, 0011, 0100, 0101, .... etc and so forth. We count this way because it matches the way we naturally count.

However, machines don''t have to count this way, and there is benefit in not doing so. Why? Take a look at the transitions between binary numbers and how many bits change. Between 0000 and 0001, only 1 bit, but then 2, 1, 3, 1, 2, 1.... If an error occurred while the machine was scanning the pattern, it might not understand that an error occurred.

Greycode is a way to count in binary that forces exactly and only one bit to change each transition. So your counting looks like this: 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, ....etc

Now if the machine''s input scanner accidentally skips over an entry, it can immediately detect it because more than one bit has changed!

A while back, I came up with simple functions to generate greycodes on 32-bit integers... At least the first one is simple... I never tried figuring out a better way to do the reverse function. And remember, the ^ is intentional, meaning bitwise-xor.

/* These functions can also be limited to a subset of numbers (ie, 0..31) by appropriately changing the mask m (and also masking off the correct bits in the first function). */ int num2grey (int n) { return (n ^ (n >> 1)); } int grey2num (int g) { // this function is untested int n, m, x; m = ~0; // all bits are set x = 0; n = 0; while (m) { x = (x >> 1) ^ (g & m); n |= x; m >>= 1; } return n; }

---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!

thanks for the answers!

another question: i found out that you can use the gray code to solve certain puzzles such as the "towers of hanoi". does anybody know about this, and can supply me with some information?
and does anyone know any more areas where the gray code can be used? (apart from electronical ones)

thanks again
ridcully

n0p3x, did you check your mailbox recently?