Работа кода Грея

Я пытаюсь понять, как работает серый код. Если мы дадим любое неотрицательное целое число n (где n - количество битов), то нам нужно вывести его последовательность кода Грея. Ниже приведены несколько примеров

2-битная последовательность кода Грея

Input = 2 bits
00 - 0
01 - 1
11 - 3
10 - 2
Output = [0,1,3,2]

3-битная последовательность кода Грея

Input  = 3
000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4
Output = [0, 1, 3, 2, 6, 7, 5, 4]

Насколько я понимаю, последовательность кода Грея начинается с 0, а в коде Грея два последовательных значения отличаются только одним битом. Я не уверен, как появился серый код 2 [0,1,3,2] и как появился серый код 3 [0,1,3,2,6,7,5,4]


gray-code
person Coding Bad    schedule 28.07.2015    source источник
comment
вы имеете дело с битами - степенью двойки. gc (2) - ›2 ^ 2 -› 4. gc (3) - ›2 ^ 3 -› 8. поскольку код Грея имеет только однобитовые различия, порядок этих битовых последовательностей НЕ является линейным. вот почему вы получаете случайный порядок десятичных чисел.   -  person Marc B    schedule 29.07.2015
comment
В порядке. Итак, вы говорите, что если я дам 2, то его gc станет 2 ^ 2 = 4. Итак, его gc станет [0,1,2,3], и порядок может меняться. Точно так же в случае 3 gc становится 2 ^ 3 = 8. Я все еще не уверен, потому что en.wikipedia. org / wiki / Gray_code утверждает, что код серого для 3 будет [0,1,3,2,6,7,5,4]. Пожалуйста, поправьте меня, если я ошибаюсь.   -  person Coding Bad    schedule 29.07.2015
comment
2-битный код Грея может иметь 2 ^ 2 = 4 значения. 3bit имеет 8 значений, бла-бла-бла. в этом нет ничего волшебного. это просто двоичная нумерация. что делает его кодом серого, так это то, что между любыми двумя позициями в списке отличается только один бит. кроме этого, это ВСЕ ЕЩЕ простой список из 4, 8, 16 или любого другого числа. но код Грея определяет порядок номеров.   -  person Marc B    schedule 29.07.2015

Ответы (3)


arrow_upward
0
arrow_downward

Обычный способ генерации кода Грея для n битов состоит в том, чтобы взять последовательность для n-1 битов с префиксом 0, за которой следует обратная последовательность для n-1 битов с префиксом 1. Последовательность базового случая для 1 бита равна 0, 1. Вы можно легко написать рекурсивную функцию, которая генерирует эту последовательность:

void printgrey(int len, int pfx=0, int rev=0) {
    if (--len >= 0) {
        printgrey(len, pfx + (rev<<len), 0);
        printgrey(len, pfx + (!rev<<len), 1);
    } else
        printf("%d\n", pfx);
}
person Chris Dodd    schedule 28.07.2015

arrow_upward
0
arrow_downward

Аппаратно серая кодировка описывается следующим образом:

function bin2gray(value : std_logic_vector) return std_logic_vector is
  variable result       : std_logic_vector(value'range);
begin
  result(result'left)   := value(value'left);
  for i in (result'left - 1) downto result'right loop
    result(i) := value(i) xor value(i + 1);
  end loop;
  return result;
end function;

Источник: PoC.utils.

Что это означает? Самый старший бит (MSB) ввода копируется в результат. Теперь цикл проходит каждый входной бит от MSB-1 до LSB и сканирует этот бит со своим левым соседом.

Пример:

in = 0x2 = 0010b
res(3) := 0
res(2) := in(3) xor in(2) = 0
res(1) := in(2) xor in(1) = 1
res(0) := in(1) xor in(0) = 1
return 0011
person Paebbels    schedule 28.07.2015

arrow_upward
0
arrow_downward

Самый простой способ сгенерировать последовательность кода Грея - начать с обычной числовой последовательности и выполнить xor для каждого числа со сдвигом вправо на один бит. В Python это выглядит так:

def graycodes(bits):
    return [x ^ (x >> 1) for x in range(1 << bits)]

>>> graycodes(2)
[0, 1, 3, 2]
>>> graycodes(3)
[0, 1, 3, 2, 6, 7, 5, 4]
>>> graycodes(4)
[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]
person Mark Ransom    schedule 09.03.2021