Монотонный код Грея — различия между версиями

Версия 01:03, 6 декабря 2016

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

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

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

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

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

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

для [math]0 \leq i \leq n[/math]. Для всех уровней выполняется соотношение [math]|V_n(i)| = \binom{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 \in E_n(i)[/math] идет перед [math]\delta_2 \in E_n(j)[/math], то [math]i \leq j[/math].

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

Элегантная идея построения [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]\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]\pi_n[/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]1110, 1111[/math]

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

Псевдокод

rotate_right(x, n):


   return x[-n:] + x[:-n]

pi(n):

   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):

   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):

   for i in range(n):
       for x in (p(n, i) if i % 2 == 0 else p(n, i, reverse=True)):
           yield x