Talk:Gray code

From Wikipedia, the free encyclopedia

Archives:

  • /Archive 1
    • Old discussion not currently relevant to article

Contents

[edit] Real numbers?

Isn't it possible to give the real numbers a gray code representation? But the article only mentions integers. A5 18:42, 20 Apr 2005 (UTC)

Maybe....though I had never heard of doing it. I suppose you can define a Gray code sequence for non-binary numbers such that only one digit changes. Following the same method for generating binary Gray codes, for trinary:

(trinary Gray code moved to main article)

You can extend this to decimal if you wish. Hmm, maybe I'll add trinary to the article. Cburnett 19:03, Apr 20, 2005 (UTC)

This doesn't exactly answer the original question. You can have gray codes for other bases, but can you have one for the real numbers? The immediate answer seems to be no, since there's no such thing in the real numbers as two "successive" numbers. Deco 00:25, 21 Apr 2005 (UTC)
You can represent real numbers in Gray code....but to finite precision. The point of the above is that you can easily find a Gray code for base 10 so its just if you care about infinite precision. Cburnett 01:25, Apr 21, 2005 (UTC)
Gray codes are codes where neighbouring elements only differ in one symbol. On the real number line, there is no such thing as a neighbour - between any two numbers, there are infinitely many other numbers--Niels Ø 08:45, Apr 21, 2005 (UTC).

There are times when it is convenient to think of the bits from a sensor (whether it uses natural binary codes or gray codes) as bits of a binary fraction (i.e., a value from 0 to 1), rather than the bits of a binary integer.

Let's think about rotary encoders (like the one in the article) with 2, 3, 4, 5, 6, ... and N rings. (It doesn't matter what order the rings are in, so let's put the coarser rings nearer the center).

If you look carefully, the 7-ring encoder is just like the 8-ring coder with the 8th (outermost) ring filed off. The 6-ring encoder is just like the 7-ring encoder with the 7th (outermost) ring filed off.

If we represent these as fractional bits (rather than trying to make an integer out of them), it makes it easier to write software that can handle any kind of encoder (with any number of rings).

When encoder positions are represented as (fixed-point arithmetic) fractions such as

0.0100100111000000 and
0.0110110111000000

, software can find the angle between encoder position without needing to know exactly how many rings the encoder has. Then it is easy to upgrade to a more-precise encoder (more rings) or reduce cost by substituding a cheaper encoder (fewer rings), without changing any software.

When encoder positions are represented as integers such as

01001001110. and
01101101110.

, software needs to know exactly how many rings the encoder has, and usually needs to be re-compiled whenever the number of rings changes (which can be annoying).

Getting back to the original point: If you can give me a natural binary representation of a "real number", I can give you a (binary) Gray code representation of that number.

Does that answer the original question?

Is this something that should go into the article ?

--DavidCary 18:23, 14 May 2005 (UTC)

[edit] n-ary gray codes

Currently, two sections in the article deals with non-binary Gray codes. Both sections may have merit, so I guess they should be merged. --Niels Ø 08:24, Apr 21, 2005 (UTC)

Doh, I missed the n-ary section. Merged. Cburnett 16:28, Apr 21, 2005 (UTC)

Are n-ary gray codes actually *used* for anything, or are they only interesting to mathematicians? --DavidCary 05:37, 6 November 2005 (UTC)

An example: I'm generating a list of colours such that each colour is "nearby" to the next in RGB-space. If each coordinate can take n values, then an (n, 3)-Gray code is what I'm after. --Taejo|대조 13:21, 23 June 2007 (UTC)

Jos.koot 23:24, 23 November 2006 (UTC) : added a real working Scheme implementation of the algorithm together with an algorithm computing one single element of a Gray code and its inverse. In the pseudo algorithm the use of array n[k+1] is not needed and the arrays can be properly sized to k elements by halting when i grows out of range.

[edit] other applications of gray codes

Added some explanation on Gray Codes in Genetic Algorithms. -Shiri (a newbie)

[edit] am i correct in thinking

that a grey code cannot exist for a circular sequence with an odd number of values? Plugwash 01:43, 26 December 2005 (UTC)

Correct. This is evident because going from one number to the next toggles one bit. An odd number of toggles cannot produce the original value; at least one bit must be different. Non-circular sequences are possible, of course. Deco 02:13, 26 December 2005 (UTC)
What about the sequence (00, 01, 11, 10, 20, 21, 22, 12, 02)? --Pezezin 23:22, 30 June 2006 (UTC)
The argument applies to binary Gray codes only. For larger bases, the situation is different.--Niels Ø 09:31, 24 November 2006 (UTC)

A remark should be added that cyclic ternary gray codes do exists for every k. (I don't know about (n,k) codes with n>3) Examples: (2,3) : (000 200 210 010 110 112 212 012 022 222 122 102 202 002 001 101 201 211 111 011 021 121 221 220 020 120 100)

(2,4): (0000 1000 1200 0200 2200 2210 0210 1210 1010 0010 2010 2110 0110 1110 1112 2112 0112 0212 2212 1212 1012 2012 0012 0022 2022 1022 1222 2222 0222 0122 2122 1122 1102 2102 0102 0202 2202 1202 1002 2002 0002 0001 1001 2001 2101 1101 0101 0201 1201 2201 2211 1211 0211 0111 1111 2111 2011 1011 0011 0021 1021 2021 2121 1121 0121 0221 1221 2221 2220 0220 1220 1020 0020 2020 2120 0120 1120 1100 0100 2100 2000)

These circular ternary gray codes can easily be produced by

(define (circular-ternary-gray-code k)
 (let-values (((f t r) (values 0 1 2))) ; permutations of 0, 1 and 2 generate different gray codes
  (define (long h f t r)
   (if (positive? h)
    (let ((h (sub1 h)))
     (long h f t r)
     (move h f r t)
     (long h t f r)
     (move h r t f)
     (long h f t r))))
  (define (strt h f t r)
   (if (positive? h)
    (let ((h (sub1 h)))
     (strt h f r t)
     (move h f t r)
     (long h r t f))))
  (define (fini h f t r)
   (if (positive? h)
    (let ((h (sub1 h)))
     (long h f r t)
     (move h f t r) 
     (fini h r t f))))
  (define result ())
  (define pattern (make-vector k f))
  (define (move h f t r)
   (vector-set! pattern h t)
   (set! result (cons (vector->list pattern) result)))
  (if (positive? k)
   (let ((h (sub1 k)))
    (strt h f r t) 
    (move h f t r) 
    (long h r f t) 
    (move h t r f) 
    (long h f t r) 
    (move h r f t)
    (fini h t f r)))
  result))

Furthermore a O(k) algorithm exists for computing the i-th element of the gray codes produced by the above algorithm. The inverse exists too, i.e. a function that accepts a gray code and returns the i telling which element it is. In fact the ternary gray codes produced by the above algorithm show how to move a tower of hanoi Tower of hanoi from one peg back onto the same peg while passing every feasible distribution of disks exactly once (circular Hamilton path)

Jos.koot 13:40, 29 November 2006 (UTC)

[edit] Single-Track Gray Codes

It's the inner two tracks of Figure 1 that are the same except for an angular offset, and the inner track supplies the most significant bit. I have changed the text to correspond. It seems an unlikely error, though - has the figure been changed?

I made the same changes in the rotary encoder article.

       - Jim Van Zandt

[edit] Are those programming examples really necessary?

If you think it would help, I could provide some alternative versions in Javascript, BASIC, FORTRAN and Z80 opcodes. We could even go the whole hog and and merge this page with the list of hello world programs. What do you reckon? -- Sakurambo 22:06, 17 May 2006 (UTC)

Assuming you're being sarcastic, people have a bizarre tendency to add implementations in their favourite language to articles. Just cut out the ones you don't like. Deco 23:28, 30 June 2006 (UTC)
The proposed languages are not bizarre enough for the bizarre tendency! If you can write it for Atanasoff-Berry Computer or at least in assembler for PDP-8/System360, it would be another story :-) Beyond the joke, I would say that all those implementations are subject to WikiBooks and should be moved there (leaving just a link here). -- Goldie (tell me) 20:49, 5 September 2006 (UTC)
Or for my wiki, LiteratePrograms. </plug> :-) Deco 13:01, 20 November 2006 (UTC)

[edit] Gray code is not invented by Frank Gray

Frank Gray have not been born when the reflective binary code was invented. I do not know who have invented it either but the code was already in use in the mid-XIX century. In the Gray's patent it is clearly stated that he is claiming only the receiver and the implemented method for translation.

Elisha Gray does have some good chances to be the first who have put the code in an electrical aparatus but anyone's "invention" will have to be proved. I have no enough time to fix the name across the whole article. -- Goldie (tell me) 21:39, 5 September 2006 (UTC)

There is no evidence to connect Elisha Gray to the Gray code, but several gray-code-like patterns and devices do pre-date Frank Gray's patent, according to the study by Don Knuth. Dicklyon 23:30, 23 November 2006 (UTC)

[edit] Code Bug

The following code can become an infinite loop:

In the programming language C, a conversion from a Gray code g to an unsigned binary representation b can be achieved efficiently through:

 b = g;
 while (g >>= 1) {b ^= g;}

INTERNATIONAL STANDARD ISO/IEC 9899, Programming languages — C

6.5.7 Bitwise shift operators

4 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 ´ 2E2, reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 ´ 2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

5 The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined. —The preceding unsigned comment was added by Crm123 (talk • contribs) 17:24, 7 May 2007 (UTC).

[edit] Code snippets

Why so many code snippets? Most of them are not even particularly intelligible. I bet if we wanted clarity and precision, then matlab code would beat them all. Any opinions? Dicklyon 06:58, 10 December 2006 (UTC)

For example, compare this to the others to convert binary B to Gray G:

 G = bitxor(B, bitshift(B, -1));

The other direction probably requires a loop and more bit twiddling, though. Dicklyon 07:11, 10 December 2006 (UTC)

OK, even though I wasn't kidding, I take it back. Reading the talk above, I took the suggestion and removed the ones I didn't like, which was all of them. Pseudocode is enough, since the details of the others only obscure the point, except for programmers who know the language; and they don't need it. Dicklyon 07:21, 10 December 2006 (UTC)

I am totally in favour of this. Gray codes are generally used in electronic hardware, so personally I don't see the need for any software examples at all. -- Sakurambo 桜ん坊 11:25, 10 December 2006 (UTC)
Well, now that hardware is usually designed by writing Verilog code, code is the lingua-franca of algorithms, so we really out to have something. But showing off programming language features and syntax is not the point. Dicklyon 17:31, 10 December 2006 (UTC)
I would like to add here that LISP is one of those languages famous for being unreadable to someone unfamiliar with it. Pseudocode? Better formatting? I'll leave it to you all, but as it stands I didn't find the snippets very illuminating. Shinobu 11:37, 17 May 2007 (UTC)

[edit] gray code toy worth a mention?

The Brain Puzzler [1] was a mechanical toy produced in the 1970s or early 80s. The solution to the puzzle was a RBGC. Worth a link from the article? 216.220.208.238 16:24, 15 December 2006 (UTC)

The "Tower of hanoi" external link is dead (404).

[edit] Single track Gray code image

I've added an image to the section, corresponding with the table, but I'm too lazy to write a caption. Shinobu 11:14, 17 May 2007 (UTC)

Is that the image that the text in that section is calling "Figure 1"? Rather than refer to the figure, the figure needs a caption that calls to the reference.

No, figure 1 refers to the normal rotary encoder. Shinobu 08:39, 11 June 2007 (UTC)


[edit] Anti-Gray Codes?

Is there a code where the bit patterns of successive elements differ from each other by a maximal, rather than minimal, number of bits?

The problem with Gray codes for positional measurements is that you're vulnerable to misreads: if you get some birdshit on one of your black blobs and it goes white, for instance, if it's the bit that differs between that position and one of its neighbours, you can no longer detect that transition. Ditto if your photocell is flaky or something. With an anti-Gray code, you have multiple bits changing at every transition, so you're much more likely to detect it. If you have a shitty photocell or a shitted-on mark, you won't get the pattern you expected, but you will get a transition to an unexpected state - at which point you declare an error condition, call the repairman or cleaner, and either stop or or take a gamble on being where you think you should be, and hope the next transition works out.

Kind of like 8b/10b encoding if you think about it in precisely the wrong way.

-- Tom Anderson 2007-09-19 2330 +0100 —Preceding unsigned comment added by 128.40.81.22 (talk) 22:31, 19 September 2007 (UTC)