Коды Грея
2-битный код Грея
00 01 11 10 |
3-битный код Грея
000 001 011 010 110 111 101 100 |
4-битный код Грея
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 |
Код Грея - такое упорядочение k-ичных (обычно двоичных) векторов, что соседние вектора отличаются только в одном разряде. Код назван в честь Фрэнка Грея, который в 1947 году получил патент на "отраженный двоичный код". Изначально он предназначался для избавления от паразитных состояний в электромеханических переключателях, однако сейчас область его применения гораздо шире.
Алгоритм построения
Существует несколько видов Кода Грея, самый простой из них - так называемый зеркальный двоичный Код Грея, строится он так: Для получения кода длины n производится n шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй - "1". С каждым шагом длина векторов увеличивается на 1, и их количество вдвое. Таким образом количество векторов длины n равно
Доказательство правильности работы алгоритма
По индукции:
- на первом шаге код отвечает условиям
- предположим, что получившийся код на шаге i есть Код Грея
- тогда на шаге i+1: первая половина кода будет корректна, так как она совпадает с кодом с шага i за исключением добавленного последнего бита 0. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит 1. На стыке: первые i бит совпадают в силу зеркальности, последние различны по построению.
Таким образом этот код - Код Грея. Индукционное предположение доказано, алгоритм работает верно.
Этот алгоритм можно обобщить и для k-ичных векторов. Также известен алгоритм преобразования двоичного кода в Код Грея.
Существует ещё несколько видов Кода Грея - сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея.
Применение
Код Грея применяется в:
- датчиках-энкодерах ( устройства, преобразующие угол поворота вала в электрический сигнал );
- как способ решения задачи о Ханойских башнях ( дано три стержня, на первом из них нанизано 8 колец разного размера в виде пирамиды; цель - перенести
пирамиду на другой стержень, сохранив упорядоченность );
- в генетических алгоритмах;
- в Картах Карно ( при передаче в карту переменные сортируются в Код Грея );
- в кодах, исправляющих ошибки;
- для связи систем с различной частотой работы.
