Монотонный код Грея

Определение:

Монотонный код Грея (англ. Monotonic Gray Code) — способ построения кода Грея, при котором $\nexists$ $g_i, g_j$, что $g_i$ содержит на $2$ или больше единиц, чем $g_j$.

Монотонный код Грея преимущественно используется в теории связанных сетей, например для минимизации ожидания линейным массивом процессоров.

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

Для начала определим такое понятие, как вес двоичного кода, им будет являтся количество $1$ в данном двоичном коде. Очевидно, что нельзя построить код Грея в котором бы вес всегда возрастал. Неплохим решением этой проблемы будет обход всех кодов со смежными с данным весами.

Мы можем формализовать модель монотонных кодов Грея рассматривая разбиение гиперкуба $Q_n = (V_n, E_n)$, вершины в котором являются двоичными кодами, на уровни с одинаковым весом вершин.

$V_n(i) = \{ v \mid V_n : v \text{ has weight } i \}$

для $0 \leqslant i \leqslant n$. Для всех уровней выполняется соотношение $|V_n(i)| = C_n^i$.

Пусть $Q_n(i)$ подграф $Q_n$, который является обединением двух смежных уровней, т. е. $V_n(i) \cup V_n(i+1)$, и пусть $E_n(i)$ множество граней $Q_n(i)$. Тогда монотонным кодом Грея будет являтся Гамильтонов путь в $Q_n$, при котором любое множество вершин $\delta_1 , \delta_2$ такие, что $\forall i, j : i \leqslant j$, то $\delta_1 \in E_n(i)$ идет перед $\delta_2 \in E_n(j)$.

Ниже на катринке Гамильтонов путь в гиперкубе $Q_4$ для $n = 4$, построенный по алгоритму Саважа-Винклера (англ. Savage-Winkler).

Элегантная идея построения $n$-ичного монотонного кода Грея состоит в том, чтобы рекурсивно строить подпути $P_{n,j}$ длинны $2 \binom{n}{j}$ включающих вершины $E_n(j)$.

Определим $P_{1,0} = (0, 1)$ и $P_{n,j} = \emptyset$, когда $j \lt 0$ или $j \geq n$ и $P_{n+1,j} = 1P^{\pi_n}_{n,j-1}, 0P_{n,j}$.

Здесь $\pi_n$ это определенная перестановка элементов множества к которому она применена, а $P^{\pi}$ это путь $P$ к котрому была применена пересатновка $\pi$. Существует два варианта построить моготонный код грея по путям $P_{n, j}$.

Назовем их $G_n^{(1)}$ и $G_n^{(2)}$. Будем строить их таким образом: $G_n^{(1)} = P_{n,0} P_{n,1}^R P_{n,2} P_{n,3}^R \ldots \text{, } G_n^{(2)} = P_{n,0}^R P_{n,1} P_{n,2}^R P_{n,3} \ldots$

Выбор перестановки $\pi_n$ обусловлен тем, чтобы получившиеся коды соответсвовали требованиям кода Грея и поэтому эта перестановка равна $\pi_n = E^{-1}(\pi_{n-1}^2)$.

Чтобы лучше разобратся в том, как сторится этот код и работает перестановка $\pi$ следует рассмотреть таблицу ниже.

Подпути алгоритма Саважа-Винклера

$P_{n,j}$	$j = 0$	$j = 1$	$j = 2$	$j = 3$
$n = 1$	$0, 1$
$n = 2$	$00, 01$	$10, 11$
$n = 3$	$000, 001$	$100, 110, 010, 011$	$101, 111$
$n = 4$	$0000, 0001$	$1000, 1100, 0100, 0110, 0010, 0011$	$1010, 1011, 1001, 1101, 0101, 0111$	$1110, 1111$

Монотонный код Грея может быть эффективно сгенерирован по этому алгоритму за время $O(n)$. Легче всего написать этот алгоритм используя сопрограмму.

Псевдокод

rotateRight(x, n): // Вспомогательная функция для генерации перестановки, циклически сдвигает битовый вектор направо [math]n[/math] раз. Принимает и возвращает котреж (англ. tuple). return x[-n:] + x[:-n] pi(n): // Рекурсивная генерация [math]n[/math]-ой перестановки. Возвращает перестановку в виде кортежа. Если n становится меньше [math]2[/math] дописывает в начало кортежа [math]0[/math] и возвращает его. if n <= 1: return (0,) x = pi(n - 1) + (n - 1,) return rotate_right(tuple(x[k] for k in x), 1) p(n, j, reverse = false): // Рекурсивная генерация пути [math]P_{n, j}[/math]. Принимает [math]n, j[/math], а так же дополнительный параметр определяющий надо-ли переворачивать кортеж. if n == 1 and j == 0: if not reverse: yield (0,) yield (1,) else: yield (1,) yield (0,) elif j >= 0 and j < n: perm = pi(n - 1) if not reverse: for x in p(n - 1, j - 1): yield (1,) + tuple(x[k] for k in perm) for x in p(n - 1, j): yield (0,) + x else: for x in p(n - 1, j, reverse=True): yield (0,) + x for x in p(n - 1, j - 1, reverse=True): yield (1,) + tuple(x[k] for k in perm) monotonic(n): // Генерация монотонного кода Грея при помощи уже написанной сопрограммы p. for i in range(n): for x in (p(n, i) if i % 2 == 0 else p(n, i, reverse=True)): yield x

Визуализация работы алгоритма

Для $n = 5$

Для $n = 6$

См. Также

• Коды Грея

• Коды антигрея

Источники информации

• Wikipedia — Gray code

• Википедия — Код Грея

• Robert W. Doran The Gray Code, Journal of Universal Computer Science, vol. 13, no. 11 (2007).

• Alternative Combinatorial Gray Codes