Про геометрический смысл кодов Грея


    Коды Грея имеют близкую родственную связь с кривой Гильберта.

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

    В результате под катом — «скандалы, интриги, расследования».

    Основная особенность кода Грея — два соседних в лексикографическом порядке значения отличаются только в одном разряде. С другой стороны, кривая Гильберта непрерывна — расстояние между двумя соседними точками всегда единица. Уже только одно это намекает об их внутренней связи.

    Код Грея описывает похождения кривой Гильберта в рамках единичного гиперкуба. В самом деле, если взять 3-разрядный код и нарисовать его в 3-мерном пространстве (принимая каждый разряд за соответствующую координату), получим


    Фиг.1 3-разрядный код Грея как 3-мерный куб

    Знакомая картина — это 3-мерный симплекс кривой Гильберта! Последовательно заменяя каждый узел симплекса на такой же симплекс (с учетом поворотов и отражений для сохранения непрерывности), получим кривую Гильберта 4х4х4.

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


    Фиг.2 несколько итераций симплекса кривой Гильберта.

    Но как так получилось?

    Известно, что код Грея самоподобен. Его иногда называют зеркальным “из-за того, что первая половина значений при изменении порядка эквивалентна второй половине, за исключением старшего бита. Старший бит просто инвертируется”. Для наглядности, 3-разрядный код — самый старший разряд — самый левый:



    Раз уж речь зашла о самоподобии, начнём с начала — с одноразрядного кода. Строго говоря, можно было бы начать и с нулевой размерности — точки, принципиально это ничего не меняет, просто слов пришлось бы написать больше.

    Одноразрядный код Грея даже проще, чем трёхлинейная винтовка, он либо 0, либо 1.

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

    Перейдём к двумерному случаю. Двумерный куб — квадрат. Принимая во внимание самоподобие, мы клонируем одномерный куб (0,1) и получаем два отрезка — (0,0 -> 1,0) и (0,1 -> 1,1). Теперь требуется соединить эти отрезки, чтобы получить обход квадрата. И здесь возникают два варианта:

    • соединяем начало предыдущей итерации — одномерного куба с началом его клона. С точностью до симметрии это тоже самое, что и соединение конца с концом. Тип симметрии — зеркальная. Этот вариант условно назовём “миссионерским”.
    • соединяем конец предыдущей итерации с началом его клона. С точностью до симметрии это тоже самое, что и соединение начала отрезка с концом клона. Тип симметрии — центральная. Назовём этот вариант “паровозиком”.

    Аналогично действуем при переходе к трёх и более мерным случаям.


    Фиг.3 Первые две итерации “миссионерского” варианта

    Здесь красным цветом выделена предыдущая итерация, синим — её клон, бирюзовым — их соединение.

    Обратим внимание — соединение всегда проходит по единственной размерности — вновь добавленной, отсюда в силу самоподобия и появляется основная особенность кода Грея. А раз соединяется конец предыдущей итерации с концом её клона, возникает “зеркальность” — при обходе, клон мы вынуждены проходить в обратном порядке. Вне зависимости от размерности. Здесь же видно происхождение и особенности кривой Гильберта — как бы ни была велика решетка (любой размерности), на низовом уровне это всё тот же единичный куб с переходами длиной в единицу.


    Фиг.4 Первые две итерации варианта “паровозик”, те же цвета

    А ведь и эта музыка нам знакома — получился симплекс Z-кривой. Слово симплекс здесь также означает, что если взять каждую его точку и заменить на симплекс, получим куб 4х4х4, продолжая итерации — можно заполнить сколь угодно большую кубическую решетку.

    Забавно, что в этом случае преобразование пройденного от начала координат пути в код, который может быть разобран на разряды-координаты тривиально.
    Тогда как случае кода Грея это G = W ^ (W >> 1), где W-пройденная длина, G — код Грея.


    Фиг.5 первые две итерации Z-кривой (wiki)


    Фиг.6 для сравнения, первые две итерации кривой Гильберта (wiki)

    А ведь других то (естественных) вариантов обхода единичного гиперкуба и нет.
    Вот и получается, что куда ни кинь, кругом Гильберт, Лебег … и пустота.

    PS: на титульной картинке круговой энкодер с восьмиразрядным кодом Грея.
    PPS: тут меня поправляют, что симплекс — вполне устоявшийся термин, нехорошо с ним так. Что-же, в данной статье ведь не просто симплекс, а симплекс кривой Гильберта или симплекс Z-кривой. Пусть правоверные математики меня простят.

    Похожие публикации

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 9

      +3
      Знакомая картина — это 3-мерный симплекс кривой Гильберта!

      Вот отсюда стало непонятно.
      Что такое симплекс?
      Что такое трехмерный симплекс?
      Что такое симплекс кривой?
        +1
        Кривая Гильберта (пусть N-мерная) получается из N-мерного единичного куба
        (с обходом вершин). Я его называю симплексом кривой Гильберта.
        Заменяя точки этого куба на такой же куб, получаем куб со стороной 2.
        Если еще раз — 4. Там ниже иллюстрация того, как это происходит.
        +1
        В свое время нашел неожиданное для себя применение коду Грэя при создании варианта пространственного индекса: infostart.ru/public/551583. Спасибо за статью — она пояснила мне полученный тогда эффект с новой стороны. Еще про октадеревья нужно будет подумать.
          +1
          Z-кривая, кстати, ещё называется Кривой Мортона. Полезная вещь при работе с вокселями в 3d.
            +1
            Впервые познакомившись с кодом Грея (он используется в схемотехнике при переходе из одного тактируемого домена в другой), я задумался о том, почему он вообще существует. И был очень рад найти изящное геометрическое доказательство. Оно по смыслу практически совпадает с тем, что приводится в этой статье и в других источниках. Только я не пытался отобразить это в кривую Гильберта, а рисовал обычный гиперкуб нужной размерности и ломаную на его ребрах.

            Я использую следующее определение. Код Грея — это такое биективное отображение g: {0,1}^n -> {0,1}^n, что g(x) и g(x+1) отличаются ровно в одном разряде. При этом обычно под операцией + подразумевают обычное сложение двоичных чисел, однако я предлагаю немного обобщить и считать, что сложение делается по модулю 2^n. Тогда точки 00…0 и 11…1 оказываются соседними, и их образы тоже должны отличаться ровно в одном разряде. Разница с классическим определением заключается в том, что соответствующая кривая в геометрическом представлении оказывается замкнутой. Теперь можно применить индуктивное построение из этой статьи, слегка модифицировав его. Возьмем замкнутую кривую размерности n, выберем на ней произвольный отрезок AB удалим его. Полученную (незамкнутую) кривую скопируем в еще одну такую же (пусть при этом точки A и B перешли в A' и B' соответственно) и полученные экземпляры кривой поместим на противоположные грани гиперкуба размерности (n+1). Теперь осталось добавить отрезки AA' и BB', чтобы получилась новая замкнутая кривая размерности (n+1) с теми же свойствами. (В качестве базы индукции можно взять n=2 (это квадрат), но и для n=1 тоже будет работать, только вместо отрезка 0—1 нужно взять цикл 0—1—0, состоящий из двух одинаковых отрезков.) Если каждый раз в качестве A и B выбирать точки 00…0 и 11…1, то получится в точности «миссионерский» вариант из статьи или, что то же самое, код Грея, полученный по алгоритму из Википедии.
              +1
              Впервые познакомившись с кодом Грея (он используется в схемотехнике при переходе из одного тактируемого домена в другой), я задумался о том, почему он вообще существует

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

              +1
              zzeng вы самоподобны!
              -RE Забавно, что в этом случае преобразование пройденного от начала координат пути в код, который может быть разобран на разряды-координаты тривиально.
              НЛО — это стеб
                +1

                Ага. Получается что любой обход графа можно рассматривать как движение по ребрам кубической гиперрешётки с размерностью равной (или большей) максимальному количеству ребер исходящих из узла.
                Интересная метрика для графа получается.
                Буду думать.
                Вопрос к знатокам это свойство где-нибудь используется?

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое