Существует ли код Грея для других баз, кроме двух? - PullRequest
Новая
       30

Существует ли код Грея для других баз, кроме двух?

4 голосов
/ 01 октября 2010

Просто из любопытства, определен ли код Грея для основ, отличных от основания два?

Я пытался сосчитать в базе 3, записывая последовательные значения, обращая внимание на изменение только одного трит одновременно.Я был в состоянии перечислить все значения до 26 (3 ** 3-1), и это, кажется, работает. 

        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

Единственная проблема, которую я вижу, состоит в том, что все три trits изменяется при возврате к нулю.Но это верно только для нечетных оснований.При использовании четных баз, возвращающихся к нулю, будет изменяться только одна цифра, как в двоичной.

Я даже предполагаю, что она может быть распространена на другие базы, даже десятичные.Это может привести к другому порядку при подсчете в базовой десятке ...: -) 

    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

Теперь вопрос, кто-нибудь когда-нибудь слышал об этом?Есть ли приложение для этого?Или это просто математическое безумие?

Ответы [ 2 ]

10 голосов
/ 01 октября 2010

Да. Взгляните на статью Grey code в Википедии. Имеет раздел по n-арный код Грея .

Существует много специализированных типов кодов Грея, отличных от двоично-отраженного кода Грея. Одним из таких типов кода Грея является n-арный код Грея , также известный как небулев код Грея . Как следует из названия, этот тип кода Грея использует в своих кодировках небулевые значения.

3 голосов
/ 01 октября 2010

Просто для полноты (как aioobe уже дал правильный ответ), вот программа на C ++, которая перечисляет все 168 двузначных кодов серого для базы 3, которые начинаются с 00, и отмечает 96 циклических кодов.Используя алгоритм из Википедии , вы можете легко создавать более длинные коды Грея для четных баз.Для неравномерных оснований вы можете изменить программу для генерации в соответствии с кодами Грея.

Первый циклический двузначный код серого, найденный с помощью этой программы, следующий: 

00 01 02 12 10 11 21 22 20

После изменения программыпервая найденная циклическая 3-значная серая следующая: 

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

Код: 

#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);
}
...