Код Грея

Код Грея (binary‐reflected Gray code, BRGC) – это способ нумерации двоичных слов фиксированной длины nnn, при котором соседние коды отличаются ровно в одном бите. Такое упорядочение образует гамильтонов цикл на n-мерном гиперкубе и широко применяется там, где важно минимизировать число «переключений» разрядов между соседними состояниями: в цифровых датчиках, АЦП, энкодерах, при построении таблиц Карно и в ряде алгоритмических задач. В контексте ЕГЭ знание кода Грея помогает:

• корректно работать с таблицами истинности и таблицами Карно (смежные клетки отличаются одним битом);

• решать задачи на кодирование и декодирование;

• анализировать переходы между двоичными состояниями, проверять «одноразрядность» изменения;

• уверенно оперировать двоичными операциями (XOR), префиксными свёртками, порядками перебора.

Формальные определения и базовые свойства

1. Двоичный отражённый код Грея
   
   

   Рекурсивное построение (отражение):
   
   

2. Аддитивное описание через XOR
   

   Пусть двоичное число b длины n записано как биты bn−1…b1b0 (старший разряд bn−1​). Тогда его код Грея g определяется покомпонентно:

   
   

   или в краткой форме для целого числа:

   
   
   

3. Обратное преобразование (декодирование)
   

   Из g получаем b префиксной XOR-свёрткой:

   
   
   

4.  Ключевые свойства
   

   • Одноразрядность: для последовательности G(n) вес XOR соседей равен 1.

   • Цикличность: G(n) образует цикл (первый и последний коды также различаются в одном бите).

   • Равномерность изменения веса: изменения числа единиц между соседями минимальны (±1).

   • Графовая интерпретация: коды – вершины гиперкуба Qn​, порядок G(n) – гамильтонов цикл/путь.

   • Связь с Карно: расположение клеток карты Карно соответствует G(k) по каждой оси, так что любые соседние клетки отличаются одним битом в адресе.

Алгоритмы генерации и преобразования

1. Генерация всей последовательности
   
   

   Рекурсивно (по определению): удобно для доказательств и задач на построение, но на практике итеративная формула короче.

2. «Следующий код» без хранения индекса
   
   

3. Кодирование и декодирование отдельных чисел
   
   

Практические «правила применения»

1. Фиксируйте разрядность n. Код Грея определён для слов ровно длины n; ведущие нули существенны (например, «001» и «1» – разные при n=3).

2. Единообразие порядка битов. В формулах выше g_n−1 – старший бит. Перепутанная нумерация породит ложные ошибки.

3. Проверка одноразрядности. Для любой последовательности претендентов проверьте: XOR соседей – степень двойки (ровно один бит установлен).

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

5. Не смешивайте коды. Если одна часть модели требует двоичного индекса, а другая – кода Грея, явно конвертируйте между ними (формулы сверху), не сравнивайте «как есть».

6. В задачах на минимизацию переключений (седьмые/последние задания с программированием, моделирование устройств) применяйте порядок Грея как «естественный» для обхода состояний.

Типичные ошибки и как их избегать

• Отсутствие ведущих нулей: «обрыв» разрядности ломает одноразрядность на стыках.

• Неверный край цикла: забывают проверить переход «последний → первый».

• Путаница порядка соседей при ручном построении G(n): нарушается отражение на втором блоке.

• Суммирование вместо XOR в декодировании – недопустимо: используется только поразрядный XOR.

Связь с подготовкой к ЕГЭ

• Таблицы истинности и Карно. При расположении строк/столбцов по Грею соседние клетки отличаются одним битом → корректно формируются группы 1, 2, 4, 8 для упрощения булевых выражений.

• Кодирование/декодирование. Встречаются задачи на вычисление кода Грея от числа (или обратно), на установление соответствий между позициями таблиц.

• Проверка свойств последовательностей. Требования «изменяется один разряд» напрямую переводятся в критерий «XOR соседей – степень двойки».

• Анализ алгоритмов и двоичных операций. Формулы сдвига/исключающего ИЛИ – отличный материал для тренировки побитовой логики, востребованной в задачах высокого уровня.

Пять упражнений (академический формат «теория + практика»)

Упражнение 1. Рекурсивное построение и проверка одноразрядности

Постройте G(3) рекурсивно по схеме отражения.
a) Запишите все 8 кодовых слов в порядке G(3).
b) Для каждой пары соседей вычислите XOR и убедитесь, что результат – степень двойки.
c) Проверьте цикличность: сравните последний и первый элементы.

Упражнение 2. Кодирование и декодирование (формулы)

Упражнение 3. «Следующий по Грею» и позиция изменяемого бита

Упражнение 4. Таблица Карно с упорядочением по Грею

Упражнение 5. Контроль «одноразрядности» заданной последовательности

Заключение

Код Грея – классический инструмент дискретной математики и информатики, обеспечивающий минимальные изменения между соседними двоичными состояниями. Его сила – в простоте формул g=b⊕(b≫1) и префиксной XOR-декодировки, строгой одноразрядности переходов и естественной связи с графовой моделью гиперкуба и картами Карно. Для ЕГЭ владение кодом Грея означает умение:

• корректно упорядочивать строки/столбцы таблиц истинности;

• быстро кодировать и декодировать двоичные числа;

• проверять и конструировать последовательности с единственным изменяемым разрядом.