Огледален двоичен код – Уикипедия

Огледалният двоичен код, известен още като двоично-реверсивен код, позиционен код или код на Грей, е вид двоичен код, в който при преминаването между две съседни стойности се променя само една цифра, т.е. има разстояние на Хеминг единица.

Пример: осемте стойности на 3-разреден огледален двоичен код са 000 → 001 → 011 → 010 → 110 → 111 → 101 → 100.

Интересно свойство на кода на Грей е неговата цикличност – първият елемент на редицата може да бъде поставен след последния и така се образува цикъл. Това свойство е съвсем естествено, като се има предвид, че n-разреден код на Грей описва Хамилтонов цикъл в n-мерния булев куб. Последното е естествено, тъй като кодът на Грей съдържа по веднъж всички n-разредни двоични вектори (които са всички върхове на n-мерния булев куб), като съседните са на разстояние на Хеминг единица (както и съседните върхове в куба).

Първоначалното име „огледален“ показва поведението на младшите разреди спрямо средата – във втората половина от кодовите значения разредите повтарят стойностите си от първата половина в обратен (огледален) ред. Това е видно от примера: ако се махне само най-старшия разряд, стойностите от първата половина при старши разряд 0 (00 → 01 → 11 → 10) се повтарят във втората при разряд 1 в обратен ред (10 → 11 → 01 → 00). Ако се махнат два разреда, симетрията се повтаря два пъти – (0 → 1 / 1 → 0).

Името „позиционен“ е следствие от употребата на кода за премахване на смущенията в електро-механичните ъглови позиционни датчици. Френският инженер Емил Бодо създава такива датчици през 1878 г. За направеното от него подобрение на телеграфните апарати, той получава Ордена на почетния легион. Това име има тясно разпространение и не трябва да се бърка с математическото понятие позиционен код - произволен код, в който една и съща цифра има различен смисъл в зависимост от позицията си.

Името „код на Грей“ първоначално се появява в САЩ благодарение на патента^[1], получен от Франк Грей от лабораториите Бел през 1953 г. за приемник на сигнали в огледален двоичен код. Въпреки неточността името се разпространява и в други страни.

Основното предимство на кода е единичната промяна между последователните стойности. При кодовете, основани на двоичната бройна система, всеки преход от нечетно към по-голямо четно число (или обратно) може да създаде неверни междинни стойности. Пример: при преход от 5₍₁₀₎=101₍₂₎ към 6₍₁₀₎=110₍₂₎ е възможно двете последни цифри да се променят неедновременно и за кратко да се появи междинна стойност 4₍₁₀₎=100₍₂₎ или 7₍₁₀₎=111₍₂₎. При преходите с промяна на повече цифри е въжможно дори да се мине през няколко междинни стойности.

Друго предимство е „цикличността“ на кода – последното значение във всяка огледално-двоична последователност е винаги от вида 100…0 и с промяна на единицата се връща до изходна стойност.

Конструирането е индуктивно и следва принципите на индукцията:

1. Едно-разредния код 0, 1 е код на Грей
2. Ако имаме построен (n-1)-разредния код на Грей построяваме n-разредния като записваме (n-1)-разредния и след края му го записваме отново в обратен ред. В ново-получената редица добавяме пред всеки елемент от първата половина 0, а пред всеки от втората половина – 1.

Пример:

• 1-разреден: 0, 1
• 2-разреден: _0, _1; _1, _0 и добавяме – 00, 01; 11, 10
• 3-разреден: _00, _01, _11, _10; _10, _11, _01, _00 и добавяме – 000, 001, 011, 010; 110, 111, 101, 100