Код Грея

Эта статья прошла проверку экспертом
Материал из «Знание.Вики»
Gray-code counter.JPG

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

Строго говоря, существует множество кодов Грея для систем счисления с любым основанием и в общем виде можно записать представление этого множества как {Gray (n, k)}, где

n — основание системы счисления,

k — число цифр в коде.

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

История создания и применение кода Грея

Фрэнк Грей

Код назван в честь исследователя Фрэнка Грея, работавшего в лаборатории Bell labs. В 1947 году была подана заявка на патент под названием «импульсный код связи», которая была удовлетворена в 1953 году (патент США № 2632058)[2]. Код назван «рефлексивным» (отражённым) из-за того, что первая половина значений при изменении порядка эквивалентна второй половине, за исключением старшего бита. Старший бит просто инвертируется. При делении каждой новой половины пополам это свойство сохраняется.

Отраженный двоичный код применялся для решения математических задач, а затем получил использование в технике, в частности, для защиты от ложного прочтения состояния электромеханических и электронных переключателей, когда необходимо исключить логические гонки. Французский инженер Эмиль Бодо применил код Грея в 1878 году в телеграфии, за эту работу он был награжден орденом Почётного легиона.

В настоящее время код Грея используется при составлении алгоритмов для создания карт Карно, которые, в свою очередь, используются в качестве инженерного инструмента при проектировании комбинационных и последовательностных логических схем. Кроме того, код Грея применяется для упрощения выявления и исправления ошибок в системах связи, а также для формирования последовательности импульсов в линейных и круговых датчиках отсчёта — энкодерах[3].

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

Преимущества кода Грея

Круговой энкодер с трёхбитовым кодом Грея

Характерной особенностью кода Грея является изменение только одной позиции при переходе от одной кодовой комбинации к другой. Это свойство широко используют как для построения некоторых типов аналого-цифровых преобразователей (АЦП), где он позволяет свести к «единице» младшего разряда погрешность неоднозначности при считывании, так и для решения других задач, требующих минимизировать погрешность перехода.

Если при преобразовании линейных и угловых перемещений использовать обычный двоичный код без дополнительного синхроимпульса, то расположенные рядом кодовые комбинации могут различаться одновременно в нескольких разрядах, поскольку двоичный код является многошаговым. Например, если на границе перехода возникла совокупность комбинаций 0111 и 1000, различающихся во всех разрядах, то за счёт неточности изготовления или установки считывателя, или неодновременности срабатывания ключей может быть прочитана ложная комбинация «нулей» и «единиц». Допустим, что третий справа считыватель сработал с отставанием, тогда в какой-то момент вместо комбинации 1000 будет прочитана комбинация 1100. Применение кода Грея для решения подобных задач позволяет свести ошибки к минимуму.

Представление информации в коде Грея

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

Powers of 4-bit Gray code permutation.svg

Ниже представлены основные алгоритмы преобразование двоичного числа в код Грея и обратного преобразования — кода Грея в двоичное число[4][5].

Алгоритм построения кода Грея

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

Например, необходимо преобразовать соседние двоичные числа 10112 = (1110) и 11002 = (1210) в код Грея:

  • сдвинем первое исходное число 1011 вправо на один бит, получим двоичную комбинацию 0101;
  • далее применим поразрядную реализацию функции «исключающее ИЛИ» над исходным числом 1011 и комбинацией сдвига 0101:
  1011

  0101
  ----
  1110G -> результат перевода двоичного числа 10112 в код Грея.

Аналогичная процедура преобразования второго двоичного числа 11002 даст в коде Грея результат 1010G.
В итоге полученные из соседних двоичных чисел комбинации кода Грея 1110G и 1010G отличаются друг от друга в одном двоичном разряде (третьем справа).

Ниже приведена схема поразрядного преобразования двоичного числа в код Грея на логических элементах XOR («исключающее ИЛИ») и таблица представления чисел в двоичном коде и в коде Грея.

Поразрядный преобразователь двоичного кода в код Грея на логических элементах XOR
Двоичное число 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Код Грея 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

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

unsigned int grayencode(unsigned int g)
{
    return g ^ (g >> 1);
}

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

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

Для перевода кода Грея в двоичное число необходимо выполнение следующих правил:

  • осуществляют сдвиг исходного числа в коде Грея на один разряд вправо и производят поразрядное сложение по модулю 2 (логическая операция «Исключающее ИЛИ») с исходным числом;
  • полученное результирующее число сдвигают на 2 разряда вправо и складывают по модулю 2 с результатом предыдущего сложения;
  • результат предыдущей операции сдвигают на 4 разряда вправо и складывают по модулю 2 с результатом предыдущего сложения;
  • очередное сложение результата предыдущей операции осуществляют с этим же числом, сдвинутым на количество разрядов, определяемое геометрической прогрессией , где n — номер шага сложения.

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

Пример перевода восьмиразрядного кода Грея в двоичное число:

   10110011G -> исходный код

    1011001  -> сдвиг на 20 (на 1 разряд)
   --------
   11101010

     111010  -> сдвиг на 21 (на 2 разряда)
   --------
   11010000

       1101  -> сдвиг на 22 (на 4 разряда). Следующий сдвиг не производится, так как приведёт к обнулению числа
   --------
   110111012 -> двоичное число

Ниже приведена схема поразрядного преобразователя из кода Грея в двоичное число, реализованная на логических элементах XOR:

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

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

unsigned int graydecode(unsigned int gray)
{
    unsigned int bin;
    for (bin = 0; gray; gray >>= 1) {
      bin ^= gray;
    }
    return bin;
}

Построение многомерного кода Грея

Существуют алгоритмы, позволяющие по -битовому коду Грея построить n-битовый код. К алгоритму такого типа относится рекурсивная генерация путём отражения исходных комбинаций битов и добавления к ним префиксов 0 или 1 (фр. prefix от лат. praefixus — «прикреплённый впереди»). Порядок действий выглядит следующим образом:

  1. Отражение исходной комбинации битов;
  2. Добавление к исходной комбинации префикса 0;
  3. Добавление к отражённой комбинации префикса 1;
  4. Объединение кодовых комбинаций, полученных в пунктах 2 и 3.
Схематичное изображение построения многомерного кода Грея

Например, создание списка комбинаций при из списка комбинаций при выглядит следующим образом:

Исходная комбинация, 00 01 11 10
Зеркальное отражение исходной комбинации 10 11 01 00
Добавление к исходной комбинации префикса 0 00 001 011 010
Добавление к отражённой комбинации префикса 1 110 111 101 100
Объединение кодовых комбинаций, 000 001 011 010 110 111 101 100

Варианты кода Грея

К вариантам кода Грея можно отнести следующие его разновидности:

  • сбалансированный код Грея;
  • двумерный код Грея.

Сбалансированный код Грея

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

Ниже представлен сбалансированный 4-битовый код Грея с 16 переходами, в течение которых каждый разряд переключается четырежды:

0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0
0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0
0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1

Для 5-битового кода Грея с 32 переходами, переключение разрядов не может быть равномерно распределено по переходам. В этом случае четыре позиции будут иметь по шесть переходов, а одна — восемь, поэтому для построения многоразрядного сбалансированного кода Грея применяют специальные алгоритмы, заключающиеся в индуктивном построении -значного кода Грея[6].

Двумерный код Грея

Диаграмма с кодом Грея для прямоугольной 16-QAM

Двумерные коды Грея используются в свя́зи для минимизации количества битовых ошибок в соседних точках квадратурной амплитудной модуляции (QAM, от англ. Quadrature amplitude modulation) в созвездии. При типичном кодировании соседние точки совокупности по горизонтали и вертикали отличаются на один бит, а соседние точки по диагонали отличаются на 2 бита.

Самые простые и наиболее часто используемые комбинации QAM состоят из точек, расположенных в квадрате, то есть 16-QAM, 64-QAM и 256-QAM (чётные степени двойки).

Двумерные коды Грея также используются в схемах идентификации местоположения. Например, код применяется к географическим картам в проекции Меркатора для расчета расстояния, объединяя характеристики расстояния Хэмминга с циклическим продолжением проекции Меркатора[7].

Одношаговые двоично-десятичные коды

Существуют двоично-десятичные коды (BCD), которые также являются одношаговыми, то есть функциональными вариантами кода Грея[8].

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

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

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

00 01 11 10
00 0 - - 9
01 1 - - 8
11 2 - - 7
10 3 4 5 6
0 1 2 3 4 5 6 7 8 9
0000 0001 0011 0010 0110 1110 1010 1011 1001 1000

Ниже приведена таблица вариантов одношаговых двоично-десятичных кодов[9].

Код
Гликсона
Коды О’Брайена Смещённый
код Грея
Коды Томпкинса Код
Петерика
0000 0000 0001 0010 0000 0010 0101
0001 0001 0011 0110 0001 0011 0001
0011 0011 0010 0111 0011 0111 0011
0010 0010 0110 0101 0010 0101 0010
0110 0110 0100 0100 0110 0100 0110
0111 1110 1100 1100 1110 1100 1110
0101 1010 1110 1101 1111 1101 1010
0100 1011 1010 1111 1101 1001 1011
1100 1001 1011 1110 1100 1011 1001
1000 1000 1001 1010 1000 1010 1101

Смещённый код Грея представляет собой код Грея, в котором исключены первые три и последние три кодовые комбинации из полного 16-позиционного набора четырёхбитового кода. Второй код О’Брайена, второй код Томпкинса и код Петерика не используют комбинации «0000» и «1111», что предоставляет практические преимущества.

Литература

Примечания

  1. КОД ГРЕЯ. Сайт phg.su. Дата обращения: 11 апреля 2024.
  2. Pulse code communication (англ.). Unite States Patent and Trademark offise (17 марта 1953). Дата обращения: 12 апреля 2024.
  3. Н. И. Сорока, Г. А. Кривинченко. Коды и кодирование. Конспект лекций. Министерство образования Республики Беларусь. Дата обращения: 11 апреля 2024.
  4. Середа С. Н. Алгоритмы построения кода Грея. Муромский институт. Владимирский государственный университет: Владимирский государственный университет. Дата обращения: 19 апреля 2024.
  5. Чепкунова Е. Г. ПОСОБИЕ ДЛЯ ПОДГОТОВКИ К ЭКЗАМЕНУ ПО ДИСЦИПЛИНЕ «ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ» РАЗДЕЛ «КОДИРОВАНИЕ ИНФОРМАЦИИ» / канд. техн. наук, доц. КНИТУ Шлеймович М.И.. — Казань: Казанский университет, 2012. — 92 с.
  6. Girish S. Bhat. Balanced Gray Codes (англ.) // The Electronic Journal of Combinatorics. — Department of Computer ScienceNorth Carolina State University, 1996.
  7. Thomas Strang, Armin Dammann, Matthias Röckl, Simon Plass. Using Gray codes as Location Identifiers (англ.) (October 2009). Дата обращения: 18 апреля 2024.
  8. В. Г. Кнорринг. Теоретические основы цифровой измерительной техники. Учебное пособие. — СПб.: Санкт-Петербургский Государственный политехнический университет. — С. 49—52. — 145 с.
  9. Gray code. BCD codes (binary coded decimal) (англ.). Wayback Machine. Дата обращения: 19 апреля 2024.
WLW Checked Off icon.svg Данная статья имеет статус «готовой». Это не говорит о качестве статьи, однако в ней уже в достаточной степени раскрыта основная тема. Если вы хотите улучшить статью — правьте смело!