Код Грея

Помимо двоичных чисел на практике применяются и другие коды, использующие два знака: 0 и 1. В этом разделе мы познакомимся с кодом Грея. При сортировке данных естественным представлением является обычное целочисленное описание, поскольку среди десяти цифр каждая на 1 больше предыдущей. При переходе к двоичному описанию эта естественность исчезает. Рассмотрим битовое представление чисел 6, 7, 8 и 9:

0110 0111 1000 1001.

Числа 6 и 7, а также 8 и 9 отличаются друг от друга на один бит. Однако числа 7 и 8 не имеют между собой ничего общего! Это свойство представления может вызвать большие проблемы при решении задач, требующих систематизации числовых данных. Для решения проблемы неоднородности представления используется код Грея.

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

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

Код Грея был разработан Фрэнком Греем, исследователем Bell Labs. Он использовал этот код в своей импульсной системе связи (на него был получен патент № 2632058).

При преобразовании бинарного кода в десятичное число мы умножаем ноль или единицу на , где – номер позиции бита в бинарном коде (; и т.д.), а затем суммируем полученные результаты.

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