Код Грея

Проблема, ради которой код придумали

Возьмите обычный двоичный счётчик и посмотрите на переход от 3 к 4. В четырёхбитной записи это 0011 → 0100: меняются сразу три бита. В идеальном мире они переключаются одновременно, в реальном — с разбросом в наносекунды или в доли миллиметра механического допуска. В момент перехода схема может считать промежуточное значение 0111 или 0000 — числа, которых в последовательности не было вовсе.

Для логического анализатора это дребезг, для абсолютного углового датчика на валу станка — команда на неправильный угол. Худший случай — переход от 0111 к 1000, где переворачиваются все четыре бита: ложным может оказаться любое из четырнадцати промежуточных значений.

Код Грея убирает саму возможность такой ситуации. В нём любые два соседних значения различаются ровно в одном разряде, поэтому промежуточное состояние либо равно старому значению, либо новому. Ошибка на границе даёт погрешность максимум в одну единицу — и никогда не даёт числа из другого конца шкалы. Фрэнк Грей из Bell Labs подал заявку на патент по импульсной кодовой связи в 1947 году, патент выдали в 1953-м, и название закрепилось за кодом, хотя сама последовательность встречалась у математиков и раньше — в решении головоломки «китайские кольца».

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

Прямое преобразование из двоичного числа занимает одну строку: g = b XOR (b >> 1). Число сдвигается вправо на один разряд и складывается с самим собой по модулю 2. Обратное преобразование чуть длиннее, потому что каждый следующий бит зависит от уже вычисленного старшего: старший разряд переносится без изменений, а дальше b[i] = b[i+1] XOR g[i]. На процессоре это разворачивается в цепочку сдвигов и XOR или в трюк с префиксным XOR.

Трёхбитная последовательность выглядит так: 000, 001, 011, 010, 110, 111, 101, 100. Проверьте любую соседнюю пару — различие ровно в одном разряде. Последнее значение 100 отличается от первого 000 тоже одним битом, то есть последовательность замкнута в кольцо. Это свойство критично для круговых датчиков: полный оборот вала возвращает счётчик в начало без скачка.

Отсюда и название «отражённый». Код для n бит строится рекурсивно: берётся код для n − 1 бит, выписывается сверху вниз с приписанным нулём, затем тот же список в обратном порядке — отражённый как в зеркале — с приписанной единицей. Симметрия конструкции гарантирует однобитовые переходы на каждом шаге, включая стык двух половин.

Распространённое заблуждение — считать код Грея отдельной системой счисления или способом сжатия. Он занимает столько же бит, сколько обычная двоичная запись тех же значений, и хранит ровно те же величины. Отличие только в порядке присвоения кодов — сравните с привычным представлением числа в позиционной системе с двойкой в качестве основания. Арифметику в коде Грея напрямую не делают: складывать и умножать проще после перевода в обычный двоичный вид.

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

Абсолютные энкодеры. Диск с прорезями на валу двигателя или на оси станка кодирует угол напрямую, без счёта импульсов. Дорожки нарезаны по коду Грея, поэтому смещение сенсора относительно границы сектора даёт ошибку в один шаг, а не выброс на половину оборота. Тот же принцип у линейных оптических линеек в измерительных приборах.

Асинхронные FIFO. При передаче указателя записи между двумя тактовыми доменами многобитное двоичное число может быть защёлкнуто в момент переключения нескольких разрядов и прочитано неверно. Указатель, преобразованный в код Грея, меняется по одному биту за такт, и худшее, что случится, — приёмник увидит значение на шаг устаревшим. Это стандартный приём в проектировании цифровых схем.

Цифровая связь. В созвездиях QAM и PSK соседние точки размечают кодом Грея. Шум чаще всего сдвигает символ к ближайшему соседу, а раз соседи различаются одним битом, одна символьная ошибка порождает одну битовую, а не три-четыре. Это заметно снижает частоту битовых ошибок при той же мощности сигнала.

Карты Карно. Строки и столбцы карты подписываются по коду Грея, чтобы соседние клетки различались одним переменным, и логическую функцию можно было минимизировать, склеивая прямоугольные группы.

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

Код Грея и штриховые коды: где сходство обманчиво

Оптический диск энкодера внешне похож на линейный штрихкод, и логика у них действительно родственная: и там, и там значение снимается с чередования светлых и тёмных зон. Но задачи разные. Штриховая символика кодирует произвольные данные и защищается контрольной цифрой, а код Грея кодирует последовательные позиции и защищает не от искажения данных, а от неоднозначности момента считывания.

В QR-кодах и DataMatrix код Грея не применяется. Там значения не образуют упорядоченной шкалы, где важна близость соседей, а ошибки приходят пятнами, и с ними разбираются коды Рида — Соломона и код Хэмминга с его наследниками. Полезно держать разницу в голове: код Грея не исправляет и не обнаруживает ошибки, в отличие от бита чётности или CRC. Он устраняет причину одного конкретного класса сбоев — неоднозначного считывания на переходе — и делает это без единого дополнительного бита избыточности.

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

Код Грея занимает меньше места, чем двоичный?

Нет, ровно столько же. Для n бит и в том, и в другом случае кодируется 2 в степени n значений. Код Грея не сжимает данные и не добавляет избыточности — он лишь меняет порядок, в котором значения сопоставляются с битовыми комбинациями. Выигрыш достигается не в объёме, а в надёжности считывания на границе между соседними значениями.

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

Одной операцией: сдвинуть число вправо на один бит и сложить со сходным по модулю 2, то есть g равно b XOR (b сдвинутое вправо на 1). Число 5 в двоичном виде 101, сдвиг даёт 010, XOR даёт 111. Обратный перевод сложнее: старший бит переносится как есть, а каждый следующий получается как XOR уже восстановленного старшего соседа с очередным битом кода.

Почему код называют отражённым?

Из-за способа построения. Список для n бит получается так: пишем список для n − 1 бит с нулём впереди, затем тот же список задом наперёд с единицей впереди — как отражение в зеркале. Симметрия гарантирует, что переход через середину списка тоже меняет ровно один бит, и последовательность остаётся замкнутой в кольцо.

Можно ли складывать числа прямо в коде Грея?

Технически можно, схемы сумматоров для него существуют, но они сложнее и медленнее обычных двоичных. На практике поступают проще: значение с датчика переводят в обычный двоичный вид, считают, а обратно в код Грея переводят только если это нужно для выдачи на такой же интерфейс. Стоимость перевода — несколько операций XOR, она пренебрежимо мала.

Есть ли связь кода Грея с шестнадцатеричной записью?

Прямой связи нет: шестнадцатеричная запись — это компактная форма записи тех же двоичных разрядов группами по четыре бита. Код Грея меняет не форму записи, а соответствие между значениями и комбинациями бит. Значение в коде Грея тоже можно записать шестнадцатеричными символами, но читаться как обычное число оно не будет.