Код Грэя

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

Код Грея, рефлексный двоичный код — двоичная система нумерования, в которой два соседних значения различаются только в одном двоичном разряде.

Изначально предназначался для защиты от ложного срабатывания электромеханических переключателей. Сегодня коды Грея широко используются для упрощения выявления и исправления ошибок в системах связи, а также в формировании сигналов обратной связи в системах управления.

Название

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

Код получил имя исследователя лабораторий Bell Labs Фрэнка Грея. Он использовал этот код в своей импульсной системе связи, для чего был написан патент за номером 2632058.

Применения

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

Фрагмент главной страницы патента Грея

Круговой энкодер с трёхбитным кодом грея

Коды Грея часто используются в датчиках-энкодерах ^[1]. Их использование удобно тем, что два соседних значения шкалы сигнала отличаются только в одном разряде. Также они используются для кодирования номера дорожек в жёстких дисках.

Код Грея можно использовать также и для решения задачи о Ханойских башнях .

Широко применяются коды Грея и в теории генетических алгоритмов ^[2] для кодирования генетических признаков, представленных целыми числами.

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

Ниже представлен один из алгоритмов создания последовательности кода Грея заданной глубины, записанный на языке

Алгоритм преобразования из двоичной системы счисления в код Грея, записанный на языке C:

 unsigned int grayencode(unsigned int g) {
   return g ^ (g >> 1);
 }

обратный алгоритм (преобразование из кода Грея в двоичную систему счисления):

 unsigned int graydecode(unsigned int gray) {
   unsigned int bin;
   for (bin = 0; gray; gray >>= 1) {
     bin ^= gray;
   }
   return bin;
 }

рекурсивная функция построение кода Грея на языке C:

//n -- требуемая длина кода,
//m -- указатель нп массив, как минимум, длины n 
       для хранения кода (должен быть выделен до вызова функции)
//depth -- параметр рекурсии
 
int gray (int n, int* m, int depth) 
 
{
	int i,t=(1<<(depth-1));
 
	if (depth==0)
		m[0]=0;
 
	else
	{
//массив хранит десятичные записи двоичных слов
		for (i=0;i<t;i++)
			m[t+i]=m[t-i-1]+(1<<(depth-1));
	}
	if (depth!=n)
		gray(n,m,depth+1);
	return 0;
}

См. также

• Код Хемминга
• Код Джонсона

Примечания

1. ↑ http://www.radioradar.net/articles/scientific_technical/encoder.html
2. ↑ http://www.basegroup.ru/genetic/math_print.htm

Библиография

• Black, Paul E. Gray code. 25 февраля 2004. NIST. [1] (англ.).

Ссылки

• NIST Dictionary of Algorithms and Data Structures: Gray code(англ.)
• Коды Грея
• Бинарные коды и код Грея, Gray-Excess