N-ичный код Грея

N-ичный код Грея — это система счисления, в которой два последовательных значения различаются только в одном разряде (цифре). В отличие от обычного двоичного, десятичного или любого другого позиционного кода, где при переходе к следующему числу может изменяться несколько разрядов одновременно (например, от 3 к 4 в двоичной системе: 011 → 100 — меняются три бита), код Грея гарантирует минимальное расстояние Хэмминга, равное 1, между соседними кодовыми словами. Назван по имени американского физика и изобретателя Фрэнка Грея, который запатентовал его в 1953 году для использования в импульсно-кодовой модуляции. N-ичный код Грея является обобщением двоичного кода Грея на системы счисления с основанием N (N ≥ 2).

История

Идея кода, в котором соседние значения отличаются только в одном разряде, возникла задолго до Грея. В 1878 году французский инженер Эмиль Бодо использовал подобный принцип в телеграфном коде (код Бодо), где последовательные буквы алфавита кодировались так, чтобы переход между ними требовал минимального изменения сигнала. Однако современная форма кода была разработана Фрэнком Греем (Frank Gray) в лабораториях Bell Telephone. В 1947 году он подал заявку на патент «Pulse Code Communication», который был выдан в 1953 году. Первоначально код предназначался для уменьшения ошибок при передаче цифровых сигналов по аналоговым линиям связи. Позднее, с развитием цифровой электроники, код Грея нашёл широкое применение в датчиках положения, энкодерах и теории кодирования.

Определение и свойства

N-ичный код Грея (также называемый кодом Грея по основанию N) представляет собой последовательность из N^k кодовых слов длины k, где каждое слово состоит из цифр от 0 до N-1. Последовательность обладает свойством: для любых двух соседних слов (включая последнее и первое, если последовательность циклическая) значения отличаются ровно в одной позиции, и разница между цифрами в этой позиции составляет ±1 (по модулю N). Это свойство называется «единичным расстоянием» (unit distance).

Основные свойства:

• Минимальное изменение: переход между любыми двумя последовательными значениями требует изменения только одного разряда.
• Цикличность (опционально): последовательность может быть замкнута в кольцо, где последнее и первое слова также отличаются в одном разряде.
• Рефлексивность: для двоичного кода Грея характерно свойство рефлексии — последовательность для (k+1)-битного кода строится путём отражения последовательности для k-битного.
• Однозначность: каждое целое число от 0 до N^k-1 соответствует ровно одному кодовому слову.

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

По основанию системы счисления (N)

1. Двоичный код Грея (N=2): наиболее распространённый вариант. Используется в цифровых энкодерах, картах Карно, при передаче данных. Пример: 000, 001, 011, 010, 110, 111, 101, 100.
2. Троичный код Грея (N=3): применяется в троичных вычислительных системах и некоторых типах датчиков. Пример для k=2: 00, 01, 02, 12, 11, 10, 20, 21, 22.
3. Десятичный код Грея (N=10): используется в десятичных энкодерах и цифровых вольтметрах. Пример для k=1: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (совпадает с обычным десятичным кодом, так как k=1).

По структуре последовательности

• Циклический код Грея: последовательность замкнута в кольцо. Например, двоичный код Грея для k=3 цикличен: после 100 снова идёт 000.
• Ациклический код Грея: последнее и первое слова не обязаны быть соседними. Используется реже, обычно в специализированных задачах.

По способу построения

• Рефлексивный код Грея: строится путём рекурсивного отражения. Для двоичного случая алгоритм: взять последовательность для k-1 бит, добавить к ней её зеркальное отражение, затем к первой половине приписать 0 в старший разряд, ко второй — 1.
• Код Грея на основе XOR: для двоичного кода Грея существует простая формула: G(i) = i XOR (i >> 1), где i — номер числа, G(i) — его код Грея.
• Код Грея на основе перестановок: для N>2 используются алгоритмы, основанные на перестановках цифр или на обобщённой рефлексии.

Алгоритмы построения

Для двоичного кода Грея

Самый простой способ получить двоичный код Грея для числа i — использовать побитовую операцию XOR: `` G(i) = i XOR (i >> 1) ` Обратное преобразование (из кода Грея в обычное двоичное число) выполняется последовательным XOR всех битов: ` i = G(0) XOR G(1) XOR ... XOR G(k-1) `` или рекурсивно.

Для N-ичного кода Грея (общий случай)

Существует несколько алгоритмов. Один из них — обобщение рефлексивного метода:

1. Построить последовательность для k=1: 0, 1, 2, ..., N-1.
2. Для k>1: взять последовательность для k-1, отразить её (записать в обратном порядке). Затем к каждому элементу первой половины приписать слева 0, ко второй половине — 1, и так далее, чередуя цифры от 0 до N-1.

Другой метод — использование формулы с делением по модулю N. Для числа i в системе с основанием N его код Грея G(i) вычисляется как: `` G(i) = (i + floor(i / N)) mod N `` для каждого разряда, но это работает только для определённых типов кодов.

Применение

В технике

• Энкодеры (датчики угла поворота): оптические и магнитные энкодеры используют код Грея для определения положения вала. Если бы использовался обычный двоичный код, при переходе между секторами возможны ошибки из-за неодновременного изменения нескольких битов. Код Грея гарантирует, что даже при неточном считывании ошибка будет не более одного кванта.
• Цифровые вольтметры и АЦП: в некоторых аналого-цифровых преобразователях применяется код Грея для уменьшения ошибок при смене диапазона.
• Карты Карно: в минимизации логических функций двоичный код Грея используется для нумерации ячеек карты Карно, так как соседние ячейки отличаются только одним битом, что упрощает поиск импликант.
• Передача данных: в некоторых протоколах (например, в системах с импульсно-кодовой модуляцией) код Грея применяется для уменьшения вероятности битовых ошибок.

В математике и информатике

• Гамильтоновы циклы: N-ичный код Грея является гамильтоновым циклом в N-арном гиперкубе (графе, вершины которого — все N-ичные последовательности длины k, а рёбра соединяют вершины, различающиеся в одной позиции на ±1).
• Головоломки: известная головоломка «Ханойская башня» имеет решение, которое можно описать с помощью кода Грея. Перемещение дисков соответствует последовательности чисел в двоичном коде Грея.
• Генетические алгоритмы: в некоторых эволюционных алгоритмах код Грея используется для кодирования хромосом, чтобы минимизировать влияние мутаций.

Примеры

Двоичный код Грея для k=3

Троичный код Грея для k=2

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

• Код Грея иногда называют «отражённым двоичным кодом» (reflected binary code, RBC) из-за свойства рефлексии.
• В 1972 году советский математик В. Н. Кабанов обобщил код Грея на случай с произвольным основанием и доказал существование N-ичных кодов Грея для любых N и k.
• Существуют так называемые «коды Грея с произвольным весом», где разница между соседними словами может быть больше 1, но сохраняется свойство минимального изменения в одном разряде.

Критика

Основной недостаток N-ичного кода Грея — сложность арифметических операций. Сложение, вычитание и умножение в коде Грея требуют предварительного преобразования в обычную систему счисления, что увеличивает задержки в вычислительных устройствах. Кроме того, для N>2 построение кода становится более сложным, а количество возможных последовательностей (для заданных N и k) может быть очень большим, что затрудняет выбор оптимального варианта. В некоторых применениях (например, в современных высокоскоростных АЦП) код Грея вытесняется более эффективными методами коррекции ошибок, такими как коды Хэмминга.

Источники

• Gray, F. «Pulse Code Communication». U.S. Patent 2,632,058, 1953.
• Knuth, D. E. «The Art of Computer Programming, Volume 4A: Combinatorial Algorithms». Addison-Wesley, 2011.
• Кабанов, В. Н. «Обобщённые коды Грея». Проблемы передачи информации, 1972.
• Press, W. H. et al. «Numerical Recipes: The Art of Scientific Computing». Cambridge University Press, 2007.