Перейти к содержанию

Код Грея

В обычном двоичном счёте при переходе от 7 к 8 меняются сразу четыре бита, и при неточном считывании легко получить мусор. В коде Грея соседние значения отличаются ровно одним битом, поэтому ошибка считывания на переходе — не больше одного шага.

Обновлено Редакция GAW

Код Грея (Gray code, отражённый двоичный код, reflected binary code) — способ записи чисел двоичными разрядами, при котором соседние числа отличаются ровно одним битом. Фрэнк Грей описал его в патенте US 2 632 058 (подан в 1947 году, выдан в 1953-м) и назвал «отражённым»: код на n + 1 разряд получают, записав код на n разрядов, затем его же в обратном порядке, и добавив спереди 0 к первой половине и 1 ко второй.

ЧислоДвоичныйКод Грея
0000000
1001001
2010011
3011010
4100110
5101111
6110101
7111100

Перевод

Из двоичного в код Грея — каждый бит складывается по модулю 2 со старшим соседом, а обратно — каждый двоичный бит равен сумме по модулю 2 всех битов кода Грея от старшего до текущего (формулы 1 и 2 патента):

g=b⊕(b≫1),bk=gn⊕gn−1⊕⋯⊕gk.g = b \oplus (b \gg 1), \qquad b_k = g_n \oplus g_{n-1} \oplus \dots \oplus g_k.

В патенте пример на 7 разрядов: 38 в обычном двоичном — 0100110, в коде Грея — 0110101. Сдвиги и XOR на C — в статье о битовых операциях.

Зачем

  • Абсолютные энкодеры. Если дорожки диска считываются чуть не одновременно, обычный код на переходе 3 → 4 может дать любое из восьми значений, а код Грея — только 3 или 4. У TT Electronics EN16AB на 16 положений выходы образуют 4-битный код Грея. Как устроены энкодеры — в статье «Энкодеры».
  • Асинхронные FIFO. Cummings (SNUG 2002) передаёт указатели записи и чтения между тактовыми доменами в коде Грея: за такт меняется один бит, и синхронизатор захватывает либо старое, либо новое значение.
  • Карты Карно упорядочивают строки и столбцы кодом Грея, чтобы соседние клетки отличались одной переменной — см. карта Карно.

Не путать с кодом Джонсона и с произвольными однобитными кодами энкодеров: например, Bourns ACE-128 тоже меняет один бит на шаг, но это не отражённый код, и переводят его таблицей. Перевод в обе стороны и таблицу на любую разрядность даёт калькулятор кода Грея.

Частые вопросы

Как перевести двоичное число в код Грея?

Сдвинуть число вправо на один бит и сложить по XOR с самим собой: g = b ^ (b >> 1). Например, 0110 (6) → 0110 ^ 0011 = 0101. Это и есть формула из патента Грея в записи на C, её же используют в примерах FIFO у Cummings.

Как перевести код Грея обратно в двоичный?

Старший бит переписать как есть, а каждый следующий двоичный бит получить как XOR предыдущего двоичного бита и текущего бита кода Грея. Программно — накопить XOR всех сдвигов: b = g ^ (g >> 1) ^ (g >> 2) ^ … до обнуления.

Где применяют код Грея?

В абсолютных энкодерах — чтобы на границе секторов не появлялось ложное положение, в указателях асинхронных FIFO между тактовыми доменами, в картах Карно для упорядочения клеток. В энкодерах встречаются и другие однобитные коды: Bourns ACE-128 выдаёт 128 положений кодом, который читают через таблицу.

Источники

  1. Gray F. Pulse Code Communication. US Patent 2,632,058, подан 13.11.1947, выдан 17.03.1953 — с. 6–8 PDF: каждое значение отличается от соседних одной цифрой; название reflected binary code — код строится отражением; таблица на 3 разряда; 38 = 0110101; формулы перевода в обычный двоичный и обратно (сложение по модулю 2)
  2. Cummings C. E. Simulation and Synthesis Techniques for Asynchronous FIFO Design. SNUG San Jose 2002, Rev 1.2 — разд. 2.3, 3.1: указатели в коде Грея меняют один бит за такт, что позволяет безопасно передать их в другой тактовый домен; примеры 6, 7: gray = (bin >> 1) ^ bin
  3. TT Electronics / BI Technologies. EN16AB Series 16 mm Absolute Encoder, Rev A 02/2022 — с. 6, Output Signal Format: вариант с 16 положениями выдаёт 4-битный код Грея положения (вариант X = 2 — обычный двоичный)

Нашли ошибку?

Смотрите также