Код Грея: соседние числа отличаются одним битом

Если ты выпишешь трёхбитный код Грея, переведёшь номер в код и обратно и объяснишь, почему при переборе подмножеств в этом порядке сумму не надо считать заново, - листай до «Теперь сам».

Как думаешь, что прочитает датчик между 3 и 4

На валу стоит диск с тремя дорожками, каждая - чёрно-белые секторы; три фотоэлемента читают три бита и получают номер сектора от 0 до 7. Вал поворачивается из сектора 3 в сектор 4: 011 сменяется на 100.

Прежде чем читать дальше, ответь себе: что прочтёт датчик, если опросить его ровно на границе? Три бита меняются одновременно только на бумаге. На деле один фотоэлемент переключится чуть раньше других, и на мгновение датчик покажет 111, 000, 110 - что угодно, включая сектор на противоположной стороне диска.

На что это похоже

Кодовый замок с тремя переключателями, и ты хочешь перебрать все восемь положений, щёлкая как можно меньше. Если идти по обычному счёту - 000, 001, 010, - то между 001 и 010 придётся щёлкнуть двумя переключателями, а между 011 и 100 - всеми тремя. Всего одиннадцать щелчков на семь переходов.

А можно найти порядок, в котором на каждый переход - ровно один щелчок, семь на всё. Такой порядок и есть код Грея. Для датчика это значит, что на границе секторов меняется один бит, и что бы он ни прочитал - старое значение или новое, - ошибка не больше одного сектора.

Механизм: отражение, формула и обратный перевод

Строится код отражением. Для одного бита порядок - 0, 1. Чтобы получить порядок для двух битов, список записывают дважды - прямо и в обратном порядке - и к первой половине приписывают слева ноль, ко второй - единицу:

1 бит:   0  1
2 бита:  00 01 | 11 10            вторая половина - первая, прочитанная назад, с единицей впереди
3 бита:  000 001 011 010 | 110 111 101 100

Внутри каждой половины соседи отличаются одним битом - они взяты из меньшего кода. На стыке половин стоят два одинаковых слова с разным старшим битом. И последний элемент отличается от первого тоже одним битом: код замкнут в кольцо.

Код Грея числа x - слово, стоящее на месте x в этом порядке. Формула: g = x ^ (x >> 1). Каждый бит кода - это ^ двух соседних битов номера: бит i кода равен единице, когда биты i и i + 1 номера различны.

x       = 1 0 1 1 0          22
x >> 1  = 0 1 0 1 1
g       = 1 1 1 0 1          старший бит переходит как есть

Почему соседи отличаются одним битом. Прибавление единицы к x переворачивает младший ноль и хвост единиц под ним - участок вида 0111 становится 1000. Бит кода - это ^ двух соседних битов номера. Внутри участка перевернулись оба соседа, и их ^ не изменился; выше участка не перевернулся ни один. Изменилась одна пара: верхний бит участка и нетронутый бит над ним. В коде Грея это один бит - тот, что соответствует верхнему биту участка. Его номер - число хвостовых нулей у нового x.

Обратно. Из формулы: старший бит номера равен старшему биту кода, а каждый следующий - ^ предыдущего бита номера с очередным битом кода. Раскрыв цепочку, получаем, что бит i номера - ^ всех битов кода от старшего до i-го.

Правило

Код Грея числа x: g = x ^ (x >> 1). Обратно: x = g ^ (g >> 1) ^ (g >> 2) ^ …, пока сдвиг не обнулит g. Коды чисел k − 1 и k различаются в одном бите, и его номер равен числу хвостовых нулей k. Последний код отличается от первого тоже одним битом.

Разбор: таблица, обратный перевод и какой бит меняется

def v_grej(x):
    return x ^ x >> 1

def iz_greya(g):
    x = g
    g = g >> 1
    while g > 0:
        x = x ^ g
        g = g >> 1
    return x

for x in range(8):
    g = v_grej(x)
    print(x, bin(x)[2:].zfill(3), bin(g)[2:].zfill(3), iz_greya(g))

0 000 000 0
1 001 001 1
2 010 011 2
3 011 010 3
4 100 110 4
5 101 111 5
6 110 101 6
7 111 100 7

Третий столбец совпал с порядком, построенным отражением. Между секторами 3 и 4 из начала урока теперь 010 и 110 - один бит.

smena = []
for k in range(1, 16):
    raznica = v_grej(k) ^ v_grej(k - 1)
    smena.append(raznica.bit_length() - 1)
print(smena)

[0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0]

Номер меняющегося бита на шаге k - число хвостовых нулей k: у нечётных это 0, у 2 и 6 - единица, у 4 и 12 - двойка, у 8 - тройка. Младший бит меняется на каждом втором шаге, следующий - на каждом четвёртом. Эту же последовательность выдаёт решение ханойских башен из первого раздела: на шаге k двигается диск с номером, равным числу хвостовых нулей k.

iz_greya делает на один круг меньше, чем битов в коде. Для 32-битного слова есть вариант за пять строк - сдвиги на 1, 2, 4, 8, 16, по образцу размазывания старшей единицы: x = x ^ x >> 1, затем x = x ^ x >> 2 и так далее. Обратный перевод дают все пять строк вместе; одной первой мало.

Разбор: перебор подмножеств с одной правкой на шаг, и граница

Сколько подмножеств набора из 12 чисел дают сумму ровно 40? В программах ves - список чисел, cel - нужная сумма; значения - в таблице ниже. Прямой способ - перебрать маски по порядку и для каждой сложить её элементы:

n = len(ves)
podhodit = 0
for m in range(1 << n):
    s = 0
    for i in range(n):
        if m >> i & 1:
            s = s + ves[i]
    if s == cel:
        podhodit = podhodit + 1
print(podhodit)

В порядке кода Грея соседние подмножества отличаются одним элементом, и сумму не пересчитывают, а поправляют:

n = len(ves)
podhodit = 0
s = 0
g = 0
if s == cel:
    podhodit = podhodit + 1
for k in range(1, 1 << n):
    i = (k & -k).bit_length() - 1
    g = g ^ 1 << i
    if g >> i & 1:
        s = s + ves[i]
    else:
        s = s - ves[i]
    if s == cel:
        podhodit = podhodit + 1
print(podhodit)

На шаге k переключается элемент с номером «число хвостовых нулей k»: если он появился в множестве - его вес прибавляется, если исчез - вычитается.

веса 3, 34, 4, 12, 5, 2, 7, 8, 11, 9, 21, 13;  цель 40

способ                         ответ      шагов
сумма заново для каждой маски    42      135 213
порядок Грея, одна правка        42       24 618

Выигрыш - множитель n: вместо n · 2ⁿ действий стало 2ⁿ. В шагах тренажёра разница - в пять с половиной раз, а не в двенадцать: шаг в порядке Грея - шесть строк, круг внутреннего цикла - меньше трёх. Он тем важнее, чем дороже пересчёт: если вместо суммы проверяется связность графа после удаления рёбер или стоимость расписания, правка одного элемента против пересчёта с нуля - это разница в порядок.

Граница. Код Грея уменьшает работу на шаг, но шагов по-прежнему 2ⁿ. Он не помогает там, где нужны не все подмножества, а только нужного размера или только подмаски данной маски: соседние по Грею множества имеют разный размер. И правка должна быть обратимой: сумму можно уменьшить вычитанием, а вот минимум элементов множества при удалении элемента так просто не восстановить.

Что ломается без этого

Первое: обратный перевод той же формулой. g ^ (g >> 1) - не обратное преобразование: применённое к коду, оно даёт третье число - из кода 110 числа 4 получается 101. Для чисел до 3 результат случайно совпадает с номером, поэтому на маленьких примерах ошибка не видна. Обратный перевод сворачивает все сдвиги, а не один.

Второе: арифметика в коде Грея. Коды нельзя складывать и сравнивать как числа: 110 в коде Грея - это 4, а 100 - это 7. Сначала перевод в обычный номер, потом действия.

Третье: счётчик между двумя схемами. Обычный двоичный счётчик, прочитанный схемой с другой тактовой частотой в момент смены нескольких битов, даёт значение, которого счётчик никогда не принимал. Указатели очередей между такими схемами передают в коде Грея ровно по причине из начала урока.

Четвёртое: код не замкнут при числе значений не степень двойки. Десять секторов вместо восьми - и отражённый код из четырёх битов, обрезанный до десяти значений, на стыке последнего с первым меняет больше одного бита. Для таких случаев берут середину шестнадцатизначного кода: коды чисел от 3 до 12.

Зачем это в работе

Датчики угла и линейного положения - от станков до колёсика мыши - выдают код Грея. Тот же довод работает в цифровых схемах всюду, где сигнал из нескольких проводов читают в непредсказуемый момент.

Перебор с одной правкой на шаг: полный перебор подмножеств в задачах на разбиение, перебор состояний при тестировании («включи и выключи каждую комбинацию опций, переключая по одной»), обход всех углов многомерного куба по рёбрам.

Карта Карно, по которой упрощают логические формулы, нумерует строки и столбцы кодом Грея, чтобы соседние клетки отличались одной переменной. А в генетических алгоритмах числа кодируют кодом Грея, чтобы маленькое изменение числа было маленьким изменением записи: в обычном коде переход от 7 к 8 переворачивает четыре бита.

Теперь сам

1. Найди код Грея числа 13.
2. Какому числу соответствует код 1011?
3. Какой бит изменится при переходе от кода числа 11 к коду числа 12?
4. Выпиши двухбитный код и построй из него трёхбитный отражением.
5. Перебор подмножеств в порядке Грея пересчитывает не сумму, а произведение элементов. Что пойдёт не так, если среди элементов есть ноль?