Что такое код graystring

Содержание

Код Грея

Всем доброго вечера) у меня такая просьба, помогите написать программу по коду Грея, чтобы пользователь сам ввел число в диапозоне от -100 до 100, ну или какой получитсья, и что бы введенное число было представленно в двоичном коде и следом в коде грея. примерно так 5 0101 0111

23.01.2011, 21:29

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

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

Код Грея
Написать блоки преобразования числа в код Грея и обратно (результатом программы должны являться 2.

Код Грея
Почему Код Грея более помехозащищен, чем обычный двоичный код?

Коды Грея

Определение:
Код Грея (англ. Gray code) — такое упорядочение [math]k[/math] -ичных (обычно двоичных) векторов, что соседние вектора отличаются только в одном разряде.

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

Содержание

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

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

Для получения кода длины [math]n[/math] производится [math]n[/math] шагов. На первом шаге код имеет длину [math]1[/math] и состоит из двух векторов [math]0[/math] и [math]1[/math] . На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается [math]0[/math] , а ко второй [math]1[/math] . С каждым шагом длина векторов увеличивается на [math]1[/math] , а их количество — вдвое. Таким образом, количество векторов длины [math]n[/math] равно [math]2^n.[/math]

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

  • [math]\mathtt[/math] — двумерный массив типа boolean, в котором [math]\mathtt[/math] — [math]b[/math] -ый бит в [math]a[/math] -ом коде Грея,
  • [math]\mathtt

    [/math] — Счетчик количества уже имеющихся кодов,

  • [math]\mathtt[/math] — Показывает количество кодов в [math](a-1)[/math] -м коде Грея.

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

  • на первом шаге код отвечает условиям
  • предположим, что код, получившийся на [math]i[/math] -ом шаге, является кодом Грея
  • тогда на шаге [math]i + 1[/math] : первая половина кода будет корректна, так как она совпадает с кодом с шага [math]i[/math] за исключением добавленного последнего бита [math]0[/math] . Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит [math]1[/math] . На стыке: первые [math]i[/math] бит совпадают в силу зеркальности, последние различны по построению.

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

Этот алгоритм можно обобщить и для [math]k[/math] -ичных векторов. Также известен алгоритм преобразования двоичного кода в код Грея.

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

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

Доказательство: [math]\triangleright[/math]

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

Пусть существует зеркальный двоичный код Грея [math]M[/math] длины [math]n[/math] , для которого выполнено, что для любого [math]i[/math] выполняется [math]е\enskip M_i = i \oplus (\lfloor i / 2 \rfloor)[/math]

Обозначим за [math]L[/math] код длины [math]n + 1[/math] , полученный из [math]M[/math] описанным выше алгоритмом. Тогда:

Для любого [math]x \lt 2^n[/math] выполняется [math]\enskip 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]x \geqslant 2^n[/math] выполняется [math]\enskip L_x = 1[/math] [math]M_y[/math] , где [math]y = 2^ — 1 — x = \neg x[/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]G[/math] — это [math]R[/math] -ичный полный цикл Грея, имеющий последовательность перехода [math](\delta_k)[/math] , [math]\delta_k = i[/math] , для [math]k = 0 \dots n[/math] если в коде Грея [math]i[/math] -й и [math](i+1)[/math] биты различны и [math]n[/math] — кол-во таких различий; отсчёты переходов (спектры) [math]G[/math] являются наборами целых чисел, определенных как [math]\lambda_k = |\< j \in \mathbb_ : \delta_j = k \>| \,[/math] для [math] k \in \mathbb_R[/math] .

Код Грея является однородным или равномерно сбалансированным, если все его отсчёты переходов равны, и в этом случае у нас есть [math]\lambda_k = R^n / n[/math] для всех [math]k[/math] . Ясно, что при [math]R = 2[/math] , такие коды существуют только при [math]n = 2[/math] . В противном случае, если [math]R^n[/math] не делится на [math]n[/math] равномерно, то можно построить сбалансированные коды Грея, где каждый отсчёт перехода либо [math]\lfloor R^n / n \rfloor [/math] либо [math] \lceil R^n / n \rceil[/math] .

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

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

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

Однодорожечный код Грея является циклическим списком уникальных двоичных кодировок длины [math]n[/math] так, что два последовательных слова отличаются ровно в одной позиции, и когда список рассматривается как [math]P_[/math] матрица, каждая колонка — это циклический сдвиг первого столбца. Название происходит от их использования датчиками вращения, где количество дорожек в настоящее время измеряется с помощью контактов, в результате для каждой дорожки на выход подаётся [math]0[/math] или [math]1[/math] .

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

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

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

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

  • В технике коды Грея используются для минимизации ошибок при преобразовании аналоговых сигналов в цифровые (например, в датчиках-энкодерах [2] ).

В частности, коды Грея и были открыты в связи с этим применением. (Код Грея — это код преобразования бинарных символов в [math]M[/math] -арные, такие, что двоичные последовательности, соответствующие соседним символам (сдвигам фаз), отличаются только одним битом. Обычная бинарная кодировка сравнивается с кодировкой Грея. При появлении ошибки в [math]M[/math] -арном символе наиболее вероятными являются ближайшие соседние символы, отличающиеся от переданного лишь одним битом, если используется кодировка Грея.

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

  • Коды Грея используются для кодирования номера дорожек в жёстких дисках.
  • Коды Грея широко применяются в теории генетических алгоритмов [3] для кодирования генетических признаков, представленных целыми числами.
  • Коды Грея используются в Картах Карно [4] (при передаче в карту переменные сортируются в код Грея).
  • Алгоритм модуляции 2B1Q (англ. 2 Binary 1 Quandary) [5]
  • Код Грея можно использовать также и для решения следующей задачи [6] :

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

Задача:
Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

Пусть [math]n[/math] — количество дисков. Начнём с кода Грея длины [math]n[/math] , состоящего из одних нулей (т.е. [math]G(0)[/math] ), и будем двигаться по кодам Грея (от [math]G(i)[/math] переходить к [math]G(i+1)[/math] ).

Поставим в соответствие каждому [math]i[/math] -ому биту текущего кода Грея [math]i[/math] -ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита [math]i[/math] как перемещение [math]i[/math] -го диска. То есть, будем понимать переход от последовательности [math]101[/math] к [math]100[/math] как перемещение [math]0[/math] -го диска на свободное место, а от [math]010[/math] к [math]110[/math] — как перемещение [math]2[/math] -го диска на свободное место.

Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для самого маленького диска всегда есть две свободные позиции, потому что он самый маленький, его можно положить сверху на любой диск. Если диск не самый маленький, то для него может быть не более одной свободной позиции. Допустим, что для него свободные две позиции. Это означает, что на двух других стержнях расположены диски размером больше, чем рассматриваемый. А так как рассматриваемый диск не самый маленький, то где-то расположен наименьший. Либо он расположен на рассматриваемом диске, тогда мы не можем переместить рассматриваемый, либо на каком-то другом, но тогда у нашего диска остаётся не более одной свободной позиции. Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если [math]n[/math] нечётно, то последовательность перемещений наименьшего диска имеет вид [math]r_ <1>\rightarrow r_ <3>\rightarrow r_ <2>\rightarrow r_ <1>\rightarrow r_ <3>\rightarrow r_ <2>\rightarrow \ldots .[/math] (где [math]r_<1>[/math] — стартовый стержень, [math]r_<3>[/math] — финальный стержень, [math]r_<2>[/math] — оставшийся стержень), а если [math]n[/math] чётно, то [math]r_ <1>\rightarrow r_ <2>\rightarrow r_ <3>\rightarrow r_ <1>\rightarrow r_ <2>\rightarrow r_ <3>\rightarrow \ldots.[/math]

Выбор обусловлен тем, на каком стержне окажется в конце пирамидка, решение с помощью кода Грея является следствием классического нерекурсивного решения [7] .

Код Грея

Автор: Холодилов Сергей Александрович

Опубликовано: 23.08.2010
Исправлено: 10.12.2020
Версия текста: 1.1

Представьте себе, что вы – молодой капитан Грей, уже знающий, что Ассоль сидит на берегу, смотрит вдаль и ждёт. Ушибленный на голову волшебник обещал ей принца, использующего такое двоичное представление чисел, что коды соседних чисел отличаются ровно на один бит.

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

Наложим несколько ограничений:

  • Было бы здорово, если бы, имея n битов, мы могли бы закодировать все числа от 0 до 2 n -1. Т.е. если у нас 8 бит, а код числа 5 ну ни как не влезает, это плохо. Даже если ни одна комбинация не пропадает, и какой-то 8-и битной соответствует число 1567 – всё равно плохо. Очень неудобно с практической точки зрения.
  • При этом код числа не должен зависеть от того, сколько битов у нас есть. Ситуации, когда при 8-и доступных битах код числа 5 требует 6 битов, а при 32-х – 17, хотелось бы избежать. Чтобы не приходилась каждый раз оговаривать, сколько битов есть. Пусть 5 всегда будет 5.

Кодировку, удовлетворяющую этим ограничениям, назовём вменяемой (это же математика! тут нельзя без строгой терминологии). Очевидное необходимое и достаточное условие вменяемости:

  • Код числа, меньшего 2 n должен занимать не более чем n битов.

ПРИМЕЧАНИЕ

Т.е. для любого x и любого n, если x n , код x не длиннее n. Длина кода – позиция старшего единичного разряда.

Отсюда сразу получаем:

  • код 0 – 0000 (для него должно хватать 0 бит, ага)
  • код 1 – 0001
  • код 2 – 0011 (а как ещё изменить только 1 бит, остаться в пределах 2-х битов, и не повториться?)
  • код 3 – 0010
  • код 4 – 0110

А вот дальше могут быть варианты. А жаль, а то бы сразу раз – и всё построили.

Разработка

Раз сразу не получилось, попробуем подумать:

  • Коды чисел до 2 n -1 влезают в n бит (это из требования вменяемости).
  • Более того, так как таких чисел слолько же, сколько кодов длины не более n, они не просто влезают, у них взаимнооднозначное соответствие. Т.е. после числа 2 n -1 свободных комбинаций из первых n битов уже не осталось.
  • Коды чисел до 2 n+1 -1 влезают в n+1 бит (по вменяемости).
  • Коды чисел от 2 n до 2 n+1 -1 не могут влезать в n бит, т.к. там уже всё разобрано. Значит у них всех n-й бит установлен в 1 (биты нумеруются с 0).
  • Рассмотрим код числа 2 n . Его n-й бит равен 1. При этом отличается от кода 2 n -1 только одним битом. Значит вот этим n-м битом и отличается, остальные совпадают.

Получили следующую схему:

ПРИМЕЧАНИЕ

Вертикальная черта (символ «|») означает конкатенацию строк.

00. 000 | код(2 n -1)

00. 001 | код(2 n -1)

в n-том бите появилась 1

00. 001 | xxxxxxxx

и эта единица передаётся дальше

00. 001 | xxxxxxxx

00. 001 | xxxxxxxx

и вплоть до 2 n+1 -1

00. 011 | xxxxxxxx

и так она оказывается в 2 n+1

00. 01 | xxxxxxxxx

а вот дальше уже не факт

Теперь предположим, что мы добрались до 2 n и надо двигаться дальше – к 2 n+1 .

  • Коды чисел до 2 n+1 -1 влезают в n+1 бит
  • При этом у кодов всех чисел от 2 n до 2 n+1 -1 n-й бит равен 1.
  • Таких кодов 2 n штук; для того, чтобы они все отличались, нам нужно перебрать все комбинации значений младших n битов.
  • Младшие n бит кода числа 2 n совпадают с кодом числа 2 n -1

Итого: нужно перебрать все комбинации из n битов, так, чтобы первой был код 2 n -1, и каждые две соседние отличались бы ровно одним битом.

Вариантов такого перебора много, но среди них есть один красивый. Дело в том, что у нас уже есть подходящая последовательность: коды чисел от 0 до 2 n -1. Если взять её в обратном порядке, получится ровно то, что нужно.

Это и есть код Грея.

Понятное объяснение

Начнём с первых двух чисел, закодируем их нулём и единицей:

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

Кодов стало больше, и соседи отличаются друг от друга не более чем одним битом. Но есть повторы. Чтобы не было повторов, допишем спереди к первой половине кодов 0, а ко второй 1.

Точно так же мы можем отразить и их

И тоже добавим в первую половину 0, а во вторую – 1.

В общем виде

Должно быть уже понятно, но на всякий случай:

зеркально отражается младший разряд

00. 000 | gray(2 n -2)

00. 000 | gray(2 n -1)

00. 001 | gray(2 n -1)

00. 001 | gray(2 n -2)

00. 001 | gray(2 n -3)

обратите внимание на то, чему равен этот код

Историческая справка

Именно в таком виде этот код был предложен инженером Bell Labs Фрэнком Греем (Frank Gray) в 1947-м году. Код описан в патенте 2632058 (оформлен в 1953-м), и подраздел «Понятное объяснение» целиком стянут оттуда (вслед за [Doran 07]). Первоначально Грей предложил название «reflected binary code», но очень быстро на него начали ссылаться просто как на «код Грея».

С предысторией несколько сложнее.

В 1870-x годах французский инженер Эмиль Бодо (Émile Baudot) занимался усовершенствованием телеграфа; в 1878-м году его телеграф получил золотую медаль на Всемирной выставке в Париже, после чего быстро распространился по миру. В то время телеграфы в основном передавали морзянку, основное отличие телеграфа Бодо было в том, что он печатал буквы. Конечно, для этого ему потребовался двоичный код фиксированной длины.

Разрабатывая код, Бодо боролся с нечеловеческим интерфейсом ввода данных. Клавиатура его телеграфа состояла из пяти клавиш, каждая из которых отвечала за один бит, коды символов вводились вручную (и при этом нужно было выдерживать правильный темп!). Бодо стремился минимизировать количество переключений и этим упростить работу оператора.

Скорее всего, он проанализировал частотность биграмм и поместил на «соседние» кодовые позиции часто встречающиеся рядом буквы. Но код Грея даёт только две соседние позиции (следующее и предыдущее слово). А для слова из пяти бит их, конечно, пять, и жалко терять остальные.

Дальше есть два варианта:

  • Честно придумать оптимальное кодирование. После чего расставить элементы как-нибудь красиво.
  • Оператор работает двумя руками: две клавиши для левой и три для правой. Если рассматривать и кодировать эти части отдельно, получаем четыре соседних кодовых слова. Четыре это почти пять, пятую при желании можно учесть отдельно.

Картинки, на которых код Бодо похож на код Грея, выглядят специфически: по горизонтали отложены четыре варианта положения клавиш левой руки, по вертикали – восемь вариантов положения правой, на пересечениях находятся символы. Положения клавиш приведены в порядке кода Грея.

В 1901-м году Дональд Мюррей (Donald Murray) сделал нормальную клавиатуру для телеграфа, и заодно переработал код.

ПРИМЕЧАНИЕ

Основная публикация, связывающая Эмиля Бодо и код Грея, это статья Heath, F. G. «Origin of the Binary Code» (Scientific American vol. 227 no. 2, Aug 1972), в сети она не доступна, но и ничего интересного (не вообще, а по данному вопросу) там нет. Аргументов о том, зачем Бодо потребовался код Грея автор не приводит (точнее, пытается привести, но явно мимо), наоборот, сообщает, что в 1882-м году Бодо переработал кодировку (больше нигде упоминаний об этом не нашёл). Значит, видимо, технических препятствий для этого не было.

Информация об устройстве телеграфа Бодо из статей про телеграф (например: раз, два). Код Грея в них не упоминается.

Генерация последовательности

Действуем по определению. Возрастающая последовательность n-битных кодов строится из последовательности (n-1)-битных следующим образом:

  • дописать спереди 0 к возрастающей (n-1)-битной последовательности
  • дописать спереди 1 к убывающей (n-1)-битной последовательности (тогда зеркально получается)

Если читать это в обратном порядке, получится, естественно, убывающая n-битная последовательность. Соответственно, она строится аналогично, изменится только старший разряд:

  • дописать спереди 1 к возрастающей (n-1)-битной последовательности (была убывающая, но если читать наоборот. )
  • дописать спереди 0 к убывающей (n-1)-битной последовательности

Или, то же самое, чуть более изящно (заметим закономерность, связывающую значения d и значения n-ного разряда):

Кодирование значения

Во-первых, это тоже можно сделать по определению. Идея очень простая:

Язык описания аппаратуры Verilog HDL

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

  • Печать
  • E-mail

Подробности Категория: Язык описания аппаратуры Verilog HDL Создано 12 Апрель 2012 Автор: Николай Ковач Просмотров: 41970

Как мы знаем, коды Грея (Gray codes) – это специальная система счисления, в которой два соседних значения отличаются только в одном разряде. Они часто используются для повышения надежности аппаратуры. Одно из применений кодов Грея – передача значений указателей головы/хвоста очереди из одного клокового домена в другой при проектировании асинхронного FIFO.

Рассмотрим способы преобразования кодов Грея в двоичное число.
Вот таблица соответствия для четырехбитных чисел:

0000 0000
0001 0001
0010 0011
0011 0010
0100 0110
0101 0111
0110 0101
0111 0100
1000 1100
1001 1101
1010 1111
1011 1110
1100 1010
1101 1011
1110 1001
1111 1000

Столбец слева – это двоичное число, а столбец справа – это соответствующие коды Грея.
Преобразование из Грея в двоичное число можно сделать на языке Verilog HDL вот так:

module gray2bin_v1(
input wire [3:0]gray,
output wire [3:0]bin
);

assign bin[0] = gray[3] ^ gray[2] ^ gray[1] ^ gray[0];
assign bin[1] = gray[3] ^ gray[2] ^ gray[1];
assign bin[2] = gray[3] ^ gray[2];
assign bin[3] = gray[3];

endmodule Используются только операции «Исключающее ИЛИ». Если откомпилировать такой модуль с помощью Quartus II, то в его RTLViewer можно увидеть получившуюся эквивалентную схему:

Для проверки правильности работы этого модуля напишем Verilog тестбенч: ` timescale 1ns/1ns

reg clk;
initial clk=0;
always
#10 clk=

reg [3:0]gr;
wire [3:0]b1;

gray2bin_v1 my_gr1(
.gray(gr),
.bin(b1)
);

initial
begin
$dumpfile(«out.vcd»);
$dumpvars(-1, test);

gr=4’b0000;
@( posedge clk); #0;
@( posedge clk); #0;
gr=4’b0001;
@( posedge clk); #0;
gr=4’b0011;
@( posedge clk); #0;
gr=4’b0010;
@( posedge clk); #0;
gr=4’b0110;
@( posedge clk); #0;
gr=4’b0111;
@( posedge clk); #0;
gr=4’b0101;
@( posedge clk); #0;
gr=4’b0100;
@( posedge clk); #0;
gr=4’b1100;
@( posedge clk); #0;
gr=4’b1101;
@( posedge clk); #0;
gr=4’b1111;
@( posedge clk); #0;
gr=4’b1110;
@( posedge clk); #0;
gr=4’b1010;
@( posedge clk); #0;
gr=4’b1011;
@( posedge clk); #0;
gr=4’b1001;
@( posedge clk); #0;
gr=4’b1000;
@( posedge clk); #0;

$finish();
end
endmodule Быстро просимулировать и посмотреть результат можно с помощью iverilog (Icarus Verilog), используя командную строку и GtkWave. Здесь же я приведу лишь получившуюся временную диаграмму:

Все работает правильно.
Недостаток описанного выше примера модуля gray2bin_v1 состоит в том, что он реализует фиксированное число бит, в данном случае четыре. Было бы удобным иметь параметризованный модуль, который без изменений мог бы быть использованным в разных проектах.

Если внимательно посмотреть на код модуля gray2bin_v1, то видно, что там имеется четыре строки assign для каждого результирующего бита. Нам нужен механизм создания заданного числа таких строк кода Verilog в момент компиляции и такой механизм есть в стандарте Verilog-2001. Использование конструкции языка generate/endgenerate позволяет в момент компиляции генерировать фрагменты кода.

Вот пример параметризованного модуля преобразователя кода Грея в двоичный код: module gray2bin_v2(
input wire [SIZE-1:0]gray,
output wire [SIZE-1:0]bin
);
parameter SIZE = 4;

generate
for (i=0; i begin : bit
assign bin[i] = ^gray[SIZE-1:i];
end
endgenerate
endmodule Переменная типа genvar существует только в момент компиляции и генерации кода. Во время симуляции ее нет. Строка “assign…” будет сгенерирована SIZE раз. Для каждого бита результирующего двоичного числа операция «Исключающее ИЛИ» будет проводиться по диапазону бит исходного кода Грея: ^gray[SIZE-1:i] .

Конечно, можно написать модуль gray2bin и иначе, без «экзотических» generate/endgenerate. Вот так: module gray2bin_v3(
input wire [SIZE-1:0]gray,
output reg [SIZE-1:0]bin
);
parameter SIZE = 4;

always @*
begin
for (i=0; i >i);
end
endmodule

Здесь, выражение (gray>>i) – это логический сдвиг вправо, он оставляет только нужные биты, между которыми будет проводиться «Исключающее ИЛИ». К сожалению, написать здеь gray[SIZE-1:i] вместо (gray>>i) не получится. Компилятор Verilog выдаст ошибку. Язык Verilog не позволяет выбрать часть бит из шины если один из индексов это переменная.

Модули gray2bin_v2 и gray2bin_v3 описывают одно и то же, разными способами. Они работают одинаково. В этом легко убедиться с помощью того же тестбенча, описанного выше.

Что такое код graystring

код Грея — Циклический двоичный код. [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 века. Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются … Википедия

Generate n-bit Gray Codes

Given a number n, generate bit patterns from 0 to 2^n-1 such that successive patterns differ by one bit.

Examples:

The above sequences are Gray Codes of different widths. Following is an interesting pattern in Gray Codes.

n-bit Gray Codes can be generated from list of (n-1)-bit Gray codes using following steps.
1) Let the list of (n-1)-bit Gray codes be L1. Create another list L2 which is reverse of L1.
2) Modify the list L1 by prefixing a ‘0’ in all codes of L1.
3) Modify the list L2 by prefixing a ‘1’ in all codes of L2.
4) Concatenate L1 and L2. The concatenated list is required list of n-bit Gray codes.

For example, following are steps for generating the 3-bit Gray code list from the list of 2-bit Gray code list.
L1 = <00, 01, 11, 10>(List of 2-bit Gray Codes)
L2 = <10, 11, 01, 00>(Reverse of L1)
Prefix all entries of L1 with ‘0’, L1 becomes <000, 001, 011, 010>
Prefix all entries of L2 with ‘1’, L2 becomes <110, 111, 101, 100>
Concatenate L1 and L2, we get

To generate n-bit Gray codes, we start from list of 1 bit Gray codes. The list of 1 bit Gray code is <0, 1>. We repeat above steps to generate 2 bit Gray codes from 1 bit Gray codes, then 3-bit Gray codes from 2-bit Gray codes till the number of bits becomes equal to n. Following is the implementation of this approach.

Kurry / Solution.java

public class Solution <
public static List Integer > grayCode ( int n ) <
if (n == 0 ) return Arrays . asList( 0 );
List String > grayCodes = grayCodeStrings(n);
List Integer > solution = new ArrayList<> ();
for ( String s : grayCodes) <
solution . add( Integer . parseInt(s, 2 ));
>
return solution;
>
public static List String > grayCodeStrings ( int n ) <
List String > list = new ArrayList<> ();
if (n == 0 ) <
list . add( » » );
return list;
> else if (n == 1 ) <
list . add( » 0 » );
list . add( » 1 » );
return list;
> else <
List String > prev = grayCodeStrings(n — 1 );
list . addAll(prev);
for ( int i = prev . size() — 1 ; i >= 0 ; i — ) <
String bits = list . get(i);
list . set(i, » 0 » + bits);
list . add( » 1 » + bits);
>
return list;
>
>
>
  • © 2020 GitHub , Inc.
  • Terms
  • Privacy
  • Security
  • Status
  • Help

You can’t perform that action at this time.

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введем некоторые обозначения:

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

Лемма

Доказательство

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

Теорема

Доказательство

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

Теперь мы можем сформулировать замечательные следствия из теоремы.

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

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

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

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

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

На этом хотелось бы закончить статью. Спасибо за внимание и до скорых встреч.

Kurry / Solution.java

public class Solution <
public static List Integer > grayCode ( int n ) <
if (n == 0 ) return Arrays . asList( 0 );
List String > grayCodes = grayCodeStrings(n);
List Integer > solution = new ArrayList<> ();
for ( String s : grayCodes) <
solution . add( Integer . parseInt(s, 2 ));
>
return solution;
>
public static List String > grayCodeStrings ( int n ) <
List String > list = new ArrayList<> ();
if (n == 0 ) <
list . add( » » );
return list;
> else if (n == 1 ) <
list . add( » 0 » );
list . add( » 1 » );
return list;
> else <
List String > prev = grayCodeStrings(n — 1 );
list . addAll(prev);
for ( int i = prev . size() — 1 ; i >= 0 ; i — ) <
String bits = list . get(i);
list . set(i, » 0 » + bits);
list . add( » 1 » + bits);
>
return list;
>
>
>
  • © 2020 GitHub , Inc.
  • Terms
  • Privacy
  • Security
  • Status
  • Help

You can’t perform that action at this time.

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.

Generate n-bit Gray Codes

Given a number n, generate bit patterns from 0 to 2^n-1 such that successive patterns differ by one bit.

Examples:

The above sequences are Gray Codes of different widths. Following is an interesting pattern in Gray Codes.

n-bit Gray Codes can be generated from list of (n-1)-bit Gray codes using following steps.
1) Let the list of (n-1)-bit Gray codes be L1. Create another list L2 which is reverse of L1.
2) Modify the list L1 by prefixing a ‘0’ in all codes of L1.
3) Modify the list L2 by prefixing a ‘1’ in all codes of L2.
4) Concatenate L1 and L2. The concatenated list is required list of n-bit Gray codes.

For example, following are steps for generating the 3-bit Gray code list from the list of 2-bit Gray code list.
L1 = <00, 01, 11, 10>(List of 2-bit Gray Codes)
L2 = <10, 11, 01, 00>(Reverse of L1)
Prefix all entries of L1 with ‘0’, L1 becomes <000, 001, 011, 010>
Prefix all entries of L2 with ‘1’, L2 becomes <110, 111, 101, 100>
Concatenate L1 and L2, we get

To generate n-bit Gray codes, we start from list of 1 bit Gray codes. The list of 1 bit Gray code is <0, 1>. We repeat above steps to generate 2 bit Gray codes from 1 bit Gray codes, then 3-bit Gray codes from 2-bit Gray codes till the number of bits becomes equal to n. Following is the implementation of this approach.

Илон Маск рекомендует:  Что такое код dio_write
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL