Огледален двоичен код

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

Диаграма на контактите на 8-позиционен ъглов датчик

Пример: осемте стойности на 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

Източници

1. United States Patent and Trademark Office - U.S. patent no. 2 632 058^{[неработеща препратка]} ((en))

Тази статия, свързана с математика, все още е мъниче. Помогнете на Уикипедия, като я редактирате и разширите.