Код Грея на пальцах

otrageniya — 29.06.2019 В жизни постоянно встречаешься с разными забавными мелкими безделицами, которые становятся частью твоей биографии, и ты время от времени испытываешь радость, что знаешь какие-то прикольные фишки, о которых другие даже не подозревают...



Глубокой осенью 1980 года после долгих бумажных проволочек, связанных с переводом из ДВПИ в ЛЭТИ, я прибыл на свой первый семинар в новой альме матери. Дело шло к концу семестра, и преподаватель схемотехники сильно призадумался, сочиняя мне тему для курсовой. В конце концов он решил бросить меня в область новую, неизведанную — преобразователь кода Грея в двоичный код. Про код Грея я раньше ничего не слышал и сразу же бросился в библиотеку (тогда ещё не было интернета, прикиньте!). Тема оказалась довольно простой и настолько забавной, что до сих пор в разных интеллектуальных компаниях после первой бутылки коньяка я демонстрирую присутствующим глубокое проникновение в предмет.

Руководитель, впрочем, остался недоволен. Преобразователь четырёхразрядного кода уложился в одну микросхему, а пояснительная записка заняла четыре страницы, что, конечно, непростительно мало для любого уважающего себя преподавателя схемотехники.

Лет через десять я сам уже вёл семинары по цифровой электронике, и передо мной встала проблема, как просто и доходчиво объяснить студентам-заочникам сущность кода Грея. И я придумал такую байку.

Этнографическая байка про код Грея

Задумывались ли вы когда-нибудь, что считая на пальцах, мы используем ресурсы своего организма крайне нерационально? Задействуя пять пальцев, мы считаем до десяти, хотя различные сочетания загнутых и разогнутых пальцев одной руки дают 2⁵ = 32 различных комбинации. Получается, что мы используем собственные вычислительные мощности всего лишь на треть.

Считать в двоичных кодах не выход, так как требуется довольно сложная координация движений разных пальцев. Например, при переходе от 15 к 16 (01111 → 10000) приходится одновременно разгибать четыре пальца и загибать пятый. Желательно же, чтобы при переходе к следующему числу, как и при счёте до 10, загибался или разгибался только один палец. Хочется также, чтобы существовал стереотип движений, то есть при счёте пальцы циклически повторяли одну и ту же последовательность сгибаний и разгибаний, что позволило бы довести счёт до автоматизма.

Однажды этнографическая экспедиция высадилась на далёкий полинезийский остров Гронгозогоро и обнаружила, что местные аборигены издревле используют именно такой способ счёта (дальше я показываю студентам, какой именно):



Понятно, что это сразу породило различные межнациональные недопонимания. На местном рынке на вопрос этнографа, сколько стоит ведро устриц, абориген изобразил фигуру, воспроизведённую на заглавной картинке. Этнограф понял это по-своему, и вытащил из сумки бутылку водки. Ещё большее недопонимание возникло, когда в ответ на аналогичный вопрос, абориген показал этнографу «фак».



Поскольку фигуры из пальцев спервоначалу трудно соотнести с привычными десятичными числами, имеет смысл предварительно преобразовать их в двоичную систему. Для этого существует такой алгоритм.

1. Старший разряд (то есть мизинец) кода Грея всегда совпадает со старшим разрядом двоичного кода.
2. Положение следующих по порядку пальцев определяется правилом: если предыдущий палец загнут, то следующий палец меняет своё положение. Если же предыдущий палец разогнут, положение следующего пальца не меняется.

Когда процесс доходит до большого пальца, искомое число оказывается закодировано на руке двоичным кодом. Не забывайте, что загнутый палец — единица, разогнутый — ноль.



Для чего это нужно?

Первое применение код Грея нашёл в кодирующих дисках угла поворота. Представьте себе, что на некоторое вращающееся устройство насажен диск, который выглядит примерно так:



Расположим вдоль радиуса диска несколько неподвижных фотодатчиков (в данном случае три, они обозначены красными кружками). Когда фотодатчик находится напротив белого сектора диска, он даёт сигнал 0, когда напротив чёрного — 1. Таким образом, в зависимости от угла поворота диска фотодатчики дают разные коды, что позволяет измерять угол поворота. В данном случае диск расчерчен так, чтобы фотодатчики давали трёхразрядный двоичный код. Например, 000 — север, 001 — северо-запад, 010 — запад и т.д. до 111 — северо-восток.



Проблема такого кодового диска состоит вот в чём. Когда линейка фотодатчиков находится на границе между двумя секторами, датчики начинают вести себя непредсказуемым образом. Вот, например, ситуация, когда диск переходит из сектора 000 в сектор 111. Понятно, что невозможно сделать фотодатчики абсолютно идентичными, а границу между секторами абсолютно ровной. В результате при переходе границы одни датчики переключатся из 0 в 1 раньше, другие — позже. В результате возникают промежуточные комбинации кодов, например 000 -> 001 -> 101 -> 111, что может дать грубую ошибку при измерении угла.



Тут на помощь приходит код Грея, где соседние сектора различаются всего одним разрядом, поэтому время срабатывания датчиков некритично.



Понятно, что применение диска, закодированного по Грею, требует для преобразования в обычный двоичный код специальной схемы, которая оказывается трогательно простой:



P.S. Помещённое выше видео я иногда посылаю по вотсапу своим недоброжелателям, и когда они встревоженно спрашивают, что это было, отвечаю, что это был магический ритуал, после которого их будут до конца жизни преследовать беды и несчастья :~).

Оставить комментарий

Популярные посты:

• Ранее
• Архив