Код Грея и бинарные строки

Часто порядок генерации кортежей бывает важен. Разберем здесь генерацию бинарных строк таким образом, чтобы каждая следующая строка отличалась от предыдущей ровно в однои бите. Такой способ кодирования называется кодом Грея.

Например, последовательность кодов Грея для $n = 4$

\align{ 0000, \quad 0001&, \quad 0011, \quad 0010, \quad 0110, \quad 0111, \quad 0101, \quad 0100, \\ 1100, \quad 1101&, \quad 1111, \quad 1110, \quad 1010, \quad 1011, \quad 1001, \quad 1000}

Код Грея можно задать рекурсивно.

Пусть $\Gamma_n$ — последовательность кодов Грея длины $n$ . Тогда $\Gamma_0 = \varepsilon$ и

\Gamma_{n+1} = 0 \, \Gamma_n, ~ 1 \, \Gamma_n^\R

где $a \, X$ означает новую последовательность, полученную путём присоединения $a$ перед всеми членами последовательности $X$ , и $X^\R$ означает новую последовательность, полученную путём разворачивания всех членов последовательности $X$ как строк.

Поскольку $\Gamma_{n+1}$ начинается с $0 \, \Gamma_n$ , то последовательность

\Gamma_\oo = g(0),~ g(1),~ g(2),~ g(3),~ g(4),~ \dotsc = 0,~ 1,~ 11,~ 10,~ 110,~ \dotsc

является перестановкой чисел $\NN_0$ , задающей коды Грея по их индексам.

Последовательность кодов Грея можно определить, явно указав члены последовательности $\Gamma_\oo$ , каждый член $g(j)$ — код Грея с индексом $j$ .

Пусть $j = 2^k + r$ , где $0 \le r < 2^k$ . Тогда можно воспользоваться рекуррентным соотношением и получить, что

g \bigl( 2^k + r \bigr) = 2^k + g \bigl( 2^k - r - 1 \bigr)

Отсюда можно вывести приятную формулу вычисления $g(j)$ .

Пусть двоичное представление $j = \bigl( \dotsm j_2 \, j_1 \, j_0 \bigr)_2$ , и двоичное представление $g(j) = \bigl( \dotsm g_2 \, g_1 \, g_0 \bigr)_2$ . Тогда

g_k = j_k \oplus j_{k+1} \qquad \text{для всех}~ k \ge 0

Имеет место и обратная формула

j_k = g_k \oplus g_{k+1} \oplus g_{k+2} \oplus g_{k+3} \oplus \dotsb = \bigoplus_{i=0}^\oo g_{k+i} \qquad \text{для всех}~ k \ge 0

С помощью этих двух формул можно получить способ очень легко и быстро вычислять код Грея и номер кода Грея с помощью битовой арифметики

g(j) = j \oplus \lfloor j/2 \rfloor

j = g(j) \oplus \lfloor g(j)/2 \rfloor \oplus \lfloor g(j)/4 \rfloor \oplus \dotsb = \bigoplus_{i=0}^\oo \left\lfloor \frac{g(j)}{2^i} \right\rfloor

В коде ещё проще

unsigned int to_gray_code(unsigned int n) {
    return n ^ (n >> 1);
}

unsigned int from_gray_code(unsigned int gray) {
    unsigned int n = gray;
    while (gray >>= 1) {
        n ^= gray;
    }
    return n;
}

На основе кодов Грея можно сделать генератор всех битовых строк фиксированной длины, при этом каждую итерацию изменяться будет только один бит в выдаваемой строке.

Нужно только понять, какой бит менять на $k$ -й итерации.

$\rho(k)$ — позиция младшего единичного бита в $k$

generator binary_tuples(int n) -> tuple[bool]:
    array[bool] bits = [0, 0, ..., 0]

    yield tuple(bits)

    for int i = 1; i < 2 ** n; i++:
        change_bit = (i ^ (i >> 1)) ^ ((i-1) ^ ((i-1) >> 1))
        pos = change_bit.bit_length() - 1
        bits[pos] ^= 1
        yield tuple(bits)

Функции Уолша и Радемахера

Здесь безумно часто будет необходимо получить конкретный бит числа. Поэтому я сразу введу обозначения

g(k) = \bigl( \dotsm g_3 \, g_2 \, g_1 \, g_0 \bigr)_2 \quad\text{и}\quad x = \bigl( \dotsm x_3 \, x_2 \, x_1 \, x_0 \bigr)_2

Здесь $x_j$ означает $j$ -й бит числа $x$ .

Функции Уолша — функции, введенные Джозефом Леонардом Уолшем для упрощения работы с комбинаторными объектами и их генерации.

w_0(x) = 1 \quad\text{и}\quad w_k(x) = (-1)^{x \bmod 2} \cdot w_{\lfloor k/2 \rfloor} ( \lfloor x/2 \rfloor ) \quad\text{для}~ k > 0

Функции Уолша классически определяют как раз через код Грея и бинарную свёртку.

w_k(x) = (-1) ^ {g(k) \circledast x}

Здесь $g(k) \circledast x$ — бинарная свёртка чисел $g(k)$ и $x$ :

g(x) \circledast x = \sum\limits_{j=0}^\oo g_j \cdot x_j

Функции Радемахера — функции, предложенные Гансом Радемахером

r_k(x) = (-1)^{x_k}

Связь с кодами Грея

Из этих свойств можно получить важное соотношение между функциями Уолша и функциями Радемахера

w_k(x) = \prod\limits_{j=0}^\oo r_j(x)^{g_j}

Отсюда заключаем, что кратность $r_j(x)$ в $w_k(x)$ представляет собой $j$ -й бит числа $g(k)$ . Тогда

w_{k}(x) = r_{\rho(k)+1}(x) \cdot w_{k-1}(x) \quad \text{для}~ k > 0

Ортогональность

И функции Уолша, и функции Радемахера ортогональны

\frac{1}{2^n} \sum\limits_{x=0}^{2^n-1} w_a(x) \cdot w_b(x) = [a = b] \quad\text{и}\quad \frac{1}{2^n} \sum\limits_{x=0}^{2^n-1} r_a(x) \cdot r_b(x) = [a = b]

Функции Радемахера мультипликативны

r_k^{a + b}(x) = r_k^{a \oplus b}(x)

Из мультипликативности функций Радемахера следует групповой закон для функций Уолша

w_a(x) \cdot w_b(x) = w_{a \oplus b}(x)

Вообще получается, что функции Уолша образуют абелеву группу относительно поточечного умножения. Из этого факта следует более слабое, но часто встречающееся свойство $w_n(x) = w_{2^k}(x) \cdot w_r(x)$ , где $n = 2^k + r$ и $0 \le r < 2^k$ .

А ещё, группа функций Уошла изоморфна натуральным числам с операцией побитового исключающего или

\bigl( \{ w_k : k \in \N_0 \}, \cdot \bigr) \isom (\NN_0, \oplus) \isom \ZZ_2^\oo

Циклы Грея

Код Грея $g(\cdot)$ является только одним из множества способов обхода всех бинарных строк с изменением только в одном бите за шаг.

Цикл Грея — последовательность бинарных строк $v_0, v_1, v_2, \dotsc, v_{2^n-1}$ такая, что $v_k$ отличается от $v_{(k+1) \bmod 2^n}$ только в одном бите. Получается, что цикл Грея является гамильтоновым циклом в бинарном $n$ -мерном кубе.

Поскольку цикл Грея является гамильтоновым циклом, можно выбрать индексы так, чтобы

v_0 = 000 \dotsm 00

Будем рассматривать битовые строки $v_0, v_1, \dotsc, v_{2^n-1}$ как числа, записанные в двоичной системе счисления.

Дельта-последовательность — последовательность чисел $\delta_k$ , для которых

v_{(k+1) \bmod 2^n} = v_k \oplus 2^{\delta_k}

Дельта-последовательность показывает, какие биты надо менять на каком шаге. Например, для обычного кода Грея $g(\cdot)$ дельта-последовательность определяется как $\delta_k = \rho(k+1)$ , но последнее значение $\delta_{2^n-1} = n-1$ , а не $n$ .

Расширение цикла Грея

Пусть $\alpha_1 \, j_1 \, \alpha_2 \, j_2 \dotsm \alpha_l \, j_l$ — дельта-последовательность для $n$ -битного цикла Грея, причем каждое $j_k$ является одной координатой, каждое $\alpha_k$ является последовательностью координат, возможно пустой, и $l$ нечётное. Тогда

\alpha_1 \, (n+1) \, \alpha_1^\R \, n \, \alpha_1 \,\, j_1 \,\, \alpha_2 \, n \, \alpha_2^\R \, (n+1) \alpha_2 \,\, j_2 \,\, \alpha_3 \, (n+1) \, \alpha_3^\R \, n \alpha_3 \,\, j_3 \,\, \cdots \,\, j_{l-1} \,\, \alpha_l \, (n+1) \, \alpha_l^\R \, n \, \alpha_l \,\, (n+1) \, \alpha_l^\R \, j_{l-1} \, \alpha_{l-1}^\R \, j_{l-2} \, \cdots \, \alpha_2^\R \, j_1 \alpha_1^\R \, n

Количества переходов

Количества переходов дельта-последовательности $\delta_0, \delta_1, \delta_2, \dotsc, \delta_{2^n-1}$ — кортеж $(c_0, c_1, c_2, \dotsc, c_{n-1})$ , в котором

c_j = \bigl( \text{количество раз, когда}~ \delta_k = j \bigr)

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

Можно аккуратно выбрать дельта-последовательность, чтобы в итоге получить более-менее сбалансированные количества переходов.

Наилучшее условие сбалансированности

Для любого $n$ существует цикл Грея с количествами переходов $(c_0, c_1, c_2, \dotsc, c_{n-1})$ , для которых

|c_j - c_k| \le 2 \quad\text{для}~ 0 \le j < k < n

Причём это условие сбалансированности является наилучшим.

Наилучшая сбалансированность. Каждое количество переходов $c_j$ должно быть чётным числом, и $c_0 + c_1 + c_2 + \dotsb + c_{n-2} + c_{n-1} = 2^n$ .

Условие $|c_j - c_k| \le 2$ для $0 \le j < k < n$ выполняется тогда и только тогда, когда $n-r$ количеств равны $2q$ и $r$ количеств равны $2q+2$ , где $q = \lfloor 2^{n-1} / n \rfloor$ и $r = 2^{n-1} \bmod n$ .