Вы уже встречались с этой формулой в разделе 5.2. Как упоминалось в этом разделе, вычисления по данной формуле можно выполнять так, как показано ниже (для л=32).

в = G * (G >> 1) В = В * (В » 2) В = В * (В » 4) В = В * (В » 8) В = В * (В >> 16) ;

Таким образом, в общем случае требуется выполнение 2 flog, п \ команд.

Поскольку преобразование двоичных чисел в код Грея выполняется очень просто, генерация последовательных чисел кода Грея представляет собой тривиальную задачу:

for (i =0; i < П; i++) { G = i * (i >> 1) ; output G;

13.2. Увеличение чисел кода Грея

Логика увеличения 4-битового двоичного числа abed может быть выражена следующим образом, с использованием обозначений булевой алгебры:

d = d c=c®d b = b®cd а = а® bed

Таким образом, один способ построения аппаратного счетчика кода Грея состоит в создании бинарного счетчика с использованием описанной логики и преобразовании его вывода а, Ь, с и d й код Грея при помощи операции исключающего или над соседними битами, как показано в схеме на рис. 13.1.

Приведем еще один способ, который может оказаться несколько эффективнее:

p=e®f®g®h h = h®p g = g®hp f = f®ghp e=e®fghp

Таким образом, в общем случае

g:=G.®(g„.,G„.,...G„p), п>2.

Поскольку четность р чередуется между О и 1, схема счетчика может поддерживать р как отдельный однобитовый регистр и просто инвертировать его при каждой итерации.

Программно наилучший способ поиска последующего элемента G для целого числа G в коде Грея, вероятно, состоит в конвертации О в двоичное число, его увеличении и обратном преобразовании в код Грея. Еще один интересный и почти такой же по эффективности путь - это определение того, какой бит должен быть изменен в числе О. Вот как выглядит последовательность этих битов, представленная в виде слов, которые при помощи операции исключающего или с числом О дают очередное число кода:

121412181214121 16

13.2. УВЕЛИЧЕНИЕ ЧИСЕЛ КОДА ГРЕЯ 229

Внимательный читатель распознает в этой последовательности маску, указывающую положение 1файнего слева бита, который изменяется при увеличении целого числа О, 1,2, 3, соответствующего позиции в приведенной последовательности. Таким образом, при увеличении числа G из кода Грея позиция инвертируемого бита определяется самым левым битом, который изменяется при прибавлении 1 к двоичному числу, соответствующему G.

Рассмотренные способы приводят нас к алгоритмам увеличения чисел кода Грея, показанным в листинге 13.1 (оба они сначала преобразуют число G в двоичное, что обозначено как index (G)).

Листинг 13.1. Увеличение числа кода Грея

в = index(G); В = index(G);

В = В + 1; М = -В Ь (В + 1) ,•

Gp = В * (В >> 1) ; Gp = G * М;

Метод увеличения чисел кода Грея "с карандашом в руке" выглядит следующим образом.

Начиная справа, найти первый бит, для которого четность данного бита и всех битов слева положиггельна. Инвертировать бит в данной позиции.

Можно воспользоваться другим, эквивалентным, правилом.

Пусть р - четность слова G. Если р четно, инвертировать младший бит. Если же р нечетно, инвертировать бит слева от крайнего единичного бита справа.

Последнее правило непосредственно выражено приведенными выше булевыми выражениями.

13.3. Отрицательно-двоичный код Грея

Если вы запишете целые числа в системе счисления по основанию -2 и преобразуете их с помощью сдвига и исключающего или так же, как обычное двоичное число преобразуется в число кода Грея, то полученные числа также дадут код Грея. Трехбитовый код Грея имеет индексы в диапазоне трехбитовых чисел в системе счисления по основанию -2, а именно от -2 до 5; четырехбитовый - от -10 до 5. Полученный таким образом код Грея не является отраженным, но очень близок к нему. Такой четырехбитовый код Грея можно построить, начиная с О и 1, отражая их относительно верха списка, затем относительно низа списка и т.д., чередуя отражения.

Для преобразования чисел такого кода Грея назад в систему счисления по основанию -2 правила, разумеется, те же, что и для преобразования обычного кода Грея в двоичные числа (так как эти операции обратны друг другу, не имеет значения, как именно трактуются битовые строки, участвующие в операциях).

13.4. Краткая история и применение

Коды Грея получили свое название по имени Франка Грея (Frank Gray), физика из ВеН Telephone Laboratories, который в 1930-х годах изобрел метод, в настоящее время используемый для передачи цветного телевизионного сигнала, совместимого с существующими методами передачи и получения черно-белого сигнала; т.е. гфИ получении цветного сигнала черно-белым приемником изображение выводится оттенками серого цвета.

Мартин Гарднер (Martin Gardner) [15] рассматривал применение кодов Грея для решения головоломок с китайскими кольцами, ханойскими башнями, и для построения гамиль-тониановых путей в графе, представляющем гиперкубы. Он также показал, каким образом можно преобразовывать числа из десятичного представления в десятичные коды Грея.

Коды Грея используются в датчиках положения. Представьте себе полосу материала, которая разделена на проводящие и непроводящие области, соответствующие нулям и единицам целых чисел кода Грея. Каждая такая полоса контактирует с проводящей щеткой. Если щетка располагается над разделяющей линией между двумя областями так, что получается неоднозначное считывание позиции, то не имеет никакого значения, как именно будет разрешена данная неоднозначность, поскольку неоднозначным может быть положение только одной щетки (и как бы не определялось ее положение, это будут две соседние области).

Полоса материала может быть серией концентрических круговых дорожек, как показано на рис. 13.2 (четыре точки указывают четыре считывающие щетки); в этом случае будет получен датчик углового положения. В данном случае, очевидно, требуется применение циклического кода Грея.

Рис. 13.2. Датчик углового положения