Код Грея

Код Грея — это двоичная система счисления, в которой два последовательных числа отличаются только в одном двоичном разряде (бите). Относится к классу рефлексных кодов и используется для минимизации ошибок при переключении между состояниями в цифровых устройствах, а также в задачах передачи данных и математических преобразованиях. Назван в честь американского инженера Фрэнка Грея (Frank Gray), который впервые описал его в патенте 1953 года, хотя известен был и ранее под названием «рефлексный двоичный код».

Принцип построения

Основное свойство кода Грея — монотонное изменение только одного бита при переходе от одного числа к следующему. Это достигается за счёт специального алгоритма рекурсивного построения. Для n-разрядного кода Грея последовательность строится следующим образом:

• Для n = 1: 0, 1.
• Для n > 1: берётся последовательность для n-1 разрядов, затем к ней добавляется зеркальное отражение (рефлексия), после чего к первой половине дописывается 0 в старший разряд, ко второй — 1.

Например, для n = 2:

1. Исходная последовательность для n=1: 0, 1.
2. Зеркальное отражение: 1, 0.
3. Объединение: 0, 1, 1, 0.
4. Добавление старшего бита: 00, 01, 11, 10.

Для n = 3:

1. Последовательность для n=2: 00, 01, 11, 10.
2. Зеркальное отражение: 10, 11, 01, 00.
3. Объединение: 00, 01, 11, 10, 10, 11, 01, 00.
4. Добавление старшего бита: 000, 001, 011, 010, 110, 111, 101, 100.

Этот метод обеспечивает, что любые два соседних кода отличаются ровно на один бит. Код Грея является циклическим: последнее и первое числа последовательности также отличаются на один бит (например, для n=3: 100 и 000).

Классификация

Код Грея не является единственным кодом с минимальным расстоянием Хэмминга, равным 1 между соседними значениями, но он наиболее распространён. Различают несколько разновидностей:

Двоичный код Грея (Binary Gray Code)

Стандартный рефлексный код, описанный выше. Используется в большинстве практических приложений.

N-ичный код Грея (Non-binary Gray Code)

Обобщение на системы счисления с основанием больше 2. Например, троичный код Грея, где последовательные числа отличаются на один трит. Строится аналогично рекурсивно, но с учётом большего числа состояний.

Сбалансированный код Грея (Balanced Gray Code)

Вариант, в котором количество изменений каждого бита в полном цикле одинаково (или почти одинаково). Применяется в некоторых схемах кодирования для равномерного износа контактов.

Однодорожечный код Грея (Single-track Gray Code)

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

Связь с двоичным кодом

Преобразование между обычным двоичным кодом и кодом Грея выполняется по простым логическим формулам. Для n-разрядного числа:

Преобразование двоичного кода в код Грея

Пусть B — двоичное число, G — код Грея. Тогда:

• G[n-1] = B[n-1] (старший бит остаётся без изменений).
• G[i] = B[i] XOR B[i+1] для i от n-2 до 0.

Пример: B = 1010 (десятичное 10). G[3] = 1, G[2] = 1 XOR 0 = 1, G[1] = 0 XOR 1 = 1, G[0] = 1 XOR 0 = 1. Результат: G = 1111.

Преобразование кода Грея в двоичный код

Обратное преобразование:

• B[n-1] = G[n-1].
• B[i] = G[i] XOR B[i+1] для i от n-2 до 0.

Пример: G = 1111. B[3] = 1, B[2] = 1 XOR 1 = 0, B[1] = 1 XOR 0 = 1, B[0] = 1 XOR 1 = 0. Результат: B = 1010.

Эти преобразования реализуются аппаратно с помощью цепочки логических элементов «исключающее ИЛИ» (XOR).

Применение

Код Грея нашёл широкое применение в различных областях цифровой техники и информатики.

Энкодеры и датчики положения

В оптических и магнитных энкодерах (например, в маховичках компьютерных мышей, в станках с ЧПУ, в робототехнике) код Грея используется для кодирования углового или линейного положения. Обычный двоичный код при переходе между соседними значениями может менять сразу несколько битов, что из-за несинхронности считывания (например, из-за разной длины дорожек) приводит к ошибкам — так называемым «глитчам» (glitches). Код Грея, меняя только один бит, исключает эту проблему.

Карты Карно

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

Передача данных

В некоторых системах связи код Грея используется для уменьшения вероятности ошибки при амплитудной или фазовой модуляции. Например, в квадратурной амплитудной модуляции (QAM) соседние символы на сигнальном созвездии кодируются кодом Грея, чтобы при однобитовой ошибке приёма искажался только один бит информации.

Задачи дискретной математики

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

Вычислительная техника

В некоторых архитектурах процессоров код Грея применяется для адресации памяти, чтобы минимизировать переключения линий адресной шины и снизить энергопотребление. Также используется в FIFO-буферах (First In, First Out) для синхронизации указателей чтения и записи в асинхронных интерфейсах.

Пример использования

Рассмотрим трёхразрядный код Грея для чисел от 0 до 7:

Как видно, каждое последующее значение кода Грея отличается от предыдущего ровно на один бит. Например, при переходе от 3 (010) к 4 (110) меняется только старший бит.

Интересные факты

• Код Грея иногда называют «рефлексным кодом» из-за способа его построения через зеркальное отражение.
• В 1878 году французский инженер Эмиль Бодо (Émile Baudot) использовал похожий код для телеграфной связи, но он не был рефлексным.
• Код Грея является одним из примеров кода с минимальным расстоянием Хэмминга, равным 1, но не единственным. Существуют и другие коды с тем же свойством.
• В математике код Грея тесно связан с гамильтоновыми путями на n-мерном кубе (гиперкубе). Последовательность кодов Грея задаёт такой путь, проходящий через все вершины куба ровно один раз.

Источники

• Gray, F. "Pulse Code Communication," U.S. Patent 2,632,058, March 17, 1953.
• Хоровиц П., Хилл У. "Искусство схемотехники", 7-е издание, 2003.
• Knuth, D. E. "The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1", 2011.
• Таненбаум Э., Остин Т. "Архитектура компьютера", 6-е издание, 2013.