List Decoding Reed–Solomon Codes in the
Lee, Euclidean, and Other Metrics

This work gives a polynomial-time algorithm that list decodes any generalized Reed–Solomon (GRS) code over a prime field in the ${\mathrm{\ell }}_p$ (semi)metric for any ; in particular, this includes the Lee (${\mathrm{\ell }}_1$) and Euclidean (${\mathrm{\ell }}_2$) metrics.¹¹1A semimetric is just a metric that does not necessarily satisfy the triangle inequality (which we will not need). Our algorithm works for a broader range of parameters, and has a better distance-rate tradeoff for all decoding distances above some moderate thresholds, than the prior algorithms for ${\mathrm{\ell }}_1$ and ${\mathrm{\ell }}_2$ [12, 16, 10]; see below for elaboration and Figure 1 for a visual depiction. For ease of comparison across the various works and ${\mathrm{\ell }}_p$ (semi)metrics, we use a suitably normalized version of distance: for code length $n$, distance $d$ corresponds to relative distance $\delta :=d/n^{1/p}$.

For $p=2$, our algorithm can handle an arbitrarily large decoding distance, for a correspondingly small enough rate: specifically, as $\delta$ and the alphabet size grow, we can decode for rates rapidly approaching $1/(\delta \sqrt{2\pi e})$. By contrast, the prior work [10] applies only for relative distance (i.e., ${\mathrm{\ell }}_2$ distance less than $\sqrt{n/2}$). In addition, our algorithm works for larger rates than the one in [10] whenever $\delta$ exceeds about $0.51797$. (See Section 5.2 for a detailed comparison.) This is particularly interesting since the rates obtained in [10] were shown to be optimal (in a certain sense) for , but not for larger values.

For $p=1$, again our algorithm (like the one from [16]) can handle an arbitrarily large decoding distance, whereas [12] is limited to relative distance (i.e., ${\mathrm{\ell }}_1$ distance less than $n$). In addition, our algorithm works for larger rates than those of [12, 16] whenever the relative decoding distance exceeds about $0.78988$, and in general, as $\delta$ and the alphabet size grow, we can decode for rates rapidly approaching $1/(2e\delta )$. (See Section 6.2 for details.) Our algorithm is also qualitatively broader: it decodes from continuous (real-valued) error, whereas the ones from [12, 16] require discrete (integer) error. While continuous error can be discretized by rounding, this can increase the relative distance from the codeword by up to $1/2$ in ${\mathrm{\ell }}_1$, which significantly degrades the distance-rate tradeoffs of the prior works, making them worse than ours for all distances.

We also give several useful supplementary results. By adapting an argument of [12], we prove lower bounds on the ${\mathrm{\ell }}_1$ and ${\mathrm{\ell }}_2$ minimum distances for a certain natural subclass of GRS codes. These imply that for many parameters of interest, our list-decoding algorithm outputs at most one codeword, i.e., it is actually a unique decoder. (See Lemmas 5.7 and 6.4 and the discussions thereafter.) And in addition to worst-case errors added by an adversarial channel, we also consider our algorithm’s performance under average-case errors produced by “memoryless additive” channels. Such channels add independent identically distributed error, drawn from some specified distribution, to each coordinate of the transmitted codeword. For Laplacian and Gaussian errors (which roughly correspond to ${\mathrm{\ell }}_1$ and ${\mathrm{\ell }}_2$, respectively), we show that our algorithm supports even larger rates than what we would get by merely applying concentration bounds on the error vector and invoking our worst-case results.

At the highest level, our algorithm for list decoding prime-field GRS codes in ${\mathrm{\ell }}_p$ follows the basic approach of [10] for list decoding (G)RS codes in ${\mathrm{\ell }}_2$: we first translate the received word into a suitable weight (or reliability) vector, then invoke a soft-decision list-decoding algorithm [7, 5, 8] for GRS codes. Informally, a weight vector specifies, for each coordinate of the received word and each symbol in the code alphabet, a “confidence level” that the transmitted codeword had that symbol at that coordinate. Given such a weight vector, a soft-decision decoding algorithm then finds all codewords that are sufficiently correlated with it, as determined by the code rate. (For the formal definitions and theorem statement, see Definitions 3.1, 3.2, and 3.3.)

For our purposes, the principal challenge is in mapping a received word to an appropriate weight vector so that any codeword that is close enough to the received word (in the ${\mathrm{\ell }}_p$ metric) has sufficient correlation with the weight vector. The prior work [10] uses very simple weights: given a real received value $r$, only its floor $\lfloor r\rfloor$ and ceiling $\lceil r\rceil$ receive positive weights, of $1-(r-\lfloor r\rfloor )$ and $1-(\lceil r\rceil -r)$, respectively. It was shown that with these weights, the cited soft-decision algorithms decode up to any ${\mathrm{\ell }}_2$ relative distance for any code rate up to $1-2{\delta }^2$. Moreover, for $\delta \le 1/2$ it was shown that this rate is optimal for those algorithms, i.e., no other weight assignment can work for a larger rate. However, [10] did not consider larger decoding distances than these, nor other metrics.

In this work, to handle large decoding distances and other metrics, we use “smoother” weights, which typically assign a positive weight to every alphabet symbol. Our overall approach (see Section 3) is quite general, and is parameterized by a function $f:ℝ\to [0,1]$ satisfying mild hypotheses, primarily that its Fourier transform $\widehat{f}$ is non-negative (see ˜2.12). This function can be seen as defining a weight – or a relative “likelihood,” in the case of a random channel – for every potential real-valued error.²²2For example, we take $f$ to be a Gaussian function for decoding in the ${\mathrm{\ell }}_2$ metric, or under a Gaussian channel. For a prime-order code alphabet ${𝔽}_q\cong {\mathbb{Z}}_q:=\mathbb{Z}/q\mathbb{Z}$, and a received real value $r\in ℝ/q\mathbb{Z}$, we assign weight $f(r-w+q\mathbb{Z})={\sum }_{e=r-w(\mathrm{mod}q)}f(e)$ to each alphabet symbol $w\in {\mathbb{Z}}_q$. Since the elements of the coset $r-w+q\mathbb{Z}$ are exactly those errors that would convert a transmitted symbol $w$ to the received value $r$, this assignment captures the total weight of all such errors.

Our first main result, given in Theorem 3.5, lower bounds the correlation between the weight vector for a received word $𝐫$ over $ℝ/q\mathbb{Z}$ and any (code)word $𝐜$ over ${\mathbb{Z}}_q$, by the ratio of two quantities determined by $f$: its (arithmetic or geometric) mean over the coordinates of the error vector $𝐫-𝐜$, and (the square root of) its sum over a certain two-dimensional integer lattice ${ℒ}_q$. So, for a particular decoding distance in a metric of interest (or channel distribution, in the average case), the goal becomes to choose a suitable function $f$ that nearly maximizes this ratio. The proof of the theorem uses a mild generalization of Fourier-analytic results on lattices from [1, 9], and is the source of our requirement that $\widehat{f}$ is non-negative, and ultimately the restriction that for ${\mathrm{\ell }}_p$ (semi)metrics.

The bulk of the remaining work is then devoted to making a suitable choice of function $f$ for the ${\mathrm{\ell }}_p$ (semi)metric (and corresponding channel distributions), and analyzing its summation over ${ℒ}_q$. In Section 4 we consider scalings of the function $f^{(p)}(x):=\exp (-{|x|}^p)$, which is known to have non-negative Fourier coefficients for (but not for any other $p$). Then in Sections 5 and 6 we specialize to $p=2$ and $p=1$, respectively, and give fairly tight upper bounds on $f({ℒ}_q)$ using Fourier-analytic techniques or direct analysis. Finally, we use these bounds to optimize the distance-rate tradeoffs for which we can list decode GRS codes in these ${\mathrm{\ell }}_p$ metrics, and for Gaussian and Laplacian random channels as well.

A linear (error-correcting) code of (block) length $n$ over the alphabet ${𝔽}_q$ is a linear subspace of ${𝔽}_q^n$. As a subspace, it has a dimension. In this paper, we consider the following family of codes.

In this work, all lattices are implicitly full rank. A lattice basis can equivalently be seen as an invertible matrix $𝐁\in {ℝ}^{n\times n}$ whose columns are the vectors ${𝐛}_1,\mathrm{\dots },{𝐛}_n$. Note that a given lattice has multiple different bases, which are all related by right-multiplication by unimodular matrices in ${\mathbb{Z}}^{n\times n}$.

Note that the determinant of a lattice is invariant under the choice of basis, by the above-mentioned relationship between the bases of a lattice.

Let $f:{ℝ}^n\to ℂ$ be a (Borel) measurable function that satisfies . Its Fourier transform $\widehat{f}:{ℝ}^n\to ℂ$ is defined as

It satisfies the following standard properties, which follow by routine calculations.

We say that $f$ is nice if it satisfies conditions that are sufficient for the following formula to hold, e.g., those given in [13, pages 106–107]. All of the specific functions $f$ we use in this work are easily seen to be nice.

We will use a more general version of the PSF for lattice cosets.

Continuing from Section 2.3, for the rest of this work we require the following properties of $f$.

Because $f$ is real, its Fourier transform is conjugate symmetric, i.e., $\widehat{f}(-w)=\widehat{f}{(w)}^{\ast }$ for all $w$, where the star denotes complex conjugation. Since $\widehat{f}$ is also real, this implies that it is symmetric, i.e., $\widehat{f}(-w)=\widehat{f}(w)$. Finally, note that if $f$ satisfies this assumption, then so does its multiplicative extension $f^k$.

We now define an important Fourier-analytic quantity that plays an important role in our analysis. We adopt the name “roughness” because it is the functional inverse of the “smoothing parameter” from [9], which is the smallest $s$ that makes the function $f_s(𝐲+ℒ)$ sufficiently “smooth” as a function of $𝐲$.

Due to space constraints, the proof is left to the full version.

To list-decode Reed–Solomon codes under various norms and probabilistic channel models, we use the “weighted,” or soft-decision, list decoder of Guruswami and Sudan (hereafter GS) [7], as elaborated upon in Guruswami’s thesis [5, Section 6.2.10] and the work of Koetter and Vardy [8]. A soft-decision decoder takes a “weight vector” as input, and outputs a set of codewords.

Conceptually, each block $W_i$ of a weight vector may be thought of as specifying a (posterior) probability distribution ${\mathrm{\Pi }}_i$ over ${𝔽}_q$, where ${\mathrm{\Pi }}_i(x)$ is proportional to the probability that the $i$th transmitted symbol was $x\in {𝔽}_q$, given what was received from the channel (which need not be an element of ${𝔽}_q$). At a formal level, this interpretation makes sense only when the channel is probabilistic (for average-case decoding), but it still serves as useful intuition when the channel is adversarial (for worst-case decoding). We consider both types of channels in our results below.

For $c\in {𝔽}_q$, define $[c]\in {[0,1]}^q$ to be the binary indicator vector indexed by ${𝔽}_q$ that has a $1$ in coordinate $c$ and $0$s elsewhere. Similarly, for any vector $𝐜=(c_1,\mathrm{\dots },c_n)\in {𝔽}_q^n$, define the weight vector $[𝐜]:=([c_1],\mathrm{\dots },[c_n])\in {[0,1]}^{qn}$. Observe that its Euclidean norm is $\parallel [𝐜]\parallel =\sqrt{n}$.

We remark that the above theorem is originally stated for rational weights, but the supporting argument (from [5, Lemma 6.20]) easily adapts to handle real-valued weights that can be lower bounded to any needed precision in polynomial time, as all of ours can be.

Here we describe a general approach for translating a received word to a weight vector. This translation is parameterized by a function that, conceptually, can be viewed as (proportional to) the channel’s probability density function, even if the channel is not actually probabilistic.

Let $f:ℝ\to [0,1]$ be a function that satisfies ˜2.12, extended multiplicatively to ${ℝ}^n$ as in Equation 2.1, and recall that $f_s(x):=f(x/s)$ for any constant $s>0$. Next let $q$ be a positive integer, and recall that we identify ${\mathbb{Z}}_q:=\mathbb{Z}/q\mathbb{Z}$ with ${𝔽}_q$ in the natural way when $q$ is prime. Let the set of possible received values be ${ℝ}_q=ℝ/q\mathbb{Z}$, and for any such value $y\in {ℝ}_q$, define the weight function $W_{s,y}:{\mathbb{Z}}_q\to [0,1]$ by

Notice that here $f_s$ is applied to a coset of $q\mathbb{Z}$, which represents an infinite series; for all our concrete choices, these series converge and so the function $W_{s,y}$ is well defined. This function can also be seen as the vector $W_{s,y}:={(W_{s,y}(x))}_{x\in {\mathbb{Z}}_q}\in {[0,1]}^q$, indexed by ${\mathbb{Z}}_q$.

In line with the probabilistic conception of weight vectors from Section 3.1 above, the function $W_{s,y}$ can be seen as follows. Suppose that a uniformly random symbol in ${\mathbb{Z}}_q$ is sent over a channel, which adds (modulo $q$) noise drawn from a distribution over $ℝ$ whose probability density function is proportional to $f_s$. Then the probability that the sent symbol was $x\in {\mathbb{Z}}_q$, conditioned on receiving $y$, is proportional to $W_{s,y}(x)$. This is because the coset $y-x\in {ℝ}_q$ is the set of all noise values that yield $y$ if $x$ is sent. Note that in the definition of $W_{s,y}$ we do not normalize by the total weight $W_{s,y}({\mathbb{Z}}_q)=f_s(y+\mathbb{Z})$ (which may vary based on the received value $y$); this turns out to yield simpler analyses and tighter results.

In order to use the soft-decision algorithm (Theorem 3.3) for decoding under an adversarial channel, it suffices to show that we can choose a suitable $s$ so that for any received word $𝐲$ and any sufficiently close codeword $𝐜$ (in the norm of interest), the correlation $\mathrm{corr}(W_{s,𝐲},𝐜)$ satisfies (3.1). Similarly, for decoding under a probabilistic channel, it suffices to show that with high probability over the channel noise $𝐞$, the transmitted codeword $𝐜$ has large enough correlation with the weight vector $W_{s,𝐲}$ of the received word $𝐲=𝐜+𝐞$ (again, for some suitably chosen $s$). To this end, in what follows we give a lower bound on $⟨W_{s,𝐲},[𝐜]⟩$ and an upper bound on $\parallel W_{s,𝐲}\parallel$, in terms of $f_s$ and the difference $𝐲-𝐜$ between the received word and the codeword of interest.

Here we state and prove the main result of this section. For this we define the two-dimensional integer lattice ${ℒ}_q$ that consists of all shifts of the lattice $q{\mathbb{Z}}^2$ by $(z,z)$ for an integer $z$, i.e.,

We have that $det({ℒ}_q)=q$, and so $det({ℒ}_q^{\ast })=1/q$. We sometimes omit the $q$ subscript when it is clear from context or its value is unimportant.

Here we consider list-decoding in the average case, where the channel is probabilistic (not worst case) and the goal is to output a list of codewords that includes the transmitted one. We consider channels that add independent, identically distributed random error (drawn from some specified distribution) to each coordinate of the transmitted codeword; this is often known as a memoryless additive channel. Specifically, we assume that the channel’s error distribution (for each coordinate) is proportional to $f_r$ for some $r>0$, i.e., it has probability density function

For example, if $f_r$ is a Gaussian function, this is known as the additive white Gaussian noise (AWGN) channel model. In some settings one may also consider a discrete channel distribution, e.g., over $\mathbb{Z}$, in which case its probability mass function is $D_r(x):=f_r(x)/f_r(\mathbb{Z})$. For any $s>0$ (which may differ from $r$), define

In Section 4 we will use the following bound for a specific family of functions $f$ to show that the transmitted codeword is recovered with high probability over the channel error.

This follows from ˜2.12, 3.5, and 2.1. Due to space constraints, the details of the proof are left to the full version.

We now address list-decoding in the ${\mathrm{\ell }}_p$ (semi)metric for , under worst-case error. Consider decoding distance $d=\delta \cdot n^{1/p}$, where $n$ is the code length, and $\delta$ can be seen as the relative decoding distance (relative to $n^{1/p}$, which is the most natural normalization factor for ${\mathrm{\ell }}_p$). For $s>0$, relative distance $\delta \ge 0$, and positive integer modulus $q$, define

By Theorems 3.5 and 3.3, to decode a GRS code of adjusted rate $R^{\ast }$ over a prime field ${𝔽}_q$ to within ${\mathrm{\ell }}_p$ distance $\delta \cdot n^{1/p}$ using the GS algorithm, it suffices to set $s>0$ so that $W_{q,\delta }^{(p)}(s)>\sqrt{R^{\ast }}$. In other words, we can decode under relative distance $\delta$ for any $R^{\ast }$ less than

The following makes this formal.

We now consider average-case decoding under a memoryless additive (continuous or discrete) channel whose density function is proportional to a scaling of $f=f^{(p)}$. Specifically, we consider the continuous distribution with probability density function $D_r(x):=f_r(x)/r$, and the discrete distribution over $\mathbb{Z}$ with probability mass function $D_r(x):=f_r(x)/f_r(\mathbb{Z})$. Following Section 3.4, for any $r,s>0$ define

For these channel distributions we derive suitable bounds on ${\mu }_{r,s}^{(p)}$, then reach the conclusion via Lemmas 3.7 and 3.3.

Due to space constraints, the proof is left to the full version.

Now, for any channel parameter $r>0$ and for $s>0$, define

where the inequality is by Lemma 4.4. By Theorems 3.5 and 3.3, to decode (with high probability) a GRS code of adjusted rate $R^{\ast }$ over a prime field ${𝔽}_q$ under a channel with parameter $r$, it suffices to set $s>0$ so that $A_{q,r}^{(p)}(s)>\sqrt{R^{\ast }}$. In other words, we can decode under channel parameter $r$ for any $R^{\ast }$ less than

The following makes this formal.

The proof is similar to that of Theorem 4.2, but using Lemma 3.7 to bound the probability that . Due to space constraints, the details are left to the full version.

In this subsection we derive fairly tight bounds on the factor $f_s({ℒ}_q)$ that appears in the quantities that govern the adjusted rates under which we can decode in the worst and average cases (Equations 4.2 and 4.4, respectively). For this purpose we need to define a suitable “fudge factor.” For $r\ge r_0:=\sqrt{\ln (4)/\pi }\approx 0.66428$, define

Notice that $E(r)$ is positive for $r>r_0$, is strictly increasing, and rapidly approaches $1$ as $r$ increases. Next, for real $s,q$ such that $s\in [r_0,q/r_0]$, define

Similarly, $E_q(s)$ is positive for $s\in (r_0,q/r_0)$, and rapidly approaches $1$ as both $s,q/s$ increase.

We next state some bounds on $f_s({ℒ}_q)$ and $E_q(s)$; Lemma 5.1 is the main one we use. Due to space constraints, the proofs are given in the full version.

This follows directly from Lemmas 5.2 and 5.4 below.

Next we bound the roughness quantities ${\epsilon }^{\prime },\tilde{\epsilon }$ from Lemmas 5.1 and 5.2, using the following classic tail inequality.

We now address list-decoding in the ${\mathrm{\ell }}_2$ metric, under worst-case error of bounded distance, by specializing the material of Section 4.1 to $p=2$ and using our bounds on $f_s({ℒ}_q)$ from Section 5.1. So, we consider decoding distance $d=\delta \sqrt{n}$, where $n$ is the code length and $\delta$ is the relative decoding distance. Then by Equations 4.2 and 4.3, we can list-decode for any $R^{\ast }$ less than

where the inequality follows by Lemma 5.1.

Corollary 5.5 below is obtained by nearly maximizing the right-hand side of (5.1). More specifically, a standard calculation shows that taking $s=\delta \sqrt{4\pi }$ maximizes the “main term” $\sqrt{2}\cdot \exp (-2\pi {\delta }^2/s^2)/s$, to have value $1/(\delta \sqrt{2\pi e})$. For moderate or larger values of $\delta$ (and hence $s$), this very nearly maximizes the entire expression, because $E_q(s)\ge E(s)$ since $q/s\ge s$, and $E(s)$ rapidly approaches $1$ as $s$ grows. For example, $E{(s)}^2\ge 1-{10}^{-8}$ for $\delta \ge 1$. So, as $\delta$ grows, the $R^{\ast }$ for which we can list-decode rapidly approaches $1/(\delta \sqrt{2\pi e})$.