Код Грея

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

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

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

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

Наприклад, десяткові числа 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 наступним чином:

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

де ${\displaystyle \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 

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

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

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

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

${\displaystyle ~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}.}$

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

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

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

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

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

${\displaystyle ~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})=}$ ${\displaystyle =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}}$

Тут передбачається, що біт, що виходить за рамки розрядної сітки (${\displaystyle 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 в двійковий код.

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

Див. також

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