код грея перевод в двоичный код

Коды Грея

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

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

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

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

Широко применяются коды Грея и в теории генетических алгоритмов [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:

Источник

Часть 2. Кодирование переменных. Код Грея

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

Таблица1

Соответствие значений переменной в десятичном, двоичном
представлениях и представлении в коде Грея

Очевидно, оптимальным решением является x_opt = 7. Таким образом, решая задачу с использованием переменных в десятичном выражении и находясь в точке x = 8, достаточно сделать единственный шаг длиной, равной фактической точности, чтобы достичь оптимального значения. Однако в двоичном выражении всё выглядит наоборот.

Расстояние Хэмминга – количество различающихся битов данных, являющееся мерой близости бинарных значений, в этом случае максимально возможно и равно 4: во всех четырёх позициях двоичных представлений 7 и 8 биты не совпадают. Это означает, что в принципе невозможно, имея значение x₍₂₎ = 1000, получить x₍₂₎ = 0111, применив любой из базовых операторов генетического алгоритма, и лишь при редчайшем стечении обстоятельств это возможно, если применить модифицированный генетический оператор. Следствие этого обстоятельства – резкое снижение эффективности поиска оптимального решения при приближении функции приспособленности к своему наилучшему значению.

Проблему решают переходом от двоичного к бинарному представлению переменных в форме кода Грея. Правила преобразования из двоичного кода в код Грея и обратно просты и основаны на использовании логической функции «Исключающее ИЛИ» (XOR). Данная функция возвращает единицу, если нечётное количество бинарных аргументов также были единицами, в противном случае функция возвращает ноль.

Правило 1.

Для представления двоичного кода в форме кода Грея требуется приписать к двоичной форме слева ноль. Тогда соответствующей формой кода Грея будет последовательность значений функции «Исключающее ИЛИ» для пар: нуля и первого гена исходной двоичной формы, первого и второго генов, второго и третьего и т. д. То есть, например, для случая преобразования двоичной последовательности (a₁, b₁, c₁) в последовательность в форме кода Грея (a₂, b₂, c₂) получим: a₂ = XOR(0, a₁); b₂ = XOR(a₁, b₁); c₂ = XOR(b₁, c₁).

Примеры соответствия бинарного представления в коде Грея (X_(Г)) двоичным и десятичным значениям представлены в табл. 1. Из таблицы видно, что расстояние Хэмминга между представлениями чисел 7 и 8 в коде Грея минимально и равно 1: отличие имеет место лишь в четвёртом разряде.

Правило 2.

Для преобразования из кода Грея в двоичную форму к исходному коду слева приписывается ноль. Тогда результирующей двоичной формой будет последовательность значений функции «Исключающее ИЛИ» для первых двух знаков расширенной последовательности, первых трёх, четырёх и т. д. Например, для преобразования кода Грея (a₁, b₁, c₁) в двоичную последовательность (a₂, b₂, c₂) получим:a₂ = XOR(0, a₁);b₂ = XOR(0, a₁, b₁); c₂ = XOR(0, a₁, b₁, c₁).

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

В соответствии с этим способом каждая переменная кодируется последовательностью: a, b, a₁, b₁, …, где a, b – двоичные параметры, позволяющие учесть знаки перед экспонентой и её степени в формуле пересчёта значения переменной из двоичной формы в десятичную:

где φ – десятичное представление степени экспоненты, закодированной последовательностью a₁, b₁, ….

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

По материалам учебного пособия:
Дударов С. П. Математические основы генетических алгоритмов: учеб. пособие/ С. П. Дударов. – М.: РХТУ им. Д. И. Менделеева, 2012. – 56 с.

Источник

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

Как мы знаем, коды Грея (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;

Конечно, можно написать модуль 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 описывают одно и то же, разными способами. Они работают одинаково. В этом легко убедиться с помощью того же тестбенча, описанного выше.

Источник

Код ГРЕЯ в многопозиционных видах модуляций

При многопозиционных видах модуляций (М-ФМн и М-КАМ) выбор положения символа в сигнальном созвездии влияет на вероятность битовой ошибки.

Рассмотрим положение символов в сигнальном созвездии для четверичной фазовой модуляции. Для 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>соответственно, то любые два соседних символа будут отличаться друг от друга не более чем на один бит. В этом случае, если произойдет любая ошибка, где будут перепутаны два соседних символа, будет потерян только один бит информации.

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

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

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

Задача назначения битовых комбинаций каждому символу в созвездии сводится к минимизации среднего количества битовых ошибок при фиксированном отношении сигнал/шум.

Источник