170
правок
Изменения
Небольшие косметические изменения и добавление псевдокода
1000
|}
== Определение == {{Определение|neat = 1|definition ='''Код Грея(Gray code)''' {{- --}} такое упорядочение <tex>k</tex>-ичных (обычно двоичных) векторов, что соседние вектора отличаются только в одном разряде. }} Код назван в честь Фрэнка Грея, который в 1947 -ом году получил патент на "отраженный отражённый двоичный код". Изначально он предназначался для избавления от паразитных состояний в электромеханических переключателях, однако сейчас область его применения гораздо шире.
== Алгоритм построения ==
Существует несколько видов Кода Грея, самый простой из них {{---}} так называемый зеркальный двоичный Код Грея, строится . Строится он так: Для получения кода длины <tex>n</tex> производится <tex>n</tex> шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй {{- --}} "1". С каждым шагом длина векторов увеличивается на 1, и а их количество {{---}} вдвое.
Таким образом, количество векторов длины <tex>n</tex> равно <tex>2^n.</tex>
* на первом шаге код отвечает условиям
* предположим, что код, получившийся код на шаге <tex>i</tex> есть Код -ом шаге, является Кодом Грея
* тогда на шаге <tex>i + 1</tex>: первая половина кода будет корректна, так как она совпадает с кодом с шага <tex>i</tex> за исключением добавленного последнего бита 0. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит 1. На стыке: первые <tex>i</tex> бит совпадают в силу зеркальности, последние различны по построению.
Таким образом, этот код {{---}} Код Грея. Индукционное предположение доказано, алгоритм работает верно.
=== Псевдокод ===
<font size=3>
buildCode(n):
GrayCode[1, n] = 0
GrayCode[2, n] = 1
p = 2
for (i = 2, i <= n, i++):
p = p * 2
for (k = i + 1, k <= 2 * i, k++):
GrayCode[k] = GrayCode[p + 1 - k]
GrayCode[k, n + 1 - i] = 1
</font>
Этот алгоритм можно обобщить и для <tex>k</tex>-ичных векторов. Также известен алгоритм преобразования двоичного кода в Код Грея.
