Сірий код: Один біт перемикання за раз

Проблема з простим бінарним кодом

Підрахунок у звичайному бінарному коді виглядає гладко на папері, але кількість бітів, які перемикаються між послідовними значеннями, дуже нерівномірна. Перехід від 3 до 4 бітів перемикає три біти (011 → 100); перехід від 7 до 8 бітів перемикає чотири (0111 → 1000). Якщо фізичний датчик — поворотний вал, механічна група перемикачів — зчитується в момент, коли кілька бітів повинні змінитись, біти рідко змінюються синхронно. Читач може зловити деякі біти, які вже перемкнені, та інші, які ще не перемкнені, створюючи хибне проміжне значення, яке ніяк не відповідає старому чи новому положенню.

Відбитий бінарний код: g = b XOR (b >> 1)

Завоювання Франком Грейом у 1953 році (на основі попередніх робіт Еміля Баудота) вирішує це, переставляючи ті самі 2ⁿ значення так, щоб кожне послідовне пари відрізнялися лише на один біт. Для звичайного бінарного числа b, його Gray code g обчислюється наступним чином:

g = b XOR (b >> 1) b (двійкове) g (Gray) 000 000 001 001 010 011 011 010 100 110 101 111 110 101 111 100 Назва "відбитий бінарний код" походить від рекурсивного побудови: n-бітова Gray послідовність є (n-1)-бітовою послідовністю, записаною вперед з ведучою нульовою, за якою слідує та сама (n-1)-бітова послідовність, записана назад (відбита) з ведучою одиницею. Кожне відображення гарантує різницю в одній біт між двома половинами — новий лідерський біт — а внутрішня частина кожної половини вже задовольняє властивість зміни лише на один біт шляхом індукції.

g = b XOR (b >> 1)

  b (binary)   g (Gray)
  000          000
  001          001
  010          011
  011          010
  100          110
  101          111
  110          101
  111          100

Розшифрування назад до бінарного коду

XOR, який побудував код Грей, легко скасувати за допомогою кумулятивного XOR-скану від найзначущої розрядної байти донизу: верхній вихідний біт дорівнює верхньому біту коду Грей, і кожен наступний біт є XOR попереднього вихідного біта з поточним бітом коду Грей.

// decode: Gray -> binary, most-significant bit first
b[0] = g[0];
for (i = 1; i < n; i++) {
  b[i] = b[i - 1] XOR g[i];
}

Гамільтонів шлях на гіперкубі

Уявіть собі граф, точки якого складають 2ⁿ вершин, усі з яких є n-бітними рядками, з ребром між будь-якими двома рядками, які відрізняються лише в одній біті — це граф гіперкуба у n вимірах. Оскільки послідовні коди Грей відрізняються на один біт за конструкцією, послідовність кодів Грей є точним гамільтоновим шляхом через цей граф: маршрут, який відвідує кожну вершину рівно один раз, рухаючись лише вздовж ребер. Стандартний код Грей насправді є гамільтоновим циклом, оскільки останній код та перший також відрізняються на один біт (лише верхній біт, за конструкцією відображення).

Цей графічний погляд пояснює, чому код Грей так добре узагальнюється: будь-який гамільтонови цикл на гіперкубі дає дійсний порядок «зміна одного біта», і код Грей є просто найсистемнішим та найпростішим для обчислення. Він також є основою класичного рекурсивного/ітеративного алгоритму для генерації всіх підмножин множини по одному елементу за раз — пересуванням по послідовності Грея ми змінюємо лише один член підмножини на кожному кроці.

Где це фактично використовується

Абсолютні поворотні та лінійні енкодери друкують малюнок у колірному коді Грей на диску або стрічку завдяки гарантії одного біта: помилка поблизу переходу не виходить за межі однієї позиції замість хаотичного стрибка. Картографічні діаграми в цифровому дизайні логіки порядку рядки та стовпчики у колірному коді Грей, щоб сусідні комірки завжди відрізнялися на один біт введення, що робить візуальне групування сусідніх одиниць у прямокутники допустимим способом для виявлення мінімальних булевих спрощень. Колірний код Грей також з'являється в генетичних алгоритмах (зміна одного біта змінює розшифроване значення на невелику, передбачувану величину, на відміну від простого бінарного коду, де одноразова мутація високого біта може величезно збільшити значення) та в схемах корекції помилок зв’язку, де він мінімізує числову шкоду, спричинену пошкодженням одного біта передачі.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Gray Code і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.