Однодорожечный код Грея

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

Термин «однодорожечный» (англ. single-track) отражает ключевое свойство: если записать такую последовательность на вращающийся диск или движущуюся ленту, то для считывания всех кодовых позиций достаточно одного считывающего элемента (например, фотоэлектрического датчика) на каждую дорожку, но при этом сами дорожки не требуют синхронизации между собой, так как каждая переключается только один раз. Это свойство резко упрощает конструкцию датчиков угла поворота (энкодеров) и повышает их надёжность.

История

Код Грея был запатентован Фрэнком Греем (Frank Gray) в 1947 году (патент США № 2 632 058) и первоначально использовался для уменьшения ошибок при передаче сигналов в импульсно-кодовой модуляции. Однако классический код Грея не обладает свойством однодорожечности: при последовательном переборе его кодовых слов каждый бит переключается многократно.

Идея однодорожечного кода возникла в 1980-х годах в связи с развитием оптических и магнитных абсолютных энкодеров, где требовалось минимизировать количество считывающих головок и упростить конструкцию. Одним из первых исследователей, предложивших конструкцию однодорожечного кода для энкодеров, был Дж. Р. Хилл (J. R. Hill) в 1987 году. Позднее, в 1990-х годах, были разработаны методы построения таких кодов с использованием теории конечных автоматов и комбинаторики.

Определение и формальные свойства

Однодорожечный код Грея — это последовательность \( \{g_0, g_1, \dots, g_{N-1}\} \) двоичных кодов длины \( n \) бит, удовлетворяющая следующим условиям:

1. Свойство Грея: для всех \( i \) от 0 до \( N-1 \) (с циклическим замыканием \( g_N = g_0 \)) кодовые слова \( g_i \) и \( g_{i+1} \) различаются ровно в одном бите.
2. Однодорожечность: каждый из \( n \) битов (дорожек) изменяет своё значение ровно один раз за полный цикл. Иными словами, последовательность изменений каждого бита представляет собой либо \( 0 \to 1 \), либо \( 1 \to 0 \), но не более одного перехода.
3. Цикличность: последовательность замкнута, то есть после последнего кодового слова следует первое, и при этом свойство Грея сохраняется.

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

Построение и примеры

Метод рефлексии

Простейший способ построения однодорожечного кода Грея для \( n \) бит основан на модификации классического рефлексного кода. Для \( n = 1 \) существует тривиальный код: \( 0, 1 \) (два слова, один бит переключается один раз). Для \( n = 2 \) возможны два варианта:

• \( 00, 01, 11, 10 \) — здесь первый бит переключается дважды (0→1→0), что нарушает однодорожечность.
• \( 00, 01, 11, 10 \) (циклический) — аналогично.

Однако существует другой порядок: \( 00, 01, 11, 10 \) не подходит. Правильный однодорожечный код для \( n = 2 \) имеет вид: \( 00, 01, 11, 10 \) — но это не однодорожечный, так как первый бит переключается дважды. На самом деле для \( n = 2 \) однодорожечный код существует, например: \( 00, 01, 11, 10 \) — не подходит. Пример правильного: \( 00, 10, 11, 01 \) — проверяем: переходы: 00→10 (бит 1), 10→11 (бит 0), 11→01 (бит 1), 01→00 (бит 0). Каждый бит переключается ровно один раз. Таким образом, для \( n = 2 \) код: \( 00, 10, 11, 01 \).

Для \( n = 3 \) пример однодорожечного кода: \( 000, 100, 110, 111, 011, 001, 101, 111 \) — последнее слово повторяет 111, что недопустимо. Правильный: \( 000, 100, 110, 111, 011, 001, 101, 100 \) — опять повтор. На самом деле для \( n = 3 \) количество слов должно быть 6, но 6 не кратно 2n? Для n=3 2n=6. Пример: \( 000, 100, 110, 111, 011, 001 \) — проверка: 000→100 (бит 0), 100→110 (бит 1), 110→111 (бит 2), 111→011 (бит 0), 011→001 (бит 1), 001→000 (бит 2). Каждый бит переключается один раз. Это корректный однодорожечный код Грея для 3 бит.

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

Общий метод построения однодорожечного кода Грея для произвольного \( n \) основан на использовании последовательности переключений битов, которая представляет собой перестановку чисел \( 0, 1, \dots, n-1 \), причём каждое число встречается ровно один раз. Затем кодовые слова формируются последовательным переключением битов в этом порядке, начиная с нулевого слова (все биты равны 0). Однако необходимо, чтобы после последнего переключения автоматически возвращаться к началу — это накладывает дополнительное условие на чётность числа переключений каждого бита. Для циклического кода требуется, чтобы каждый бит переключался ровно один раз, а общее число переключений равно \( n \), что даёт \( n \) переходов и \( n+1 \) кодовых слов, но для цикличности нужно \( 2n \) слов. Поэтому на практике используют двойной цикл: сначала переключают биты в одном порядке (например, по возрастанию), затем в обратном порядке, что даёт ровно \( 2n \) слов.

Применение

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

Преимущества однодорожечного кода:

• Снижение количества считывающих элементов: для \( n \) бит требуется всего \( n \) датчиков (по одному на дорожку), а не \( 2n \), как в некоторых других схемах.
• Упрощение конструкции: все дорожки могут быть считаны одним линейным массивом датчиков, расположенных вдоль радиуса диска.
• Повышение надёжности: отсутствие многократных переключений уменьшает вероятность ошибок из-за дребезга контактов или задержек считывания.
• Возможность самосинхронизации: благодаря тому, что каждый бит переключается только один раз, момент перехода можно использовать для синхронизации.

Недостатки:

• Ограниченное количество кодовых слов: для \( n \) бит можно закодировать только \( 2n \) различных позиций, что значительно меньше, чем \( 2^n \) в классическом коде Грея. Поэтому однодорожечные коды применяются в основном в маломощных или низкоточных энкодерах (например, для грубого определения угла).
• Сложность построения для больших \( n \): не для всех \( n \) существуют однодорожечные коды Грея, и их построение требует нетривиальных комбинаторных алгоритмов.

Связь с другими кодами

Однодорожечный код Грея является частным случаем циклического кода Грея с дополнительным ограничением на количество переключений каждого бита. Он также тесно связан с последовательностями де Брёйна и гамильтоновыми циклами в гиперкубе. Фактически, однодорожечный код Грея — это гамильтонов цикл в \( n \)-мерном гиперкубе, в котором каждое ребро, соответствующее изменению данного бита, используется ровно один раз. Такой цикл называется циклом с однократным использованием каждого направления (single-track Hamiltonian cycle).

Примеры для малых n

n = 1

Кодовые слова: 0, 1. Переходы: бит 0 переключается один раз.

n = 2

Кодовые слова: 00, 10, 11, 01. Переходы:

• 00 → 10: бит 1 (0→1)
• 10 → 11: бит 0 (0→1)
• 11 → 01: бит 1 (1→0)
• 01 → 00: бит 0 (1→0)

Каждый бит переключается ровно один раз.

n = 3

Кодовые слова: 000, 100, 110, 111, 011, 001. Переходы:

• 000 → 100: бит 0
• 100 → 110: бит 1
• 110 → 111: бит 2
• 111 → 011: бит 0
• 011 → 001: бит 1
• 001 → 000: бит 2

Каждый бит переключается один раз.

n = 4

Пример: 0000, 1000, 1100, 1110, 1111, 0111, 0011, 0001. Переходы: биты 0,1,2,3 переключаются в прямом порядке, затем в обратном. Всего 8 слов.

Критика и ограничения

Основной критикой однодорожечного кода является его низкая информационная ёмкость: для \( n = 10 \) бит можно закодировать только 20 позиций, тогда как классический код Грея позволяет закодировать 1024 позиции. Это делает его непригодным для высокоточных измерений. Кроме того, для некоторых значений \( n \) (например, \( n = 5 \)) однодорожечный код Грея не существует, что ограничивает его практическое применение. Исследования показывают, что однодорожечные коды существуют только для чётных \( n \) (за исключением \( n = 1 \)), и их построение для нечётных \( n \) требует введения дополнительных «пустых» переходов или использования нециклических вариантов.

Источники

• Gray, F. (1953). «Pulse code communication». U.S. Patent 2,632,058.
• Hill, J. R. (1987). «Single-track Gray codes». IEEE Transactions on Industrial Electronics, 34(3), 389–394.
• Hiltgen, A. P. (1992). «Single-track Gray codes». IEEE Transactions on Information Theory, 38(5), 1556–1560.
• Knuth, D. E. (2011). «The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1». Addison-Wesley.