# Generating \(m\)-[PERSON] Gray Codes and Related Algorithms
## 3 The \(m\)-Ary Modular (Shifted) Gray Code  
In [3], the authors define the directional distance of \(b\) from \(a\), where \(a,b\in\mathbb{Z}_{m}\), denoted by \(\sigma(b-a)\) and equal to \((b-a)\pmod{m}\). Next, they define the directional distance of a vector from another vector in \(\mathbb{Z}_{m}^{n}\) as the sum of directional distances between their respective components, or  
\[d_{D}(u,v)=\sum_{i=1}^{n}\sigma(b_{i}-a_{i}),\;\;u=(a_{1},\ldots,a_{n}),\;v=(b _{1},\ldots,b_{n})\in\mathbb{Z}_{m}^{n}.\]  
It is worth mentioning that the directional distance is not a metric in \(\mathbb{Z}_{m}^{n}\) because there are vectors \(u,v\in\mathbb{Z}_{m}^{n}\), such that \(d_{D}(v,u)\
eq d_{D}(u,v)\). In [3], ([Lemma 1]), it was proved that \(d_{D}(v,u)+d_{D}(u,v)=md_{H}(u,v)\), where \(d_{H}\) is the Hamming distance between the vectors. In this section, we study the \(m\)-ary Gray code defined in [3] as an ordered sequence of the vectors of \(\mathbb{Z}_{m}^{n}\), such that each vector differs from the preceding vector by directional distance one. This means that to obtain the next codeword, we add one modulo \(m\) to exactly one coordinate and do not change the other coordinates. We denote the thus-defined code that starts from the zero vector by \(G(m,n)\) and call it a _modular_ (or _shifted_) Gray code. In the \(m\)-ary modular Gray code, the \(m\)-ary vectors are ordered such that every two consecutive vectors differ by exactly one coordinate, and the difference is \(+1\) modulo \(m\). If \(m=2\), this Gray code coincides with the reflected Gray code, so we can consider it as another generalization of the binary reflected Gray code. We present the ternary modular Gray code of length 3 in Table 3.  
A formula how from the \(m\)-adic representation of the integer \(a\) to obtain the corresponding codeword \(g=(g_{1},\ldots,g_{n})\in G(m,n)\) is given in [3]. If \(a=a_{1}m^{n-1}+a_{2}m^{n-2}+\cdots+a_{n}\), \(0\leq a_{i}\leq m-1\), \(i=1,\ldots,n\), then  
\[g_{i}= \begin{cases}a_{i},\text{ if }i=1,\\ m-a_{i-1}+a_{i}\pmod{m},\text{ if }i\geq 2.\end{cases}  \tag{4}\]  
Conversely, we have  
\[a_{i}=\sum_{j=1}^{i}g_{i}\pmod{m}. \tag{5}\]  
Algorithm 9 implements these formulas with \(\Theta(n)\) running time. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Number** & **Number** & **Codeword** & **Number** & **Number** & **Number** & **Codeword** \\ \multicolumn{6}{c}{**(Rank)**} \\ \hline
0 & 000 & 000 & 14 & 112 & 101 \\
1 & 001 & 001 & 15 & 120 & 111 \\
2 & 002 & 002 & 16 & 121 & 112 \\
3 & 010 & 012 & 17 & 122 & 110 \\
4 & 011 & 010 & 18 & 200 & 210 \\
5 & 012 & 011 & 19 & 201 & 211 \\
6 & 020 & 021 & 20 & 202 & 212 \\
7 & 021 & 022 & 21 & 210 & 222 \\
8 & 022 & 020 & 22 & 211 & 220 \\
9 & 100 & 120 & 23 & 212 & 221 \\
10 & 101 & 121 & 24 & 220 & 201 \\
11 & 102 & 122 & 25 & 221 & 202 \\
12 & 110 & 102 & 26 & 222 & 200 \\
13 & 111 & 100 & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Ranking for the codewords in \(G(3,3)\). The authors in [3] also present a generating recursive procedure for the code. As in the previous section, we again use the matrix representation of the codes. Obviously,  
\[G(m,1)=G_{m}(1)=(0,1,\ldots,m-1)^{T}.\]  
Let  
\[G^{(i)}(m,1)=(m-i,m-i+1,\ldots,m-i-1)^{T},\;i=1,\ldots,m,\]  
be obtained on cyclically shifting of the elements of \(G(m,1)\) by \(i\) positions. Then  
\[G(m,2)=\left( \begin{array}{cc}0&\\ \vdots&G(m,1)\\ 0&\\ \hline 1&\\ \vdots&G^{(1)}(m,1)\\ 1&\\ \hline 2&\\ \vdots&G^{(2)}(m,1)\\ 2&\\ \hline\vdots&\vdots\\ \hline m-1&\\ \vdots&G^{(m-1)}(m,1)\\ m-1&\\ \end{array} \right).