Код Грея

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Фрагмент сторінки патента Грея

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

Загальні відомості[ред.ред. код]

З курсу біології ми знаємо, що будь-який організм може бути поданий своїм фенотипом, який фактично визначає, чим є об'єкт у реальному світі, і генотипом, який містить інформацію про об'єкт на рівні хромосомного набору. При цьому кожен ген, тобто елемент інформації генотипу, має своє відображення у фенотипі. Таким чином, для розв'язання задач нам необхідно зобразити кожну ознаку об'єкта у формі, придатній для використання в генетичному алгоритмі. Усе функціонування генетичного алгоритму вимагає лише інформацію про генотип, тобто інформація про об'єкт не потрібна. Найпоширенішим різновидом кодування є побітове, тобто використання бітових рядків. При цьому кожному атрибуту об'єкта у фенотипі відповідає один ген у генотипі.

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

Наприклад, десяткові числа 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-й біт коду Грея Gi виражається через біти двійкового коду Bi наступним чином:

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

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

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

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

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^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 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


Див. також[ред.ред. код]