N-й серый код

Question

формула для вычисления n-го серого кода:

(n-1) XOR (floor((n-1)/2))  
(Source: wikipedia)

Я закодировал ее как:

int gray(int n)
{
  n--;
  return n ^ (n >> 1);
}

Может кто-нибудь объяснить, как работает приведенная выше формула, или, возможно, ее вывод?

Answer 1

Если вы посмотрите на двоичную последовательность подсчета, вы заметите, что соседние коды отличаются на несколько последних битов (без дырок), поэтому, если вы их зафиксируете, вы увидите паттерн из нескольких конечных единиц.Кроме того, когда вы сдвигаете числа вправо, xors также будет сдвигаться вправо: (A xor B) >> N == A >> N xor B >> N.

    N                    N>>1                  gray
 0000           .        0000           .      0000           .
    | >xor = 0001             >xor = 0000           >xor = 0001
 0001          .         0000          .       0001          .
   || >xor = 0011           | >xor = 0001           >xor = 0010
 0010           .        0001           .      0011           .
    | >xor = 0001             >xor = 0000           >xor = 0001
 0011         .          0001         .        0010         .
  ||| >xor = 0111          || >xor = 0011           >xor = 0100
 0100                    0010                  0110

Исходные результаты Xor и сдвинутые результатыотличаются одним битом (я пометил их точкой выше).Это означает, что если вы их xor, вы получите шаблон с установленным 1 битом.Итак,

(A xor B) xor (A>>1 xor B>>1) == (A xor A>>1) xor (B xor B>>1) == gray (A) xor gray (B)

Поскольку xor дает нам 1 с разными битами, это доказывает, что соседние коды отличаются только одним битом, и это основное свойство кода Грея, которое мы хотим получить.

Таким образом, для полноты следует доказать, что N можно восстановить из его значения N ^ (N >> 1): зная n-й бит кода, мы можем восстановить n-1-й бит, используя xor.

A_[bit n-1] = A_[bit n] xor gray(A)_[bit n-1]

Начиная с самого большого бита (он обозначен 0), поэтому мы можем восстановить целое число.

Answer 2

Запись в Википедии , на которую вы ссылаетесь, объясняет это уравнение очень замысловато.

Тем не менее, полезно начать с этого:

Следовательно, кодирование стабильно, в том смысле, что как только двоичное число появляется в Gn, оно появляется в одной и той же позиции всесписки;поэтому имеет смысл поговорить о отражающем значении кода Грея числа: G (m) = m-й отражающий код Грея, считая от 0.

Другими словами, Gn(m) & 2^n-1 - этолибо Gn-1(m & 2^n-1), либо ~Gn-1(m & 2^n-1).Например, G(3) & 1 это либо G(1), либо ~G(1).Теперь мы знаем, что Gn(m) & 2^n-1 будет отражено (поразрядно обратным), если m больше 2^n-1.

Другими словами:

G(m, bits), k= 2^(bits - 1)
G(m, bits)= m>=k ? (k | ~G(m & (k - 1), bits - 1)) : G(m, bits - 1)
G(m, 1) = m

Разработка математикив целом вы получаете (m ^ (m >> 1)) для кода Грея, начинающегося с нуля.

Answer 3

Докажите по индукции.

Подсказка: значения от 1<<k -го до (1<<(k+1))-1 -го в два раза больше значений от 1<<(k-1) -го до (1<<k)-1-го плюс плюс ноль или единица.

Редактировать: Это было слишком запутанным. Что я действительно имею в виду, это

gray(2*n) и gray(2*n+1) - это 2*gray(n) и 2*gray(n)+1 в некотором порядке.

Answer 4

Увеличивая число, когда вы смотрите на него побитово, переворачивает все конечные единицы в нули и последний ноль в единицу.Это перевернуло много битов, и цель кода Грея - сделать его ровно одним.Это преобразование делает оба числа (до и после приращения) равными для всех переворачиваемых битов, кроме старшего.

До:

011...11
     + 1 
---------
100...00

После:

010...00
     + 1
---------
110...00
^<--------This is the only bit that differs 
          (might be flipped in both numbers by carry over from higher position)

n ^ (n >> 1) легче вычислить, но кажется, что только изменение трейлинг 011..1 на 010..0 (т. Е. Обнуление всего трейлинг-блока из 1, кроме старшего 1) и 10..0 до 11..0 (т. Е. Переворачиваниенаивысшее значение 0 в конце (0) достаточно для получения кода Грея.