Does Gray code exist for other bases than two?

Question

Just a matter of curiosity, is the Gray code defined for bases other than base two?

I tried to count in base 3, writing consecutive values paying attention to change only one trit at a time. I've been able to enumerate all the values up to 26 (3**3-1) and it seems to work.

        000              122              200
        001              121              201
        002              120              202
        012              110              212
        011              111              211
        010              112              210
        020              102              220
        021              101              221
        022              100              222

The only issue I can see, is that all three trits change when looping back to zero. But this is only true for odd bases. When using even bases looping back to zero would only change a single digit, as in binary.

I even guess it can be extended to other bases, even decimal. This could lead to another ordering when counting in base ten ... :-)

    0  1  2  3  4  5  6  7  8  9 19 18 17 16 15 14 13 12 11 10
   20 21 22 23 24 25 26 27 28 29 39 38 37 36 35 34 33 32 31 30

Now the question, has anyone ever heard of it? Is there an application for it? Or it is just mathematical frenzy?

Answer 1

Yes. Have a look at the Gray code article at wikipedia. It has a section on n-ary Gray Code.

There are many specialized types of Gray codes other than the binary-reflected Gray code. One such type of Gray code is the n-ary Gray code, also known as a non-Boolean Gray code. As the name implies, this type of Gray code uses non-Boolean values in its encodings.

Answer 2

Just for completeness (as aioobe already gave the right answer), here's a C++ program that lists all the 168 2-digit gray codes for base 3 that start with 00 and marks the 96 cyclic ones. Using the algorithm from Wikipedia, you can construct longer Gray codes easily for even bases. For uneven bases, you can change the program to generate according Gray codes.

The first cyclic 2-digit gray code found with this program is this one:

00 01 02 12 10 11 21 22 20

After changing the program, the first cyclic 3-digit gray found is this:

000 001 002 012 010 011 021 020 022 122 102 100 101 111
110 112 212 202 222 220 120 121 221 201 211 210 200

Code:

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

// Highest number using two trits
#define MAXN 9

int gray_code_count, cyclic_count;

bool changes_one_trit(int code1, int code2) {
  int trits_changed = 0;
  if ((code1 / 3) != (code2 / 3)) trits_changed++;
  if ((code1 % 3) != (code2 % 3)) trits_changed++;
  return (trits_changed == 1);
}

int generate_gray_code(int* code, int depth) {
  bool already_used;

  if (depth == MAXN) {
    for (int i = 0; i < MAXN; i++) {
      printf("%i%i ", code[i]/3, code[i]%3);
    }
    // check if cyclic
    if (changes_one_trit(code[MAXN-1], 0)) {
      printf("cyclic");
      cyclic_count++;
    }
    printf("\n");
    gray_code_count++;    
  }

  // Iterate through the codes that only change one trit
  for (int i = 0; i < MAXN; i++) {
    // Check if it was used already
    already_used = false;
    for (int j = 0; j < depth; j++) {
      if (code[j] == i) already_used = true;
    }
    if (already_used) continue;

    if (changes_one_trit(code[depth-1], i)) {
      code[depth] = i;
      generate_gray_code(code, depth + 1);
    }
  }
}

int main() {
  int* code = (int*)malloc(MAXN * sizeof(int));
  code[0] = 0;
  gray_code_count = 0;
  generate_gray_code(code, 1);
  printf("%i gray codes found, %i of them are cyclic\n", gray_code_count, cyclic_count);
  free(code);
}