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