<p>A <em>Gray code</em> consists of <span class="math-container">$n$</span>-bit distinct strings <span class="math-container">$s_1,s_2, \ldots,s_N$</span> such that each <span class="math-container">$s_i$</span> and <span class="math-container">$s_{i+1}$</span> differs by one bit.
For example: <span class="math-container">$000, 001, 010, 011, 111, 110, 101, 100$</span>.
It is known that we can have <span class="math-container">$N=2^n$</span> for every integer <span class="math-container">$n$</span>.</p>
<p>A <em>two-dimensional Gray code</em> consists of <span class="math-container">$m*n$</span> strings <span class="math-container">$s_{i,j}$</span> for each <span class="math-container">$1\leq i\leq m$</span> and <span class="math-container">$1\leq j\leq n$</span>, such that each <span class="math-container">$s_{i,j}$</span> and <span class="math-container">$s_{i+1,j}$</span> differs by one bit, each <span class="math-container">$s_{i,j}$</span> and <span class="math-container">$s_{i,j+1}$</span> differs by one bit, and each <span class="math-container">$s_{i,j}$</span> and <span class="math-container">$s_{i+1,j+1}$</span> differs by two bits.
For example, the following is a <span class="math-container">$4*4$</span> Gray code using the optimal <span class="math-container">$\log_2 4*4=4$</span> bits.</p>
<p>0000, 0100, 1100, 1000</p>
<p>0001, 0101, 1101, 1001</p>
<p>0011, 0111, 1111, 1011</p>
<p>0010, 0110, 1110, 1010</p>
<p>It is not hard to construct <span class="math-container">$m*n$</span> 2d-gray codes using <span class="math-container">$\log mn + O(1)$</span> bits. My question is, if the &quot;coordinates&quot; <span class="math-container">$(i,j)$</span> does not form a rectangle (say, they lie arbitrarily on a grid), then is there an (almost) optimal 2d Gray code?
That is, given <span class="math-container">$N$</span> coordinates <span class="math-container">$X=\{(i,j)\}$</span>, can we construct a 2d Gray code for each <span class="math-container">$s_{i,j}$</span> using only <span class="math-container">$\log N+O(1)$</span> bits, for any <span class="math-container">$N$</span> and <span class="math-container">$X$</span>?</p>

CC BY-SA 4.0
2023-04-07T11:02:57.473Z
Nice question. Where is this applicable?
Turbo
CC BY-SA 4.0
2023-04-07T16:32:06.090Z
Are holes between the $s_{i,j}$ allowed? (and - for example - the codes for $s_{i,j}$, $s_{i+2,j+2}$ must have hamming distance 4)
Marzio De Biasi
CC BY-SA 4.0
2023-04-08T06:27:18.510Z
@Turbo I think it would have some application in succinct encoding.
Kai-Yuan Lai 賴開元
CC BY-SA 4.0
2023-04-08T06:34:11.133Z
@MarzioDeBiasi What do you mean by holes? In my mind the subgraph of a grid (induced by the coordinates) is connected, but there could be $(i,j)\in X$ and $(i+1,j)\notin X$.
Kai-Yuan Lai 賴開元
CC BY-SA 4.0
2023-04-08T06:38:56.423Z
@MarzioDeBiasi the property you said does not hold when $(i+1,j),(i+2,j),(i+1,j+1),(i+2,j+1)\notin X$.
Kai-Yuan Lai 賴開元
CC BY-SA 4.0
2023-04-08T12:13:01.277Z
ok, I was only asking if the points in the grid graph must be connected; and how many different bits must have $s_{1,1}$ and $s_{3,3}$ if they are both in $X$, but $s_{2,2}$ is not in $X$ (the term hamming distance that I used is not correct)
Marzio De Biasi
<coding-theory>
The existence of (non-rectangular) two dimensional Gray code
Kai-Yuan Lai 賴開元
# The existence of (non-rectangular) two dimensional Gray code

(Asked by: username_0 on 2023-04-07)

A *Gray code* consists of $n$-bit distinct strings $s\_1,s\_2, \ldots,s\_N$ such that each $s\_i$ and $s\_{i+1}$ differs by one bit.
For example: $000, 001, 010, 011, 111, 110, 101, 100$.
It is known that we can have $N=2^n$ for every integer $n$.

A *two-dimensional Gray code* consists of $m\*n$ strings $s\_{i,j}$ for each $1\leq i\leq m$ and $1\leq j\leq n$, such that each $s\_{i,j}$ and $s\_{i+1,j}$ differs by one bit, each $s\_{i,j}$ and $s\_{i,j+1}$ differs by one bit, and each $s\_{i,j}$ and $s\_{i+1,j+1}$ differs by two bits.
For example, the following is a $4\*4$ Gray code using the optimal $\log\_2 4\*4=4$ bits.

0000, 0100, 1100, 1000

0001, 0101, 1101, 1001

0011, 0111, 1111, 1011

0010, 0110, 1110, 1010

It is not hard to construct $m\*n$ 2d-gray codes using $\log mn + O(1)$ bits. My question is, if the "coordinates" $(i,j)$ does not form a rectangle (say, they lie arbitrarily on a grid), then is there an (almost) optimal 2d Gray code?
That is, given $N$ coordinates $X=\{(i,j)\}$, can we construct a 2d Gray code for each $s\_{i,j}$ using only $\log N+O(1)$ bits, for any $N$ and $X$?

**Tags:** coding-theory
> **Comments:**
> **username_1**: Nice question. Where is this applicable?  
> **username_2**: Are holes between the $s_{i,j}$ allowed? (and - for example - the codes for $s_{i,j}$, $s_{i+2,j+2}$ must have hamming distance 4)  
> **username_0**: @Turbo I think it would have some application in succinct encoding.  
> **username_0**: @MarzioDeBiasi What do you mean by holes? In my mind the subgraph of a grid (induced by the coordinates) is connected, but there could be $(i,j)\in X$ and $(i+1,j)\notin X$.  
> **username_0**: @MarzioDeBiasi the property you said does not hold when $(i+1,j),(i+2,j),(i+1,j+1),(i+2,j+1)\notin X$.  
> **username_2**: ok, I was only asking if the points in the grid graph must be connected; and how many different bits must have $s_{1,1}$ and $s_{3,3}$ if they are both in $X$, but $s_{2,2}$ is not in $X$ (the term hamming distance that I used is not correct)  

---

## 0 answers

