Talk:Gray code

Archives

Animation

The rotary encode and, in particular, the STGC images would benefit enormously from animation! Casual viewers could miss the magic of this concept: making paper versions to explain this to my children was time-consuming and probably less clear than an animation could be. —Preceding unsigned comment added by 81.108.210.118 (talk) 09:49, 8 October 2009 (UTC)[reply]

Ternary Gray Code

The section explains that other gray codes exist but would benefit from at least one example. Since the given algorithm is cyclic, perhaps a reflected version would help make the point. Is this a viable alternative?:

81.108.210.118 (talk) 11:06, 9 October 2009 (UTC)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

Would it be okay to bring back one pseudo-code (or C-like language) example for encoding, and one example for decoding? I actually came back to this page looking for them, since it is useful sometimes for encoding integers in genetic algorithms. I do agree that previously there were too many, and it was messy, but I think a single snippet for each of encoding/decoding would be nice. Fstonedahl (talk) 20:52, 11 January 2009 (UTC)[reply]

The useful 'C-like' language for a web page is JavaScript. There could be code snippets which actually demonstrate something in the browser: an edit box to a text output, for example. —Preceding unsigned comment added by 81.108.210.118 (talk) 09:31, 8 October 2009 (UTC)[reply]

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)[reply]

If you consider the recursive method for Gray Code construction, one solution to creating "Anti-Gray Codes" is to add 01010101... instead of 00000...11111... to the code at every step. E.g.: (0, 1), (00, 11, 01, 10), (000, 111, 001, 110, 010, 101, 011, 100)... this creates a large distance between adjacent codes, but not necessarily between further codes.72.231.157.16 (talk) 05:27, 18 April 2009 (UTC)[reply]

haskell code?

Quoting the article :

(The base case can also be thought of as a single zero-bit Gray code (n=0, G = { " " }) which is made into the one-bit code by the recursive process, as demonstrated in the Haskell example below).

I don't see any haskell code in the article. Anyone does? Stdazi (talk) 09:06, 18 August 2008 (UTC)[reply]

I have added some Haskell code, if someone thinks that this code is in wrong place, cut and paste as is to move it.

I had some problems to format this code, because wiki translated lists to links. The style is very simple, because I take into account that imperative languages programers are not familiar with recursive definitions, much more less with higher order functions. But, I used map, a higher order function, if you think it obscures the program, change transpose to:

transpose :: [ anytype_t ] -> [ anytype_t ]
transpose [] = []
transpose ([]:xss) = []
transpose ((x:xs):xss)=
      (heads ((x:xs):xss)):(transpose (tails ((x:xs):xss)))
  where heads [] = []
        heads (x:xs) = (head x):(heads xs)
        tails [] = [] 
        tails (x:xs) = (tail x):(tails xs)

or let them search more about haskell and map in Wikipedia :) —Preceding unsigned comment added by Elias (talk • contribs) 04:30, 3 January 2009 (UTC)[reply]

Gillham code

I have been searching and searching for hours and did not find any theory behind Gillham code which is another type of Gray code. Gillham code is used in aviation altitude encoders/ transponders. I would really appreciate if someone could post some info on Gillham code, conversion algorithm, etc... —Preceding unsigned comment added by Myval (talk • contribs) 07:29, 25 September 2008 (UTC)[reply]

Algorithm correct?

A test using Java with grayN(21, 3, 3) gives me: {-1,2,2}

Obviously that is not correct!

Using this code:

    static int[] grayN(int value, int base, int digits)
    {
        // parameters: value, base, digits
        // Convert a value to a graycode with the given base and digits. Iterating
        // through a sequence of values would result in a sequence of graycodes in
        // which only one digit changes at a time.

        int baseN[] = new int[digits];  // Stores the ordinary base-N number, one digit per entry
        int gray[] = new int[digits];   // Stores the base-N graycode number

        int i;
        // Put the normal baseN number into the baseN array. For base 10, 109
        // would be stored as [9,0,1]
        for (i = 0; i < digits; i++)
        {
            baseN[i] = (value / (int) Math.pow(base, i)) % base;
        }

        // Convert the normal baseN number into the graycode equivalent. Note that
        // the loop starts at the most significant digit and goes down.
        int shift = 0;
        for (i = digits - 1; i >= 0; i--)
        {
            // The gray digit gets shifted down equal to the sum of the higher
            // digits.
            gray[i] = (baseN[i] + base - shift) % base;  // + base to prevent neg
            shift += gray[i];
        }

        return gray;
    }

Is my code wrong, or is there a bug in the algorithm shown on the article? —CobraA1 01:15, 13 February 2009 (UTC)[reply]

The C code is wrong in some senses. First, the first loop gets the digits in the reverse order to the stated one; the comment is right as is your code, but the C code does it wrong. Second, just adding base does not avoid negatives. Third, it does not declare the loop variable. I'm fixing all these issues, but ultimately I think this fragment should be replaced by pseudocode or a description. --pgimeno (talk) 16:21, 7 August 2009 (UTC)[reply]

another example

http://blog.plover.com/2009/06/21/ (maybe this is worth adding it) —Preceding unsigned comment added by 91.37.9.19 (talk) 23:51, 21 June 2009 (UTC)[reply]

The conversion methods in the last couple of lines are interesting, but the small error described in the bulk of the article is chance: the height happened to occur where the least significant bit changed; if it had occurred where the most significant bit changed the reading could be very inacurate! —Preceding unsigned comment added by 81.108.210.118 (talk) 09:43, 8 October 2009 (UTC)[reply]

You are completely wrong. The whole point of gray code is that there isn't a "most significant" bit. —Dominus (talk) 12:44, 3 January 2010 (UTC)[reply]

Iterative construction

I came to this page looking for the information below, and didn't find it, so I added it in the section Constructing an n-bit gray code. I don't think I explained it brilliantly though, so I'd appreciate improvements.

To construct the binary-reflected Gray code iteratively, start with the code 0, and at step i find the bit position of the least significant '1' in the binary representation of i - flip the bit at that position in the previous code to get the next code. The bit positions start 0, 1, 0, 2, 0, 1, 0, 3, ... (sequence A007814 in the OEIS).

Motivation: I'm writing code that needs to traverse all 2^edges possible graphs of n nodes, and easiest is to change one edge at a time from the previous graph. Hv (talk) 12:12, 2 January 2010 (UTC)[reply]

Examples please

Snakes and coils - in the Snake-in-the-box codes section - sound interesting - but what do they look like? Not every reader capable of understanding the description has the chops to actually construct something from an abstract definition. If anyone could add an example or two of each of these objects, it would communicate the notions involved much better. Simple folk like me need plenty of concrete examples to wrap my head around. ;-) yoyo (talk) 10:07, 9 June 2010 (UTC)[reply]

How many Gray codes are there?

I was asked recently how many distinct binary Gray codes there are are n bits. Given the canonical Gray code on n bits, you can easily create (2^n)*n! Gray codes by choosing any of the 2^n vertices as starting points, and permuting the columns of bitflips. Example, if the bits are numbered from right to left as this: 4 3 2 1, then the Gray code on 4 bits is made by flipping the following positions in order: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1. Now this can be permuted by anything in S₄, so for any of the 16 starting points, there are 24 Gray codes. Does this hit all possible ones? If so, they are all isomorphic to the canonical one, and the formula is nice. If not, then the problem is more interesting. --147.26.161.144 (talk) 20:23, 18 July 2010 (UTC)[reply]

Iterative construction cleanup.

Some proposed wording: Informally, to construct a Gray code on n bits from one on n - 1 bits, take the previous Gray code and list the elements first in order, then in reverse order. Prepend a 0 to the elements that are listed in order, and a 1 to the elements that are listed in reverse order.

Somewhat more formally, let G_n be the canonical Gray code on n bits, let G_n(k) be the k-th entry in the code, where 0 ≤ k < 2ⁿ, and let #G_n(k) be the k-th entry of the code preceded by # (where # is either 1 or 0). The following constructs the canonical Gray code on n bits:

G₁ = (0, 1).

If n > 1, then:

If 0 ≤ k ≤ 2^{n - 1} - 1, then G_n(k)=0G_{n - 1}(k).
If 2^{n - 1} ≤ k ≤ 2ⁿ - 1, then G_n(k)=1G_n-1(2ⁿ - (k + 1)).

So G₂(0) = 0G₁(0) = 00. Similarly, G₂(1) = 0G₁(1) = 01.

How does this sound? --147.26.161.144 (talk) 20:51, 18 July 2010 (UTC)[reply]

The first paragraph is OK. The subsequent formalism doesn't contribute much: harder to understand and less helpful than the current text. The [01]G(n) notation feels sort of ad hoc. The example could be more illustrative (e.g., pick one of the values from the reversed sequence). (I am, of course, not exactly a disinterested party!) -- Elphion (talk) 16:53, 19 July 2010 (UTC)[reply]

My use of the phrase "iterative construction" was intended to convey the concept of "determining the next value from the previous one". Your proposal however looks to be a rewrite of the presentation of the recursive algorithm at the start of the Constructing an n-bit Gray code section, which already seems to me quite adequate as it stands. What issue are you aiming to address with this? Hv (talk) 09:22, 21 July 2010 (UTC)[reply]

Connection to symbolic dynamics

I'd like to hint at a connection with Symbolic dynamics, specifically the Tent map. A sort of Gray code of real numbers $x\in [0,1]$ is constructed as follows. Let $T:[0,1]\rightarrow [0,1]$ be the Tent map with slope 2 and $\Omega =\{0,c,1\}$ be a set of symbols. Define an address map $A:[0,1]\rightarrow \{0,c,1\}$ by letting $A(x)=0$ whenever $x<{\frac {1}{2}}$ , $A(x)=c$ only for $x={\frac {1}{2}}$ and $A(x)=1$ otherwise. Then the infinite Gray code of $x$ is given as the sequence $g_{n}(x)=A(T^{n}(x))$ . This sequence is an element of the so-called Shift space $\Omega ^{\mathbb {N} }$ . Now, for an integer $k$ with $k<2^{m}$ consider the real number $x={\frac {k}{2^{m}-1}}$ . Then the m-digit Gray code of $k$ is the first m digits of the sequence $g_{n}(x)$ defined above. 80.1.165.108 (talk) 01:04, 26 March 2011 (UTC) O. Klinke, University of Birmingham, UK[reply]

Incorrect link to Chain code?

In Gray code#Single-track Gray code, there is "(compared to chain codes, also called De Bruijn sequences)". But the chain codes described at that article are for compressing monochrome images and seem unrelated to De Bruijn sequences. There's also a reference to “code chains”. Could someone more familiar with this material correct these links or add explanation of how they're related? — Unbitwise (talk) 21:03, 22 June 2011 (UTC)[reply]

Vietnamese-rings puzzle?

The binary-reflected Gray code can also be used to serve as a solution guide for the Tower of Hanoi problem, as well a classical Vietnamese-rings puzzle and a sequential mechanical puzzle mechanism. Apart from the unclear syntax ("as well a" = as well as for a?), what is a classical Vietnamese-rings puzzle? Some variant of the Chinese rings puzzle?--85.75.178.41 (talk) 11:27, 23 June 2011 (UTC)[reply]