Код Ґрея

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

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

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

Використання кодів Ґрея базується насамперед на тому, що він мінімізує ефект помилок при перетворенні аналогових сигналів у цифрові (наприклад, у багатьох видах давачів). Як вище зазначалося, коди Ґрея найчастіше застосовуються в давачах-енкодер. Як приклад на рис.1.3 наведено круговий енкодер з трьохбітним кодом Ґрея. Їх використання зручно тим, що два сусідніх значення шкали сигналу відрізняються лише в одному розряді. Також вони використовуються для кодування номера доріжок в жорстких дисках. Код Ґрея можна використовувати також і для вирішення задачі про Ханойські вежі. Широко застосовуються коди Ґрея і в теорії генетичних алгоритмів для кодування генетичних ознак, представлених цілими числами. Код Ґрея використовується для генерації сполучень методом обертових дверей.

Рис.1.3. Круговий енкодер з трьохбітним кодом Ґрея.

Перетворення двійкового коду в код Ґрея

Коди Ґрея легко виходять з двійкових чисел шляхом побітової операції «виключає АБО» (встановлює біт тільки в тому випадку, якщо в одному операнді біт встановлено, а в іншому немає) з тим же числом, зcунутим вправо на один біт (зсуває всі значущі біти лівого операнду на число позицій, визначені в правому операнді). Отже, i-й біт коду Ґрея G_i виражається через біти двійкового коду B_i наступним чином:

де – операція «виключає АБО»; біти нумеруються справа наліво, починаючи з молодшого.

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

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

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

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

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

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

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

Тут передбачається, що біт, що виходить за рамки розрядної сітки (), дорівнює нулеві.

Приклад: перетворити код Ґрея 11101 у двійковий код.

Генерування коду Ґрея

Код Ґрея для n біт може бути рекурсивно побудований на основі коду для n-1 біт шляхом перевертання списку біт (тобто записуванням кодів у зворотному порядку), конкатенації вихідного і перевернутого списків, дописування нулів на початку кожного коду у вихідному списку та одиниць – у початок кодів в перевернутому списку. Так, для генерації списку для n = 3 біт на підставі кодів для двох біт необхідно виконати наступні кроки: