что такое код грея

Что такое код грея

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

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

Содержание

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

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

Код получил имя исследователя лабораторий 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:

Источник

Код грея

Код Грея, рефлексный двоичный код — двоичная система нумерования, в которой два соседних значения различаются только в одном двоичном разряде.

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

Содержание

Название

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

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

Применения

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

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

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

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

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

обратный алгоритм (преобразование из кода Грея в двоичную систему счисления):

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

См. также

Примечания

Библиография

Ссылки

Полезное

Смотреть что такое «Код грея» в других словарях:

код Грея — Циклический двоичный код. [http://www.morepc.ru/dict/] Тематики информационные технологии в целом EN Gray code … Справочник технического переводчика

Код Грея — 2 битный код Грея 00 01 11 10 3 битный код Грея 000 001 011 010 110 111 101 100 4 битный код Грея 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 Код Грея система счисления, в которой два соседних значения… … Википедия

код Грея — Gray kodas statusas T sritis automatika atitikmenys: angl. Gray code vok. Gray Code, m rus. код Грея, m pranc. code de Gray, m ryšiai: sinonimas – Grėjaus kodas … Automatikos terminų žodynas

код Грея — n мерная двоичная система в виде графа. Коды Грея задаются так, чтобы двоичные слова отличались на расстояние Хемминга, равное единице … Словарь лингвистических терминов Т.В. Жеребило

Код Джонсона — Код Джонсона двоичная система счисления, в которой два соседних значения различаются только в одном двоичном разряде. Принципы формирования кода Джонсона 1. Код Джонсона является кодом с избытком, то есть для числа разрядов больше 2 в коде… … Википедия

Код Грэя — 2 битный код Грея 00 01 11 10 3 битный код Грея 000 001 011 010 110 111 101 100 4 битный код Грея 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 Код Грея, рефлексный двоичный код двоичная система нумерования, в… … Википедия

Коды грея — 2 битный код Грея 00 01 11 10 3 битный код Грея 000 001 011 010 110 111 101 100 4 битный код Грея 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 Код Грея, рефлексный двоичный код двоичная система нумерования, в… … Википедия

Преобразователь угол-код — Датчик угла Датчик угла или преобразователь угол код, также называемый энкодер устройство, предназначенное для преобразования угла поворота вращающегося объекта (вала) в электрические сигналы, позволяющие определить угол его поворота. Широко… … Википедия

рефлексный код — код Грея циклический код — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы код Греяциклический код EN reflected code … Справочник технического переводчика

Ханойская башня — Модель Ханойской башни с восемью дисками Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются … Википедия

Источник

Код Грея

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

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

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

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

Источник

Коды Грея

Код назван в честь Фрэнка Грея, который в 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] переданных битов.)

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

Источник

Коды грея

Код Грея, рефлексный двоичный код — двоичная система нумерования, в которой два соседних значения различаются только в одном двоичном разряде.

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

Содержание

Название

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

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

Применения

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

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

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

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

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

обратный алгоритм (преобразование из кода Грея в двоичную систему счисления):

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

См. также

Примечания

Библиография

Ссылки

Полезное

Смотреть что такое «Коды грея» в других словарях:

Код Грея — 2 битный код Грея 00 01 11 10 3 битный код Грея 000 001 011 010 110 111 101 100 4 битный код Грея 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 Код Грея система счисления, в которой два соседних значения… … Википедия

Код грея — 2 битный код Грея 00 01 11 10 3 битный код Грея 000 001 011 010 110 111 101 100 4 битный код Грея 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 Код Грея, рефлексный двоичный код двоичная система нумерования, в… … Википедия

код Грея — n мерная двоичная система в виде графа. Коды Грея задаются так, чтобы двоичные слова отличались на расстояние Хемминга, равное единице … Словарь лингвистических терминов Т.В. Жеребило

Код Грэя — 2 битный код Грея 00 01 11 10 3 битный код Грея 000 001 011 010 110 111 101 100 4 битный код Грея 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 Код Грея, рефлексный двоичный код двоичная система нумерования, в… … Википедия

Ханойская башня — Модель Ханойской башни с восемью дисками Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются … Википедия

Сигнальное созвездие — (англ. constellation diagram) представление манипулированных радиосигналов на комплексной плоскости. Содержание 1 Описание 2 Решётчатая кодированная модуляция … Википедия

СИМВОЛИЗМ — худож. направление, сложившееся в зап. европ. культуре в к. 60 нач. 70 х гг. 19 в. (первоначально в лит ре, затем и в других видах искусства изобразит., муз., театральном) и вскоре включившее в себя иные явления культуры философию,… … Энциклопедия культурологии

Microsoft Research — (MSR) подразделение корпорации Microsoft, созданное в 1991 году для исследования различных вопросов и тем в области информатики. Здесь в данное время работают обладатели премии Тьюринга Чарльз Хоар и Батлер Лэмпсон, обладатель Филдсовской… … Википедия

Приютино (усадьба) — Запрос «Приютино» перенаправляется сюда; см. также другие значения. Микрорайон Приютино … Википедия

Источник