Коды Грея и задачи перебора

    В данной статье будет показан математический подход к составлению алгоритмов на примере следующих вопросов и задач:
    • Двоичные коды Грея. Их существование. Перебор подмножеств данного множества в порядке минимального изменения.
    • Существование и реализация перебора подмножеств из k элементов в порядке минимального изменения.

    Итак, приступим.

    Двоичный код Грея


    Двоичным кодом Грея порядка n называется последовательность всех image n-битных кодов, в которой любые два соседних кода различаются ровно в одном разряде.

    Пример кодов Грея порядка 2:
    • 00
    • 01
    • 11
    • 10


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

    Существование


    Существование кодов Грея легко доказывается по индукции.
    База — image — пустая последовательность.
    Переход. Пусть image — последовательность кодов Грея порядка image. image — последовательность image записанная в обратном порядке. Тогда последовательность image получается приписыванием нуля слева к каждому коду в последовательности image и единицы слева к каждому коду image и последующим их объединением, т.е. image. Нетрудно проверить, что свойство кодов Грея в последовательности image, построенную таким образом, не нарушается. image

    Коды Грея, полученные таким способом, называются рефлексивными или симметрично отраженными. В дальнейшем мы будем рассматривать именно рефлексивные двоичные коды Грея.

    В качестве упражнения выпишите симметрично отраженные коды Грея порядка 3 по приведенной в доказательстве формуле: image.

    А теперь перейдем к приложению кодов Грея для решения некоторых задач комбинаторики.

    Перебор подмножеств данного множества в порядке минимального изменения


    Рассмотрим следующую задачу: «Дано множество из n элементов. Требуется вывести все его подмножества в таком порядке, что каждое следующее подмножество получается из предыдущего удалением или добавлением ровно одного элемента(т.е. в порядке минимального изменения).»

    Будем считать, что элементы нашего множества пронумерованы от 1 до n. Тогда любому набору элементов множества можно поставить в соответствие n-битный двоичный код: если i-ый элемент множества входит в набор, то i-ый бит кода равен единице, иначе нулю. Таким образом, перебор всех подмножеств сводится к перебору двоичных кодов порядка n, а перебор подмножеств в порядке минимального изменения — к перебору двоичных кодов Грея.

    Идея алгоритма рекурсивного перебора кодов Грея непременно следует из доказательства их существования, а именно приведенного в нем рекуррентного соотношения image.

    image Собственно, как и говорилось в доказательстве, код Грея порядка n получается из кода Грея порядка n-1 приписыванием нуля слева(этому соответствует вызов функции и присвоение перед ним) и обратного кода Грея порядка n-1 приписыванием единицы слева(этому соответствует вызов функции и присвоение перед ним).

    Перейдем к оценке сложности данного алгоритма. Очевидно, что дерево вызовов функции image является полным двоичным деревом высоты n. Следовательно, общее число вызовов функции при генерации кодов Грея порядка n есть ни что иное, как image, что равно количеству всевозможных n-битных кодов. Следовательно, алгоритм оптимален.

    В качестве упражнения читателю предлагается проанализировать следующий, более короткий, алгоритм рекурсивного перебора.
    Пример


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

    А теперь давайте перейдем к последней и самой интересной задаче.


    Перебор подмножеств из k элементов в порядке минимального изменения.


    Начнем с постановки задачи: «Дано множество из n элементов. Требуется вывести все его подмножества, состоящие ровно из k элементов, в таком порядке, что каждое следующее подмножество получается из предыдущего заменой ровно одного элемента(т.е. в порядке минимального изменения).»

    Здесь сразу приходит в голову идея алгоритма из предыдущей задачи, но выводить мы будем только те коды Грея, в которых ровно k единиц. При этом возникает вопрос о корректности этого алгоритма: нам никто не гарантирует, что соседние коды в последовательности image, в которой оставлены только двоичные коды с количеством единиц равным k, расположены в порядке минимального изменения — с разницей ровно в двух разрядах — получаются друг из друга заменой одного элемента. Поэтому перейдем к дальнейшему изучению свойств симметрично-отраженных кодов Грея.

    Введем некоторые обозначения:
    • image — строка, получаемая конкатенацией символа x (m раз) и конкатенацией символа y (k раз). Пример: image.
    • image — последовательность всех n-битных кодов с k единицами, в которой коды идут в том порядке, в котором они расположены в последовательности image.
    • image — последовательность всех n-битных кодов с k единицами, в которой коды идут в том порядке, в котором они расположены в последовательности image.


    Лемма

    Первый двоичный код с image единицами в последовательности image имеет вид image, а последний — image или image, если image.
    Доказательство
    Доказывать будем индукцией по image и image.
    База — image — верно(нетрудно проверить приведенные формулы для двух кодов 0 и 1).
    Переход. Пусть формулы верны для image и любого image. Вспомним формулу из доказательства существования кодов Грея: image. Отсюда получим, что первый код с image единицами в последовательности image с приписанным слева нулем является первым кодом с image единицами в последовательности image. При image получим единственный код с image единицей, для которого формула также верна. При image последний код с image единицами в последовательности image есть первый код с image единицей и приписанной слева единицей в последовательности image. При image формула также верна. image

    Теорема

    Соседние двоичные коды в последовательности image различаются ровно в двух разрядах.
    Доказательство
    Доказывать будем также индукцией по image и image.
    База — image — очевидно(всего один возможный код в последовательности).
    Переход. Пусть теорема верна для image и image. При image или image имеем всего один код в последовательности image. При image соседние слова находящиеся полностью в image или в image по индукционному предположению различаются ровно в двух разрядах. Остается проверить одну пару соседних кодов в image последний код с image единицами в image и первый код с image единицами в image (последний с image единицей в image с приписанной слева единицей). По лемме, при image, они имеют вид image и image соответственно, а при imageimage и image. Нетрудно видеть, что они различаются ровно в двух разрядах. image

    Теперь мы можем сформулировать замечательные следствия из теоремы.
    • Наивный алгоритм, предложенный ранее, корректен, то есть, если в последовательности image оставить только те двоичные коды, в которых ровно k единиц, то они будут расположены в порядке минимального изменения(каждый следующий получается из предыдущего заменой одного элемента).
    • Последовательность image задается следующим рекуррентным соотношением: image. Это можно проверить по индукции.
    • Последовательность image задается следующим рекуррентным соотношением: image. Также проверяется по индукции.


    Эти следствия можно и нужно использовать для написания программы рекурсивного перебора подмножеств из k элементов в порядке минимального изменения.
    Хотелось бы обратить внимание на то, что вывод двоичного кода подразумевает еще и заполнение оставшихся разрядов единицами или нулями, в зависимости от значения u и v.

    Перейдем к оценке сложности приведенного алгоритма. Заметим, что при углублении в рекурсию значение u всегда уменьшается. То есть мы сделаем не больше n углублений для достижения какого-то двоичного кода. Всего таких кодов — . Получаем итоговую асимптотику . Это довольно грубая оценка, но она всяко лучше image, особенно при величине k стремящейся к n: алгоритм практически линеен.

    Легко заметить, что дерево вызовов будет двоичным, но не будет полным. Проведем параллель оценки сложности в терминах деревьев: каждый лист соответствует получению какого-то двоичного кода, а расстояние до листа в дереве не превышает n. Оценка говорит нам о том, что мы просто просуммировали верхнюю оценку длин — n — всех путей до листов. Но ведь многие из этих путей имеют длину меньше n, а еще больше путей пересекаются друг с другом. Это должно наталкивать нас на мысль, что асимптотика приведенного алгоритма на самом деле намного лучше.

    Точная оценка асимптотики — далеко не тривиальный факт, который можно найти в книге Э.Рейнгольда, Ю.Нивергельта и Н.Део «Комбинаторные алгоритмы. Теория и практика», либо попытаться доказать самому.

    На этом хотелось бы закончить статью. Спасибо за внимание и до скорых встреч.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 18

      +1
      Очень много формул. :( (4 утра, я не готов ещё вникать)
      Хотелось бы в конце вывод. что нам дают коды Грея?
        0
        Много формул потому что статья писалась преимущественно для хаба «Математика», но карма не позволила опубликовать статью в нем. Собственно здесь демонстрируется математический подход к составлению алгоритмов.

        Коды Грея дают нам элегантное решение двух описанных в статье комбинаторных задач. Это естественно не главное их применение. Если верить Википедии, то
        Сегодня коды Грея широко используются для упрощения выявления и исправления ошибок в системах связи, а также в формировании сигналов обратной связи в системах управления.

        Но это уже другая история.
          0
          Автор, не обижайтесь, но из-за такого изложения многие и не любят математику. Мне понравилось что вы последовательно расписали теоремы, и вам плюс за статью. Но плохо понятно их применение, и главное, зачем вы об этом пишите. Какие у вас мотивы? Если показать пример, как математически формулировать алгоритмы, то так и напишите. Хабр ж не лекториум, где профессор должен наболтать лекцию на 2, а студенты законспектировать.

          За статью спасибо.
            +1
            Если бы вместо формул я пытался бы изложить все в виде текста и картинок — статья бы вышла размером раз в 10 больше, как и время затраченное на ее написание. Да, придется напрячься, чтобы разобраться в написанном — но это так и в любой математической литературе.
            Что касается мотивов, то их несколько: показать математический подход к составлению алгоритмов, разобрать две полезные комбинаторные задачи, ну и чисто для себя — попрактиковаться в изложении материала.
              –2
              Вы не поняли. Против формул я ничего не имею, и очень даже за. Вопрос в том, что я ранее не встречался с кодами Грея. Мне интересно, но абсолютно непонятно откуда это и как применить. Даже в математических текстах есть abstract, где дается контекст проблемы.
                +1
                Разве этот самый abstract не есть решение приведенных в статье задач? А те места, где эти задачи всплывают уже являются узко-направленными(ниже в комментариях есть примеры), также как и изначальное применение таких кодов Греем. Это уже темы для другой статьи или соответствующей литературы, с которой я, увы, не знаком. Как и большинство теории в математике — до поры до времени непонятно где ее использовать, поэтому каждый сам найдет для себя применение этим знаниям.
              0
              А по мне так наоборот, математические доказательства тут излишни. Важнее сама идея, алгоритм, примеры
            +1
            Коды Грея используются, например, еще для кодирования вещественных чисел в бинарных строках. И при этом малое изменение вещественного числа приведет к малому изменению бинарного числа. Это используется, например, в алгоритмах оптимизации.
              +2
              код грея используется для повышения надежности аппаратуры, например, в устройствах-энкодерах или при передаче данных из одного клокового домена в другой (это когда данные фиксируются с частотой отличной от частоты на которой эти данные формируются: marsohod.org/index.php/ourblog/11-blog/190-meta1).

                0
                что нам дают коды Грея?

                Про весь спектр применения кодов Грея не скажу, упомяну лишь частное.
                При проектировании проектов на ПЛИС, например. Если создать большой счетчик на 20 триггерах, то при его инкрементировании обязательно возникают ситуации, когда сразу несколько триггеров меняют свое состояние:
                255: 0_1111_1111 => 256: 1_0000_0000
                при этом, триггеры переключаются в разное время и это очень плохо, стабильность такого счетчика оставляет желать лучшего и на больших частотах схема может работать неправильно.
                Если же использовать коды Грея, то такой проблемы не будет, тк в соседних состояниях отличным может быть только один разряд. Те только один триггер переключится, что исключает так называемую «гонку сигналов».
                Ну это простым языком)
                +1
                Программу для k-элементных подмножеств заставить работать удалось, но с большим трудом. Там нужно если v=0, то вместо последних u элементов массива печатать нули, а если v=u — то единицы. И не забывать, что индексы в массиве нумеруются с 1, а не с 0! Иначе выводится непонятно что.
                Работающая версия выглядит так:
                int X[100],N;
                void PrintX(int a,int b){
                  for(int i=0;i<N;i++) printf("%d",i<a ? X[i] : b);
                  printf("\n");
                }
                void Gray(int u,int v,int d){
                	if(u==v) PrintX(N-u,1);
                	else if(v==0) PrintX(N-u,0);
                	else{
                		X[N-u]=d;
                		Gray(u-1,v-d,0);
                		X[N-u]=1-d;
                		Gray(u-1,v+d-1,1);
                	}
                }
                  0
                  Я же написал справа от кода
                  Хотелось бы обратить внимание на то, что вывод двоичного кода подразумевает еще и заполнение оставшихся разрядов единицами или нулями, в зависимости от значения u и v.

                  тем самым предоставляя этот нюанс читателю.
                  0
                  А можно расширить до перебора всех подмножеств?
                    +1
                    Как-то так:
                    void SGray(char *s,int n){
                    	for(char c='0';n;c='1'){
                    		*--s=c;
                    		SGray(s,--n);
                    		*s^=1;
                    	}
                    	puts(s);
                    }
                    void SGray(int n,char *buf){
                    	buf[n]=0;
                    	SGray(buf+n,n);
                    }
                    +1
                    Кстати, есть ещё более простой способ генерации кодов Грея:
                    void Gray2(int n){
                    	for(int k=1<<n;--k>=0;){
                    		int s=k^(k>>1);
                    		for(int i=0;i<n;i++) printf("%d",(s>>i)&1);
                    		printf("\n");
                    	}
                    }
                    
                      +1
                      Если n <= 32 (или 64), можно использовать простую формулу (с вики):
                      gray(n) = n ^ (n >> 1)
                        0
                        n <= 32 это в смысле чтобы в регистр влезло. Если есть поддержка длинных чисел (например на Python), подойдет для любого n.

                        Правда, это формула для получения n-го члена последовательности, а не генерации всей последовательности.
                      0

                      В дополнение
                      Один из способов генерации 2D кода Грея (сигнального созвездия) для: QAM-4, QAM-16, QAM-64, QAM-256, ...


                      И если в университете вам показывали "метод зиг-зага", и вам было трудно его запомнить/понять/использовать, то этот способ будет более простым/наглядным/быстрым, чем "зиг-заг".


                      P.S. Возможно скоро кто-нибудь сделает видео получше (у меня плохо получаются real-time записи), и добавит в него QAM-64 и QAM-256. ...возможно.

                      Only users with full accounts can post comments. Log in, please.