Код грея исправление ошибок

Код назван в честь Фрэнка Грея, который в 1947-ом году получил патент на «отражённый двоичный код».

Алгоритм построения

Существует несколько видов кода Грея, самый простой из них — так называемый зеркальный двоичный код Грея. Строится он так:

Для получения кода длины производится шагов. На первом шаге код имеет длину и состоит из двух векторов и . На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается , а ко второй . С каждым шагом длина векторов увеличивается на , а их количество — вдвое.
Таким образом, количество векторов длины равно

Псевдокод

buildCode(n):
   GrayCode[1, n] = false
   GrayCode[2, n] = true                  // Построение кода длины 1 
   p = 2
   for i = 2 to n
      t = p
      p = p * 2
      for k = (p / 2 + 1) to p
         GrayCode[k] = GrayCode[t]        // Отражение имеющихся кодов 
         GrayCode[t, n + 1 - i] = false
         GrayCode[k, n + 1 - i] = true    // Добавление 0 и 1 в начало 
         t--
   return GrayCode 

Доказательство правильности работы алгоритма

По индукции:

• на первом шаге код отвечает условиям
• предположим, что код, получившийся на -ом шаге, является кодом Грея
• тогда на шаге : первая половина кода будет корректна, так как она совпадает с кодом с шага за исключением добавленного последнего бита . Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит . На стыке: первые бит совпадают в силу зеркальности, последние различны по построению.

Таким образом, этот код — код Грея. Индукционное предположение доказано, алгоритм работает верно.

Этот алгоритм можно обобщить и для -ичных векторов. Также известен алгоритм преобразования двоичного кода в код Грея.

Существует ещё несколько видов кода Грея — сбалансированный код Грея, код Баркера-Грея, одноколейный код Грея.^[1] Кроме того, коды Грея используются для упорядочения перестановок.

Явная формула для получения зеркального двоичного кода Грея

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

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

Чтобы показать это точнее, пусть — это -ичный полный цикл Грея, имеющий последовательность перехода , , для если в коде Грея -й и биты различны и — кол-во таких различий; отсчёты переходов (спектры) являются наборами целых чисел, определенных как для .

Код Грея является однородным или равномерно сбалансированным, если все его отсчёты переходов равны, и в этом случае у нас есть для всех . Ясно, что при , такие коды существуют только при . В противном случае, если не делится на равномерно, то можно построить сбалансированные коды Грея, где каждый отсчёт перехода либо либо .

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

Однодорожечный код Грея

Еще один вид кода Грея — это однодорожечный код Грея, разработанный Спеддингом и уточнен Хильтгеном, Патерсоном и Брандестини.

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

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

Не путать с цепными кодами, получаемых циклическим сдвигом.

Применение

Фрэнк Грей изобрел метод для преобразования аналоговых сигналов в отраженные двоичные кодовые группы с использованием аппарата на основе вакуумной трубки. Способ и устройство были запатентованы в 1953 году, а код получил название код Грея. «PCM трубка» — аппарат, запатентованный Греем, был сделан Раймондом У. Сирсом из (англ.) Bell Labs, работая с Греем и Уильямом М. Гудоллом.

• В технике коды Грея используются для минимизации ошибок при преобразовании аналоговых сигналов в цифровые (например, в датчиках-энкодерах ^[2]).

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

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

• Коды Грея используются для кодирования номера дорожек в жёстких дисках.

• Коды Грея широко применяются в теории генетических алгоритмов ^[3] для кодирования генетических признаков, представленных целыми числами.

• Коды Грея используются в Картах Карно^[4] (при передаче в карту переменные сортируются в код Грея).

• Алгоритм модуляции 2B1Q (англ. 2 Binary 1 Quandary) ^[5]

• Код Грея можно использовать также и для решения следующей задачи^[6]:

Задача о Ханойских башнях

Решение:

Пусть — количество дисков. Начнём с кода Грея длины , состоящего из одних нулей (т.е. ), и будем двигаться по кодам Грея (от переходить к ).

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

Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для самого маленького диска всегда есть две свободные позиции, потому что он самый маленький, его можно положить сверху на любой диск. Если диск не самый маленький, то для него может быть не более одной свободной позиции. Допустим, что для него свободные две позиции. Это означает, что на двух других стержнях расположены диски размером больше, чем рассматриваемый. А так как рассматриваемый диск не самый маленький, то где-то расположен наименьший. Либо он расположен на рассматриваемом диске, тогда мы не можем переместить рассматриваемый, либо на каком-то другом, но тогда у нашего диска остаётся не более одной свободной позиции. Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если нечётно, то последовательность перемещений наименьшего диска имеет вид (где — стартовый стержень, — финальный стержень, — оставшийся стержень), а если чётно, то

Выбор обусловлен тем, на каком стержне окажется в конце пирамидка, решение с помощью кода Грея является следствием классического нерекурсивного решения^[7].

См. Также

• Коды антигрея

Примечания

Источники информации

• Wikipedia — Gray code

• Википедия — Код Грея

• Robert W. Doran The Gray Code, Journal of Universal Computer Science, vol. 13, no. 11 (2007).

The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit).

For example, the representation of the decimal value «1» in binary would normally be «001» and «2» would be «010«. In Gray code, these values are represented as «001» and «011«. That way, incrementing a value from 1 to 2 requires only one bit to change, instead of two.

Gray codes are widely used to prevent spurious output from electromechanical switches and to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.

Function[edit]

Many devices indicate position by closing and opening switches. If that device uses natural binary codes, positions 3 and 4 are next to each other but all three bits of the binary representation differ:

Decimal	Binary
…	…
3	011
4	100
…	…

The problem with natural binary codes is that physical switches are not ideal: it is very unlikely that physical switches will change states exactly in synchrony. In the transition between the two states shown above, all three switches change state. In the brief period while all are changing, the switches will read some spurious position. Even without keybounce, the transition might look like 011 — 001 — 101 — 100. When the switches appear to be in position 001, the observer cannot tell if that is the «real» position 1, or a transitional state between two other positions. If the output feeds into a sequential system, possibly via combinational logic, then the sequential system may store a false value.

This problem can be solved by changing only one switch at a time, so there is never any ambiguity of position, resulting in codes assigning to each of a contiguous set of integers, or to each member of a circular list, a word of symbols such that no two code words are identical and each two adjacent code words differ by exactly one symbol. These codes are also known as unit-distance,^{[3][4][5][6][7]} single-distance, single-step, monostrophic^[8][9][6][7] or syncopic codes,^[8] in reference to the Hamming distance of 1 between adjacent codes.

Invention[edit]

In principle, there can be more than one such code for a given word length, but the term Gray code was first applied to a particular binary code for non-negative integers, the binary-reflected Gray code, or BRGC. Bell Labs researcher
George R. Stibitz described such a code in a 1941 patent application, granted in 1943.^[10][11][12] Frank Gray introduced the term reflected binary code in his 1947 patent application, remarking that the code had «as yet no recognized name».^[13] He derived the name from the fact that it «may be built up from the conventional binary code by a sort of reflection process».

In the standard encoding the least significant bit follows a repetitive pattern of 2 on, 2 off ( … 11001100 … ); the next digit a pattern of 4 on, 4 off; the nth least significant bit a pattern of 2ⁿ on 2ⁿ off. The four-bit version of this is shown below:

Decimal	Binary	Gray	Decimal of Gray
0	0000	0000	0
1	0001	0001	1
2	0010	0011	3
3	0011	0010	2
4	0100	0110	6
5	0101	0111	7
6	0110	0101	5
7	0111	0100	4
8	1000	1100	12
9	1001	1101	13
10	1010	1111	15
11	1011	1110	14
12	1100	1010	10
13	1101	1011	11
14	1110	1001	9
15	1111	1000	8

For decimal 15 the code rolls over to decimal 0 with only one switch change. This is called the cyclic or adjacency property of the code.^[14]

In modern digital communications, Gray codes play an important role in error correction. For example, in a digital modulation scheme such as QAM where data is typically transmitted in symbols of 4 bits or more, the signal’s constellation diagram is arranged so that the bit patterns conveyed by adjacent constellation points differ by only one bit. By combining this with forward error correction capable of correcting single-bit errors, it is possible for a receiver to correct any transmission errors that cause a constellation point to deviate into the area of an adjacent point. This makes the transmission system less susceptible to noise.

Despite the fact that Stibitz described this code^[10][11][12] before Gray, the reflected binary code was later named after Gray by others who used it. Two different 1953 patent applications use «Gray code» as an alternative name for the «reflected binary code»;^[15][16] one of those also lists «minimum error code» and «cyclic permutation code» among the names.^[16] A 1954 patent application refers to «the Bell Telephone Gray code».^[17] Other names include «cyclic binary code»,^[11] «cyclic progression code»,^[18][11] «cyclic permuting binary»^[19] or «cyclic permuted binary» (CPB).^[20][21]

The Gray code is sometimes misattributed to 19th century electrical device inventor Elisha Gray.^{[12][22][23][24]}

History and practical application[edit]

Mathematical puzzles[edit]

Reflected binary codes were applied to mathematical puzzles before they became known to engineers.

The binary-reflected Gray code represents the underlying scheme of the classical Chinese rings puzzle, a sequential mechanical puzzle mechanism described by the French Louis Gros in 1872.^[25][12]

It can serve as a solution guide for the Towers of Hanoi problem, based on a game by the French Édouard Lucas in 1883.^{[26][27][28][29]} Similarly, the so-called Towers of Bucharest and Towers of Klagenfurt game configurations yield ternary and pentary Gray codes.^[30]

Martin Gardner wrote a popular account of the Gray code in his August 1972 Mathematical Games column in Scientific American.^[31]

The code also forms a Hamiltonian cycle on a hypercube, where each bit is seen as one dimension.

Telegraphy codes[edit]

When the French engineer Émile Baudot changed from using a 6-unit (6-bit) code to 5-unit code for his printing telegraph system, in 1875^[32] or 1876,^[33][34] he ordered the alphabetic characters on his print wheel using a reflected binary code, and assigned the codes using only three of the bits to vowels. With vowels and consonants sorted in their alphabetical order,^[35][36][37] and other symbols appropriately placed, the 5-bit character code has been recognized as a reflected binary code.^[12] This code became known as Baudot code^[38] and, with minor changes, was eventually adopted as International Telegraph Alphabet No. 1 (ITA1, CCITT-1) in 1932.^[39][40][37]

About the same time, the German-Austrian Otto Schäffler [de]^[41] demonstrated another printing telegraph in Vienna using a 5-bit reflected binary code for the same purpose, in 1874.^[42][12]

Analog-to-digital signal conversion[edit]

Frank Gray, who became famous for inventing the signaling method that came to be used for compatible color television, invented a method to convert analog signals to reflected binary code groups using vacuum tube-based apparatus. Filed in 1947, the method and apparatus were granted a patent in 1953,^[13] and the name of Gray stuck to the codes. The «PCM tube» apparatus that Gray patented was made by Raymond W. Sears of Bell Labs, working with Gray and William M. Goodall, who credited Gray for the idea of the reflected binary code.^[43]

Gray was most interested in using the codes to minimize errors in converting analog signals to digital; his codes are still used today for this purpose.

Position encoders[edit]

Gray codes are used in linear and rotary position encoders (absolute encoders and quadrature encoders) in preference to weighted binary encoding. This avoids the possibility that, when multiple bits change in the binary representation of a position, a misread will result from some of the bits changing before others.

For example, some rotary encoders provide a disk which has an electrically conductive Gray code pattern on concentric rings (tracks). Each track has a stationary metal spring contact that provides electrical contact to the conductive code pattern. Together, these contacts produce output signals in the form of a Gray code. Other encoders employ non-contact mechanisms based on optical or magnetic sensors to produce the Gray code output signals.

Regardless of the mechanism or precision of a moving encoder, position measurement error can occur at specific positions (at code boundaries) because the code may be changing at the exact moment it is read (sampled). A binary output code could cause significant position measurement errors because it is impossible to make all bits change at exactly the same time. If, at the moment the position is sampled, some bits have changed and others have not, the sampled position will be incorrect. In the case of absolute encoders, the indicated position may be far away from the actual position and, in the case of incremental encoders, this can corrupt position tracking.

In contrast, the Gray code used by position encoders ensures that the codes for any two consecutive positions will differ by only one bit and, consequently, only one bit can change at a time. In this case, the maximum position error will be small, indicating a position adjacent to the actual position.

Genetic algorithms[edit]

Due to the Hamming distance properties of Gray codes, they are sometimes used in genetic algorithms.^[14] They are very useful in this field, since mutations in the code allow for mostly incremental changes, but occasionally a single bit-change can cause a big leap and lead to new properties.

Boolean circuit minimization[edit]

Gray codes are also used in labelling the axes of Karnaugh maps since 1953^[44][45][46] as well as in Händler circle graphs since 1958,^{[47][48][49][50]} both graphical methods for logic circuit minimization.

Error correction[edit]

In modern digital communications, Gray codes play an important role in error correction. For example, in a digital modulation scheme such as QAM where data is typically transmitted in symbols of 4 bits or more, the signal’s constellation diagram is arranged so that the bit patterns conveyed by adjacent constellation points differ by only one bit. By combining this with forward error correction capable of correcting single-bit errors, it is possible for a receiver to correct any transmission errors that cause a constellation point to deviate into the area of an adjacent point. This makes the transmission system less susceptible to noise.

Communication between clock domains[edit]

Digital logic designers use Gray codes extensively for passing multi-bit count information between synchronous logic that operates at different clock frequencies. The logic is considered operating in different «clock domains». It is fundamental to the design of large chips that operate with many different clocking frequencies.

Cycling through states with minimal effort[edit]

If a system has to cycle through all possible combinations of on-off states of some set of controls, and the changes of the controls require non-trivial expense (e.g. time, wear, human work), a Gray code minimizes the number of setting changes to just one change for each combination of states. An example would be testing a piping system for all combinations of settings of its manually operated valves.

A balanced Gray code can be constructed,^[51] that flips every bit equally often. Since bit-flips are evenly distributed, this is optimal in the following way: balanced Gray codes minimize the maximal count of bit-flips for each digit.

Gray code counters and arithmetic[edit]

George R. Stibitz utilized a reflected binary code in a binary pulse counting device in 1941 already.^[10][11][12]

A typical use of Gray code counters is building a FIFO (first-in, first-out) data buffer that has read and write ports that exist in different clock domains. The input and output counters inside such a dual-port FIFO are often stored using Gray code to prevent invalid transient states from being captured when the count crosses clock domains.^[52]
The updated read and write pointers need to be passed between clock domains when they change, to be able to track FIFO empty and full status in each domain. Each bit of the pointers is sampled non-deterministically for this clock domain transfer. So for each bit, either the old value or the new value is propagated. Therefore, if more than one bit in the multi-bit pointer is changing at the sampling point, a «wrong» binary value (neither new nor old) can be propagated. By guaranteeing only one bit can be changing, Gray codes guarantee that the only possible sampled values are the new or old multi-bit value. Typically Gray codes of power-of-two length are used.

Sometimes digital buses in electronic systems are used to convey quantities that can only increase or decrease by one at a time, for example the output of an event counter which is being passed between clock domains or to a digital-to-analog converter. The advantage of Gray codes in these applications is that differences in the propagation delays of the many wires that represent the bits of the code cannot cause the received value to go through states that are out of the Gray code sequence. This is similar to the advantage of Gray codes in the construction of mechanical encoders, however the source of the Gray code is an electronic counter in this case. The counter itself must count in Gray code, or if the counter runs in binary then the output value from the counter must be reclocked after it has been converted to Gray code, because when a value is converted from binary to Gray code,^{[nb 1]} it is possible that differences in the arrival times of the binary data bits into the binary-to-Gray conversion circuit will mean that the code could go briefly through states that are wildly out of sequence. Adding a clocked register after the circuit that converts the count value to Gray code may introduce a clock cycle of latency, so counting directly in Gray code may be advantageous.^[53]

To produce the next count value in a Gray-code counter, it is necessary to have some combinational logic that will increment the current count value that is stored. One way to increment a Gray code number is to convert it into ordinary binary code,^[54] add one to it with a standard binary adder, and then convert the result back to Gray code.^[55] Other methods of counting in Gray code are discussed in a report by Robert W. Doran, including taking the output from the first latches of the master-slave flip flops in a binary ripple counter.^[56]

Gray code addressing[edit]

As the execution of program code typically causes an instruction memory access pattern of locally consecutive addresses, bus encodings using Gray code addressing instead of binary addressing can reduce the number of state changes of the address bits significantly, thereby reducing the CPU power consumption in some low-power designs.^[57][58]

Constructing an n-bit Gray code[edit]

The binary-reflected Gray code list for n bits can be generated recursively from the list for n − 1 bits by reflecting the list (i.e. listing the entries in reverse order), prefixing the entries in the original list with a binary 0, prefixing the entries in the reflected list with a binary 1, and then concatenating the original list with the reversed list.^[12] For example, generating the n = 3 list from the n = 2 list:

The one-bit Gray code is G₁ = (0,1). This can be thought of as built recursively as above from a zero-bit Gray code G₀ = ( Λ ) consisting of a single entry of zero length. This iterative process of generating G_n+1 from G_n makes the following properties of the standard reflecting code clear:

• G_n is a permutation of the numbers 0, …, 2ⁿ − 1. (Each number appears exactly once in the list.)
• G_n is embedded as the first half of G_n+1.
• Therefore, the coding is stable, in the sense that once a binary number appears in G_n it appears in the same position in all longer lists; so it makes sense to talk about the reflective Gray code value of a number: G(m) = the mth reflecting Gray code, counting from 0.
• Each entry in G_n differs by only one bit from the previous entry. (The Hamming distance is 1.)
• The last entry in G_n differs by only one bit from the first entry. (The code is cyclic.)

These characteristics suggest a simple and fast method of translating a binary value into the corresponding Gray code. Each bit is inverted if the next higher bit of the input value is set to one. This can be performed in parallel by a bit-shift and exclusive-or operation if they are available: the nth Gray code is obtained by computing . Prepending a 0 bit leaves the order of the code words unchanged, prepending a 1 bit reverses the order of the code words. If the bits at position of codewords are inverted, the order of neighbouring blocks of codewords is reversed. For example, if bit 0 is inverted in a 3 bit codeword sequence, the order of two neighbouring codewords is reversed

000,001,010,011,100,101,110,111 → 001,000,011,010,101,100,111,110  (invert bit 0)

If bit 1 is inverted, blocks of 2 codewords change order:

000,001,010,011,100,101,110,111 → 010,011,000,001,110,111,100,101  (invert bit 1)

If bit 2 is inverted, blocks of 4 codewords reverse order:

000,001,010,011,100,101,110,111 → 100,101,110,111,000,001,010,011  (invert bit 2)

Thus, performing an exclusive or on a bit at position with the bit at position leaves the order of codewords intact if , and reverses the order of blocks of codewords if . Now, this is exactly the same operation as the reflect-and-prefix method to generate the Gray code.

A similar method can be used to perform the reverse translation, but the computation of each bit depends on the computed value of the next higher bit so it cannot be performed in parallel. Assuming is the th Gray-coded bit ( being the most significant bit), and is the th binary-coded bit ( being the most-significant bit), the reverse translation can be given recursively: , and . Alternatively, decoding a Gray code into a binary number can be described as a prefix sum of the bits in the Gray code, where each individual summation operation in the prefix sum is performed modulo two.

To construct the binary-reflected Gray code iteratively, at step 0 start with the , and at step find the bit position of the least significant 1 in the binary representation of and flip the bit at that position in the previous code to get the next code . The bit positions start 0, 1, 0, 2, 0, 1, 0, 3, ….^{[nb 2]} See find first set for efficient algorithms to compute these values.

Converting to and from Gray code[edit]

The following functions in C convert between binary numbers and their associated Gray codes. While it may seem that Gray-to-binary conversion requires each bit to be handled one at a time, faster algorithms exist.^{[59][54][nb 1]}

typedef unsigned int uint;

// This function converts an unsigned binary number to reflected binary Gray code.
uint BinaryToGray(uint num)
{
    return num ^ (num >> 1); // The operator >> is shift right. The operator ^ is exclusive or.
}

// This function converts a reflected binary Gray code number to a binary number.
uint GrayToBinary(uint num)
{
    uint mask = num;
    while (mask) {           // Each Gray code bit is exclusive-ored with all more significant bits.
        mask >>= 1;
        num   ^= mask;
    }
    return num;
}

// A more efficient version for Gray codes 32 bits or fewer through the use of SWAR (SIMD within a register) techniques. 
// It implements a parallel prefix XOR function. The assignment statements can be in any order.
// 
// This function can be adapted for longer Gray codes by adding steps.

uint GrayToBinary32(uint num)
{
    num ^= num >> 16;
    num ^= num >>  8;
    num ^= num >>  4;
    num ^= num >>  2;
    num ^= num >>  1;
    return num;
}
// A Four-bit-at-once variant changes a binary number (abcd)2 to (abcd)2 ^ (00ab)2, then to (abcd)2 ^ (00ab)2 ^ (0abc)2 ^ (000a)2.

On newer processors, the number of ALU instructions in the decoding step can be reduced by taking advantage of the CLMUL instruction set. If MASK is the constant binary string of ones ended with a single zero digit, then carryless multiplication of MASK with the grey encoding of x will always give either x or its bitwise negation.

Special types of Gray codes[edit]

In practice, «Gray code» almost always refers to a binary-reflected Gray code (BRGC).
However, mathematicians have discovered other kinds of Gray codes.
Like BRGCs, each consists of a list of words, where each word differs from the next in only one digit (each word has a Hamming distance of 1 from the next word).

Gray codes with n bits and of length less than 2ⁿ[edit]

It is possible to construct binary Gray codes with n bits with a length of less than 2ⁿ, if the length is even. One possibility is to start with a balanced Gray code and remove pairs of values at either the beginning and the end, or in the middle.^[60] OEIS sequence A290772 ^[61] gives the number of possible Gray sequences of length 2 n which include zero and use the minimum number of bits.

n-ary Gray code[edit]

There are many specialized types of Gray codes other than the binary-reflected Gray code. One such type of Gray code is the n-ary Gray code, also known as a non-Boolean Gray code. As the name implies, this type of Gray code uses non-Boolean values in its encodings.

For example, a 3-ary (ternary) Gray code would use the values 0,1,2.^[30] The (n, k)-Gray code is the n-ary Gray code with k digits.^[62]
The sequence of elements in the (3, 2)-Gray code is: 00,01,02,12,11,10,20,21,22. The (n, k)-Gray code may be constructed recursively, as the BRGC, or may be constructed iteratively. An algorithm to iteratively generate the (N, k)-Gray code is presented (in C):

// inputs: base, digits, value
// output: Gray
// Convert a value to a Gray code with the given base and digits.
// Iterating through a sequence of values would result in a sequence
// of Gray codes in which only one digit changes at a time.
void toGray(unsigned base, unsigned digits, unsigned value, unsigned gray[digits])
{ 
	unsigned baseN[digits];	// Stores the ordinary base-N number, one digit per entry
	unsigned i;		// The loop variable
 
	// Put the normal baseN number into the baseN array. For base 10, 109 
	// would be stored as [9,0,1]
	for (i = 0; i < digits; i++) {
		baseN[i] = value % base;
		value    = value / base;
	}
 
	// Convert the normal baseN number into the Gray code equivalent. Note that
	// the loop starts at the most significant digit and goes down.
	unsigned shift = 0;
	while (i--) {
		// The Gray digit gets shifted down by the sum of the higher
		// digits.
		gray[i] = (baseN[i] + shift) % base;
		shift = shift + base - gray[i];	// Subtract from base so shift is positive
	}
}
// EXAMPLES
// input: value = 1899, base = 10, digits = 4
// output: baseN[] = [9,9,8,1], gray[] = [0,1,7,1]
// input: value = 1900, base = 10, digits = 4
// output: baseN[] = [0,0,9,1], gray[] = [0,1,8,1]

There are other Gray code algorithms for (n,k)-Gray codes. The (n,k)-Gray code produced by the above algorithm is always cyclical; some algorithms, such as that by Guan,^[62] lack this property when k is odd. On the other hand, while only one digit at a time changes with this method, it can change by wrapping (looping from n − 1 to 0). In Guan’s algorithm, the count alternately rises and falls, so that the numeric difference between two Gray code digits is always one.

Gray codes are not uniquely defined, because a permutation of the columns of such a code is a Gray code too. The above procedure produces a code in which the lower the significance of a digit, the more often it changes, making it similar to normal counting methods.

See also Skew binary number system, a variant ternary number system where at most two digits change on each increment, as each increment can be done with at most one digit carry operation.

Balanced Gray code[edit]

Although the binary reflected Gray code is useful in many scenarios, it is not optimal in certain cases because of a lack of «uniformity».^[51] In balanced Gray codes, the number of changes in different coordinate positions are as close as possible. To make this more precise, let G be an R-ary complete Gray cycle having transition sequence ; the transition counts (spectrum) of G are the collection of integers defined by

A Gray code is uniform or uniformly balanced if its transition counts are all equal, in which case we have
for all k. Clearly, when , such codes exist only if n is a power of 2.^[63] If n is not a power of 2, it is possible to construct well-balanced binary codes where the difference between two transition counts is at most 2; so that (combining both cases) every transition count is either or .^[51] Gray codes can also be exponentially balanced if all of their transition counts are adjacent powers of two, and such codes exist for every power of two.^[64]

For example, a balanced 4-bit Gray code has 16 transitions, which can be evenly distributed among all four positions (four transitions per position), making it uniformly balanced:^[51]

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

whereas a balanced 5-bit Gray code has a total of 32 transitions, which cannot be evenly distributed among the positions. In this example, four positions have six transitions each, and one has eight:^[51]

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

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

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

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

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

We will now show a construction^[65] and implementation^[66] for well-balanced binary Gray codes which allows us to generate an n-digit balanced Gray code for every n. The main principle is to inductively construct an (n + 2)-digit Gray code given an n-digit Gray code G in such a way that the balanced property is preserved. To do this, we consider partitions of into an even number L of non-empty blocks of the form

where , , and ). This partition induces an -digit Gray code given by

If we define the transition multiplicities

to be the number of times the digit in position i changes between consecutive blocks in a partition, then for the (n + 2)-digit Gray code induced by this partition the transition spectrum is

The delicate part of this construction is to find an adequate partitioning of a balanced n-digit Gray code such that the code induced by it remains balanced, but for this only the transition multiplicities matter; joining two consecutive blocks over a digit transition and splitting another block at another digit transition produces a different Gray code with exactly the same transition spectrum , so one may for example^[64] designate the first transitions at digit as those that fall between two blocks. Uniform codes can be found when and , and this construction can be extended to the R-ary case as well.^[65]

Long run Gray codes[edit]

Long run (or maximum gap) Gray codes maximize the distance between consecutive changes of digits in the same position. That is, the minimum run-length of any bit remains unchanged for as long as possible.^[67]

Monotonic Gray codes[edit]

Monotonic codes are useful in the theory of interconnection networks, especially for minimizing dilation for linear arrays of processors.^[68]
If we define the weight of a binary string to be the number of 1s in the string, then although we clearly cannot have a Gray code with strictly increasing weight, we may want to approximate this by having the code run through two adjacent weights before reaching the next one.

We can formalize the concept of monotone Gray codes as follows: consider the partition of the hypercube into levels of vertices that have equal weight, i.e.

for . These levels satisfy . Let be the subgraph of induced by , and let be the edges in . A monotonic Gray code is then a Hamiltonian path in such that whenever comes before in the path, then .

An elegant construction of monotonic n-digit Gray codes for any n is based on the idea of recursively building subpaths of length having edges in .^[68] We define , whenever or , and

otherwise. Here, is a suitably defined permutation and refers to the path P with its coordinates permuted by . These paths give rise to two monotonic n-digit Gray codes and given by

The choice of which ensures that these codes are indeed Gray codes turns out to be . The first few values of are shown in the table below.

	j = 0	j = 1	j = 2	j = 3
n = 1	0, 1
n = 2	00, 01	10, 11
n = 3	000, 001	100, 110, 010, 011	101, 111
n = 4	0000, 0001	1000, 1100, 0100, 0110, 0010, 0011	1010, 1011, 1001, 1101, 0101, 0111	1110, 1111

These monotonic Gray codes can be efficiently implemented in such a way that each subsequent element can be generated in O(n) time. The algorithm is most easily described using coroutines.

Monotonic codes have an interesting connection to the Lovász conjecture, which states that every connected vertex-transitive graph contains a Hamiltonian path. The «middle-level» subgraph is vertex-transitive (that is, its automorphism group is transitive, so that each vertex has the same «local environment» and cannot be differentiated from the others, since we can relabel the coordinates as well as the binary digits to obtain an automorphism) and the problem of finding a Hamiltonian path in this subgraph is called the «middle-levels problem», which can provide insights into the more general conjecture. The question has been answered affirmatively for , and the preceding construction for monotonic codes ensures a Hamiltonian path of length at least 0.839N where N is the number of vertices in the middle-level subgraph.^[69]

Beckett–Gray code[edit]

Another type of Gray code, the Beckett–Gray code, is named for Irish playwright Samuel Beckett, who was interested in symmetry. His play «Quad» features four actors and is divided into sixteen time periods. Each period ends with one of the four actors entering or leaving the stage. The play begins and ends with an empty stage, and Beckett wanted each subset of actors to appear on stage exactly once.^[70] Clearly the set of actors currently on stage can be represented by a 4-bit binary Gray code. Beckett, however, placed an additional restriction on the script: he wished the actors to enter and exit so that the actor who had been on stage the longest would always be the one to exit. The actors could then be represented by a first in, first out queue, so that (of the actors onstage) the actor being dequeued is always the one who was enqueued first.^[70] Beckett was unable to find a Beckett–Gray code for his play, and indeed, an exhaustive listing of all possible sequences reveals that no such code exists for n = 4. It is known today that such codes do exist for n = 2, 5, 6, 7, and 8, and do not exist for n = 3 or 4. An example of an 8-bit Beckett–Gray code can be found in Donald Knuth’s Art of Computer Programming.^[12] According to Sawada and Wong, the search space for n = 6 can be explored in 15 hours, and more than 9,500 solutions for the case n = 7 have been found.^[71]

Snake-in-the-box codes[edit]

Snake-in-the-box codes, or snakes, are the sequences of nodes of induced paths in an n-dimensional hypercube graph, and coil-in-the-box codes,^[72] or coils, are the sequences of nodes of induced cycles in a hypercube. Viewed as Gray codes, these sequences have the property of being able to detect any single-bit coding error. Codes of this type were first described by William H. Kautz in the late 1950s;^[4] since then, there has been much research on finding the code with the largest possible number of codewords for a given hypercube dimension.

Single-track Gray code[edit]

Yet another kind of Gray code is the single-track Gray code (STGC) developed by Norman B. Spedding^[73][74] and refined by Hiltgen, Paterson and Brandestini in «Single-track Gray codes» (1996).^[75][76] The STGC is a cyclical list of P unique binary encodings of length n such that two consecutive words differ in exactly one position, and when the list is examined as a P × n matrix, each column is a cyclic shift of the first column.^[77]

The name comes from their use with rotary encoders, where a number of tracks are being sensed by contacts, resulting for each in an output of 0 or 1. To reduce noise due to different contacts not switching at exactly the same moment in time, one preferably sets up the tracks so that the data output by the contacts are in Gray code. To get high angular accuracy, one needs lots of contacts; in order to achieve at least 1° accuracy, one needs at least 360 distinct positions per revolution, which requires a minimum of 9 bits of data, and thus the same number of contacts.

If all contacts are placed at the same angular position, then 9 tracks are needed to get a standard BRGC with at least 1° accuracy. However, if the manufacturer moves a contact to a different angular position (but at the same distance from the center shaft), then the corresponding «ring pattern» needs to be rotated the same angle to give the same output. If the most significant bit (the inner ring in Figure 1) is rotated enough, it exactly matches the next ring out. Since both rings are then identical, the inner ring can be cut out, and the sensor for that ring moved to the remaining, identical ring (but offset at that angle from the other sensor on that ring). Those two sensors on a single ring make a quadrature encoder. That reduces the number of tracks for a «1° resolution» angular encoder to 8 tracks. Reducing the number of tracks still further cannot be done with BRGC.

For many years, Torsten Sillke^[78] and other mathematicians believed that it was impossible to encode position on a single track such that consecutive positions differed at only a single sensor, except for the 2-sensor, 1-track quadrature encoder. So for applications where 8 tracks were too bulky, people used single-track incremental encoders (quadrature encoders) or 2-track «quadrature encoder + reference notch» encoders.

Norman B. Spedding, however, registered a patent in 1994 with several examples showing that it was possible.^[73] Although it is not possible to distinguish 2ⁿ positions with n sensors on a single track, it is possible to distinguish close to that many. Etzion and Paterson conjecture that when n is itself a power of 2, n sensors can distinguish at most 2ⁿ − 2n positions and that for prime n the limit is 2ⁿ − 2 positions.^[79] The authors went on to generate a 504-position single track code of length 9 which they believe is optimal. Since this number is larger than 2⁸ = 256, more than 8 sensors are required by any code, although a BRGC could distinguish 512 positions with 9 sensors.

An STGC for P = 30 and n = 5 is reproduced here:

Single-track Gray code for 30 positions

Angle	Code		Angle	Code		Angle	Code		Angle	Code		Angle	Code
0°	10000	72°	01000	144°	00100	216°	00010	288°	00001
12°	10100	84°	01010	156°	00101	228°	10010	300°	01001
24°	11100	96°	01110	168°	00111	240°	10011	312°	11001
36°	11110	108°	01111	180°	10111	252°	11011	324°	11101
48°	11010	120°	01101	192°	10110	264°	01011	336°	10101
60°	11000	132°	01100	204°	00110	276°	00011	348°	10001

Each column is a cyclic shift of the first column, and from any row to the next row only one bit changes.^[80]
The single-track nature (like a code chain) is useful in the fabrication of these wheels (compared to BRGC), as only one track is needed, thus reducing their cost and size.
The Gray code nature is useful (compared to chain codes, also called De Bruijn sequences), as only one sensor will change at any one time, so the uncertainty during a transition between two discrete states will only be plus or minus one unit of angular measurement the device is capable of resolving.^[81]

Two-dimensional Gray code[edit]

Two-dimensional Gray codes are used in communication to minimize the number of bit errors in quadrature amplitude modulation (QAM) adjacent points in the constellation. In a typical encoding the horizontal and vertical adjacent constellation points differ by a single bit, and diagonal adjacent points differ by 2 bits.^[82]

Two-dimensional Gray codes also have uses in location identifications schemes, where the code would be applied to area maps such as a Mercator projection of the earth’s surface and an appropriate cyclic two-dimensional distance function such as the Mannheim metric be used to calculate the distance between two encoded locations, thereby combining the characteristics of the Hamming distance with the cyclic continuation of a Mercator projection.^[83]

Excess-Gray-Code[edit]

If a subsection of a specific codevalue is extracted from that value, for example the last 3 bits of a 4-bit gray-code, the resulting code will be an «excess gray code». This code shows the property of counting backwards in those extracted bits if the original value is further increased. Reason for this is that gray-encoded values do not show the behaviour of overflow, known from classic binary encoding, when increasing past the «highest» value.

Example: The highest 3-bit gray code, 7, is encoded as (0)100. Adding 1 results in number 8, encoded in gray as 1100. The last 3 bits do not overflow and count backwards if you further increase the original 4 bit code.

When working with sensors that output multiple, gray-encoded values in a serial fashion, one should therefore pay attention whether the sensor produces those multiple values encoded in 1 single gray-code or as separate ones, as otherwise the values might appear to be counting backwards when an «overflow» is expected.

Gray isometry[edit]

The bijective mapping { 0 ↔ 00, 1 ↔ 01, 2 ↔ 11, 3 ↔ 10 } establishes an isometry between the metric space over the finite field with the metric given by the Hamming distance and the metric space over the finite ring (the usual modular arithmetic) with the metric given by the Lee distance. The mapping is suitably extended to an isometry of the Hamming spaces and . Its importance lies in establishing a correspondence between various «good» but not necessarily linear codes as Gray-map images in of ring-linear codes from .^[84][85]

[edit]

There are a number of binary codes similar to Gray codes, including:

• Datex codes aka Giannini codes (1954), as described by Carl P. Spaulding,^{[8][86][87][88][89][7]} use a variant of O’Brien code II.
• Codes used by Varec (ca. 1954),^{[90][91][92][93]} use a variant of O’Brien code I as well as base-12 and base-16 Gray code variants.
• Lucal code (1959)^[1][2][56] aka modified reflected binary code (MRB)^{[1][2][nb 3]}
• Gillham code (1961/1962),^{[87][94][7][95][96]} uses a variant of Datex code and O’Brien code II.
• Leslie and Russell code (1964)^{[97][9][98][94]}
• Royal Radar Establishment code^[94]
• Hoklas code (1988)^{[99][100][101]}

The following binary-coded decimal (BCD) codes are Gray code variants as well:

• Petherick code (1953),^{[18][102][103][104][54][100][nb 4]} also known as Royal Aircraft Establishment (RAE) code.^[105]
• O’Brien codes I and II (1955)^{[106][107][108][88][89][100]} (An O’Brien type-I code^{[nb 5]} was already described by Frederic A. Foss of IBM^[109][110] and used by Varec in 1954. Later, it was also known as Watts code or Watts reflected decimal (WRD) code and is sometimes ambiguously referred to as reflected binary modified Gray code.^{[111][19][20][112][113][114][115][116][117][nb 1][nb 3]} An O’Brien type-II code was already used by Datex in 1954.^{[nb 4]})
• Excess-3 Gray code (1956)^[118] (aka Gray excess-3 code,^[88][89][7] Gray 3-excess code, reflex excess-3 code, excess Gray code,^[100] Gray excess code, 10-excess-3 Gray code or Gray–Stibitz code), described by Frank P. Turvey Jr. of ITT.^[118]
• Tompkins codes I and II (1956)^{[3][107][108][88][89][100]}
• Glixon code (1957), sometimes ambiguously also called modified Gray code^{[119][54][120][121][107][108][88][89][100][nb 3][nb 5]}

See also[edit]

• Linear-feedback shift register
• De Bruijn sequence
• Steinhaus–Johnson–Trotter algorithm – an algorithm that generates Gray codes for the factorial number system
• Minimum distance code
• Prouhet–Thue–Morse sequence – related to inverse Gray code
• Ryser formula
• Hilbert curve

Notes[edit]

References[edit]

Further reading[edit]

• Richards, Richard Kohler (1955). Arithmetic Operations in Digital Computers (5 ed.). New York, USA: D. Van Nostrand Co., Inc.
• Richards, Richard Kohler (1967). Electronic Digital Components and Circuits. D. Van Nostrand Co., Inc. pp. 490, 500–504, 510–511.
• Black, Paul E. (2004-02-25). «Gray code». NIST.
• Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (2007). «Section 22.3. Gray Codes». Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York, USA: Cambridge University Press. ISBN 978-0-521-88068-8.
• Savage, Carla Diane (1997). «A Survey of Combinatorial Gray Codes». SIAM Review. Society for Industrial and Applied Mathematics (SIAM). 39 (4): 605–629. Bibcode:1997SIAMR..39..605S. CiteSeerX 10.1.1.39.1924. doi:10.1137/S0036144595295272. JSTOR 2132693. S2CID 6375360.
• Wilf, Herbert Saul (1989). «Chapters 1–3». Combinatorial algorithms: An update. Society for Industrial and Applied Mathematics (SIAM). ISBN 0-89871-231-9.
• Dewar, Megan; Stevens, Brett (2012-08-29). Ordering Block Designs – Gray Codes, Universal Cycles and Configuration. CMS Books in Mathematics (1 ed.). New York, USA: Springer Science+Business Media. doi:10.1007/978-1-4614-4325-4. ISBN 978-1-46144324-7. ISSN 1613-5237.
• Maxfield, Clive «Max» (2012-10-01) [2011-05-28]. «Gray Code Fundamentals». Design How-To. EETimes. Part 1. Archived from the original on 2017-10-30. Retrieved 2017-10-30. Part 2 Part 3
• Warren, Jr., Henry S. (2013). «Chapter 13: Gray Code». Hacker’s Delight (2 ed.). Addison Wesley – Pearson Education, Inc. pp. 311–317. ISBN 978-0-321-84268-8. (7 pages)
• Zinovik, Igor; Kroening, Daniel; Chebiryak, Yury (2008-03-21). «Computing Binary Combinatorial Gray Codes Via Exhaustive Search With SAT Solvers». IEEE Transactions on Information Theory. IEEE. 54 (4): 1819–1823. doi:10.1109/TIT.2008.917695. hdl:20.500.11850/11304. S2CID 2854180. (5 pages)
• O’Brien, Joseph A. (June 1957). «Unit-Distance Binary-Decimal Code Translators». IRE Transactions on Electronic Computers. EC-6 (2): 122–123. doi:10.1109/TEC.1957.5221585. ISSN 0367-9950. Retrieved 2020-05-25. (2 pages)
• Barr, K. G. (March 1981). «A decimal Gray code – Easily converted for shaft position coding» (PDF). Wireless World. Vol. 87, no. 1542. Faculty of Natural Sciences, University of the West Indies. pp. 86–87. Archived (PDF) from the original on 2020-07-28. Retrieved 2020-07-28.

External links[edit]

• «Gray Code» demonstration by Michael Schreiber, Wolfram Demonstrations Project (with Mathematica implementation). 2007.
• NIST Dictionary of Algorithms and Data Structures: Gray code.
• Hitch Hiker’s Guide to Evolutionary Computation, Q21: What are Gray codes, and why are they used?, including C code to convert between binary and BRGC.
• Dragos A. Harabor uses Gray codes in a 3D digitizer.
• Single-track gray codes, binary chain codes (Lancaster 1994), and linear-feedback shift registers are all useful in finding one’s absolute position on a single-track rotary encoder (or other position sensor).
• AMS Column: Gray codes
• Optical Encoder Wheel Generator
• ProtoTalk.net – Understanding Quadrature Encoding – Covers quadrature encoding in more detail with a focus on robotic applications

Отражение двоичного кода ( RBC ), также известный как отраженный двоичный ( RB ) или код Грея после Frank Gray , является упорядочение двоичной системе счисления таким образом, что две последовательные значения различаются только в одной битовой (двоичный разряд).

Например, представление десятичного значения «1» в двоичном формате обычно будет « 001 », а «2» будет « 010 ». В коде Грея эти значения представлены как « 001 » и « 011 ». Таким образом, для увеличения значения с 1 до 2 потребуется изменить только один бит вместо двух.

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

Мотивация и имя

Многие устройства указывают положение, замыкая и размыкая переключатели. Если это устройство использует естественные двоичные коды , позиции 3 и 4 находятся рядом друг с другом, но все три бита двоичного представления различаются:

Десятичный	Двоичный
…	…
3	011
4	100
…	…

Проблема с естественными двоичными кодами заключается в том, что физические переключатели не идеальны: очень маловероятно, что физические переключатели будут изменять состояния точно синхронно. При переходе между двумя показанными выше состояниями все три переключателя изменяют состояние. В течение короткого периода времени, когда все меняется, переключатели будут считывать какое-то ложное положение. Даже без нажатия клавиш переход может выглядеть как 011 — 001 — 101 — 100 . Когда переключатели оказываются в положении 001 , наблюдатель не может сказать, является ли это «реальным» положением 1 или переходным состоянием между двумя другими положениями. Если выходной сигнал поступает в последовательную систему, возможно, через комбинационную логику , тогда последовательная система может сохранить ложное значение.

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

В принципе, может быть более одного такого кода для данной длины слова, но термин «код Грея» сначала был применен к конкретному двоичному коду для неотрицательных целых чисел, двоично-отраженному коду Грея или BRGC . Исследователь
Bell Labs Джордж Р. Стибиц описал такой код в заявке на патент 1941 года, выданной в 1943 году. Фрэнк Грей ввел термин « отраженный двоичный код» в своей патентной заявке 1947 года, отметив, что код «пока не имеет общепризнанного имени». Он получил название от того факта, что он «может быть построен из обычного двоичного кода посредством своего рода процесса отражения».

В стандартном кодировании младший значащий бит следует повторяющейся схеме: 2 вкл. , 2 выкл. (… 11001100 …); следующая цифра — комбинация 4 вкл., 4 выкл .; п — й наименее значимый бит картина 2 ^п 2 ^п выкл. Четырехбитная версия этого показана ниже:

Десятичный	Двоичный	серый	Десятичная дробь серого
0	0000	0000	0
1	0001	0001	1
2	0010	0011	3
3	0011	0010	2
4	0100	0110	6
5	0101	0111	7
6	0110	0101	5
7	0111	0100	4
8	1000	1100	12
9	1001	1101	13
10	1010	1111	15
11	1011	1110	14
12	1100	1010	10
13	1101	1011	11
14	1110	1001	9
15	1111	1000	8

Для десятичного числа 15 код переключается на десятичный 0 с одним переключением переключателя. Это называется свойством цикличности или смежности кода.

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

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

Код Грея иногда ошибочно приписывали Элише Грею .

История и практическое применение

Математические головоломки

Отраженные двоичные коды применялись к математическим головоломкам еще до того, как они стали известны инженерам.

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

Он может служить руководством для решения проблемы Ханойских башен , основанной на игре французского Эдуарда Лукаса в 1883 году. Аналогичным образом, так называемые игровые конфигурации «Башни Бухареста» и «Башни Клагенфурта» дают троичные и пентарные коды Грея.

Мартин Гарднер написал популярное описание кода Грея в своей колонке «Математические игры» в журнале Scientific American за август 1972 года .

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

Коды телеграфии

Когда французский инженер Эмиль Бодо в 1875 или 1876 году перешел от использования 6-значного (6-битного) кода к 5-значному коду для своей печатной телеграфной системы, он заказал буквенные символы на своем печатном колесе, используя отраженный двоичный код, и назначил коды, используя только три из битов для гласных. Благодаря тому, что гласные и согласные звуки отсортированы в алфавитном порядке, а другие символы размещены соответствующим образом, 5-битный символьный код был распознан как отраженный двоичный код. Этот код стал известен как код Бодо и с небольшими изменениями в конечном итоге был принят как Международный телеграфный алфавит № 1 (ITA1, CCITT-1) в 1932 году.

Примерно в то же время немецко-австрийский Отто Шеффлер  [ де ] продемонстрировал в Вене еще один печатный телеграф, использующий для той же цели 5-битный отраженный двоичный код, в 1874 году.

Преобразование аналого-цифрового сигнала

Фрэнк Грей , прославившийся тем, что изобрел метод передачи сигналов, который стал использоваться для совместимого цветного телевидения, изобрел метод преобразования аналоговых сигналов в группы отраженного двоичного кода с использованием устройства на основе вакуумной лампы . Поданный в 1947 году, метод и устройство получили патент в 1953 году, и имя Грэя закрепилось за кодами. Аппарат « трубка ИКМ », который запатентовал Грей, был создан Рэймондом У. Сирсом из Bell Labs в сотрудничестве с Греем и Уильямом М. Гудоллом, которые приписали Грею идею отраженного двоичного кода.

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

Датчики положения

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

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

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

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

Генетические алгоритмы

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

Минимизация логической схемы

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

Исправление ошибки

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

Связь между доменами часов

Разработчики цифровой логики широко используют коды Грея для передачи многобитовой информации между синхронной логикой, которая работает на разных тактовых частотах. Считается, что логика работает в разных «тактовых областях». Это фундаментально для дизайна больших микросхем, которые работают с множеством разных тактовых частот.

Циклическое переключение состояний с минимальными усилиями

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

Сбалансированный Серый код может быть построен, что каждый бит переворачивается одинаково часто. Поскольку битовые перевороты распределены равномерно, это оптимально следующим образом: сбалансированные коды Грея минимизируют максимальное количество битовых переворотов для каждой цифры.

Счетчики кода Грея и арифметика

Джордж Р. Стибиц использовал отраженный двоичный код в устройстве для счета двоичных импульсов еще в 1941 году.

Типичное использование счетчиков кода Грея — это создание буфера данных FIFO (first-in, first-out), который имеет порты чтения и записи, которые существуют в разных тактовых доменах. Входные и выходные счетчики внутри такого двухпортового FIFO часто хранятся с использованием кода Грея, чтобы предотвратить захват недопустимых переходных состояний, когда счетчик пересекает тактовые области. Обновленные указатели чтения и записи должны передаваться между доменами часов при их изменении, чтобы иметь возможность отслеживать состояние пустого и полного FIFO в каждом домене. Каждый бит указателей выбирается недетерминированно для этой передачи тактовой области. Таким образом, для каждого бита распространяется либо старое значение, либо новое значение. Следовательно, если более одного бита в многобитовом указателе изменяется в точке выборки, «неправильное» двоичное значение (ни новое, ни старое) не может быть передано. Гарантируя возможность изменения только одного бита, коды Грея гарантируют, что единственными возможными значениями выборки являются новое или старое многобитовое значение. Обычно используются коды Грея с длиной степени двойки.

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

Чтобы произвести следующее значение счетчика в счетчике кода Грея, необходимо иметь некоторую комбинационную логику, которая будет увеличивать текущее сохраненное значение счетчика. Один из способов увеличения числа кода Грея — преобразовать его в обычный двоичный код, добавить к нему единицу с помощью стандартного двоичного сумматора, а затем преобразовать результат обратно в код Грея. Другие методы подсчета в коде Грея обсуждаются в отчете Роберта У. Дорана , включая получение выходных данных с первых защелок триггеров «ведущий-ведомый» в двоичном счетчике пульсаций.

Адресация кода Грея

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

Построение n- битного кода Грея

Список двоично-отраженных кодов Грея для n битов может быть сгенерирован рекурсивно из списка для n  — 1 битов путем отражения списка (т. Е. Перечисления записей в обратном порядке), добавления к записям в исходном списке префикса двоичного 0 и префикса записи в отраженном списке с двоичной  единицей , а затем объединение исходного списка с обратным списком. Например, создание  списка n = 3 из списка n  = 2:

Однобитовый код Грея G ₁  = ( 0,1 ). Это можно представить как построенное рекурсивно, как указано выше, из нулевого битового кода Грея G ₀  = (  Λ  ), состоящего из единственной записи нулевой длины. Этот итеративный процесс генерации G _{n +1} из G _n проясняет следующие свойства стандартного отражающего кода:

• G _n — это перестановка чисел 0,…, 2 ⁿ  — 1. (Каждое число появляется в списке ровно один раз.)
• G _n вкладывается как первая половина G _{n +1} .
• Следовательно, кодирование является стабильным в том смысле, что как только двоичное число появляется в G _n, оно появляется в той же позиции во всех более длинных списках; так что имеет смысл говорить о с отражающим кодом Грея значение ряда: G ( м ) = в м — м , отражающий код Грея, считая от 0.
• Каждая запись в G _n отличается от предыдущей только на один бит. (Расстояние Хэмминга равно 1.)
• Последняя запись в G _n отличается от первой только на один бит. (Код циклический.)

Эти характеристики предлагают простой и быстрый метод преобразования двоичного значения в соответствующий код Грея. Каждый бит инвертируется, если следующий более высокий бит входного значения установлен в единицу. Это может выполняться параллельно с помощью битового сдвига и операции «исключающее ИЛИ», если они доступны: n- й код Грея получается вычислением . Добавление бита 0 оставляет порядок кодовых слов неизменным, добавление бита 1 меняет порядок кодовых слов на обратный. Если биты в позиции кодовых слов инвертируются, порядок соседних блоков кодовых слов меняется на обратный. Например, если бит 0 инвертируется в 3-битовой последовательности кодовых слов, порядок двух соседних кодовых слов меняется на противоположный.

000,001,010,011,100,101,110,111 → 001,000,011,010,101,100,111,110  (инвертировать бит 0)

Если бит 1 инвертирован, блоки из 2 кодовых слов изменяют порядок:

000,001,010,011,100,101,110,111 → 010,011,000,001,110,111,100,101  (инвертировать бит 1)

Если бит 2 инвертирован, блоки из 4 кодовых слов меняют порядок:

000,001,010,011,100,101,110,111 → 100,101,110,111,000,001,010,011  (инвертировать бит 2)

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

Аналогичный метод можно использовать для выполнения обратного преобразования, но вычисление каждого бита зависит от вычисленного значения следующего более высокого бита, поэтому его нельзя выполнять параллельно. Предполагая, что это -й бит, закодированный по Грею ( являющийся наиболее значимым битом), и является -м битом с двоичным кодированием ( являющимся наиболее значимым битом), обратное преобразование может быть выполнено рекурсивно:, и . В качестве альтернативы декодирование кода Грея в двоичное число можно описать как префиксную сумму битов в коде Грея, где каждая отдельная операция суммирования в префиксной сумме выполняется по модулю два.

Чтобы итеративно построить двоично-отраженный код Грея, на шаге 0 начните с , а на шаге найдите битовую позицию наименее значащей 1 в двоичном представлении и переверните бит в этой позиции в предыдущем коде, чтобы получить следующий код. . Позиции битов начинаются с 0, 1, 0, 2, 0, 1, 0, 3,…. См. Раздел « Найти первый набор» для получения информации об эффективных алгоритмах вычисления этих значений.

Преобразование в код Грея и обратно

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

typedef unsigned int uint;

// This function converts an unsigned binary number to reflected binary Gray code.
uint BinaryToGray(uint num)
{
    return num ^ (num >> 1); // The operator >> is shift right. The operator ^ is exclusive or.
}

// This function converts a reflected binary Gray code number to a binary number.
uint GrayToBinary(uint num)
{
    uint mask = num;
    while (mask) {           // Each Gray code bit is exclusive-ored with all more significant bits.
        mask >>= 1;
        num   ^= mask;
    }
    return num;
}

// A more efficient version for Gray codes 32 bits or fewer through the use of SWAR (SIMD within a register) techniques. 
// It implements a parallel prefix XOR function. The assignment statements can be in any order.
// 
// This function can be adapted for longer Gray codes by adding steps.

uint GrayToBinary32(uint num)
{
    num ^= num >> 16;
    num ^= num >>  8;
    num ^= num >>  4;
    num ^= num >>  2;
    num ^= num >>  1;
    return num;
}
// A Four-bit-at-once variant changes a binary number (abcd)2 to (abcd)2 ^ (00ab)2, then to (abcd)2 ^ (00ab)2 ^ (0abc)2 ^ (000a)2.

Специальные типы кодов Грея

На практике «код Грея» почти всегда относится к двоично-отраженному коду Грея (BRGC). Однако математики открыли другие виды кодов Грея. Как и BRGC, каждое из них состоит из списка слов, где каждое слово отличается от следующего только одной цифрой (каждое слово имеет расстояние Хэмминга, равное 1, от следующего слова).

n -аричный код Грея

Помимо двоичного кода Грея, существует множество специализированных типов кодов Грея. Одним из таких типов кода Грея является n- мерный код Грея , также известный как небулев код Грея . Как следует из названия, этот тип кода Грея использует в своих кодировках не- логические значения.

Например, 3-арный ( тройной ) код Грея будет использовать значения 0,1,2. ( N ,  k ) — код Грея — это n- мерный код Грея с k цифрами. Последовательность элементов в (3, 2) -сером коде: 00,01,02,12,11,10,20,21,22. ( N ,  k ) -серый код может быть построен рекурсивно, как BRGC, или может быть построен итеративно . Алгоритм итеративно генерировать ( N ,  K ) -Грэй код представлено (в C ):

// inputs: base, digits, value
// output: Gray
// Convert a value to a Gray code with the given base and digits.
// Iterating through a sequence of values would result in a sequence
// of Gray codes in which only one digit changes at a time.
void toGray(unsigned base, unsigned digits, unsigned value, unsigned gray[digits])
{ 
	unsigned baseN[digits];	// Stores the ordinary base-N number, one digit per entry
	unsigned i;		// The loop variable
 
	// Put the normal baseN number into the baseN array. For base 10, 109 
	// would be stored as [9,0,1]
	for (i = 0; i < digits; i++) {
		baseN[i] = value % base;
		value    = value / base;
	}
 
	// Convert the normal baseN number into the Gray code equivalent. Note that
	// the loop starts at the most significant digit and goes down.
	unsigned shift = 0;
	while (i--) {
		// The Gray digit gets shifted down by the sum of the higher
		// digits.
		gray[i] = (baseN[i] + shift) % base;
		shift = shift + base - gray[i];	// Subtract from base so shift is positive
	}
}
// EXAMPLES
// input: value = 1899, base = 10, digits = 4
// output: baseN[] = [9,9,8,1], gray[] = [0,1,7,1]
// input: value = 1900, base = 10, digits = 4
// output: baseN[] = [0,0,9,1], gray[] = [0,1,8,1]

Существуют и другие алгоритмы кода Грея для ( n , k ) -кодов Грея. ( N , k ) -серый код, созданный вышеуказанным алгоритмом, всегда циклический; некоторые алгоритмы, такие как алгоритм Гуана, лишены этого свойства, когда k нечетно. С другой стороны, хотя с помощью этого метода изменяется только одна цифра, она может изменяться путем переноса (цикл от n  — 1 до 0). В алгоритме Гуана счетчик поочередно растет и падает, так что числовая разница между двумя цифрами кода Грея всегда равна единице.

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

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

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

Хотя двоичный отраженный код Грея полезен во многих сценариях, в некоторых случаях он не оптимален из-за отсутствия «единообразия». В сбалансированных кодах Грея количество изменений в различных положениях координат максимально близко. Чтобы сделать это более точным, пусть G будет R -арным полным циклом Грея, имеющим последовательность переходов ; что отсчеты переходов ( спектр ) из G являются набором целых чисел , определенных

Код Грея является однородным или равномерно сбалансированным, если все его счетчики переходов равны, и в этом случае мы имеем
для всех k . Ясно, что когда такие коды существуют, только если n является степенью 2. В противном случае, если n не делится равномерно, можно построить хорошо сбалансированные коды, в которых каждый счетчик переходов равен или . Коды Грея также могут быть экспоненциально сбалансированы, если все их счетчики переходов являются смежными степенями двойки, и такие коды существуют для каждой степени двойки.

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

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

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

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

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

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

Теперь мы покажем конструкцию и реализацию для хорошо сбалансированных двоичных кодов Грея, которые позволяют нам генерировать n -значный сбалансированный код Грея для каждого n . Главный принцип состоит в том, чтобы индуктивно построить ( n  + 2) -значный код Грея, заданный n- значным кодом Грея G, таким образом, чтобы сохранялось свойство сбалансированности. Для этого рассмотрим разбиение на четное число L непустых блоков вида

где ` ` и ). Это разбиение индуцирует -цифровой код Грея, задаваемый формулой

Если мы определим кратности переходов

— количество раз, когда цифра в позиции i изменяется между последовательными блоками в разделе, то для ( n  + 2) -значного кода Грея, индуцированного этим разделом, спектр переходов равен

Сложная часть этой конструкции состоит в том, чтобы найти адекватное разбиение сбалансированного n- значного кода Грея так, чтобы индуцированный им код оставался сбалансированным, но для этого важна только кратность переходов; соединение двух последовательных блоков при переходе цифр и разделение другого блока при переходе другой цифры дает другой код Грея с точно таким же спектром переходов , поэтому можно, например, обозначить первые переходы на цифре как те, которые попадают между двумя блоками. Равномерные коды могут быть найдены, когда и , и эта конструкция может быть расширена также на R -арный случай.

Долгосрочные коды Грея

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

Монотонные коды Грея

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

Мы можем формализовать понятие монотонных кодов Грея следующим образом: рассмотрим разбиение гиперкуба на уровни вершин, имеющих одинаковый вес, т. Е.

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

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

иначе. Здесь — подходящим образом определенная перестановка, относящаяся к пути P с его координатами, переставленными на . Эти пути приводят к двум монотонным п -значных кодов Грея и задаются

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

Подпути в алгоритме Сэвиджа – Винклера

	j = 0	j = 1	j = 2	j = 3
п = 1	0, 1
п = 2	00, 01	10, 11
п = 3	000, 001	100, 110, 010, 011	101, 111
п = 4	0000 0001	1000, 1100, 0100, 0110, 0010, 0011	1010, 1011, 1001, 1101, 0101, 0111	1110, 1111

Эти монотонные коды Грея могут быть эффективно реализованы таким образом, что каждый последующий элемент может быть сгенерирован за время O ( n ). Алгоритм проще всего описать с помощью сопрограмм .

Монотонные коды имеют интересную связь с гипотезой Ловаса , которая утверждает, что каждый связный вершинно-транзитивный граф содержит гамильтонов путь. Подграф «среднего уровня» является вершинно-транзитивным (то есть его группа автоморфизмов транзитивна, так что каждая вершина имеет одно и то же «локальное окружение», и ее нельзя отличить от других, так как мы можем переназначить координаты, а также двоичные цифры для получения автоморфизма ), и проблема поиска гамильтонова пути в этом подграфе называется «проблемой среднего уровня», которая может пролить свет на более общую гипотезу. На этот вопрос был дан положительный ответ , и предыдущий конструкция для монотонных кодов обеспечивает гамильтонов путь длиной не менее 0,839 N, где N — количество вершин в подграфе среднего уровня.

Код Беккета – Грея

Другой тип кода Грея, код Беккета – Грея , назван в честь ирландского драматурга Сэмюэля Беккета , интересовавшегося симметрией . Его пьеса « Квад » состоит из четырех актеров и разделена на шестнадцать временных периодов. Каждый период заканчивается тем, что один из четырех актеров выходит на сцену или покидает ее. Спектакль начинается с пустой сцены, и Беккет хотел, чтобы каждая группа актеров появлялась на сцене ровно один раз. Очевидно, что набор действующих лиц на сцене может быть представлен 4-битным двоичным кодом Грея. Беккет, однако, наложил дополнительное ограничение на сценарий: он хотел, чтобы актеры входили и выходили, чтобы актер, который находился на сцене дольше всех, всегда выходил. Затем актеры могут быть представлены очередью « первым пришел — первым вышел» , так что (из актеров на сцене) удаляемый из очереди всегда оказывается тем, кто был поставлен в очередь первым. Беккет не смог найти код Беккета – Грея для своей пьесы, и действительно, исчерпывающий список всех возможных последовательностей показывает, что такого кода не существует для n = 4. Сегодня известно, что такие коды действительно существуют для n = 2, 5. , 6, 7 и 8 и не существуют для n = 3 или 4. Пример 8-битного кода Беккета – Грея можно найти в книге Дональда Кнута « Искусство компьютерного программирования» . По словам Савады и Вонга, пространство поиска для n = 6 можно исследовать за 15 часов, и было найдено более 9500 решений для случая n = 7.

Коды змейки в коробке

Коды змеи в коробке , или змеи , представляют собой последовательности узлов индуцированных путей в n- мерном графе гиперкуба , а коды катушки в коробке, или катушки , представляют собой последовательности узлов индуцированных циклов в гиперкуб. Рассматриваемые как коды Грея, эти последовательности обладают способностью обнаруживать любую однобитовую ошибку кодирования. Коды этого типа были впервые описаны Уильямом Х. Каутцем в конце 1950-х годов; с тех пор было проведено много исследований по поиску кода с максимально возможным количеством кодовых слов для данного измерения гиперкуба.

Однодорожечный код Грея

Еще одним видом кода Грея является однопутный код Грея (STGC), разработанный Норманом Б. Спеддингом и уточненный Хильтгеном, Патерсоном и Брандестини в «Однопутных кодах Грея» (1996). STGC — это циклический список из P уникальных двоичных кодировок длины n, так что два последовательных слова отличаются ровно в одной позиции, и когда список исследуется как матрица P  ×  n , каждый столбец представляет собой циклический сдвиг первого столбца.

Название происходит от их использования с поворотными энкодерами , где несколько дорожек распознаются контактами, в результате для каждого на выходе получается 0 или 1 . Чтобы уменьшить шум из-за того, что разные контакты не переключаются в один и тот же момент времени, желательно настроить дорожки так, чтобы данные, выводимые контактами, были в коде Грея. Чтобы получить высокую угловую точность, нужно много контактов; Чтобы достичь точности не менее 1 °, необходимо как минимум 360 различных позиций на оборот, что требует минимум 9 бит данных и, следовательно, такое же количество контактов.

Если все контакты расположены в одном угловом положении, то потребуется 9 дорожек, чтобы получить стандартный BRGC с точностью не менее 1 °. Однако, если производитель перемещает контакт в другое угловое положение (но на такое же расстояние от центрального вала), то соответствующий «кольцевой узор» необходимо повернуть на тот же угол, чтобы получить тот же выходной сигнал. Если самый старший бит (внутреннее кольцо на рисунке 1) достаточно повернуть, он точно соответствует следующему кольцу. Поскольку оба кольца в этом случае идентичны, внутреннее кольцо можно вырезать, а датчик для этого кольца переместить на оставшееся идентичное кольцо (но со смещением под этим углом от другого датчика на этом кольце). Эти два датчика на одном кольце образуют квадратурный энкодер. Это уменьшает количество дорожек для углового энкодера с разрешением 1 ° до 8 дорожек. Еще больше уменьшить количество дорожек с помощью BRGC невозможно.

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

Однако Норман Б. Спеддинг зарегистрировал патент в 1994 году с несколькими примерами, показывающими, что это возможно. Несмотря на то, что это не возможно различить 2 ^н позиции с п датчиков на одной дорожке, то это можно различить близко к тому , что многие. Эцион и Патерсон предполагают, что когда n само является степенью 2, n датчиков могут различать не более 2 ⁿ  — 2 n позиций, а для простого n предел составляет 2 ⁿ  — 2 позиции. Авторы продолжили генерировать 504-позиционный однодорожечный код длиной 9, который, по их мнению, является оптимальным. Поскольку это число больше 2 ⁸ = 256, для любого кода требуется более 8 датчиков, хотя BRGC может различать 512 позиций с 9 датчиками.

Здесь воспроизводится STGC для P  = 30 и n  = 5:

Однодорожечный код Грея для 30 позиций

Угол	Код		Угол	Код		Угол	Код		Угол	Код		Угол	Код
0 °	10000	72 °	01000	144 °	00100	216 °	00010	288 °	00001
12 °	10100	84 °	01010	156 °	00101	228 °	10010	300 °	01001
24 °	11100	96 °	01110	168 °	00111	240 °	10011	312 °	11001
36 °	11110	108 °	01111	180 °	10111	252 °	11011	324 °	11101
48 °	11010	120 °	01101	192 °	10110	264 °	01011	336 °	10101
60 °	11000	132 °	01100	204 °	00110	276 °	00011	348 °	10001

Каждый столбец представляет собой циклический сдвиг первого столбца, и от любой строки к следующей строке изменяется только один бит. Одноколейный характер (например, кодовая цепь) полезен при изготовлении этих колес (по сравнению с BRGC), поскольку требуется только одна гусеница, что снижает их стоимость и размер. Природа кода Грея полезна (по сравнению с цепными кодами , также называемыми последовательностями Де Брюйна ), поскольку только один датчик будет изменяться в любой момент времени, поэтому неопределенность во время перехода между двумя дискретными состояниями будет только плюс или минус одна единица угловой измерение, которое устройство способно разрешить.

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

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

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

Серая изометрия

Биективное отображение {0 ↔ 00 , 1 ↔ 01 , 2 ↔ 11 , 3 ↔ 10 } устанавливает изометрию между метрическим пространством над конечным полем с метрикой, заданной расстоянием Хэмминга, и метрическим пространством над конечным кольцом (обычное модульная арифметика ) с метрикой, заданной расстоянием Ли . Отображение подходящим образом продолжается до изометрии пространств Хэмминга и . Его важность заключается в установлении соответствия между различными «хорошо» , но не обязательно линейные коды как Серо-карты изображений в из кольцевых линейных кодов с .

Существует ряд двоичных кодов, похожих на коды Грея, в том числе:

• Коды Datex, также известные как коды Джаннини (1954), как описано Карлом П. Сполдингом, используют вариант кода О’Брайена II .
• Коды, используемые Вареком (ок. 1954 г.), используют вариант кода О’Брайена I, а также варианты кода Грея с основанием 12 и 16.
• Lucal code (1959), также известный как модифицированный отраженный двоичный код (MRB)
• Код Гиллхэма (1961/1962), использует вариант кода Datex и кода О’Брайена II .
• Код Лесли и Рассела (1964)
• Код учреждения Royal Radar
• Кодекс Хоклас (1988 г.)

Следующие двоично-десятичные коды (BCD) также являются вариантами кода Грея:

• Код Петерика (1953 г.), также известный как код Королевского авиастроительного предприятия (RAE).
• Коды О’Брайена I и II (1955) (Код О’Брайена типа I был уже описан Фредериком А. Фоссом из IBM и использовался Вареком в 1954 году. Позже он был также известен как код Уоттса или отраженный десятичный код Уоттса ( WRD) и иногда неоднозначно называют отраженным двоичным модифицированным кодом Грея. Код О’Брайена типа II уже использовался Datex в 1954 году.)
• Код Грея с избытком-3 (1956) (также известный как код с избытком-3 по Грею, код с избытком 3 по Грею, код с избытком-3 по рефлексу, код с избытком Грея, код с избытком Грея, код с избытком 10-3 или код Грея-Стибица), описан Фрэнком П. Терви-младшим из ITT .
• Коды Томпкинса I и II (1956)
• Код Гликсона (1957 г.), иногда неоднозначно также называемый модифицированным кодом Грея.