зачем нужен код грея

Код Грея

Код Грея — двоичный код, иначе зеркальный код, он же код с отражением, в котором две «соседние» (в упорядоченном, то есть лексикографическом, наборе) кодовые комбинации различаются только цифрой в одном двоичном разряде. Иными словами, расстояние Хэмминга между соседними кодовыми комбинациями равно 1.

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

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

Название

Код Грея назван «рефлексивным» (отражённым) из-за того, что первая половина значений при изменении порядка эквивалентна второй половине, за исключением старшего бита. Старший бит просто инвертируется. При делении каждой новой половины пополам это свойство сохраняется (см. самоподобие).

Код назван в честь исследователя Фрэнка Грея, работавшего в лаборатории «Bell labs». Грей запатентовал (патент № 2632058) и впервые использовал этот код в своей импульсной системе связи.

Применения

Код Грея используется в передаче меняющихся цифровых сигналов в отсутствие тактового сигнала синхронизации (например, во многих видах датчиков). Представим себе, что код (обычный двоичный) перескакивает 3→4, или 0112 → 1002. Если из-за несовершенства считывателя мы прочитаем первый бит от 011, а остальные два — от 100, мы получим 0002=0 — число, далёкое от реальных значений. В коде Грея никаких посторонних значений не будет: перескок будет в одном разряде, 010G → 110G, и мы считаем либо старое 010G=3, либо новое 110G=4.

Если считыватель настолько медленный, что за время считывания показания несколько раз сменились, код Грея гарантирует, что ошибка будет невелика — меньше, чем реальное изменение сигнала. Например, если за время считывания показания сменились 010G=3 → 110G → 111G=5, то помимо этих трёх значений, можно получить 011G=2 — выходит ошибка на единицу.

Если датчик круговой (например, угловой энкодер), то ему приходится перескакивать и с максимума до нуля. Такой перескок (с 100G=7 до 000G=0) тоже изменяет один разряд.

Фрагмент главной страницы патента Грея

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

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

Широко применяются коды Грея и в теории генетических алгоритмов для кодирования генетических признаков, представленных целыми числами.

Код Грея используется для генерации сочетаний методом двери-вертушки.

В некоторых компьютерных играх (например, Duke Nukem 3D) для успешного прохождения уровня требуется подобрать нужную комбинацию положений нескольких переключателей. Никаких подсказок нет, надо просто перебрать все комбинации. Для минимизации числа переключений при переборе вариантов следует использовать код Грея. Например, если переключателей три, пробуем их в порядке 000, 001, 011, 010, 110…

Сложные датчики, требующие синхросигнала, отходят от кода Грея и работают в обычном двоичном.

Алгоритмы преобразования

Преобразование двоичного кода в код Грея

Коды Грея легко получаются из двоичных чисел путём побитовой операции «Исключающее ИЛИ» с тем же числом, сдвинутым вправо на один бит и в котором старший разряд заполняется нулём. Следовательно, i-й бит кода Грея Gi выражается через биты двоичного кода Bi следующим образом:

где ⊕ — операция «исключающее ИЛИ»; биты нумеруются справа налево, начиная с младшего.

Ниже приведён алгоритм преобразования из двоичной системы счисления в код Грея, записанный на языке C:

unsigned int grayencode(unsigned int g) < return g ^ (g >> 1); >

Однако, необходимо помнить, что данный алгоритм будет работать правильно, если компилятор реализует нециклический логический сдвиг (например, стандарт языка C не уточняет тип сдвига для знаковых чисел, но для unsigned типов поддержка гарантируется).

Тот же самый алгоритм, записанный на языке Паскаль:

function BinToGray(b: integer): integer; begin BinToGray := b xor (b shr 1) end;

Пример: преобразовать двоичное число 10110 в код Грея.

Преобразование кода Грея в двоичный код

Обратный алгоритм — преобразование кода Грея в двоичный код — можно выразить рекуррентной формулой

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

где N — число битов в коде Грея (для увеличения быстродействия алгоритма в качестве N можно взять номер старшего ненулевого бита кода Грея); знак ⊕ означает суммирование при помощи операции «исключающее ИЛИ», то есть

Действительно, подставив в формулу выражение для i-го бита кода Грея, получим

Здесь предполагается, что бит, выходящий за рамки разрядной сетки ( B N + 1 > ), равен нулю.

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

unsigned int graydecode(unsigned int gray) < unsigned int bin; for (bin = 0; gray; gray >>= 1) < bin ^= gray; >return bin; >

Тот же самый алгоритм, записанный на языке Паскаль:

function GrayToBin(b: integer): integer; var g: integer; begin g := 0; while b > 0 do begin g := g xor b; b := b shr 1; end; GrayToBin := g; end;

Пример: преобразовать код Грея 11101 в двоичный код.

Быстрое преобразование 8/16/24/32-разрядного значения кода Грея в двоичный код на языке C (Примечание: исходный код Грея является составным. Где каждая тетрада бит является отдельным числом и закодирована отдельно. Этот код не является полноценным кодом Грея. И правило изменения одного бита при переходе к новому числу сохраняется только в пределах каждой четвёрки. Например при переходе от 0x0F к 0x10 изменяются одновременно два бита так как мы имеем изменение двух тетрад 0->1 и F->0):

Простой способ преобразования двоичного числа в код Грея выполняется по правилу: старший разряд записывается без изменения, каждый следующий символ кода Грея нужно инвертировать, если в натуральном коде перед этим была получена «1», и оставить без изменения, если в натуральном коде был получен «0».

Генерация кодов Грея

Код Грея для n бит может быть рекурсивно построен на основе кода для n-1 бит путём переворачивания списка бит (то есть записыванием кодов в обратном порядке), конкатенации исходного и перевёрнутого списков, дописывания нулей в начало каждого кода в исходном списке и единиц — в начало кодов в перевёрнутом списке. Так, для генерации списка для n = 3 бит на основании кодов для двух бит необходимо выполнить следующие шаги:

Ниже представлен один из алгоритмов создания последовательности кода Грея заданной глубины, записанный на языке Perl:

Необычные вариации кода Грея

Сбалансированный код Грея

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

0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1

Здесь в 4-битном коде каждый разряд переключается четырежды. В 5-битном коде такое невозможно, приходится переключать один бит 8 раз, остальные — по 6.

Однодорожечный код Грея

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

Двухбитный код Грея является однодорожечным, это можно увидеть в компьютерной мыши — как в шариковом механизме старых мышей, так и в колесе прокрутки новых. Два датчика стоят в разных точках одной дорожки. Если довести эту систему до крайности — половина диска «чёрная», половина «белая», и датчики стоят на 90° друг относительно друга — то можно узнать абсолютное положение диска с дискретностью в 90°.

Для кодов Грея более высокой разрядности это не так, приходится увеличивать количество дорожек, это делает датчик громоздким и дорогим. Поэтому, если возможно, обходятся двумя дорожками — одна для двухбитного кода Грея, и одна — позиция нуля. Однако существуют коды, где дорожка именно одна, правда, все 2n позиций так закодировать невозможно. Для 5 бит рекорд — 30 позиций, для 9 — 360.

Двухмерный код Грея

Используется в квадратурной модуляции сигналов. Соседние точки «созвездия» отличаются одним битом, диагональные — двумя.

Источник

Коды Грея

Код назван в честь Фрэнка Грея, который в 1947-ом году получил патент на «отражённый двоичный код».

Содержание

Алгоритм построения [ править ]

Существует несколько видов кода Грея, самый простой из них — так называемый зеркальный двоичный код Грея. Строится он так:

Псевдокод [ править ]

Доказательство правильности работы алгоритма [ править ]

Таким образом, этот код — код Грея. Индукционное предположение доказано, алгоритм работает верно.

Существует ещё несколько видов кода Грея — сбалансированный код Грея, код Баркера-Грея, одноколейный код Грея. [1] Кроме того, коды Грея используются для упорядочения перестановок.

Явная формула для получения зеркального двоичного кода Грея [ править ]

Для кода длиной [math]1[/math] бит утверждение проверяется непосредственно.

Для любого [math]x \lt 2^n[/math] выполняется [math]\enspace L_x = 0M_x[/math] и, по условию, равно

[math]L_x = 0(x_x_ \dots x_ <0>\oplus 0x_x_ \dots x_<1>)[/math] раскрыв скобки, получим новое выражение [math]L_x[/math] :

[math]= 0x_x_ \dots x_ <0>\oplus 00x_x_ \dots x_<1>[/math] что равно (второе слагаемое равно первому, побитово сдвинутого вправо.)

[math]= x \oplus (\lfloor x / 2 \rfloor)[/math]

[math]L_x = 1(\overline x_ \dots x_<0>> \oplus 0 \overline x_ \dots x_<1>>)[/math] что по свойству xor ( [math]\neg x \oplus \neg y = x \oplus y[/math] ) равно

[math]= 1(\overline >x_ \dots x_ <0>\oplus 0x_x_ \dots x_<1>)[/math] или (все по тому же свойству)

[math]= 1(x_x_ \dots x_ <0>\oplus 1x_x_ \dots x_<1>)[/math] раскрыв скобки, получим

[math]= 1x_x_ \dots x_ <0>\oplus 01x_x_ \dots x_<1>[/math] откуда получаем, зная из условия, что старший разряд [math]L_x[/math] равен [math]1[/math]

[math]= x_x_x_ \dots x_ <0>\oplus 0x_x_x_ \dots x_<1>[/math] что, аналогично первому пункту, равно

[math]= x \oplus (\lfloor x / 2 \rfloor)[/math]

Таким образом, шаг индукции доказан, следовательно, теорема верна.[math]\triangleleft[/math]

Сбалансированный код Грея [ править ]

Несмотря на то, что зеркальный двоичный код Грея полезен во многих случаях, он не является оптимальным в некоторых ситуациях из-за отсутствия «однородности». В сбалансированном коде Грея, количество изменений в различных координатных позициях сделаны максимально приближенными настолько, насколько это возможно.

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

Однодорожечный код Грея [ править ]

Еще один вид кода Грея — это однодорожечный код Грея, разработанный Спеддингом и уточнен Хильтгеном, Патерсоном и Брандестини.

Чтобы снизить уровнень шума различных контактов не переключаясь в тот же момент времени, один датчик предпочтительно устанавливает дорожки так, что выход данных от контактов находится в коде Грея. Чтобы получить высокую угловую точность, нужно много контактов; для достижения точности хотя бы в [math]1[/math] градус нужно, по крайней мере, [math]360[/math] различных позиций на оборот, который требует минимум [math]9[/math] бит данных, и тем самым такое же количество контактов.

Не путать с цепными кодами, получаемых циклическим сдвигом.

Применение [ править ]

Фрэнк Грей изобрел метод для преобразования аналоговых сигналов в отраженные двоичные кодовые группы с использованием аппарата на основе вакуумной трубки. Способ и устройство были запатентованы в 1953 году, а код получил название код Грея. «PCM трубка» — аппарат, запатентованный Греем, был сделан Раймондом У. Сирсом из (англ.) Bell Labs, работая с Греем и Уильямом М. Гудоллом.

Таким образом, высока вероятность того, что при кодировании с помощью кода Грея в случае возникновения ошибки ошибочным будет только один из [math]k = \log_2 M[/math] переданных битов.)

Задача о Ханойских башнях [ править ]

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Код Грея

Из Википедии — свободной энциклопедии

Код Гре́я — двоичный код, иначе зеркальный код, он же код с отражением, в котором две «соседние» (в упорядоченном, то есть лексикографическом, наборе) кодовые комбинации различаются только цифрой в одном двоичном разряде. Иными словами, расстояние Хэмминга между соседними кодовыми комбинациями равно 1.

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

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

Источник

Зачем нужен код грея

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

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

Содержание

[править] Название

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

Код получил имя исследователя лабораторий Bell Labs Фрэнка Грея. Он запатентовал и использовал этот код в своей импульсной системе связи (патент № 2632058).

[править] Применения

Использование кодов Грея основано прежде всего на том, что он минимизирует эффект ошибок при преобразовании аналоговых сигналов в цифровые (например, во многих видах датчиков).

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

Широко применяются коды Грея и в теории генетических алгоритмов [1] для кодирования генетических признаков, представленных целыми числами.

[править] Алгоритмы преобразования

[править] Преобразование двоичного кода в код Грея

Коды Грея легко получаются из двоичных чисел путём побитовой операции «Исключающее ИЛИ» с тем же числом, сдвинутым вправо на один бит. Следовательно, i-й бит кода Грея G i выражается через биты двоичного кода B i следующим образом:

где – операция «исключающее ИЛИ»; биты нумеруются справа налево, начиная с младшего.

Ниже приведён алгоритм преобразования из двоичной системы счисления в код Грея, записанный на языке C:

Однако, необходимо помнить, что данный алгоритм будет работать правильно, если компилятор реализует циклический логический сдвиг (стандарт языка C не уточняет тип сдвига). Тот же самый алгоритм, записанный на языке Паскаль:

Пример: преобразовать двоичное число 10110 в код Грея.

[править] Преобразование кода Грея в двоичный код

Обратный алгоритм – преобразование кода Грея в двоичный код – можно выразить рекуррентной формулой

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

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

где N – число битов в коде Грея (для увеличения быстродействия алгоритма в качестве N можно взять номер старшего ненулевого бита кода Грея); знак означает суммирование при помощи операции «исключающее ИЛИ», то есть

Действительно, подставив в формулу выражение для i-го бита кода Грея, получим

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

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

Тот же самый алгоритм, записанный на языке Паскаль:

Пример: преобразовать код Грея 11101 в двоичный код.

Быстрое преобразование 8/16/24/32-разрядного значения кода Грея в двоичный код на языке BlitzBasic:

Простой способ преобразования двоичного числа в код Грея выполняется по правилу: старший разряд записывается без изменения, каждый следующий символ кода Грея нужно инвертировать, если в натуральном коде перед этим была получена «1», и оставить без изменения, если в натуральном коде был получен «0».

[править] Генерация кодов Грея

Код Грея для n бит может быть рекурсивно построен на основе кода для n–1 бит путём переворачивания списка бит (то есть записыванием кодов в обратном порядке), конкатенации исходного и перевёрнутого списков, дописывания нулей в начало каждого кода в исходном списке и единиц — в начало кодов в перевёрнутом списке. Так, для генерации списка для n = 3 бит на основании кодов для двух бит необходимо выполнить следующие шаги:

Ниже представлен один из алгоритмов создания последовательности кода Грея заданной глубины, записанный на языке Perl:

Рекурсивная функция построение кода Грея на языке C:

Быстрое преобразование 8/16/24/32-разрядного бинарного кода в код Грея на языке BlitzBasic:

Источник