Код Грея

Код Грея — одна із систем кодування інформації, в якій два послідовні коди відрізняються значенням лише одного біта.

Загальні відомості

Для кодування ознак можна скористатись найпростішим варіантом: двійковим значенням цієї ознаки. Тоді легко використовувати бітові рядки фіксованої довжини для подання всіх можливих значень цієї ознаки.

Наприклад, десяткові числа 7 і 8 можна легко закодувати у двійкові числа B(7)=0111 і B(8)=1000, використовуючи двійкову техніку. Проте, якщо ми хочемо переміститися з фенотипу 7 у фенотип 8, то повинні змінити всі три біти в їх зображенні від B(7)=0111 до B(8)=1000. Інакше кажучи, при роботі ГА необхідні три окремі дії для переміщення від розв'язку 7 до розв'язку 8, які призведуть до додаткових витрат часу. З іншого боку, якщо ми хочемо переміститися від розв'язку 7 до розв'язку 8, то нам необхідна лише одна операція. Це ускладнює використання ГА й погіршує його збіжність.

Щоб уникнути цього, краще використовувати кодування, в якому значення розрізняються на один біт. Таким є код Грея. Розглянемо принцип його побудови:

Десятковий Код Грея
0 0000
1 0001

нульовий розряд вичерпав свої ресурси (0,1)
ставиться «дзеркало» і від нього «відображаються» значення 0-го
розряду, але з одиницею в старшому розряді.

2 0011
3 0010

Так само і з рештою розрядів.

4 0110
5 0111
6 0101
7 0100

8 1100
9 1101

Використання

Використання кодів Грея засновано насамперед на тому, що він мінімізує ефект помилок при перетворенні аналогових сигналів у цифрові (наприклад, у багатьох видах датчиків).

Коди Грея часто застосовуються в датчиках-енкодерах. Їх використання зручно тим, що два сусідніх значення шкали сигналу відрізняються лише в одному розряді. Також вони використовуються для кодування номера доріжок в твердих дисках.

Код Грея можна використовувати також і для вирішення задачі про Ханойські вежі. Широко застосовуються коди Грея і в теорії генетичних алгоритмів для кодування генетичних ознак, які представлені цілими числами. Код Грея використовується для генерації сполучень методом обертових дверей.

Алгоритми перетворення

Перетворення двійкового коду в код Грея

Коди Грея легко виходять з двійкових чисел шляхом побітової операції «виключне АБО» з тим же числом, зрушеним вправо на один біт. Отже, i-й біт коду Грея G_i виражається через біти двійкового коду B_i наступним чином:

G_{i}=B_{i}\oplus B_{i+1},

де $\oplus$ — операція «виключне АБО»; біти нумеруються справа наліво, починаючи з молодшого. Нижче наведено алгоритм перетворення з двійкової системи числення в код Грея, записаний на мові C (мова програмування):

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

Той же алгоритм, записаний на мові Pascal:

function BinToGray(b:integer):integer;
begin
  BinToGray:=b xor (b shr 1)
end;

Приклад: перетворити двійкове число 10110 в код Грея.

10110
01011
-----
11101

Перетворення коду Грея в двійковий код

Зворотний алгоритм — перетворення коду Грея в двійковий код — можна виразити рекурентною формулою

~B_{i}=B_{i+1}\oplus G_{i},

причому перетворення здійснюється побітно, починаючи зі старших розрядів, і значення Bi + 1, використовуване у формулі, обчислюється на попередньому кроці алгоритму. Дійсно, якщо підставити в цю формулу вищенаведений вираз для i-го біта коду Грея, отримаємо

~B_{i}=B_{i+1}\oplus G_{i}=B_{i+1}\oplus (B_{i}\oplus B_{i+1})=B_{i}\oplus (B_{i+1}\oplus B_{i+1})=B_{i}\oplus 0=B_{i}.

Однак наведений алгоритм, пов'язаний з маніпуляцією окремими бітами, незручний для програмної реалізації, тому на практиці використовують видозмінений алгоритм:

~B_{k}=\bigoplus \limits _{i=k}^{N}G_{i},

де N — кількість бітів в коді Грея (для збільшення швидкодії алгоритму за N можна взяти номер старшого ненульового біта коду Грея); знак $\oplus$ означає підсумовування за допомогою операції «виключне АБО», тобто

~\bigoplus \limits _{i=k}^{N}G_{i}=G_{k}\oplus G_{k+1}\oplus ...\oplus G_{N-1}\oplus G_{N}.

Дійсно, підставивши в формулу вираз для i-го біта коду Грея, отримаємо

~B_{k}=\bigoplus \limits _{i=k}^{N}G_{i}=\bigoplus \limits _{i=k}^{N}(B_{i}\oplus B_{i+1})=(B_{k}\oplus B_{k+1})\oplus (B_{k+1}\oplus B_{k+2})\oplus ...\oplus (B_{N-1}\oplus B_{N})\oplus (B_{N}\oplus B_{N+1})=

=B_{k}\oplus (B_{k+1}\oplus B_{k+1})\oplus ...\oplus (B_{N}\oplus B_{N})\oplus B_{N+1}=B_{k}\oplus B_{N+1}=B_{k}

Тут передбачається, що біт, що виходить за рамки розрядної сітки ( $B_{N+1}$ ), дорівнює нулю. Нижче приведена функція на мові С, що реалізує даний алгоритм. Вона здійснює послідовний зсув вправо і підсумовування вихідного двійкового числа, до тих пір, поки черговий зсув не обнулить доданок.

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

Той же самий алгоритм, записаний на мові Паскаль:

function GrayToBin(b:integer):integer;
 var g:integer;
begin
  g:=0;
  while b>0 do begin
    g:=g xor b;
    b:=b shr 1;
  end;
  GrayToBin:=g;
end;

Приклад: перетворити код Грея 11101 в двійковий код.

Швидке перетворення 8/16/24/32-разрядного значення коду Грея в двійковий код на мові BlitzBasic:

Function GRAY_2_BIN%(X%)
Return X Xor ((X And $88888888) Shr 4) Xor ((X And $CCCCCCCC) Shr 2) Xor ((X And $EEEEEEEE) Shr 1)
End Function

Генерація кода Грея

Код Грея для n біт може бути рекурсивно побудований на основі коду для n-1 біт шляхом перевертання списку біт (тобто записуванням кодів у зворотному порядку), конкатенації вихідного і перевернутого списків, дописування нулів на початку кожного коду у вихідному списку та одиниць — у початок кодів в перевернутому списку. Так, для генерації списку для n = 3 біт на підставі кодів для двох біт необхідно виконати наступні кроки:

Коди для n = 2 біт:	00, 01, 11, 10
Перевернутий список кодів:		10, 11, 01, 00
Об'єднаний список:	00, 01, 11, 10	10, 11, 01, 00
До початкового списку дописані нулі:	000, 001, 011, 010	10, 11, 01, 00
До перевернутого списку дописані одиниці:	000, 001, 011, 010	110, 111, 101, 100

Нижче представлений один з алгоритмів створення послідовності коду Грея заданої глибини, записаний на мові Perl:

  my $depth = 16; # generate 16 Gray codes, 4 bits wide each
  my @gray_codes = ( '0', '1' );
  while(scalar(@gray_codes)<$depth)
     {
     my @forward_half=map{'0'.$_} @gray_codes;
     my @reverse_half=map{'1'.$_} reverse(@gray_codes);
     @gray_codes=(@forward_half,@reverse_half);
     }

Рекурсивна функція побудова коду Грея мовою 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;
}

Швидке перетворення 8/16/24/32-разрядного бінарного коду в код Грея мовою BlitzBasic:

Function BIN_2_GRAY%(X%)
Return X Xor ((X And $EEEEEEEE) Shr 1)
End Function

Таблиця відповідності між двійковим кодом та кодом Грея


Ціле	Двійковий код	Код Грея
0	0000	0000
1	0001	0001
2	0010	0011
3	0011	0010
4	0100	0110
5	0101	0111
6	0110	0101
7	0111	0100
8	1000	1100
9	1001	1101
10	1010	1111
11	1011	1110
12	1100	1010
13	1101	1011
14	1110	1001
15	1111	1000

Див. також

Код Грея

Статус версії сторінки

Зміст

Загальні відомості

Використання

Алгоритми перетворення

Перетворення двійкового коду в код Грея

Перетворення коду Грея в двійковий код

Генерація кода Грея

Таблиця відповідності між двійковим кодом та кодом Грея

Див. також

Навігаційне меню

Код Грея

Загальні відомості

Використання

Алгоритми перетворення

Перетворення двійкового коду в код Грея

Перетворення коду Грея в двійковий код

Генерація кода Грея

Таблиця відповідності між двійковим кодом та кодом Грея

Див. також

Навігаційне меню

Пошук