170
правок
Изменения
Исправление недочётов
Существует несколько видов Кода Грея, самый простой из них {{---}} так называемый зеркальный двоичный Код Грея. Строится он так:
Для получения кода длины <tex>n</tex> производится <tex>n</tex> шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй {{---}} "1". С каждым шагом длина векторов увеличивается на 1, а их количество {{---}} вдвое.
Таким образом, количество векторов длины <tex>n</tex> равно <tex>2^n.</tex>
{| border="0"
|align="left" colspan="4"|
GrayCode {{---}} двухмерный массив, в котором GrayCode[a, b] {{---}} <tex>b</tex>-ый бит в <tex>a</tex>-ом коде Грея.
<font size=3>
buildCode(n):
GrayCode[1, n] = 0
GrayCode[2, n] = 1{построение кода длины 1} p = 2{p {{---}} количество уже имеющихся кодов}
for (i = 2, i <= n, i++):
for (k = i + 1, k <= 2 * i, k++):
GrayCode[k] = GrayCode[p + 1 - k]{отражение имеющихся кодов} GrayCode[k - i, n + 1 - i] = 0 GrayCode[k, n + 1 - i] = 1{добавление 0 и 1 в начало}
</font>
|}
|id = th1.
|statement =
В двоичном зеркальном коде Грея <tex>i</tex>-ый код может быть получен по формуле <tex>G_i = i \oplus (\lfloor i / 2 \div 2rfloor)</tex> при нумерации кодов с нуля.
|proof =
Для кода длиной 1 бит утверждение очевиднопроверяется непосредственно. Пусть существует зеркальный двоичный код Грея <tex>M</tex> длины <tex>n</tex>, для которого выполнено , что для любого <tex>\forall i \enskip M_i = i \oplus (\lfloor i / 2 \div 2rfloor)</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}) =</tex><tex> 0x_{n-1}x_{n-2}...x_{0} \oplus 00x_{n-1}x_{n-2}...x_{1} = x \oplus (\lfloor x / 2 \div 2rfloor)</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}) =</tex>
<tex>= 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}</tex>
<tex> \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} =</tex>
<tex> x \oplus (\lfloor x / 2 \div 2rfloor)</tex>
Таким образом, по теореме о математической шаг индукции требуемое доказанодоказан, следовательно, теорема верна.
}}
Код Грея применяется в:
* датчиках-энкодерах ( устройства, преобразующие угол поворота вала в электрический сигнал );* как способ решения задачи о Ханойских башнях ( дано три стержня, на первом из них нанизано 8 колец разного размера в виде пирамиды; цель {{---}} перенести пирамиду на другой стержень, сохранив упорядоченность );* в генетических алгоритмах;* в Картах Карно ( при передаче в карту переменные сортируются в Код Грея );* в кодах, исправляющих ошибки;
* для связи систем с различной частотой работы.
