Главная       Скачать       Коммерческая поддержка       FAQ       Forum       О нас       Английская версия

Системы счисления: код Грея

Автор: Белоусов Аркадий

Введение

Известно множество схем кодирования чисел (систем счисления) - совокупностей символов и правил их комбинации для обозначения числа. Основной признак, по которому все системы разделяют - позиционная ли это система. В свою очередь, позиционные системы различаются "весами", соответствующими каждой позиции в представлении числа. В одних системах вес цифры каждого разряда меньше веса цифры следующего старшего разряда в одно и тоже число раз. В других системах для каждого разряда определён свой вес, который может быть равен, больше или меньше весов других разрядов в произвольное число раз.

К позиционным системам с постоянным основанием относится десятичная система, системой с произвольным основанием является система счёта времени - секунд в минутах и минут в часах по 60, а часов в сутках 24. Непозиционные системы счисления из повседневности практически вытеснены, хотя римская система до сих пор используется, например, для указания номера века, а иногда и года.

В современных цифровых компьютерах основное место занимает двоичная система счисления (позиционная система с постоянным основанием, равным 2) и прямые её производные (восьмеричная и шестнадцатиричная системы). Однако и другие системы не были забыты. Например, при двоично-десятичном кодировании чисел каждой десятичной цифре отводится по четыре двоичных цифры (бита), веса которых могут быть равны не только 8-4-2-1, но и, скажем, 2-4-2-1.

Встречаются в цифровой технике и непозиционные системы. Наиболее известныйиз них - код Грея, называемый также рефлексным (отражённым) двоичным кодом. Этот код строится из двоичных цифр таким образом, что соседние числа в нём отличаются всегда только в одном разряде. Кодов с такой же характеристикой много, но для кода Грея имеется простой алгоритм перевода чисел в двоичный позиционный код и обратно.

Строение кода Грея

Код Грея - непозиционный код с одним набором символов (0 и 1) для каждого разряда. Таким образом, в отличие от римской системы счисления число в коде Грея не является суммой цифр. Чтобы показать соответствие последовательности чисел коду Грея можно воспользоваться таблицей, но есть и наглядное правило построения этой последовательности.

Младший разряд в последовательности чисел в коде Грея принимает значения 0 и 1, затем следующий старший разряд становится единичным и младший разряд принимает свои значения уже в обратном порядке (1, 0). Этим и объясняется название кода - "отражённый". Соответственно, два младших разряда принимают значения 00, 01, 11, 10, а затем, при единичном следующем старшем разряде, те же значения в обратном порядке (10, 11, 01, 00). Ниже дана таблица, показывающая первые восемь чисел в двоичном коде и в коде Грея.

Nдвоичный кодкод Грея Nдвоичный кодкод Грея
0000000 4100110
1001001 5101111
2010011 6110101
3011010 7111100

Использование кода Грея

Благодаря своему основному свойству (отличие соседних чисел только в одном разряде) код Грея применяется, например, в построенных на кодовых дисках определителях углового положения вала. В оптическом кодовом диске единицы и нули кодируются прозрачными и непрозрачными областями. С одной стороны диск просвечивается ориентированной вдоль его радиуса световой щелью, с другой стороны размещаются фотодиоды. Считываемый с фотодиодов двоичный код и указывает угол поворота диска. Ниже показаны 3-разрядные диски на позиционном коде и коде Грея (в силу ограниченности выразительных средств диски "разрезаны" посредине последнего угла и "вытянуты" в ленту, как это делается и для карт земного шара):

позиционный кодпозиционный код
код Греякод Грея

Недостаток кодирования позиционным двоичным кодом заключается в том, что при смене нечётного кода чётным считанный с фотодиода код может оказаться неверным. Характеристики фотодиодов обычно не идентичны и при смене сразу нескольких разрядов выходные уровни фотодиодов могут измениться не строго одновременно. Например, при переходе от третьего угла к четвёртому или от седьмого угла к нулевому меняются все разряды и какое-то время на выходе фотодиодов можно получить любое значение от 0 до 7. В коде же Грея при переходах ошибка не будет превышать один угол.

Алгоритмы преобразования кода Грея

Как сказано выше, алгоритм перевода чисел в коде Грея в позиционный код прост: каждый разряд в позиционном коде равен сумме по модулю 2 этого и всех более старших разрядов в коде Грея. Старшие разряды, соответственно, совпадают. На языке C это алгоритм может выглядеть так:

	unsigned gray2bin(unsigned v){
		unsigned sum = v, length = BITS;
		while(length > 0) v >>= 1, sum ^= v, length--;
		return sum;
		}

Этот код является дословным переводом на язык C основного алгоритма, но его можно оптимизировать за счёт накопления промежуточных сумм в самом числе:

	for(unsigned i = 1; i < BITS; i <<= 1) v ^= (v >> i);

Поскольку количество итераций здесь является уже логарифмом от числа бит и мало даже для очень больших чисел, то этот цикл лучше развернуть:

	v ^= v >> 1;	/* для 2-разрядных чисел */
	v ^= v >> 2;	/* для 4-разрядных чисел */
	v ^= v >> 4;	/* для 8-разрядных чисел */
	v ^= v >> 8;	/* для 16-разрядных чисел */
	...

Перевод из позиционного кода в код Грея ещё проще: каждый разряд в коде Грея равен сумме по модулю 2 этого и следующего старшего разряда в позиционном коде. На языке C этот алгоритм реализуется выражением v^(v>>1). Реализации на языке C этих алгоритмов также представлены в отдельном файле [GRAY.C].

Заметьте: код Грея отличается от позиционного кода только интерпретацией значения бит в числе, поэтому числа в разных кодах можно хранить в одних и тех же переменных. Более того, одно и то же значение переменной также можно интерпретировать по-разному - это просто даст разные числа.

Литература

И.С.Потёмкин "Функциональные узлы цифровой автоматики", М.: Энергоатомиздат, 1988

 

ALGLIB® - numerical analysis library, 1999-2016.
ALGLIB is registered trademark of the ALGLIB Project.