2
$\begingroup$

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$?

$\endgroup$
6
  • $\begingroup$ Nice question. Where is this applicable? $\endgroup$
    – Turbo
    Commented Apr 7, 2023 at 11:02
  • $\begingroup$ 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) $\endgroup$ Commented Apr 7, 2023 at 16:32
  • $\begingroup$ @Turbo I think it would have some application in succinct encoding. $\endgroup$ Commented Apr 8, 2023 at 6:27
  • $\begingroup$ @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$. $\endgroup$ Commented Apr 8, 2023 at 6:34
  • $\begingroup$ @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$. $\endgroup$ Commented Apr 8, 2023 at 6:38

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.