170
правок
Изменения
Явная формула и немного косметики
{{Определение
|id = def1.
|neat = 1
|definition =
Для получения кода длины <tex>n</tex> производится <tex>n</tex> шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй {{---}} "1". С каждым шагом длина векторов увеличивается на 1, а их количество {{---}} вдвое.
Таким образом, количество векторов длины <tex>n</tex> равно <tex>2^n.</tex>
=== Псевдокод ===
GrayCode[k, n + 1 - i] = 1
</font>
=== Доказательство правильности работы алгоритма ===
По индукции:
* на первом шаге код отвечает условиям
* предположим, что код, получившийся на <tex>i</tex>-ом шаге, является Кодом Грея
* тогда на шаге <tex>i + 1</tex>: первая половина кода будет корректна, так как она совпадает с кодом с шага <tex>i</tex> за исключением добавленного последнего бита 0. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит 1. На стыке: первые <tex>i</tex> бит совпадают в силу зеркальности, последние различны по построению.
Таким образом, этот код {{---}} Код Грея. Индукционное предположение доказано, алгоритм работает верно.
Этот алгоритм можно обобщить и для <tex>k</tex>-ичных векторов. Также известен алгоритм преобразования двоичного кода в Код Грея.
Существует ещё несколько видов Кода Грея {{---}} сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея.
== Явная формула для получения зеркального двоичного кода Грея ==
{{Теорема
|id = th1.
|statement =
В двоичном зеркальном коде Грея <tex>i</tex>-ый код может быть получен по формуле <tex>G_i = i \oplus (i \div 2)</tex> при нумерации кодов с нуля.
|proof =
Для кода длиной 1 бит утверждение очевидно.
Пусть существует зеркальный двоичный код Грея <tex>M</tex> длины <tex>n</tex>, для которого выполнено <tex>\forall i \enskip M_i = i \oplus (i \div 2)</tex>
Обозначим за <tex>L</tex> код длины <tex>n + 1</tex>, полученный из <tex>M</tex> описанным выше алгоритмом. Тогда:
<tex>\forall x < 2^n \enskip L_x = 0M_x = 0(x_{n-1}x_{n-2}...x_{0} \oplus 0x_{n-1}x_{n-2}...x_{1}) = 0x_{n-1}x_{n-2}...x_{0} \oplus 00x_{n-1}x_{n-2}...x_{1} = x \oplus (x \div 2)</tex>
<tex>\forall x \geq 2^n \enskip L_x = 1M_y</tex>, где <tex>y = 2^{n+1} - 1 - x = \neg x</tex>, то есть <tex>L_x = 1(\neg x_{n-1} \neg x_{n-2}... \neg x_{0} \oplus 0 \neg x_{n-1} \neg x_{n-2}... \neg x_{1}) = 1(\neg x_{n-1}x_{n-2}...x_{0} \oplus 0x_{n-1}x_{n-2}...x_{1}) = 1(x_{n-1}x_{n-2}...x_{0} \oplus 1x_{n-1}x_{n-2}...x_{1}) = 1x_{n-1}x_{n-2}...x_{0} \oplus 01x_{n-1}x_{n-2}...x_{1} = x_{n}x_{n-1}x_{n-2}...x_{0} \oplus 0x_{n}x_{n-1}x_{n-2}...x_{1} = x \oplus (x \div 2)</tex>
Таким образом, по теореме о математической индукции требуемое доказано.
}}
== Применение ==
