Код Грея (Gray code) - код в котором при переходе к следующему числу меняется только один бит. Frank Gray. физик Bell Telephony Labs в 1930х Необходимость кода Грея: пример шаговые электродвигатели - отслеживание позиции. (если будет менятся более чем 1 бит - получим краевые эффекты). или логические автоматы со сложными состояниями. Gray code(N) = N xor (N/2) Пример для 3х бит: N N/2 GRAY 000 000 000 001 000 001 010 001 0011 011 001 010 100 010 110 101 010 111 110 011 101 111 011 100 Пример диска на 4-бит (бинарный код):
Пример диска на 4-бит (код Грея):
Конвертор бинарного кода в код Грея:
Конвертор кода Грея в бинарный код:
Пример отображения Кода Грея как функции от бинарного числа:
Код Грея симметричен Построение кода Грея - симметрия: ===== 0 1 ===== отражаем ===== 0 1 --- 1 0 ===== добавляем следущий разряд: ====== 00 01 -- 11 10 ====== отражаем: ====== 00 01 11 10 -- 10 11 01 00 ====== добавляем следующий разряд: ======= 000 001 011 010 --- 110 111 101 100 =======
Gray(n,k) n - основание СЧ k - число цифр в коде Только с четным n - имеет циклическую структуру как в двоичном случае. К сожалению для нечентых N - отражением не построить ===== 0 1 2 ===== ===== 2 1 0 --- 0 1 2 --- 2 1 0 ===== Но вообще возможен симметричный код с переходом у нуля: G(3,2) ====== 00 01 02 12 11 10 20 21 22 ====== WRAP G(3,3) ======= 000 001 002 012 011 010 020 021 022 122 121 120 110 111 112 102 101 100 200 201 202 212 211 210 220 221 222 ======= WRAP или код сохраняющий изменения на 1 между соседними значениями, но не симметричный: ====== 00 10 11 21 20 22 12 02 01 ====== для четных n проблем нет: ===== 0 1 2 3 ===== ===== 0 1 2 3 --- 3 2 1 0 --- 0 1 2 3 --- 3 2 1 0 ===== G(4,2) ====== 00 01 02 03 -- 13 12 11 10 -- 20 21 22 23 -- 33 32 31 30 ====== G(4,3) (0 0 0) (0 0 1) (0 0 2) (0 0 3) (0 1 3) (0 1 2) (0 1 1) (0 1 0) (0 2 0) (0 2 1) (0 2 2) (0 2 3) (0 3 3) (0 3 2) (0 3 1) (0 3 0) (1 3 0) (1 3 1) (1 3 2) (1 3 3) (1 2 3) (1 2 2) (1 2 1) (1 2 0) (1 1 0) (1 1 1) (1 1 2) (1 1 3) (1 0 3) (1 0 2) (1 0 1) (1 0 0) (2 0 0) (2 0 1) (2 0 2) (2 0 3) (2 1 3) (2 1 2) (2 1 1) (2 1 0) (2 2 0) (2 2 1) (2 2 2) (2 2 3) (2 3 3) (2 3 2) (2 3 1) (2 3 0) (3 3 0) (3 3 1) (3 3 2) (3 3 3) (3 2 3) (3 2 2) (3 2 1) (3 2 0) (3 1 0) (3 1 1) (3 1 2) (3 1 3) (3 0 3) (3 0 2) (3 0 1) (3 0 0)
Есть вариант построения кодировки для десятичных (типа как BCD, но обладающий свойствами кода Грея. Decimal Gray code in one of variants: -------------------- Decimal Gray Digit Code -------------------- 0 0000 1 0001 2 0011 3 0010 4 0110 5 1110 6 1010 7 1011 8 1001 9 1000 --------------------
В принципе код Грея - это непересекающая закольцованная линия проходящая через все клетки карты Карно.