| Определение: |
| Монотонный код Грея (англ. Monotonic Gray Code) — способ построения кода Грея, при котором [math]\nexists[/math] [math]g_i, g_j[/math], что [math]g_i[/math] содержит на [math]2[/math] или больше единиц, чем [math]g_j[/math]. |
Монотонный код Грея преимущественно используется в теории связанных сетей, например для минимизации ожидания линейным массивом процессоров.[1]
Алгоритм построения
Для начала определим такое понятие, как вес двоичного кода, им будет являтся количество [math]1[/math] в данном двоичном коде. Очевидно, что нельзя построить код Грея в котором бы вес всегда возрастал.
Неплохим решением этой проблемы будет обход всех кодов со смежными с данным весами.
Мы можем формализовать модель монотонных кодов Грея рассматривая разбиение гиперкуба [math]Q_n = (V_n, E_n)[/math], вершины в котором являются двоичными кодами, на уровни с одинаковым весом вершин.
[math]
V_n(i) = \{ v \mid V_n : v \text{ has weight } i \}
[/math]
для [math]0 \leqslant i \leqslant n[/math]. Для всех уровней выполняется соотношение [math]|V_n(i)| = C_n^i[/math].
Пусть [math]Q_n(i)[/math] подграф [math]Q_n[/math], который является обединением двух смежных уровней, т. е. [math]V_n(i) \cup V_n(i+1)[/math], и пусть [math]E_n(i)[/math] множество граней [math]Q_n(i)[/math].
Тогда монотонным кодом Грея будет являтся Гамильтонов путь в [math]Q_n[/math], при котором любое множество вершин [math]\delta_1 , \delta_2[/math] такие, что [math]\forall i, j : i \leqslant j[/math], то [math]\delta_1 \in E_n(i)[/math] идет перед [math]\delta_2 \in E_n(j)[/math].
Ниже на катринке Гамильтонов путь в гиперкубе [math]Q_4[/math] для [math]n = 4[/math], построенный по алгоритму Саважа-Винклера (англ. Savage-Winkler).[2]
Элегантная идея построения [math]n[/math]-ичного монотонного кода Грея состоит в том, чтобы рекурсивно строить подпути [math]P_{n,j}[/math] длинны [math]2 \binom{n}{j}[/math] включающих вершины [math]E_n(j)[/math].
Определим [math]P_{1,0} = (0, 1)[/math] и [math]P_{n,j} = \emptyset[/math], когда [math]j \lt 0[/math] или [math]j \geq n[/math] и
[math]
P_{n+1,j} = 1P^{\pi_n}_{n,j-1}, 0P_{n,j}
[/math].
Здесь [math]\pi_n[/math] это определенная перестановка элементов множества к которому она применена, а [math]P^{\pi}[/math] это путь [math]P[/math] к котрому была применена пересатновка [math]\pi[/math].
Существует два варианта построить моготонный код грея по путям [math]P_{n, j}[/math].
Назовем их [math]G_n^{(1)}[/math] и [math]G_n^{(2)}[/math]. Будем строить их таким образом:
[math]
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
[/math]
Выбор перестановки [math]\pi_n[/math] обусловлен тем, чтобы получившиеся коды соответсвовали требованиям кода Грея и поэтому эта перестановка равна [math]\pi_n = E^{-1}(\pi_{n-1}^2)[/math].
Чтобы лучше разобратся в том, как сторится этот код и работает перестановка [math]\pi[/math] следует рассмотреть таблицу ниже.
Подпути алгоритма Саважа-Винклера
| [math]P_{n,j}[/math]
|
[math]j = 0[/math]
|
[math]j = 1[/math]
|
[math]j = 2[/math]
|
[math]j = 3[/math]
|
| [math]n = 1[/math]
|
[math]0, 1[/math] |
|
|
|
| [math]n = 2[/math]
|
[math]00, 01[/math] |
[math]10, 11[/math] |
|
|
| [math]n = 3[/math]
|
[math]000, 001[/math] |
[math]100, 110, 010, 011[/math] |
[math]101, 111[/math] |
|
| [math]n = 4[/math]
|
[math]0000, 0001[/math] |
[math]1000, 1100, 0100, 0110, 0010, 0011[/math] |
[math]1010, 1011, 1001, 1101, 0101, 0111[/math] |
[math]1110, 1111[/math]
|
Монотонный код Грея может быть эффективно сгенерирован по этому алгоритму за время [math]O(n)[/math]. Легче всего написать этот алгоритм используя сопрограмму.
Псевдокод
|
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
|
Визуализация работы алгоритма
Для [math]n = 5[/math]
Для [math]n = 6[/math]
См. Также
Примечания
Источники информации
