Как сделать код грея
Обновлено: 02.07.2024
Одношаговый код — это код в котором при переходе от одного числа к другому меняется лишь один из всех битов числа.
Таким кодом является код Грея .
Соответствие десятичных кодов и кодов Грея.
Двоичное кодирование Кодирование по коду Грея
Десятичный код Двоичное значение Шестнадцатеричное значение Десятичный код Двоичное значение Шестнадцатеричное значение
0 0000 0h 0 0000 0h
1 0001 1h 1 0001 1h
2 0010 2h 3 0011 3h
3 0011 3h 2 0010 2h
4 0100 4h 6 0110 6h
5 0101 5h 7 0111 7h
6 0110 6h 5 0101 5h
7 0111 7h 4 0100 4h
8 1000 8h 12 1100 Ch
9 1001 9h 13 1101 Dh
10 1010 Ah 15 1111 Fh
11 1011 Bh 14 1110 Eh
12 1100 Ch 10 1010 Ah
13 1101 Dh 11 1011 Bh
14 1110 Eh 9 1001 9h
15 1111 Fh 8 1000 8h
Программа предназначена для генерации кодов Грея , а именно, рефлексного двоичного кода Грея.
Результатом вычислений будет таблица подобная представленной ниже.
Dec Bin Gray
0 0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 0111
6 0110 0101
7 0111 0100
8 1000 1100
9 1001 1101
10 1010 1111
11 1011 1110
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000
Обозначения столбцов следующие:
Dec — десятичное число;
Bin — двоичное число;
Gray — представление числа в кодировке Грея;
Код Грея в 13-канальном абсолютном поворотном оптическом энкодере . Тринадцать дорожек появляются вокруг заводной головки, расположенной на уровне двух винтов Phillips.
Код Грея , также известный как код Грея или отраженный двоичный код , представляет собой тип двоичного кодирования для изменения только одного бита за раз при увеличении числа. Это свойство важно для нескольких приложений.
Название кода принадлежит американскому инженеру Фрэнку Грею, который опубликовал патент на этот код в 1953 году, но сам код старше.
Резюме
Принцип и пример
Код Грея - это двоичное кодирование, то есть функция, которая связывает двоичное представление с каждым числом. Этот метод отличается от естественного двоичного кодирования. В следующей таблице частично показано 4-битное кодирование (представлены только первые 8 значений, следующие восемь с первым битом, установленным в 1, нет).
| Десятичное кодирование | Естественное двоичное кодирование | Отраженное серое или двоичное кодирование |
|---|---|---|
| 0 | 0000 | 0000 |
| 1 | 0001 | 0001 |
| 2 | 0010 | 0011 |
| 3 | 0011 | 0010 |
| 4 | 0100 | 0110 |
| 5 | 0101 | 0111 |
| 6 | 0110 | 0101 |
| 7 | 0111 | 0100 |
Основное различие между ними заключается в том, что кодирование Греем двух последовательных чисел отличается только на одну позицию. Например, 5 кодируется 0111, а 6 кодируется 0101: изменяется только второй бит.
Методы приращения
Существует как минимум четыре метода увеличения (то есть добавления 1) к числу, написанному в коде Грея.
Инвертируйте, чтобы получить новый номер
Чтобы перейти от одной строки к другой, переверните бит как можно правее, чтобы получить новое число.
С симметрией
Отраженное имя двоичного кода получено из более удобного метода построения выбора, какой бит инвертировать при переходе от одного числа к другому:
- выбираем начальный код: ноль кодируется 0, а единица - 1,
- затем, каждый раз, когда нам нужен дополнительный бит, мы зеркалируем список уже полученных кодов (как отражение в зеркале),
- наконец, мы добавляем 0, а затем 1 в начале (слева) каждого из кодов. Таким образом, количество сформированных кодов увеличилось вдвое.
По паритету
Другой метод расчета, позволяющий переходить от одного числа Грея к другому и имеющий то преимущество, что не требует знания набора предыдущих чисел, заключается в следующем:
- если число 1 четное, последнюю цифру нужно поменять местами.
- если число 1 нечетное, число слева от крайнего правого числа должно быть перевернуто.
С эксклюзивным ИЛИ
И, наконец, последний метод состоит в вычислении исключающего ИЛИ (обозначенного здесь символом ^) между начальным двоичным кодом и этим же двоичным кодом, сдвинутым на одну строку вправо.
Примеры: мы хотим представить 7, 10, 15 в коде Грея.
7 записывается как 0111 по основанию 2.
7 в десятичной системе счисления представляет собой 0100 в коде Грея.
10 записывается как 1010 по основанию 2. Следовательно:
10 в десятичной системе счисления представляет 1111 в коде Грея.
Последний пример: 15 записывается как 1111 по основанию 2.
15 в десятичной системе счисления представлено 1000 в коде Грея.
Двоичное / серое перекодирование
Отметив целое число, записанное в двоичном формате (где - старший бит ), и аналогичным образом отметив соответствующий код Грея, можно показать (например, используя таблицы Карно), что (где обозначает функцию Исключающее ИЛИ ); другими словами, чтобы получить , достаточно выполнить исключающее ИЛИ между и этим же числом, сдвинутым на один бит вправо (то есть в двоичном формате, деленном на 2), что выражается следующей функцией, записанной в C язык : б знак равно б 0 б 1 . . . б k b_ . b_ > б 0 > грамм знак равно грамм 0 грамм 1 . . . грамм k g_ . g_ > грамм я знак равно б я ⊕ б я - 1 = b_ \ oplus b_ > ⊕ грамм б б
Алгоритм кодирования кода Грея для числа b:
Алгоритм быстрого декодирования 64-битных слов (для 32-битных слов замените 32 на 16):
Серое / двоичное перекодирование
Отметив целое число, записанное в двоичном формате (где - самый старший бит ), и аналогичным образом указав соответствующий код Грея, в соответствии с вышеизложенным, мы легко определяем двоичное число данного кода Грея: (где обозначает функцию исключающего ИЛИ ) . Итак, у нас есть: б знак равно б 0 б 1 . . . б k b_ . b_ > б 0 > грамм знак равно грамм 0 грамм 1 . . . грамм k g_ . g_ > б я знак равно грамм 0 ⊕ грамм 1 ⊕ грамм 2 ⊕ . . . ⊕ грамм я = g_ \ oplus g_ \ oplus g_ \ oplus . \ oplus g_ > ⊕
Итак, чтобы получить двоичный код данного кода Грея, мы идем слева (высокий порядок) вправо (низкий порядок). Самый старший бит в двоичном коде такой же, как и в коде Грея . Следующий двоичный бит остается неизменным, если следующий бит Грея равен нулю, и изменяется, если следующий бит Грея равен 1. Это повторяется для всех битов, вплоть до самого младшего бита. б 0 знак равно грамм 0 = g_ >
Интересы и приложения
Избегайте переходных состояний
Колесо модуля и энкодера
Следует отметить, что переход от максимума ( семи из 3 битов) к нулю также осуществляется путем изменения только одного бита. Это позволяет, например, кодировать угол, например направление флюгера: 0 = север , 1 = северо-восток , 2 = восток , . 7 = северо-запад . Переключение с северо-запада на север также выполняется без проблем путем изменения только одного бита (см. Колесо энкодера )
Декодирование световых сигналов механической оси мыши представляет собой 2-битное декодирование кода Грея (в данном случае дифференциальное декодирование, потому что мы хотим получить не декодированное значение, а переходы ± 1 по модулю 4 декодированного значения).
Таблицы Карно
Код Грея также используется в таблицах Карно, используемых при проектировании логических схем.
Код Бодо
Принцип кода Грея можно найти в коде Бодо , в котором гласные и согласные классифицируются в их алфавитном порядке, а один бит изменяется между двумя последовательными буквами.
Исторический
Американский инженер Фрэнк Грей, который подал патент на этот код в 1947 году, но сам код старше; он особенно использовался в коде Бодо.
Люк-Агафон-Луи Гро, который был нотариусом, а затем советником Апелляционного суда Лиона, опубликовал в 1872 году брошюру Théorie du baguenodier par un clerc de notaire lyonnais , где этот кодекс был впервые представлен в связи с головоломка, игра в багенодье .
Глубокой осенью 1980 года после долгих бумажных проволочек, связанных с переводом из ДВПИ в ЛЭТИ, я прибыл на свой первый семинар в новой альме матери. Дело шло к концу семестра, и преподаватель схемотехники сильно призадумался, сочиняя мне тему для курсовой. В конце концов он решил бросить меня в область новую, неизведанную — преобразователь кода Грея в двоичный код. Про код Грея я раньше ничего не слышал и сразу же бросился в библиотеку (тогда ещё не было интернета, прикиньте!). Тема оказалась довольно простой и настолько забавной, что до сих пор в разных интеллектуальных компаниях после первой бутылки коньяка я демонстрирую присутствующим глубокое проникновение в предмет.
Руководитель, впрочем, остался недоволен. Преобразователь четырёхразрядного кода уложился в одну микросхему, а пояснительная записка заняла четыре страницы, что, конечно, непростительно мало для любого уважающего себя преподавателя схемотехники.
Лет через десять я сам уже вёл семинары по цифровой электронике, и передо мной встала проблема, как просто и доходчиво объяснить студентам-заочникам сущность кода Грея. И я придумал такую байку.
Этнографическая байка про код Грея
Задумывались ли вы когда-нибудь, что считая на пальцах, мы используем ресурсы своего организма крайне нерационально? Задействуя пять пальцев, мы считаем до десяти, хотя различные сочетания загнутых и разогнутых пальцев одной руки дают 2 5 = 32 различных комбинации. Получается, что мы используем собственные вычислительные мощности всего лишь на треть.
Считать в двоичных кодах не выход, так как требуется довольно сложная координация движений разных пальцев. Например, при переходе от 15 к 16 (01111 → 10000) приходится одновременно разгибать четыре пальца и загибать пятый. Желательно же, чтобы при переходе к следующему числу, как и при счёте до 10, загибался или разгибался только один палец. Хочется также, чтобы существовал стереотип движений, то есть при счёте пальцы циклически повторяли одну и ту же последовательность сгибаний и разгибаний, что позволило бы довести счёт до автоматизма.
Однажды этнографическая экспедиция высадилась на далёкий полинезийский остров Гронгозогоро и обнаружила, что местные аборигены издревле используют именно такой способ счёта (дальше я показываю студентам, какой именно):
Поскольку фигуры из пальцев спервоначалу трудно соотнести с привычными десятичными числами, имеет смысл предварительно преобразовать их в двоичную систему. Для этого существует такой алгоритм.
1. Старший разряд (то есть мизинец) кода Грея всегда совпадает со старшим разрядом двоичного кода.
2. Положение следующих по порядку пальцев определяется правилом: если предыдущий палец загнут, то следующий палец меняет своё положение. Если же предыдущий палец разогнут, положение следующего пальца не меняется.
Когда процесс доходит до большого пальца, искомое число оказывается закодировано на руке двоичным кодом. Не забывайте, что загнутый палец — единица, разогнутый — ноль.
Для чего это нужно?
Первое применение код Грея нашёл в кодирующих дисках угла поворота. Представьте себе, что на некоторое вращающееся устройство насажен диск, который выглядит примерно так:
Расположим вдоль радиуса диска несколько неподвижных фотодатчиков (в данном случае три, они обозначены красными кружками). Когда фотодатчик находится напротив белого сектора диска, он даёт сигнал 0, когда напротив чёрного — 1. Таким образом, в зависимости от угла поворота диска фотодатчики дают разные коды, что позволяет измерять угол поворота. В данном случае диск расчерчен так, чтобы фотодатчики давали трёхразрядный двоичный код. Например, 000 — север, 001 — северо-запад, 010 — запад и т.д. до 111 — северо-восток.
Проблема такого кодового диска состоит вот в чём. Когда линейка фотодатчиков находится на границе между двумя секторами, датчики начинают вести себя непредсказуемым образом. Вот, например, ситуация, когда диск переходит из сектора 000 в сектор 111. Понятно, что невозможно сделать фотодатчики абсолютно идентичными, а границу между секторами абсолютно ровной. В результате при переходе границы одни датчики переключатся из 0 в 1 раньше, другие — позже. В результате возникают промежуточные комбинации кодов, например 000 -> 001 -> 101 -> 111, что может дать грубую ошибку при измерении угла.
Тут на помощь приходит код Грея, где соседние сектора различаются всего одним разрядом, поэтому время срабатывания датчиков некритично.
Понятно, что применение диска, закодированного по Грею, требует для преобразования в обычный двоичный код специальной схемы, которая оказывается трогательно простой:
Как мы знаем, коды Грея (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];
Для проверки правильности работы этого модуля напишем Verilog тестбенч: ` timescale 1ns/1ns
reg [3:0]gr;
wire [3:0]b1;
gray2bin_v1 my_gr1(
.gray(gr),
.bin(b1)
);
initial
begin
$dumpfile("out.vcd");
$dumpvars(-1, test);
$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;
always @*
begin
for (i=0; i >i);
end
endmodule
Модули gray2bin_v2 и gray2bin_v3 описывают одно и то же, разными способами. Они работают одинаково. В этом легко убедиться с помощью того же тестбенча, описанного выше.
Читайте также: