What are Gray Codes?
[Editors note: For the refs cited here, you will have to go to: {ga faq}.]
     The correct spelling is "Gray"---not  "gray",  "Grey",  or  "grey"---
     since Gray codes are named after the Frank Gray  who  patented  their
     use for shaft encoders in 1953  [1].   Gray  codes  actually  have  a
     longer history, and the inquisitive reader may want to  look  up  the
     August, 1972,  issue  of  Scientific  American,  which  contains  two
     articles of interest: one on the origin  of  binary  codes  [2],  and
     another by Martin  Gardner  on  some  entertaining  aspects  of  Gray
     codes [3].  Other references containing descriptions  of  Gray  codes
     and more modern, non-GA, applications include the second  edition  of
     Numerical  Recipes  [4],  Horowitz  and  Hill  [5],  Kozen  [6],  and
     Reingold [7].

     A Gray code represents  each  number  in  the  sequence  of  integers
     {0...2^N-1} as a binary string of length N  in  an  order  such  that
     adjacent integers have Gray code representations that differ in  only
     one bit position.  Marching through the  integer  sequence  therefore
     requires flipping just one bit at a time.  Some  call  this  defining
     property of Gray codes the "adjacency property" [8].

     Example (N=3):  The binary coding of {0...7} is {000, 001, 010,  011,
     100, 101, 110, 111}, while one Gray coding is {000,  001,  011,  010,
     110, 111, 101, 100}.  In essence, a Gray code takes a binary sequence
     and shuffles  it  to  form  some  new  sequence  with  the  adjacency
     property.  There exist,  therefore,  multiple  Gray  codings  or  any
     given N.  The example shown here belongs to a  class  of  Gray  codes
     that goes by the fancy name "binary-reflected Gray codes".  These are
     the most  commonly  seen  Gray  codes,  and  one  simple  scheme  for
     generationg such a Gray code sequence says, "start with all bits zero
     and successively flip the right-most bit that produces a new string."

     Hollstien [9] investigated the use of GAs for optimizing functions of
     two variables and claimed that  a  Gray  code  representation  worked
     slightly better than the binary representation.  He attrributed  this
     difference to the adjacency property of Gray codes.   Notice  in  the
     above example that the step from three to four requires the  flipping
     of all the bits in the binary representation.  In  general,  adjacent
     integers in the binary representaion often lie many bit flips  apart.
     This  fact makes it less likely that a MUTATION operator  can  effect
     small changes for a binary-coded INDIVIDUAL.

     A Gray code representation seems to  improve  a  MUTATION  operator's
     chances of making incremental improvements, and a  close  examination
     suggests why.  In  a  binary-coded  string  of  length  N,  a  single
     mutation in the most significant  bit  (MSB)  alters  the  number  by
     2^(N-1).  In a Gray-coded string, fewer mutations lead  to  a  change
     this large.  The user of Gray codes does, however, pay  a  price  for
     this feature: those "fewer mutations" lead to  much  larger  changes.
     In the Gray code illustrated above, for example, a single mutation of
     the left-most bit changes a zero to a seven and vice-versa, while the
     largest change a single mutation can make to a corresponding  binarycoded INDIVIDUAL is always four.  One might still view this aspect of
     Gray codes with some favor:  most  mutations  will  make  only  small
     changes, while the occasional  mutation  that  effects  a  truly  big
     change may initiate EXPLORATION of an  entirely  new  region  in  the
     space of CHROMOSOMEs.

     The algorithm for converting between the binary-reflected  Gray  code
     described above  and  the  standard  binary  code  turns  out  to  be
     surprisingly simple to state.  First label the bits of a binary-coded
     string B[i], where larger i's represent more  significant  bits,  and
     similarly label the corresponding Gray-coded string G[i].  We convert
     one to the other as follows:  Copy the most  significant  bit.   Then
     for each smaller i  do  either  G[i] = XOR(B[i+1], B[i])---to convert
     binary to  Gray---or B[i] = XOR(B[i+1], G[i])---to  convert  Gray  to

     One may easily implement the above algorithm in C.   Imagine  you  do
     something like

          typedef unsigned short ALLELE;

     and then use type "allele" for each bit in your CHROMOSOME, then  the
     following two functions will convert between  binary  and  Gray  code
     representations.  You must pass them the address  of  the  high-order
     bits for each of the two strings  as  well  as  the  length  of  each
     string.  (See  the  comment  statements  for  examples.)   NB:  These
     functions assume a chromosome arranged  as  shown  in  the  following

     index:    C[9]                                                    C[0]
     Char C:   |  1  |  1  |  0  |  0  |  1  |  0  |  1  |  0  |  0  |  0  |
               ^^^^^                                                 ^^^^^
               high-order bit                                  low-order bit


     /* Gray <==> binary conversion routines */
     /* written by Dan T. Abell, 7 October 1993 */
     /* please send any comments or suggestions */
     /* to dabell@quark.umd.edu */

     void gray_to_binary (Cg, Cb, n)
     /* convert chromosome of length n from */
     /* Gray code to binary representation */
     allele    *Cg,*Cb;
     int  n;
          int j;
*Cb = *Cg; /* copy the high-order bit */
          for (j = 0; j < n; j++) {
               Cb--; Cg--;         /* for the remaining bits */
               *Cb= *(Cb+1)^*Cg;   /* do the appropriate XOR */

     void binary_to_gray(Cb, Cg, n)
     /* convert chromosome of length n from */
     /* binary to Gray code representation */
     allele    *Cb, *Cg;
     int  n;
          int j;
*Cg = *Cb; /* copy the high-order bit */
          for (j = 0; j < n; j++) {
               Cg--; Cb--;         /* for the remaining bits */
               *Cg= *(Cb+1)^*Cb;   /* do the appropriate XOR */

  1. F. Gray, "Pulse Code Communication", U. S. Patent 2 632 058, March 17, 1953.
  1. F. G. Heath, "Origins of the Binary Code", Scientific American v.227,n.2 (August, 1972) p.76.
    1. Martin Gardner, "Mathematical Games", Scientific American v.227,n.2 (August, 1972) p.106.
  2. William H. Press, et al., Numerical Recipes in C, Second Edition (Cambridge University Press, 1992).
    1. Paul Horowitz and Winfield Hill, The Art of Electronics, Second Edition (Cambridge University Press, 1989).
  3. Dexter Kozen, The Design and Analysis of Algorithms (Springer- Verlag, New York, NY, 1992).
    1. Edward M. Reingold, et al., Combinatorial Algorithms (Prentice Hall, Englewood Cliffs, NJ, 1977).
  4. David E. Goldberg, GENETIC ALGORITHMs in Search, OPTIMIZATION, and Machine Learning (Addison-Wesley, Reading, MA, 1989).
    1. R. B. Hollstien, Artificial Genetic Adaptation in Computer Control Systems (PhD thesis, University of Michigan, 1971).

Hope this helps,

Paul Holmes email: bsc0123@uk.ac.napier.dcs Computer Studies Department Napier University Edinburgh

From genetic-programming-owner@list.Stanford.EDU Fri Dec 9 06:29 MET 1994
        ( id AA26570; Fri, 9 Dec 1994 06:29:34 +0100
        id AA06986; Fri, 9 Dec 1994 06:32:51 +0100
        id AA13908; Thu, 8 Dec 94 22:27:30 MST
Errors-To: mail-errors@list.Stanford.EDU
Errors-To: mail-errors@list.Stanford.EDU
        via Fnet-EUnet id AA16477; Fri, 9 Dec 1994 05:23:28 +0100 (MET)
From: mgix@jpn.thomson-di.fr (Emmanuel Mogenet)
To: bru@kosice.upjs.sk
Cc: genetic-programming@cs.stanford.edu
Reply-To: mgix@jpn.thomson-di.fr
X-Mailer: ELM [version 2.4 PL21]
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Content-Length: 5980      
Branislav Brutovsky writes:
>Hi everybody,
>Would you send me the formula for construction decimal number from its >Gray counterpart, please. I would really appreciate it. >Thanks in advance.
>Branislav Brutovsky
Find my personal brew attached.


  1. It's C++, but easyly downgraded to C.

  2. I've been using it for 6 month. It seems to work but I never bothered to check its correctness for real.

  3. It's built to run on a 32 bit machines. As far as I can tell, endian-ness shouldn't matter, except maybe for the test routine at the end.

  4. It has the advantage over most implementations I've seen to let you choose between two modes:
            a) Either your genetic code is seen has a collection of 32 bits chunks
            over which the gray coding is applied as many times as they are chunks
            b) Either your genetic code is seen has one long bit string
            representing one single binary number over which gray coding is applied
  5. It should be rather fast.
Emmanuel Mogenet <mgix@thomson-di.fr> PGP Key on Request. MIME Groked.






#include <stdio.h>
#include <stdlib.h>



typedef int             reg;
typedef unsigned int    uint32;
typedef unsigned short  uint16;
typedef unsigned char   uint8;






*******************************************************************************/ static uint16 initDone=0; // Has Lookup been Built ? static uint16 lookup[2][256]; // Gray Codes Lookup





        z= lookup[last][ s[3] ];

        d[3]= z&0xFF;

        last= prop ? z>>8 : 0;



static uint8    uniq[65535];
static char     *bindump[]=
    "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
    "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111",


    /* Check the first 64k


    uint32      last=1;

    for( i=0; i<65536; ++i )

        Gray( &gray, &bin, 1, 0 );
        Ungray( &bin, &gray, 1, 0 );
        if( bin!=i || Hamming(last,gray)!=1 )
            printf( "Failure at %d\n", i );


    for( i=0; i<65536; ++i )

        if( uniq[i]!=1 )
            printf( "Mapping not 1 to 1\n" );




** LOG

// $Log: gcode.c++,v $


From: David_vun_Kannon_at_NY-RES@resgate.rch.gs.com
I wrote some c code for this when I did GA work a couple of years ago.
      However, I convinced myself that it wasn't really helpful to GA on 
bitstrings. The basic argument for using Gray coded bits is that single bit mutations in a Gray coded number will only change the value by a little bit also, as opposed to the usual power of 2 code, where changing one bit might change the value by as much as 2^(n-1) for n its. Unfortunately, this arguement ignores the wraparound that occurs between the first and last encoded values, which in Gray code are always 000... and 100.... A mutation between these two strings is still just a single bit, but it produces a value jump of 2^n. What has happened in effect is that Gray code has saved up the possible accumulated error and put it all in one place. put another way, I think that total error over all one bit changes in any representation is constant, all you can do is change the distribution of the error weight over the set of changes. I didn't find the bimodal distribution of error produced by Gray codes particularly more compelling than the approximately Gaussian distribution of the binary representation, and I couldn't come up with a representation that had uniform distribution without resorting to a hash table. So I gave up on Gray codes.