Код Грея

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

Фрагмент сторінки патента Грея

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

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

Наприклад, десяткові числа 7 і 8 можна легко закодувати у двійкові числа B(7)=011 і B(8)=100, використовуючи двійкову техніку. Проте, якщо ми хочемо переміститися з фенотипу 7 у фенотип 8, то повинні змінити всі три біти в їх зображенні від B(7)=011 до B(8)=100. Інакше кажучи, при роботі ГА необхідні три окремі дії для переміщення від розв'язку 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 наступним чином:

де  — операція «виключне АБО»; біти нумеруються справа наліво, починаючи з молодшого. Нижче наведено алгоритм перетворення з двійкової системи числення в код Грея, записаний на мові 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 

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

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

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

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

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

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

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

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 в двійковий код.

11101 01110 00111 00011 00001 ----- 10110 

Швидке перетворення 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

Див. також

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