Improved Construction of Robust Gray Codes

In [1], Lolck and Pagh introduce the notion of a robust Gray code. Informally, a robust Gray code $\mathcal{G}\subseteq\{0,1\}^{d}$ has an encoding map $\mathrm{Enc}_{\mathcal{G}}:\{0,\ldots,N-1\}\to\{0,1\}^{d}$ that maps integers to bitstrings, with the following desiderata.

• •

  $\mathcal{G}$ should be a Gray code.¹¹1The paper [1] also gives a more general definition, where the code should have low sensitivity, meaning that $|\mathrm{Enc}_{\mathcal{G}}(j)-\mathrm{Enc}_{\mathcal{G}}(j+1)|$ is small; however, both their code and our code is a Gray code, so we specialize to that case (in which the sensitivity is $1$). That is, for any $j\in\{0,\ldots,N-2\}$, $|\mathrm{Enc}_{\mathcal{G}}(j)-\mathrm{Enc}_{\mathcal{G}}(j+1)|=1$.

• •

  $\mathcal{G}$ should be “noise robust.” Informally, this means that we should be able to approximately recover an integer $j\in\{0,\ldots,N-1\}$ given a noisy version of $\mathrm{Enc}_{\mathcal{G}}(j)$. Slightly more formally, $\mathcal{G}$ should have a decoding map $\mathrm{Dec}_{\mathcal{G}}:\{0,1\}^{d}\to\{0,\ldots,N-1\}$, so that when $\eta\sim\mathrm{Ber}(p)^{n}$, the estimate $\hat{j}=\mathrm{Dec}_{\mathcal{G}}(\mathrm{Enc}_{\mathcal{G}}(j)\oplus\eta)$ should be close to $j$ with high probability.

• •

  $\mathcal{G}$ should have high rate. The rate $\frac{d}{\log N}$ of $\mathcal{G}$ should be as close to $1$ as possible.

• •

  $\mathcal{G}$ should have efficient algorithms. Both $\mathrm{Enc}_{\mathcal{G}}$ and $\mathrm{Dec}_{\mathcal{G}}$ should have running time polynomial (ideally, near-linear) in $d$.

Robust Gray codes have applications in differential privacy; see [1, 2, 3, 4] for more details on the connection. It is worth mentioning that there exist non-binary codes based on the Chinese Remainder Theorem [5, 6] that have nontrivial sensitivity, but in our work, we focus on binary codes.

More precisely, for $p\in(0,1/2)$, [1] give a general recipe for turning a binary error-correcting code $\mathcal{C}$ with rate $R$ into a robust Gray code $\mathcal{G}$ with rate $\Omega(R)$, and with the following robustness guarantee:

where the probability is over the noise vector $\eta\sim\mathrm{Ber}(p)^{d}$, and $P_{\text{fail}}(\mathcal{C})$ is the failure probability of the code $\mathcal{C}$ on the binary symmetric channel with parameter $p$.

Our main result is a similar transformation that turns a (linear) binary code $\mathcal{C}$ with good performance on the binary symmetric channel into a robust Gray code $\mathcal{G}$. We obtain a similar robustness guarantee as (1) (see Theorem 1 for the precise statement), but with better rate. Concretely, if the original code $\mathcal{C}$ has rate $R\in(0,1)$, the rate of the robust Gray code from [1] is proven to be $\Omega(R)$, where the constant inside the $\Omega$ approaches $1/4$ when $\mathcal{C}$ has sublinear distance; this comes from the fact that the a codeword in their final construction involves four codewords from $\mathcal{C}$. In contrast, under the same conditions, our robust Gray code $\mathcal{G}$ has rate approaching $R/2$; this is because our construction involves only two codewords from $\mathcal{C}$. (See Observation 2 for the formal statement). Moreover, if the encoding and decoding algorithms for $\mathcal{C}$ are efficient, then so are the encoding and decoding algorithms for our construction $\mathcal{G}$; concretely, the overhead on top of the encoding and decoding algorithms for $\mathcal{C}$ is $O(d)$ (see Lemma 7 for the formal statement).

As a result, when instantiated with, say, a constant-rate Reed-Muller code or a polar code (both of which have sublinear distance and good performance on the BSC($p$) (see, e.g., [7, 8, 9, 10, 11])), our construction gives efficient robust Gray codes with a rate about two times larger than than previous work, approaching $1/2$.

The main difference between our construction and that of previous work is how we build and order $\mathcal{W}$. First, we use a standard Gray code to construct an ordering of the codewords in $\mathcal{C}$. Then, we build $\mathcal{W}$ as follows. Let $c_{i}$ be the $i$’th codeword in $\mathcal{C}$. Then the $i$’th codeword in $\mathcal{W}$ is given by

where $s_{i}$ is a short string that is all zeros if $i$ is even and all ones otherwise, and $\circ$ denotes concatenation. Then we form $\mathcal{G}$ by interpolating as described above.

Our decoding algorithm ends up being rather complicated, but the idea is simple. Suppose that for a codeword $g\in\mathcal{G}$, we see a corrupted version $g+\eta\in\mathbb{F}_{2}^{d}$, where $\eta$ is a noise vector. As described above, $g$ is made up of a prefix from $w_{i+1}$ and a suffix from $w_{i}$, for some $i$. Let $h\in[d]$ be the index where $g$ “crosses over” from $w_{i+1}$ to $w_{i}$. Notice that, as this crossover point can only be in one place, at least one of the two codewords of $\mathcal{C}$ appearing in $g$ will be complete, and equal to either $c_{i}$ or $c_{i+1}$. Thus, if we could identify where the crossover point $h$ was, then we could use $\mathcal{C}$’s decoder to decode whichever the complete $\mathcal{C}$-codeword was to identify $i$; and then use our knowledge of where $h$ is to complete the decoding. The simple observation behind our construction is that, because the strings $s_{i}$ (which are either all zeros or all ones) flip with the parity of $i$, we can tell (approximately) where $h$ was! Indeed, these strings will be all zeros before $h$ and all ones after $h$, or vice versa. Of course, some noise will be added, but provided that the length of the strings $s_{i}$ are long enough, we will still be able to approximately locate $h$ with high probability.

However, there are several challenges to implementing this simple idea. For example, given $i$ and $h$, how do we efficiently compute $j$? (Here is where the fact that we ordered $\mathcal{C}$ carefully comes in; it’s not trivial because the number of codewords of $\mathcal{G}$ inserted between $w_{i}$ and $w_{i+1}$ depends on $i$, so naively adding up the number of codewords of $\mathcal{G}$ that come before $w_{i}$ and then adding $h$ would take exponential time.) Or, what happens when the crossover point $h$ is very close to the end of $g_{j}+\eta$? (Here, it might be the case that we mis-identify $i$; but we show that this does not matter, with high probability, because our final estimate will still be close to $j$ with high probability). In the rest of the paper, we show how to deal with these and other challenges.

We begin by setting notation. Throughout, we work with linear codes over $\mathbb{F}_{2}$, so all arithmetic between codewords is modulo 2. For $x,y\in\mathbb{F}_{2}^{\ell}$, let $\Delta(x,y)$ denote the Hamming distance between $x$ and $y$. We use $\|x\|$ to denote the Hamming weight of a vector $x\in\mathbb{F}_{2}^{\ell}$. For a code $\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$, the minimum distance of the code is given by $D(\mathcal{C}):=\max_{c\neq c^{\prime}\in C}\Delta(c,c^{\prime})$.

For two strings $s_{1}$ and $s_{2}$, we use $s_{1}\circ s_{2}$ to denote the concatenation of $s_{1}$ and $s_{2}$. For a string $s\in\mathbb{F}_{2}^{\ell}$ and for $i\leq\ell$, we use $\text{pref}_{i}(s)\in\mathbb{F}_{2}^{i}$ to denote the prefix of the string $s$ ending at (and including) index $i$. Analogously, we use $\text{suff}_{i}(s)\in\mathbb{F}_{2}^{\ell-i}$ be defined as the suffix of $s$ starting at (and including) index $i$. For an integer $\ell$, we use $[\ell]$ to denote the set $\{1,\ldots,\ell\}$.

For $\ell\in\mathbb{Z}$, let $\mathrm{Maj}_{\ell}:\mathbb{F}_{2}^{\ell}\rightarrow\mathbb{F}_{2}$ be majority function on $\ell$ bits. (In the case that $\ell$ is even and a string $y\in\mathbb{F}_{2}^{\ell}$ has an equal number of zeros and ones, $\mathrm{Maj}_{\ell}(y)$ is defined to be a randomized function that outputs $0$ or $1$ each with probability $1/2$.) We use $\mathrm{Ber}(p)$ to denote the Bernoulli-$p$ distribution on $\mathbb{F}_{2}$, so if $X\sim\mathrm{Ber}(p)$, then $X$ is $1$ with probability $p$ and $0$ with probability $1-p$.

Next we define Binary Reflected Codes, a classical Gray code ([12]; see also, e.g., [13]); we will use these to define our ordering on $\mathcal{C}$.

It is not hard to see that for any two successive integers $i$ and $i+1$, the encoded values $\mathcal{R}_{k}(i)$ and $\mathcal{R}_{k}(i+1)$ differ in exactly one bit. We will need one more building-block, the Unary code.

Next, we define the failure probability of a code $\mathcal{C}$.

We recall the high-level overview of our construction from the introduction: To construct $\mathcal{G}$ we will start with a base code $\mathcal{C}$ where $\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$, which we will order in a particular way (Definition 4). Then we construct an intermediate code $\mathcal{W}=\{w_{0},\ldots,w_{2^{k}-1}\}\subseteq\mathbb{F}_{2}^{d}$  by transforming the codewords of $\mathcal{C}$ (Definition 5); the codewords of $\mathcal{W}$ inherit an order of $\mathcal{C}$. Finally, we create final code $\mathcal{G}\subseteq\mathbb{F}_{2}^{d}$ by adding new codewords that “interpolate” between the codewords of $\mathcal{W}$ so that it satisfies the Gray code condition (Definition 6). We discuss each of these steps in the subsequent subsections.

In this section, we define our decoding algorithm and analyze it. We begin with some notation for the different parts of the codewords $g_{j}\in\mathcal{G}$. For a string $x$, we use $x[i:i^{\prime}]$ to denote the substring $(x_{i},x_{i+1},\ldots,x_{i^{\prime}-1})$. With this notation, for any $x\in\mathbb{F}_{2}^{d}$, define the following substrings:

• •

  $s_{1}(x)=x[0:D(\mathcal{C})]$

• •

  $\tilde{c}_{1}(x)=x[D(\mathcal{C}):D(\mathcal{C})+n]$

• •

  $s_{2}(x)=x[D(\mathcal{C})+n:2D(\mathcal{C})+n]$

• •

  $\tilde{c}_{2}(x)=x[2D(\mathcal{C})+n,2D(\mathcal{C})+2n]$

• •

  $s_{3}(x)=x[2D(\mathcal{C})+2n:3D(\mathcal{C})+2n]$.

Notice that if $x\in\mathcal{G}$, then $\tilde{c}_{1}$ and $\tilde{c}_{2}$ are in locations corresponding to the codewords of $\mathcal{C}$ that appear in codewords of $\mathcal{W}$, while $s_{1},s_{2}$, and $s_{3}$ are in locations corresponding to the $0^{D(\mathcal{C})}$ and $1^{D(\mathcal{C})}$ strings.

Before we formally state the algorithm (Algorithm 2 below), we prove a few lemmas to motivate its structure.

Our first lemma formalizes the intuition in the introduction that at most one of the “chunks” in each codeword $g_{j}$ is broken up by the crossover point $h_{i,\bar{j}}$.

Using the language of Lemma 3, we say that a substring in $\mathcal{S}$ that is equal to its corresponding substring in $w_{i}$ is a full chunk. Thus, Lemma 3 implies that there are at least four full chunks in any $g_{j}\in\mathcal{G}$. Notice that it is possible that a substring $\tilde{c}_{\ell}$ is in $\mathcal{C}$ but is not a full chunk. We say that all full chunks are decoded correctly if, for full chunk of $x$, when we run the corresponding decoder, we get the right answer. That is, if $\tilde{c}_{1}(x)$ is a full chunk, then if we were to run $\mathrm{Dec}_{\mathcal{C}}$ on $\tilde{c}_{1}(x)$ we would obtain $\tilde{c}_{1}(g_{j})$, and similarly for $\tilde{c}_{2}$; and if $s_{1}(x)$ is a full chunk, and we were to run $\mathrm{Maj}_{D(\mathcal{C})}$ on $s_{1}(x)$, we would obtain $s_{1}(g_{j})$, and similarly for $s_{2}$ and $s_{3}$.

Next, we show that if the “crossover point” $h_{i,\bar{j}}$ does not point to one of chunks $s_{1},s_{2}$, or $s_{3}$, then there are at least two of them that differ.

Finally, we break things up into three cases, which will be reflected in our algorithm. In each case, we can use the pattern of the chunks $s_{1}(x),s_{2}(x),s_{3}(x)$ to get an estimate for $c_{i}$ or $c_{i+1}$, and bound where the crossover point $h_{i,\bar{j}}$ will be.