Gray Code | Hacker News Reader

Gray Code

en.wikipedia.org

86 pointsbrudgers22 comments

In the past 15 years, Gray code is the only part of my Computer Science education I've actually found a use for in my day-to-day work developing business applications. I've used it to simplify overly complex if/else logic down to its simplest possible form. All the rest of the knowledge I use on a daily basis has been learned on the job.

Could you expand on that? I don't really understand how you could simplify if/else logic by using this which is a bijection from one binary counting system to another.

Karnaugh maps I'm guessing. https://en.wikipedia.org/wiki/Karnaugh_map

Made a tiny webapp to do this, which lets you hover over the different parts of the resulting expression, to see which parts of the karnaugh map they cover: https://github.com/ysangkok/py-kmap

Yes, that's it, thanks for jogging my memory!

I count in Gray code using my fingers. It's twice as fast as binary because the LSB switches half as often! I've also found patterns that are even better, but they're harder to learn.

some pleasant tree patterns:

  0000000000000000000000000000000011111111111111111111111111111111
  0000000000000000111111111111111111111111111111110000000000000000
  0000000011111111111111110000000000000000111111111111111100000000
  0000111111110000000011111111000000001111111100000000111111110000
  0011110000111100001111000011110000111100001111000011110000111100
  0110011001100110011001100110011001100110011001100110011001100110

(the first 64 gray codes, as columns)

python code to generate this thing:

    def graytree(n):
      for row in range(n, 0, -1):
        d = 2**(row-1)
        yield ''.join(str(((i+d)>>row)%2) for i in range(2**n))

    for r in graytree(6):
      print(r)

or in J

    graycodes=: verb define
        >(0&,&.>,1&,&.>@:|.)^:(<:y) 0 1
    )
    ' +'{~|:graycodes 6

                                ++++++++++++++++++++++++++++++++
                ++++++++++++++++++++++++++++++++                
        ++++++++++++++++                ++++++++++++++++        
    ++++++++        ++++++++        ++++++++        ++++++++    
  ++++    ++++    ++++    ++++    ++++    ++++    ++++    ++++  
 ++  ++  ++  ++  ++  ++  ++  ++  ++  ++  ++  ++  ++  ++  ++  ++

To convert between binary and Gray, take the xor of adjacent bits. It works in both directions.

That's so cool. When I was a kid, I had a panel with a ton of switches. I've been thinking about the way to cycle through all of the possible switch combinations (I already knew combinatorics and binary), and I invented Gray codes in the process :)

I never thought it could be useful for anything but my amusement.

Knuth thinks they're pretty cool too and talks about them in TAoCP volume 4. The pre-fascicle of his discussion is available in gzipped PostScript.

http://www-cs-faculty.stanford.edu/~uno/fasc2a.ps.gz

The application to optical encoders is one of the most beautiful intersections between discrete math and the physical world ever imo.

I remember years ago when I accidentally reinvented this a few years ago.

https://www.reddit.com/r/math/comments/o1l8p/i_accidentally_...

As used by the Intel RealSense depth camera (http://2.bp.blogspot.com/-ICUq6I74X7A/VMvn4I4ujWI/AAAAAAAALZ...)

Yes, I dig Gray Code. It's not at all related to my site http://GreyCoder.Com

I see what you did there :)

I dig Gray Code too, and here are some pretty pictures http://datagenetics.com/blog/november32014/index.html

Nothing related to Gray codes, but I love your site. There are so many interesting things to explore there. Thanks for making it!

Thanks for the kind words!

So much innovation that came from one place: Bell Labs. Quite extraordinary.

Learned about this in school, cool to see it on HN.

Mmmmm, yes?

Reply on news.ycombinator.com