код грея для чайников
Монотонный код Грея
Монотонный код Грея преимущественно используется в теории связанных сетей, например для минимизации ожидания линейным массивом процессоров. [1]
Содержание
Алгоритм построения [ править ]
Для начала определим такое понятие, как вес двоичного кода, им будет являтся количество [math]1[/math] в данном двоичном коде. Очевидно, что нельзя построить код Грея в котором бы вес всегда возрастал. Неплохим решением этой проблемы будет обход всех кодов со смежными с данным весами.
Чтобы лучше разобратся в том, как сторится этот код и работает перестановка [math]\pi[/math] следует рассмотреть таблицу ниже.
| [math]P_ | [math]j = 0[/math] | [math]j = 1[/math] | [math]j = 2[/math] | [math]j = 3[/math] |
|---|---|---|---|---|
| [math]n = 1[/math] | [math]0, 1[/math] | |||
| [math]n = 2[/math] | [math]00, 01[/math] | [math]10, 11[/math] | ||
| [math]n = 3[/math] | [math]000, 001[/math] | [math]100, 110, 010, 011[/math] | [math]101, 111[/math] | |
| [math]n = 4[/math] | [math]0000, 0001[/math] | [math]1000, 1100, 0100, 0110, 0010, 0011[/math] | [math]1010, 1011, 1001, 1101, 0101, 0111[/math] | [math]1110, 1111[/math] |
Псевдокод [ править ]
yield — аналог return только для функций-генераторов. То есть генераторы это тоже итерируемые объекты, но прочитать их можно лишь один раз. Это связано с тем, что они не хранят значения в памяти, а генерируют их на лету.
С конструкциями типа (0,) или (1,) все проще. Используя ее совместно с yield мы можем изменять наш генерируемый объект. Например, yield (0,) допишет к генерируемому объекту (в нашем случае кортежу (англ. tuple)) [math]0[/math] в начало.
Инкрементные (квадратурные) и абсолютные энкодеры. Код Грея.
С помощью одного светодиода и одного фототранзистора можно измерять скорость вращения или перемещение без учета направления вращения. Такой датчик сложно назвать энкодером, так как, при реверсе нет возможности точно определить положение или направление вращения. Это просто датчик скорости вращения.
Конструктивное исполнение датчиков вращения:
Энкодеры подразделяются на инкрементальные энкодеры (квадратурные энкодеры) и абсолютные энкодеры. Инкрементальные энкодеры, формируют импульсы, по которым принимающее устройство определяет текущее координаты путем подсчета числа импульсов. Для привязки системы отсчета к началу координат инкрементальные датчики перед началом работы должны быть установлены в начальное положение.
В старых компьютерных мышках, в которых применялся шарик, присутствовали два аналогичных энкодера. В них использовались специальные фототранзисторы «2 в одном»:
В нашей конструкции мы используем два отдельных фототранзистора:
Иногда требуется знать положение сразу после включения устройства. Т.е. нет технической возможности вывести устройство в исходное положение и затем по количеству «кликов» оценить положение.
Исходный растр диска:
разбит на два диска:
Между дисками установлена двусторонняя плата со светодиодами, за дисками фототранзисторы. Таким образом были уменьшены габариты.
Внимательный читатель мог заметить, что растр кодового диска абсолютного энкодера не соответствует обычному двоичному коду. В энкодерах применяют специальный код Грея.
Что такое код Грея? Представьте себе некоторое устройство, скажем датчик положения, которое выдает положение в двоичном виде по трем проводам. На выходе могут быть следующие комбинации в двоичном коде:
000 001 010 011 100 101 110 111
Код Грея
Из Википедии — свободной энциклопедии
| Число | Бинарный код | Код Грея |
|---|---|---|
| 0 | 0000 | 0000 |
| 1 | 0001 | 0001 |
| 2 | 0010 | 0011 |
| 3 | 0011 | 0010 |
| 4 | 0100 | 0110 |
| 5 | 0101 | 0111 |
| 6 | 0110 | 0101 |
| 7 | 0111 | 0100 |
| 8 | 1000 | 1100 |
| 9 | 1001 | 1101 |
| 10 | 1010 | 1111 |
| 11 | 1011 | 1110 |
| 12 | 1100 | 1010 |
| 13 | 1101 | 1011 |
| 14 | 1110 | 1001 |
| 15 | 1111 | 1000 |
Код Гре́я — двоичный код, иначе зеркальный код, он же код с отражением, в котором две «соседние» (в упорядоченном, то есть лексикографическом, наборе) кодовые комбинации различаются только цифрой в одном двоичном разряде. Иными словами, расстояние Хэмминга между соседними кодовыми комбинациями равно 1.
Наиболее часто на практике применяется рефлексивный двоичный код Грея, хотя в общем случае существует бесконечное множество кодов Грея со значениями цифр в разрядах, взятых из различных алфавитов. В большинстве случаев, под термином «код Грея» понимают именно рефлексивный бинарный код Грея.
Изначально предназначался для защиты от ложного срабатывания электромеханических переключателей. Сегодня коды Грея широко используются для упрощения выявления и исправления ошибок в системах связи, а также в формировании сигналов обратной связи в системах управления.
Задача о ранце и код Грея
Не так давно на Хабре была статья «Коды Грея и задачи перебора». Статья эта скорее, математическая, нежели программистская, и мне, как простому программисту, читать её было невыносимо тяжело. Но сама тема мне знакома, поэтому я решил описать её своим взглядом, а так же рассказать о том, как использовал её в решении задачи о ранце.
КДПВ: задача о ранце на живом примере
Предыстория
Всё началось 10 лет назад, когда я учился в девятом классе. Я случайно подслушал разговор учителя по информатике, рассказывающего задачку кому-то из старших: дан набор чисел, и ещё одно число — контрольное. Надо найти максимальную сумму чисел из набора, которая не превышала бы контрольное число.
Задача почему-то запала мне в душу. Вернувшись домой, я быстро накатал решение: наивный перебор всех возможных сумм с выбором наилучшего. Сочетания я получал, перебирая все N-разрядные двоичные числа и беря суммы тех исходных чисел, которым соответствуют единицы. Но я с огорчением обнаружил, что при количестве элементов начиная где-то с 30, программа работает очень долго. Оно и не удивительно, ведь время работы такого алгоритма — n*2 n (количество сочетаний, умноженное на длину суммы).
Прошло 5 лет. Я успел закончить школу и поступить в университет, но эта задача по-прежнему была со мной. Один раз, листая книгу «Алгоритмические трюки для программистов» (Hacker’s Delight / Henry S. Warren Jr.), я наткнулся на описание кода Грея: это последовательность двоичных чисел, каждое из которых отличается от предыдущего только одним битом. «Стоп!» — подумал я — «Это означает… Да! Это означает, что в той самой задаче на каждом шаге перебора можно не считать сумму целиком, а лишь добавлять или вычитать одно число». И я тут же углубился в изучение темы.
Построение кода Грея
Код Грея можно построить для числа любой разрядности. Для одного разряда он очевиден:
Чтобы добавить второй разряд, можно к этой последовательности дописать такую же задом наперёд
и ко второй половине дописать единицы:
Аналогично для трёх разрядов:
Такой код, полученный отражением кода меньшей разрядности, называется рефлексным (отражённым) кодом Грея. Бывают и другие последовательности, но на практике обычно используется именно эта.
Этот код назван в честь Фрэнка Грея, который изобрёл ламповый АЦП, выдававший цифровой сигнал именно в этом коде. При небольших изменениях уровня входного сигнала цифровой выход мог измениться только в одном бите, и этим исключались резкие скачки из-за неодновременного переключения битов.
Иллюстрация патента Фрэнка Грея
Самое наглядное применение кода Грея — в датчиках угла поворота. Датчик, аналогичный тем, что был в старых механических мышах, но определяющий не относительное смещение, а абсолютное значение угла. Для этого на каждый датчик нужно несколько оптопар и несколько щелевых решёток. Причём каждое следующее положение датчика должно отличаться от предыдущего только состоянием одного бита, иначе на границах возможно несинхронное переключение битов, и следственно — резкие скачки в показаниях прибора. Здесь видна любопытная особенность кода Грея: последнее число также отличается от первого одним битом, поэтому его можно «закольцевать».
Датчик абсолютного угла поворота. Оптические щели расположены в соответствии с кодом Грея
Применение в задаче о ранце
Но вернёмся к задаче о ранце. Стандартная формула даёт нам код Грея по номеру:
По ней мы можем только посчитать сумму все нужных элементов. А мы собирались на каждой итерации добавлять или вычитать одно значение, верно? Значит, нам нужно получить номера изменяемых битов. Для многоразрядных чисел эти номера будут такими:
Ничего не напоминает? Это номер бита, который мы устанавливаем в единицу, когда просто перечисляем обычные двоичные числа. Или иначе — номер младшей единицы в двоичном числе. Эта операция называется find first set и в большинстве процессоров существует в виде отдельной инструкции. Visual C++ предоставляет эту инструкцию в виде функции _BitScanForward.
Итак, теперь мы готовы написать программу, решающую задачу о ранце через код Грея. Сформулируем задачу так:
В файле input.txt в первой строке указана вместимость рюкзака, а в остальных строках — размеры вещей. В консоль нужно вывести максимальную загрузку рюкзака и размеры выбранных вещей. Проверку корректности ввода и пр. — нафиг.
Мы будем хранить битовую маску использованных вещей, и по мере необходимости добавлять или убирать одну из них. Чтобы обойтись int-ами, ограничим количество вещей (и используемых бит) тридцатью одной.
Прощу прощения за возможные шероховатости; к сожалению, C++ уже давно не мой профильный язык.
Работает действительно быстрее, чем сборка с нуля всех сумм, разница заметна уже при 20 числах, а при 30-и я так и не дождался выполнения наивного алгоритма, в то время как новый вариант выполняется за 7 секунд. Впрочем, учитывая экспоненциальную сложность, это совсем не мало: для 50 чисел использовать этот алгоритм уже нет смысла. К сожалению, любой точный алгоритм будет работать не быстрее, чем за 2 n ; быстрее возможно только приблизительное решение. (Апдейт: в некоторых случаях динамическое программирование и meet-in-the-middle решают задачу быстрее; подробности см. в комментариях.)
Наверное, именно поэтому я обречён до конца жизни нести свой ранец, пытаясь ускорить эту программу. Я уже однажды переписывал цикл на ассемблере, получив небольшой прирост в скорости, а сейчас даже подумываю сделать многопоточную версию программы. Вам же остаётся лишь мне посочувствовать. 🙂
Код ГРЕЯ в многопозиционных видах модуляций
При многопозиционных видах модуляций (М-ФМн и М-КАМ) выбор положения символа в сигнальном созвездии влияет на вероятность битовой ошибки.
Рассмотрим положение символов в сигнальном созвездии для четверичной фазовой модуляции. Для 4-ФМн каждый символ представляется 2 битами. Назначим каждому символу по часовой стрелке комбинацию бит в обычной двоичной системе счисления: <00; 01; 10; 11>.
При воздействии шумов могут возникать ошибки, которые появляются в результате того, что был принят не тот символ, который передавался. Вероятность перепутать один символ с другим (т.е. допустить ошибку при приёме) тем больше, чем ближе символы на созвездии находятся друг к другу.
Пример кодирования двоичного кода
Рассмотрим пример по рисунку выше. Пусть был передан символ S0, который кодирован битами <00>. Из-за воздействия шумов наиболее частой ошибкой будет прием символа S1 или S3, т.к. они расположены ближе, чем символ S2. Ошибочный прием символа S2 также будет, но такие ошибки будут происходить реже.
Если возникла ошибка, при которой был принят символ S1 <01>вместо S0 <00>, то будет потерян всего 1 бит информации, т.к. символ S1 отличается от символа S2 на один бит. Однако если возникла ошибка, при которой был принят символ S3 <11>, то будет потеряно уже 2 бита информации.
Возникает вопрос, можно ли символам назначить такие комбинации бит, чтобы любые два соседних символа отличались не более чем на один бит. Ответ на этот вопрос положительный – нужно воспользоваться кодом Грея.
Код Грея определение
В таблице ниже представлен код Грея для 2-х и 3-х бит.
Код Грея образуется путем перестановки некоторых кодовых комбинаций таким образом, что любые две соседние кодовые комбинации отличаются друг от друга на один бит.
Если символы 4-ФМн закодировать кодом Грея, т.е. символам S0 S1 S2 S3 назначить комбинацию бит <00; 01; 10; 11>соответственно, то любые два соседних символа будут отличаться друг от друга не более чем на один бит. В этом случае, если произойдет любая ошибка, где будут перепутаны два соседних символа, будет потерян только один бит информации.
Код Грея применим в том случае, когда у каждого символа в созвездии только два соседа, т.е. близлежащих символов. Это случай четверичной и восьмеричной фазовой манипуляции.
Если рассматривать созвездие амплитудно-фазовых модуляций, в том числе КАМ, то видно, что у каждого символа более двух соседей. В этом случае нельзя придумать такой код, при котором все близлежащие символы отличались бы только на один бит. Но и в этом случае играет большую роль, каким символам, какие кодовые комбинации назначаются. Те символы, которые расположены ближе всего друг к другу, должны отличаться на минимальное количество бит, в идеальном случае на один.
Если невозможно сделать так, чтобы все соседи отличались на один бит, тогда допускается отличие на два бита, и т.д. Чем дальше символы в созвездии располагаются друг от друга, тем реже возникает ошибка, при которой эти символы будут перепутаны, следовательно, тем на большее количество бит они могут отличаться.
Задача назначения битовых комбинаций каждому символу в созвездии сводится к минимизации среднего количества битовых ошибок при фиксированном отношении сигнал/шум.