Код Грея

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 

Код Грея - система числення, в якій два сусідні значення розрізняються тільки в одному розряді. Найбільш часто на практиці застосовується рефлексивний двійковий код Грея, хоча в загальному випадку існує нескінченна безліч кодів Грея для систем числення з будь-якою основою. У більшості випадків, під терміном "код Грея" розуміють саме рефлексивний бінарний код Грея.

Спочатку призначався для захисту від помилкового спрацьовування електромеханічних перемикачів. Сьогодні коди Грея широко використовуються для спрощення виявлення та виправлення помилок в системах зв'язку, а також у формуванні сигналів зворотного зв'язку в системах управління.


1. Назва

Назва Рефлексний (відбитий) двійковий код походить від факту, що друга половина значень в коді Грея еквівалентна першій половині, тільки в зворотному порядку, за винятком старшого біта, який просто інвертується. Якщо ж розділити кожну половину ще раз навпіл, властивість буде зберігатися для кожної з половин половини і т. д.

Код отримав ім'я дослідника лабораторій Bell Labs Френка Грея. Він запатентував і використовував цей код в своїй імпульсної системі зв'язку (патент № 2632058).


2. Застосування

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

Фрагмент головної сторінки патенту Грея
Кругової енкодер з трехбітним кодом гріючи

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

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

Широко застосовуються коди Грея і в теорії генетичних алгоритмів [1] для кодування генетичних ознак, представлених цілими числами.

Код Грея використовується для генерації сполучень методом обертових дверей [2]

У деяких комп'ютерних іграх (наприклад, Duke Nukem 3D) для успішного проходження рівня потрібно підібрати потрібну комбінацію положень декількох перемикачів. Для мінімізації числа перемикань при переборі варіантів слід використовувати код Грея.


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

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

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

Однак, необхідно пам'ятати, що даний алгоритм буде працювати правильно, якщо компілятор реалізує циклічний логічний зрушення (стандарт мови C не уточнює тип зсуву). Той же самий алгоритм, записаний на мові Паскаль:

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

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

 10110 01011 ----- 11101 

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

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

~ B_i = B_ {i +1} \ oplus G_i,

причому перетворення здійснюється побітне, починаючи зі старших розрядів, і значення B_ {i +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 ^ N_ {i = k} G_i,

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

~ \ Bigoplus \ limits ^ N_ {i = k} G_i = G_k \ oplus G_ {k +1} \ oplus ... \ Oplus G_ {N-1} \ oplus G_N.

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

~ B_k = \ bigoplus \ limits ^ N_ {i = k} G_i = \ bigoplus \ limits ^ N_ {i = k} (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 в двійковий код.

 11101 01110 00111 00011 00001 ----- 10110 

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

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

Простий спосіб перетворення двійкового числа в код Грея виконується за правилом: старший розряд записується без зміни, кожен наступний символ коду Грея потрібно інвертувати, якщо в натуральному коді перед цим була отримана "1", і залишити без зміни, якщо в натуральному коді був отриманий " 0 ".


3.3. Генерація кодів Грея

Код Грея для 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 

Примітки

  1. BaseGroup.ru :: Генетичні алгоритми - математичний апарат - www.basegroup.ru / genetic / math_print.htm
  2. Кнут, Дональд, Е. Мистецтво програмування, том 4, випуск 3: генерація всіх поєднань і розбиттів (розділ 7.2.1.3): Пер. з англ. - М.: ТОВ "І.Д. Вільямс", 2007. - 208 с. : Іл.]

5. Бібліографія

  • Black, Paul E. Gray code. 25 лютого 2004. NIST. [1] - www.nist.gov / dads / HTML / graycode.html (Англ.) .