Editing Gray code (section)

=== Balanced Gray code ===

Although the binary reflected Gray code is useful in many scenarios, it is not optimal in certain cases because of a lack of "uniformity".<ref name="Bhat-Savage_1996"/> 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 <math>(\delta_k)</math>; the ''transition counts'' (''spectrum'') of ''G'' are the collection of integers defined by

<math display="block">\lambda_k = |\{ j \in \mathbb{Z}_{R^n} : \delta_j = k \}| \, , \text { for } k \in \mathbb{Z}_n</math>

A Gray code is ''uniform'' or ''uniformly balanced'' if its transition counts are all equal, in which case we have <math>\lambda_k = \tfrac{R^n}{n}</math> for all ''k''. Clearly, when <math>R = 2</math>, such codes exist only if ''n'' is a power of 2.<ref>{{cite journal |first1=D. G. |last1=Wagner |first2=J. |last2=West |title=Construction of Uniform Gray Codes |journal=Congressus Numerantium |volume=80 |year=1991 |pages=217–223}}</ref> 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 <math>2\left\lfloor \tfrac{2^n}{2n} \right\rfloor</math> or <math>2\left\lceil \tfrac{2^n}{2n} \right\rceil</math>.<ref name="Bhat-Savage_1996"/> 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.<ref name="Suparta_2005"/>

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:<ref name="Bhat-Savage_1996"/>
{{block indent|1= {{mono|0 {{fontcolor|red|1}} 1 1 1 1 1 {{fontcolor|red|0}} 0 0 0 0 0 {{fontcolor|red|1}} 1 {{fontcolor|red|0}}}} }}
{{block indent|1= {{mono|0 0 {{fontcolor|red|1}} 1 1 1 {{fontcolor|red|0}} 0 {{fontcolor|red|1}} 1 1 1 {{fontcolor|red|0}} 0 0 0}} }}
{{block indent|1= {{mono|0 0 0 0 {{fontcolor|red|1}} 1 1 1 1 {{fontcolor|red|0}} 0 {{fontcolor|red|1}} 1 1 {{fontcolor|red|0}} 0}} }}
{{block indent|1= {{mono|{{fontcolor|red|0}} 0 0 {{fontcolor|red|1}} 1 {{fontcolor|red|0}} 0 0 0 0 {{fontcolor|red|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:<ref name="Bhat-Savage_1996"/>
{{block indent|1= {{mono|{{fontcolor|red|1}} 1 1 1 1 {{fontcolor|red|0}} 0 0 0 {{fontcolor|red|1}} 1 1 1 1 1 {{fontcolor|red|0}} 0 {{fontcolor|red|1}} 1 1 1 1 {{fontcolor|red|0}} 0 0 0 0 0 0 0 0 0}} }}
{{block indent|1= {{mono|0 0 0 {{fontcolor|red|1}} 1 1 1 1 1 1 1 {{fontcolor|red|0}} 0 0 0 0 0 0 {{fontcolor|red|1}} 1 1 1 1 1 {{fontcolor|red|0}} 0 0 {{fontcolor|red|1}} 1 {{fontcolor|red|0}} 0 0}}}}
{{block indent|1= {{mono|1 1 {{fontcolor|red|0}} 0 {{fontcolor|red|1}} 1 1 {{fontcolor|red|0}} 0 0 0 0 0 {{fontcolor|red|1}} 1 1 {{fontcolor|red|0}} 0 0 {{fontcolor|red|1}} 1 1 1 1 1 {{fontcolor|red|0}} 0 0 0 0 {{fontcolor|red|1}} 1}} }}
{{block indent|1= {{mono|1 {{fontcolor|red|0}} 0 0 0 0 0 0 {{fontcolor|red|1}} 1 1 1 1 1 {{fontcolor|red|0}} 0 0 0 0 0 {{fontcolor|red|1}} 1 1 1 1 1 1 1 {{fontcolor|red|0}} 0 0 {{fontcolor|red|1}}}}}}
{{block indent|1= {{mono|1 1 1 1 1 1 {{fontcolor|red|0}} 0 0 0 {{fontcolor|red|1}} 1 {{fontcolor|red|0}} 0 0 0 0 0 0 0 0 {{fontcolor|red|1}} 1 {{fontcolor|red|0}} 0 0 {{fontcolor|red|1}} 1 1 1 1 1}}}}

We will now show a construction<ref name="Flahive-Bose_2007"/> and implementation<ref name="Strackx-Piessens_2016"/> 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''&nbsp;+&nbsp;2)-digit Gray code <math>G'</math> given an ''n''-digit Gray code ''G'' in such a way that the balanced property is preserved. To do this, we consider partitions of <math>G = g_0, \ldots, g_{2^n-1}</math> into an even number ''L'' of non-empty blocks of the form

<math display="block">\left\{g_0\right\}, \left\{g_1, \ldots, g_{k_2}\right\}, \left\{g_{k_2+1}, \ldots, g_{k_3}\right\}, \ldots, \left\{g_{k_{L-2}+1}, \ldots, g_{-2}\right\}, \left\{g_{-1}\right\}</math>

where <math>k_1 = 0</math>, <math>k_{L-1} = -2</math>, and <math>k_{L} \equiv -1 \pmod{2^n}</math>). This partition induces an <math>(n+2)</math>-digit Gray code given by

{{block indent|1=<math display="block">\begin{align}
&\mathtt{00}g_0,\\
&\mathtt{00}g_1, \ldots, \mathtt{00}g_{k_2}, \mathtt{01}g_{k_2}, \ldots, \mathtt{01}g_1, \mathtt{11}g_1, \ldots, \mathtt{11}g_{k_2}, \\
&\mathtt{11}g_{k_2+1}, \ldots, \mathtt{11}g_{k_3}, \mathtt{01}g_{k_3}, \ldots, \mathtt{01}g_{k_2+1}, \mathtt{00}g_{k_2+1}, \ldots, \mathtt{00}g_{k_3}, \ldots,\\
&\mathtt{00}g_{-2}, \mathtt{00}g_{-1}, \mathtt{10}g_{-1}, \mathtt{10}g_{-2}, \ldots, \mathtt{10}g_0, \mathtt{11}g_0, \mathtt{11}g_{-1}, \mathtt{01}g_{-1}, \mathtt{01}g_0
\end{align}</math>}}

If we define the ''transition multiplicities''

<math display="block">m_i = \left|\left\{ j : \delta_{k_j} = i, 1 \leq j \leq L \right\}\right|</math>

to be the number of times the digit in position ''i'' changes between consecutive blocks in a partition, then for the (''n''&nbsp;+&nbsp;2)-digit Gray code induced by this partition the transition spectrum <math>\lambda'_i</math> is

<math display="block">
\lambda'_i = \begin{cases}
4 \lambda_i - 2 m_i, & \text{if } 0 \leq i < n \\
L, & \text{ otherwise }
\end{cases}
</math>

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 <math>i</math> transition and splitting another block at another digit <math>i</math> transition produces a different Gray code with exactly the same transition spectrum <math>\lambda'_i</math>, so one may for example<ref name="Suparta_2005"/> designate the first <math>m_i</math> transitions at digit <math>i</math> as those that fall between two blocks. Uniform codes can be found when <math>R \equiv 0 \pmod 4</math> and <math>R^n \equiv 0 \pmod n</math>, and this construction can be extended to the ''R''-ary case as well.<ref name="Flahive-Bose_2007"/>