Коды Грея: Безопасные переходы в цифровых системах
В классической двоичной системе счисления переход от одного числа к следующему может потребовать изменения сразу нескольких битов. Например, при переходе от числа 3 (011 в двоичной записи) к числу 4 (100) меняются все три бита. В идеальном математическом мире это не проблема, но в реальной микроэлектронике и электромеханических датчиках биты не переключаются абсолютно синхронно. Возникает опасный момент, когда система может выдать ложное промежуточное значение. Решение этой проблемы лежит в использовании специальной кодировки — кода Грея.
Фрэнк Грей, инженер лаборатории Bell Labs, в 1947 году запатентовал систему бинарного кодирования, обладающую одним ключевым свойством: любые два соседних значения в этом коде различаются ровно в одном бите (расстояние Хэмминга между ними строго равно единице).
Посмотрим на последовательность первых чисел в стандартном двоичном коде: 000, 001, 010, 011, 100.
А теперь та же последовательность (от 0 до 4) в коде Грея: 000, 001, 011, 010, 110.
Если механический датчик угла поворота (энкодер) на станке с ЧПУ будет использовать обычный двоичный код, то на границе перехода от 011 к 100 микроконтроллер может на долю миллисекунды считать значение 111 (число 7 вместо 4), если старший бит переключится чуть раньше остальных. Это может привести к аварии станка. В коде Грея переход от 3 (010) к 4 (110) меняет только один старший бит. Даже если произойдет задержка считывания, контроллер увидит либо старое значение (3), либо новое (4). Никаких случайных выбросов и глитчей не возникнет в принципе.
Математически, отраженный (рефлексивный) код Грея длины N строится рекурсивно. Мы берем код длины N-1, записываем его в прямом порядке, приписывая спереди нули, а затем записываем его же в обратном порядке (как в зеркале), приписывая спереди единицы. Для быстрого преобразования обычного бинарного числа (B) в код Грея (G) в процессоре используется простейшая побитовая операция XOR с логическим сдвигом вправо: G = B ^ (B >> 1).
Помимо аппаратного обеспечения (энкодеры, системы ФАПЧ), код Грея активно применяется в чистой дискретной математике. Он лежит в основе визуального метода минимизации булевых функций — Карт Карно (Karnaugh maps). Обозначения строк и столбцов в этих картах упорядочены именно по коду Грея, чтобы соседние клетки таблицы различались только одной логической переменной, что позволяет визуально "склеивать" блоки единиц в компактные логические формулы. Также код Грея популярен в генетических алгоритмах машинного обучения для кодирования хромосом, так как он обеспечивает плавность мутаций (изменение одного бита не приводит к резким скачкам фенотипа).
