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

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

Среди невзвешенных двоичных кодов специальные применения находят такие, у которых переход к соседнему числу сопровождается изменениями только в одном разряде (коды с обменной единицей). Так, в технике аналого-цифрового преобразования и пересчетных устройствах широко используется код Грея [73], называемый также циклическим или рефлексно-двоичным кодом (табл. 1.3). Он позволяет существенно сократить гремя преобразования, упростить кодирующую логику, а также повысить эффективность защиты от нежелательных сбоев при переходах выходного кода. Недостатком кода Грея является то, что в нем затруднено выполнение арифметических операций и цифроаналоговое преобразование. Поэтому при необходимости код Грея преобразуется в обычный двоичный код.

Переход от двоичного кода к коду Грея осуществляется по правилу (рис. 1.2,а): старшие разряды совпадают, а любой следующий разряд кода Грея равен сумме по модулю 2 соответствующего и предыдущего хразрядов двоичного кода, т. е.

14. Код Грея

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

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

Счётчик Грэя

//——————————————————
// Имя модуля : gray_counter
// Имя файла : gray_counter.v
// Функц. назначение : 8-ми разрядный счётчик Грэя
// Программист : www.portal-ed.ru
//——————————————————
module gray_counter (
out , // Выход счётчика
enable , // Разрешение счёта
clk , // Такты
rst // Вход сброса лог. «1» — активный сигнал
);
//————Входные порты—————
input clk, rst, enable;
//———-Выходные порты—————-
output [ 7:0] out;
//————Внутренние переменные———
wire [7:0] out;
reg [7:0] count;
//————-Начало кода———
always @ (posedge clk)
if(rst)
count Системы счисления: код Грея

Автор: Белоусов Аркадий

Введение

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

К позиционным системам с постоянным основанием относится десятичная система, системой с произвольным основанием является система счёта времени — секунд в минутах и минут в часах по 60, а часов в сутках 24. Непозиционные системы счисления из повседневности практически вытеснены, хотя римская система до сих пор используется, например, для указания номера века, а иногда и года.

В современных цифровых компьютерах основное место занимает двоичная система счисления (позиционная система с постоянным основанием, равным 2) и прямые её производные (восьмеричная и шестнадцатиричная системы). Однако и другие системы не были забыты. Например, при двоично-десятичном кодировании чисел каждой десятичной цифре отводится по четыре двоичных цифры (бита), веса которых могут быть равны не только 8-4-2-1, но и, скажем, 2-4-2-1.

Встречаются в цифровой технике и непозиционные системы. Наиболее известныйиз них — код Грея, называемый также рефлексным (отражённым) двоичным кодом. Этот код строится из двоичных цифр таким образом, что соседние числа в нём отличаются всегда только в одном разряде. Кодов с такой же характеристикой много, но для кода Грея имеется простой алгоритм перевода чисел в двоичный позиционный код и обратно.

Строение кода Грея

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

Младший разряд в последовательности чисел в коде Грея принимает значения 0 и 1, затем следующий старший разряд становится единичным и младший разряд принимает свои значения уже в обратном порядке (1, 0). Этим и объясняется название кода — «отражённый». Соответственно, два младших разряда принимают значения 00, 01, 11, 10, а затем, при единичном следующем старшем разряде, те же значения в обратном порядке (10, 11, 01, 00). Ниже дана таблица, показывающая первые восемь чисел в двоичном коде и в коде Грея.

Использование кода Грея

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

позиционный код
код Грея

Недостаток кодирования позиционным двоичным кодом заключается в том, что при смене нечётного кода чётным считанный с фотодиода код может оказаться неверным. Характеристики фотодиодов обычно не идентичны и при смене сразу нескольких разрядов выходные уровни фотодиодов могут измениться не строго одновременно. Например, при переходе от третьего угла к четвёртому или от седьмого угла к нулевому меняются все разряды и какое-то время на выходе фотодиодов можно получить любое значение от 0 до 7.

В коде же Грея при переходах ошибка не будет превышать один угол.

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

Как сказано выше, алгоритм перевода чисел в коде Грея в позиционный код прост: каждый разряд в позиционном коде равен сумме по модулю 2 этого и всех более старших разрядов в коде Грея. Старшие разряды, соответственно, совпадают. На языке C это алгоритм может выглядеть так:

unsigned gray2bin(unsigned v) < unsigned sum = v, length = BITS; while(length >0) v >>= 1, sum ^= v, length—; return sum; >

Этот код является дословным переводом на язык C основного алгоритма, но его можно оптимизировать за счёт накопления промежуточных сумм в самом числе:

for(unsigned i = 1; i > i);

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

v ^= v >> 1; /* для 2-разрядных чисел */ v ^= v >> 2; /* для 4-разрядных чисел */ v ^= v >> 4; /* для 8-разрядных чисел */ v ^= v >> 8; /* для 16-разрядных чисел */ …

Перевод из позиционного кода в код Грея ещё проще: каждый разряд в коде Грея равен сумме по модулю 2 этого и следующего старшего разряда в позиционном коде. На языке C этот алгоритм реализуется выражением v^(v>>1). Реализации на языке C этих алгоритмов также представлены в отдельном файле [GRAY.C].

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

Литература

И.С.Потёмкин «Функциональные узлы цифровой автоматики», М.: Энергоатомиздат, 1988

ALGLIB® — numerical analysis library, 1999-2018.
ALGLIB is registered trademark of the ALGLIB Project.

Источник

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

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

p, blockquote 1,0,0,0,0 —>

p, blockquote 2,0,0,0,0 —>

Рассмотрим положение символов в сигнальном созвездии для четверичной фазовой модуляции. Для 4-ФМн каждый символ представляется 2 битами. Назначим каждому символу по часовой стрелке комбинацию бит в обычной двоичной системе счисления: <00; 01; 10; 11>.

p, blockquote 3,0,0,0,0 —>

p, blockquote 4,0,0,0,0 —>

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

p, blockquote 5,0,1,0,0 —>

Пример кодирования двоичного кода

Рассмотрим пример по рисунку выше. Пусть был передан символ S0, который кодирован битами <00>. Из-за воздействия шумов наиболее частой ошибкой будет прием символа S1 или S3, т.к. они расположены ближе, чем символ S2. Ошибочный прием символа S2 также будет, но такие ошибки будут происходить реже.

p, blockquote 6,0,0,0,0 —>

Если возникла ошибка, при которой был принят символ S1 <01>вместо S0 <00>, то будет потерян всего 1 бит информации, т.к. символ S1 отличается от символа S2 на один бит. Однако если возникла ошибка, при которой был принят символ S3 <11>, то будет потеряно уже 2 бита информации.

p, blockquote 7,0,0,0,0 —>

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

p, blockquote 8,0,0,0,0 —>

Код Грея определение

В таблице ниже представлен код Грея для 2-х и 3-х бит.

p, blockquote 9,0,0,0,0 —>

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

p, blockquote 11,0,0,0,0 —>

Если символы 4-ФМн закодировать кодом Грея, т.е. символам S0 S1 S2 S3 назначить комбинацию бит <00; 01; 10; 11>соответственно, то любые два соседних символа будут отличаться друг от друга не более чем на один бит. В этом случае, если произойдет любая ошибка, где будут перепутаны два соседних символа, будет потерян только один бит информации.

p, blockquote 12,0,0,0,0 —>

p, blockquote 13,0,0,0,0 —>

p, blockquote 14,0,0,0,0 —>

Возникает вопрос, а есть ли существенная разница между тем, сколько бит информации потеряно? Ведь информация в любом случае оказалась искаженной! Дело в том, что в радиотехнических системах практически всегда применяется помехоустойчивое кодирование , задача которого исправлять ошибки. У помехоустойчивого кода есть ограничение на количество ошибок, которые он может исправить – этот параметр называется кратностью исправляемых ошибок. Соответственно необходимо стремиться к уменьшению количества ошибок, т.к. малое количество ошибок может исправить помехоустойчивый код.

p, blockquote 15,0,0,1,0 —>

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

p, blockquote 16,0,0,0,0 —>

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

p, blockquote 17,0,0,0,0 —>

p, blockquote 18,0,0,0,0 —>

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

p, blockquote 19,0,0,0,0 —> p, blockquote 20,0,0,0,1 —>

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

Источник