162
правки
Изменения
Новая страница: «{{Определение |definition = '''Монотонный код Грея''' (англ. ''Monotonic Gray Code'') {{---}} способ построения ...»
{{Определение
|definition =
'''Монотонный код Грея''' (англ. ''Monotonic Gray Code'') {{---}} способ построения кода Грея, что <tex>\nexists</tex> <tex>g_i, g_j</tex>, что <tex>g_i</tex> содержит на 2 или больше единиц, чем <tex>g_j</tex>.
}}
Монотонный код Грея приемущественно используется в теории взамиосвязанных сетей, например для минимизации ожидания линейным массивом процессоров.
== Алгоритм построения ==
Для начала определим такое понятие, как ''вес'' двоичного кода, им будет являтся количество <tex>1</tex> в данном двоичном коде. Очевидно, что нельзя построить код Грея в котором бы вес всегда возрастал.
Неплохим решением этой проблемы будет обход всех кодов со смежными с данным весами.
Мы можем формализовать модель монотонных кодов Грея рассматривая разбиение гиперкуба <tex>Q_n = (V_n, E_n)</tex>, вершины в котором являются двоичными кодами, на уровни с одинаковым весом вершин.
<tex>
V_n(i) = \{ v \in V_n : v \text{ has weight } i \}
</tex>
для <tex>0 \leq i \leq n</tex>. Для всех уровней выполняется соотношение <tex>|V_n(i)| = \binom{n}{i}</tex>.
Пусть <tex>Q_n(i)</tex> подграф <tex>Q_n</tex>, который является обединением двух смежных уровней, т. е. <tex>V_n(i) \cup V_n(i+1)</tex>, и пусть <tex>E_n(i)</tex> множество граней <tex>Q_n(i)</tex>.
Тогда монотонным кодом Грея будет являтся Гамильтонов путь в <tex>Q_n</tex>, при котором любой <tex>\delta_1 \in E_n(i)</tex> идет перед <tex>\delta_2 \in E_n(j)</tex>, то <tex>i \leq j</tex>.
Ниже на катринке Гамильтонов путь в гиперкубе <tex>Q_4</tex> для <tex>n = 4</tex>, построенный по алгоритму Саважа-Винклера(англ. ''Savage-Winkler'').
[[Файл:Monotonic_Gray_Code_Graph.png|center|4-ичный монотооный код Грея]]
Элегантная идея построения <tex>n</tex>-ичного монотонного кода Грея состоит в том, чтобы рекурсивно строить подпути <tex>P_{n,j}</tex> длинны <tex>2 \binom{n}{j}</tex> включающих вершины <tex>E_n(j)</tex>.
Определим <tex>P_{1,0} = (0, 1)</tex> и <tex>P_{n,j} = \emptyset</tex>, когда <tex>j < 0</tex> или <tex>j \geq n</tex> и
<tex>
P_{n+1,j} = 1P^{\pi_n}_{n,j-1}, 0P_{n,j}
</tex>.
Здесь <tex>\pi_n</tex> это определенная перестановка элементов множества к которому она применена, а <tex>P^{\pi}</tex> это путь <tex>P</tex> к котрому была применена пересатновка <tex>\pi</tex>.
Существует два варианта построить моготонный код грея по путям <tex>P_{n, j}</tex>.
Назовем их <tex>G_n^{(1)}</tex> и <tex>G_n^{(2)}</tex>. Будем строить их таким образом:
<tex>
G_n^{(1)} = P_{n,0} P_{n,1}^R P_{n,2} P_{n,3}^R \cdots \text{, } G_n^{(2)} = P_{n,0}^R P_{n,1} P_{n,2}^R P_{n,3} \cdots
</tex>
Выбор перестановки <tex>\pi_n</tex> обусловлен тем, чтобы получившиеся коды соответсвовали требованиям кода Грея и поэтому эта перестановка равна <tex>\pi_n = E^{-1}(\pi_{n-1}^2)</tex>.
Чтобы лучше разобратся в том, как сторится этот код и работает перестановка <tex>\pi</tex> следует рассмотреть таблицу ниже.
<center>
{|class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
|+ Подпути алгоритма Саважа-Винклера
|-
! scope="col" style="width:3em;"| <math>P_{n,j}</math>
! scope="col" | <tex>j = 0</tex>
! scope="col" | <tex>j = 1</tex>
! scope="col" | <tex>j = 2</tex>
! scope="col" | <tex>j = 3</tex>
|-
! scope="row" | <tex>n = 1</tex>
| <tex>0, 1</tex> || || ||
|-
! scope="row" | <tex>n = 2</tex>
| <tex>00, 01</tex> || <tex>10, 11</tex> || ||
|-
! scope="row" | <tex>n = 3</tex>
| <tex>000, 001</tex> || <tex>100, 110, 010, 011</tex> || <tex>101, 111</tex> ||
|-
! scope="row" | <tex>n = 4</tex>
| <tex>0000, 0001</tex> || <tex>1000, 1100, 0100, 0110, 0010, 0011</tex> || <tex>1010, 1011, 1001, 1101, 0101, 0111</tex> || <tex>1110, 1111</tex>
|}
</center>
Монотонный код Грея может быть эффективно сгенерирован по этому алгоритму за время <tex>O(n)</tex>. Легче всего написать этот алгоритм используя сопрограмму, пример которой будет предложен ниже.
=== Псевдокод ===
{| border="0"
|align="left" colspan="4"|
<code>
<font color = brown>rotate_right</font>(x, n):
'''return''' x[-n:] + x[:-n]
<font color = brown>pi</font>(n):
'''if''' n <= 1:
'''return''' (0,)
x = pi(n - 1) + (n - 1,)
'''return''' rotate_right('''tuple'''(x[k] '''for''' k '''in''' x), 1)
<font color = brown>p</font>(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)
<font color = brown>monotonic</font>(n):
'''for''' i '''in''' range(n):
'''for''' x '''in''' (p(n, i) '''if''' i % 2 == 0 '''else''' p(n, i, reverse=True)):
'''yield''' x
</code>
|}
==Визуализация работы алгоритма==
Для <tex>n = 5</tex>
[[Файл:Monotonic_Gray_Code_Ex1.png|center|Визуализация работы алгоритма для 5-ичного кода]]
Для <tex>n = 6</tex>
[[Файл:Monotonic_Gray_Code_Ex2.png|center|Визуализация работы алгоритма для 6-ичного кода]]
==См. Также==
*[[:Коды_Грея|Коды Грея]]
*[[:Коды_антигрея|Коды антигрея]]
==Примечания==
<references />
== Источники информации ==
* [http://en.wikipedia.org/wiki/Gray_code Wikipedia {{---}} Gray code]
* [http://ru.wikipedia.org/wiki/код_Грея Википедия {{---}} Код Грея]
* [http://www.jucs.org/jucs_13_11/the_gray_code/jucs_13_11_1573_1597_doran.pdf Robert W. Doran The Gray Code, Journal of Universal Computer Science, vol. 13, no. 11 (2007).]
*[http://sciyoshi.com/2010/12/gray-codes Alternative Combinatorial Gray Codes]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
|definition =
'''Монотонный код Грея''' (англ. ''Monotonic Gray Code'') {{---}} способ построения кода Грея, что <tex>\nexists</tex> <tex>g_i, g_j</tex>, что <tex>g_i</tex> содержит на 2 или больше единиц, чем <tex>g_j</tex>.
}}
Монотонный код Грея приемущественно используется в теории взамиосвязанных сетей, например для минимизации ожидания линейным массивом процессоров.
== Алгоритм построения ==
Для начала определим такое понятие, как ''вес'' двоичного кода, им будет являтся количество <tex>1</tex> в данном двоичном коде. Очевидно, что нельзя построить код Грея в котором бы вес всегда возрастал.
Неплохим решением этой проблемы будет обход всех кодов со смежными с данным весами.
Мы можем формализовать модель монотонных кодов Грея рассматривая разбиение гиперкуба <tex>Q_n = (V_n, E_n)</tex>, вершины в котором являются двоичными кодами, на уровни с одинаковым весом вершин.
<tex>
V_n(i) = \{ v \in V_n : v \text{ has weight } i \}
</tex>
для <tex>0 \leq i \leq n</tex>. Для всех уровней выполняется соотношение <tex>|V_n(i)| = \binom{n}{i}</tex>.
Пусть <tex>Q_n(i)</tex> подграф <tex>Q_n</tex>, который является обединением двух смежных уровней, т. е. <tex>V_n(i) \cup V_n(i+1)</tex>, и пусть <tex>E_n(i)</tex> множество граней <tex>Q_n(i)</tex>.
Тогда монотонным кодом Грея будет являтся Гамильтонов путь в <tex>Q_n</tex>, при котором любой <tex>\delta_1 \in E_n(i)</tex> идет перед <tex>\delta_2 \in E_n(j)</tex>, то <tex>i \leq j</tex>.
Ниже на катринке Гамильтонов путь в гиперкубе <tex>Q_4</tex> для <tex>n = 4</tex>, построенный по алгоритму Саважа-Винклера(англ. ''Savage-Winkler'').
[[Файл:Monotonic_Gray_Code_Graph.png|center|4-ичный монотооный код Грея]]
Элегантная идея построения <tex>n</tex>-ичного монотонного кода Грея состоит в том, чтобы рекурсивно строить подпути <tex>P_{n,j}</tex> длинны <tex>2 \binom{n}{j}</tex> включающих вершины <tex>E_n(j)</tex>.
Определим <tex>P_{1,0} = (0, 1)</tex> и <tex>P_{n,j} = \emptyset</tex>, когда <tex>j < 0</tex> или <tex>j \geq n</tex> и
<tex>
P_{n+1,j} = 1P^{\pi_n}_{n,j-1}, 0P_{n,j}
</tex>.
Здесь <tex>\pi_n</tex> это определенная перестановка элементов множества к которому она применена, а <tex>P^{\pi}</tex> это путь <tex>P</tex> к котрому была применена пересатновка <tex>\pi</tex>.
Существует два варианта построить моготонный код грея по путям <tex>P_{n, j}</tex>.
Назовем их <tex>G_n^{(1)}</tex> и <tex>G_n^{(2)}</tex>. Будем строить их таким образом:
<tex>
G_n^{(1)} = P_{n,0} P_{n,1}^R P_{n,2} P_{n,3}^R \cdots \text{, } G_n^{(2)} = P_{n,0}^R P_{n,1} P_{n,2}^R P_{n,3} \cdots
</tex>
Выбор перестановки <tex>\pi_n</tex> обусловлен тем, чтобы получившиеся коды соответсвовали требованиям кода Грея и поэтому эта перестановка равна <tex>\pi_n = E^{-1}(\pi_{n-1}^2)</tex>.
Чтобы лучше разобратся в том, как сторится этот код и работает перестановка <tex>\pi</tex> следует рассмотреть таблицу ниже.
<center>
{|class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
|+ Подпути алгоритма Саважа-Винклера
|-
! scope="col" style="width:3em;"| <math>P_{n,j}</math>
! scope="col" | <tex>j = 0</tex>
! scope="col" | <tex>j = 1</tex>
! scope="col" | <tex>j = 2</tex>
! scope="col" | <tex>j = 3</tex>
|-
! scope="row" | <tex>n = 1</tex>
| <tex>0, 1</tex> || || ||
|-
! scope="row" | <tex>n = 2</tex>
| <tex>00, 01</tex> || <tex>10, 11</tex> || ||
|-
! scope="row" | <tex>n = 3</tex>
| <tex>000, 001</tex> || <tex>100, 110, 010, 011</tex> || <tex>101, 111</tex> ||
|-
! scope="row" | <tex>n = 4</tex>
| <tex>0000, 0001</tex> || <tex>1000, 1100, 0100, 0110, 0010, 0011</tex> || <tex>1010, 1011, 1001, 1101, 0101, 0111</tex> || <tex>1110, 1111</tex>
|}
</center>
Монотонный код Грея может быть эффективно сгенерирован по этому алгоритму за время <tex>O(n)</tex>. Легче всего написать этот алгоритм используя сопрограмму, пример которой будет предложен ниже.
=== Псевдокод ===
{| border="0"
|align="left" colspan="4"|
<code>
<font color = brown>rotate_right</font>(x, n):
'''return''' x[-n:] + x[:-n]
<font color = brown>pi</font>(n):
'''if''' n <= 1:
'''return''' (0,)
x = pi(n - 1) + (n - 1,)
'''return''' rotate_right('''tuple'''(x[k] '''for''' k '''in''' x), 1)
<font color = brown>p</font>(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)
<font color = brown>monotonic</font>(n):
'''for''' i '''in''' range(n):
'''for''' x '''in''' (p(n, i) '''if''' i % 2 == 0 '''else''' p(n, i, reverse=True)):
'''yield''' x
</code>
|}
==Визуализация работы алгоритма==
Для <tex>n = 5</tex>
[[Файл:Monotonic_Gray_Code_Ex1.png|center|Визуализация работы алгоритма для 5-ичного кода]]
Для <tex>n = 6</tex>
[[Файл:Monotonic_Gray_Code_Ex2.png|center|Визуализация работы алгоритма для 6-ичного кода]]
==См. Также==
*[[:Коды_Грея|Коды Грея]]
*[[:Коды_антигрея|Коды антигрея]]
==Примечания==
<references />
== Источники информации ==
* [http://en.wikipedia.org/wiki/Gray_code Wikipedia {{---}} Gray code]
* [http://ru.wikipedia.org/wiki/код_Грея Википедия {{---}} Код Грея]
* [http://www.jucs.org/jucs_13_11/the_gray_code/jucs_13_11_1573_1597_doran.pdf Robert W. Doran The Gray Code, Journal of Universal Computer Science, vol. 13, no. 11 (2007).]
*[http://sciyoshi.com/2010/12/gray-codes Alternative Combinatorial Gray Codes]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
