List Decoding
\gdef\p#1{\left({#1}\right)} \gdef\ceil#1{\left\lceil{#1}\right\rceil} \gdef\norm#1{\left|{#1}\right|} \gdef\setn#1{\mathcal{#1}} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\F{\mathbb{F}} \gdef\Z{\mathbb{Z}} \gdef\vd{𝛅} \gdef\i{\mathrm{i}} \gdef\j{\mathrm{j}} \gdef\om{\mathrm{\omega}} \gdef\wt{\operatorname{wt}} \gdef\d{\operatorname{d}} \gdef\A{\operatorname{A}} \gdef\Aut{\operatorname{Aut}} \gdef\Iso{\operatorname{Iso}} \gdef\L{\operatorname{L}} \gdef\span{\operatorname{span}}
Definition 1. The Hamming weight of a vector \vec{v} \in \F_q^n is defined as the number [0,n] of non-zero coordinates in \vec{v}, denoted as
\wt(\vec v) = \norm{\set{i \in [0,n) \mid v_i \neq 0}} \text{.}
Given a subset \setn{S} \subseteq \F_q^n, its (minimum) weight or minimum distance is
d = \wt(\setn S) = \min_{\vec v \in \setn S} \wt(\vec v)
and its weight distribution is
\A_i(\setn S) = \norm{\set{\vec v \in \setn S \mid \wt(\vec v) = i}}
for i \in [0,n].
Definition 2. Given a subspace \setn C \subseteq \F_q^n and a vector \vec r \in \F_q^n, the coset of \setn C with offset \vec r is the affine subspace
\vec r + \setn C = \set{\vec r + \vec c \mid \vec c \in \setn C} \text{.}
The list decoding size of \vec r is
\L_i(\setn C, \vec r) = \sum_{j \in [0,i]} \A_j(\vec r + \setn C) \text{.}
And the list decoding bound of \setn C is
\L_i(\setn C) = \max_{\vec r \in \F_q^n} \L_i(\setn C, \vec r) \text{.}
Lemma 3. Given a subspace \setn C \subseteq \F_q^n we have the singleton bound
\wt(\setn C) \leq n - \dim \setn C + 1 \text{,}
and when the bound is tight, i.e., when equality holds, then \setn C is called maximum distance separable (MDS).
We can now solve the coset size of two special cases when \setn C is MDS, the first one when \vec r = \vec 0:
Lemma 4. Given an MDS \setn C \subseteq \F_q^n we have
\A_i(\setn C) = \begin{cases} 1 & \text{if } i = 0 \\ 0 & \text{if } 1 \leq i < d \\ \binom{n}{d} (q-1) & \text{if } i = d \\ f_i(q,n,d) & \text{if } i \geq d \text{,} \end{cases}
where
f_i(q,n,d) = \binom{n}{i} (q-1)\sum_{j=0}^{i - d} (-1)^j \binom{i-1}{j} q^{i - d - j} \text{.}
A second special case is when \vec r is such that the span of \setn C and \vec r is also MDS.
Lemma 5. Given an MDS \setn C \subseteq \F_q^n and a vector \vec r \in \F_q^n such that \setn D = \span(\setn C \cup \{\vec r\}) is also MDS, we have
\A_i(\vec r + \setn C) = \begin{cases} 0 & \text{if } i < d - 1 \\ \binom{n}{d-1} & i = d - 1 \\[1em] \frac{f_i(q, n, d - 1) - f_i(q, n, d)}{q - 1} & \text{if } i \geq d \text{.} \end{cases}
Proof: Since \setn D is MDS, its minimum distance is
d' = n - \dim \setn D + 1 = n - (\dim \setn C + 1) + 1 = d - 1 \text{.}
By Huffman-Pless lemma 7.5.1 we have
\A_i(\vec r + \setn C) = \frac{\A_i(\setn D) - \A_i(\setn C)}{q - 1} \text{.}
For i = both \A_i(\setn D) and \A_i(\setn C) are one and cancel out. For i < d - 1 both \A_i(\setn D) and \A_i(\setn C) are zero. For i = d - 1 we have \A_i(\setn D) = \binom{n}{d-1} (q-1) and \A_i(\setn C) = 0. For i \geq d we get
\footnotesize \begin{align*} \frac{\A_i(\setn D) - \A_i(\setn C)}{q-1} &= \frac{f_i(q, n, d - 1) - f_i(q, n, d)}{q - 1} \\ &= \binom{n}{i} \p {\sum_{j=0}^{i - d - 1} (-1)^j \binom{i-1}{j} q^{i - d - 1 - j} - \sum_{j=0}^{i - d } (-1)^j \binom{i-1}{j} q^{i - d - j}} \\ &= \binom{n}{i} \p{\sum_{j=0}^{i - d - 1} (-1)^j \binom{i-1}{j} \p{q^{i - d - 1 - j} - q^{i - d - j}} - (-1)^{i - d} \binom{i-1}{i - d}} \end{align*}
We conjecture that these two cosets alternately bound the weight distributions of all other cosets of MDS codes, with the zero coset being the upper bound for i = d, lower bound for i = d + 1, etc. And the MDS coset being the upper bound for i = d - 1, lower bound for i = d, etc.
Absolute chaos below
Definition 1. The Hamming weight of a vector \vec{v} \in \F_q^n is defined as the number [0,n] of non-zero coordinates in \vec{v}, denoted as \wt(\vec v).
The Hamming distance between two vectors \vec{u}, \vec{v} \in \F_q^n is defined as the Hamming weight of their difference, \d(\vec{u}, \vec{v}) = \wt(\vec{u} - \vec{v}), or equivalently the number of coordinates in which they differ. The function \d is a metric on \F_q^n.
Given a subset \setn{S} \subseteq \F_q^n, its (minimum) weight is \wt(\setn S) = \min_{\vec v \in \setn S} \wt(\vec v) and its weight distribution is \A_i(\setn S) = \norm{\set{\vec v \in \setn S \mid \wt(\vec v) = i}} for i \in [0,n].
A linear subspace \setn{C} \subseteq \F_q^n is MDS iff \wt(\setn C) = n - \dim \setn C - 1.
Lemma 2. The set of transformations that preserve the \F_q^n-linear structure and the Hamming weight (equivalently, the Hamming distance) are exactly the monomial transformations together with global \F_q-automorphisms. That is, for any \vec{v} \in \F_q^n, monomial matrix \mat{M} \in \operatorname{Mon}(n, \F_q), and field automorphism \sigma \in \Aut(\F_q), we have
\wt(\mat{M} \cdot \sigma(\vec{v}) ) = \wt(\vec{v}) \text{.}
The group of all such weight and distance preserving transformations is denoted
\Iso\!\p{\F_q^n} = \operatorname{Mon}(n, \F_q) \rtimes \Aut(\F_q) \text{.}
Recall that a monomial matrix is a square matrix with exactly one non-zero entry in each row and column, or equivalently, the product of a permutation matrix and an invertible diagonal matrix. For finite fields \F_{p^m} the automorphisms are precisely the m powers of the Frobenius automorphism \sigma(x) = x^p. For prime field m =1 and the only automorphism is the identity. The automorphism \sigma is applied coordinate-wise to high dimensional objects.
Definition 3. A linear code is a subspace \setn{C} \subseteq \F_q^n to which we attach a lot of verbiage:
- alphabet, symbols: the field \F_q and its elements.
- messages: the elements of \F_q^k.
- words: the elements of \F_q^n.
- length: n.
- size: \norm{\setn{C}} = q^k.
- dimension: k = \dim(\setn{C}).
- redundancy: r = n - k.
- rate: \rho = \frac{k}{n}.
- capacity: q^k.
- minimum distance: d = \wt(\setn{C} \setminus \{0\}).
- generator matrix: a matrix \mat G \in \F_q^{k \times n} whose rows form a basis of \setn{C}.
- systematic form: a generator matrix of the form \mat G = [\mat{I}_k \mid \mat{A}].
- dual code: the linear code \setn{C}^\perp.
- parity matrix: a generator matrix of the dual code \setn{C}^\perp.
- syndrome space: the space \F_q^r.
Two codes \setn{C}, \setn{C'} are said to be monomialy equivalent if from some \sigma \in \Iso\!\p{\F_q^n} we have \setn{C'} = \sigma(\setn{C}).
When we fix a generator matrix \mat G for a code \setn{C}, we can identify messages \vec{m} \in \F_q^k with codewords \vec{c} = \vec{m} \cdot \mat G \in \setn{C}. We call \vec{c} the encoding of \vec{m}.
The point of all this is that we allow some number t of coordinates in the encoding to get corrupted (i.e. replaced by an arbitrary \F_q), and still be able to recover the original message, or at least constrain it to a small set. The nature of these corruptions is modeled by the Hamming distance.
Definition 4. A Reed-Solomon (RS) code \operatorname{RS}_q(n, k, \vec{x}) with \vec{x} \in F_q^n all distinct is generated by the n \times k matrix \mat G_{ij} = x_i^j. We can extend it with an additional evaluation point that has powers x^j = 0 for j < k - 1 and x^{(k-1)} = 1.
By monomial equivalence, permuting the evaluation points does not materially change the code. We can also scale the evaluation points by non-zero \lambda_i \in \F_q^\times to get a more general generator matrix \mat G_{ij} = \lambda_i x_i^j.
The \vec{\lambda} doesn't add much, other than making the class closed under monomial equivalence. Typically the x_i's form (a coset of) a subgroup of \F_q^\times to allow fast NTT algorithms, but the only requirement is that they are distinct. It is popular to interpret Reed–Solomon codes as evaluations of low-degree polynomials, but we will avoid introducing even more terminology here.
Conjecture. (RS equivalence) The weight spectra of all [n,k] Reed-Solomon codes over \F_q are identical for fixed parameters q,n,k.
Evidence. Has been tested up to q=p=7.
Fails for [13,6,2]!
Conjecture. (MDS Conjecture) If k ≤ q then a linear MDS code has length n ≤ q + 1 unless q is even and k = 3 or k = q − 1, in which case n ≤ q + 2.
Evidence. It is proven to hold for:
- k < \sqrt{q}/4, q odd, k <\sqrt{q}, q even (Segre, 1967).
- k < \sqrt{pq}, q =p^{2h+1} (Voloch, 1991).
- k < \sqrt{q}/2, q = p^{2h}, p > 5 (Hirschfeld-Korchmaros, 1996).
- k < q, q = p (Ball, 2010).
- k < 2\sqrt{q}, q = p^2 (Ball-De Beule, 2011).
If p ≥ k ≥ 3, then a linear MDS code of length q + 1 over the finite field Fq, q = p^h, is a Reed-Solomon code. https://cage.ugent.be/~ls/website2017/abstracts/abstractJanDeBeule.pdf
MDS Classification Conjecture: All MDS codes are equivalent to a Reed-Solomon code or a trivial extension thereof.
https://building-babylon.net/2025/01/17/from-equivalences-of-reed-solomon-codes-to-algebraic-geometry-codes/
Definition 5. List decoding is a function \L : \F_q^n \times [0, n] \to \setn{P}(\setn{C}) that maps a received word \vec{r} \in \F_q^n and a decoding radius t \in [0, n] to the set of codewords within Hamming distance t of \vec{r}:
\L_{\setn{C}}(\vec{r}, t) = \set{ \vec{c} \in \setn{C} \mid d(\vec{r}, \vec{c}) \leq t } \text{.}
Sometimes relative distance \vd = \frac{t}{n} is used instead of absolute distance t. We call \ell = \norm{\L_{\setn{C}}(\vec{r}, t)} the list size for received word \vec{r} and radius t.
A code \setn{C} is said to be (t, \ell)-list decodable if
\norm{\L_{\setn{C}}(\vec{r}, t)} \leq \ell \text{ for all } \vec{r} \in \F_q^n \text{.}
We say this is exact if there exists some \vec{r} \in \F_q^n such that \norm{\L_{\setn{C}}(\vec{r}, t)} = \ell.
We say r is a unique decoding radius if \setn{C} is (r, 1)-list decodable.
Some trivial corrolaries:
- If \setn{C} is (t, \ell)-list decodable, then it is also (t', \ell)-list decodable for all t' \leq t.
- If \setn{C} is (t, \ell)-list decodable, then it is also (t, \ell')-list decodable for all \ell' \geq \ell.
- Every code \setn{C} is exactly (0, 1)-list decodable.
- Every code \setn{C} is exactly (n, \norm{C})-list decodable.
Maximum list sizes
Let \L_{\setn{C}}: [0,n] \to \N denote the maximum list size over all received words \vec{r} \in \F_q^n for decoding radius t, i.e.,
\L_{\setn{C}}(t) = \max_{\vec{r} \in \F_q^n} \norm{\L_{\setn{C}}(\vec{r}, t)} \text{.}
Then \setn{C} is exactly (t, \L(t))-list decodable for all t \in [0,n]. Hence we are interested in computing or bounding the function \L_{\setn{C}}(t).
There are a number of identical ways to express \L_{\setn{C}}(\vec r, t):
\begin{aligned} \L_{\setn{C}}(\vec{r}, t) &= \set{ \vec{c} \in \setn{C} \mid d(\vec{r}, \vec{c}) \leq t } \\ &= \setn{C} \cap (\vec r + \setn{B}_t) \\ &= \set{ \mat{H} \cdot \vec e \mid \wt(\vec e) \leq t} \\ \end{aligned}
where \setn{B}_t = \set{\vec{v} \in \F_q^n \mid \wt(\vec{v}) \leq t} is the Hamming ball of radius t centered at \vec{0}.
Syndrome decoding: \vec r = \vec c + \vec e for some codeword \vec c \in \setn{C} and error vector \vec e \in \setn{C}^\perp with \wt(\vec e) \leq t. Then \vec c = \vec r - \vec e.
To find \vec e, we compute the syndrome of the received word \vec r:
\vec s = \mat{H} \cdot \vec r = \mat{H} \cdot (\vec c + \vec e) = \mat{H} \cdot \vec e \text{,}
where we use the fact that \mat H \cdot \vec c = \vec 0 for all \vec c \in \setn{C}. Thus the list decoding problem reduces to finding all error vectors \vec e of weight at most t with syndrome \vec s:
\L(\vec{r}, t) = \set{ \vec r - \vec e \mid \vec e \in \setn{B}_t \wedge \mat H \cdot \vec e = \mat H \cdot \vec r} \text{.}
Applying this to the maximum list size function, we get
\begin{aligned} \L(t) &= \max_{\vec r \in \F_q^n}\ \L(\vec r, t) \\ &= \max_{\vec r \in \F_q^n}\ \norm{\set{ \vec e \mid \vec e \in \setn{B}_t \wedge \mat H \cdot \vec e = \mat H \cdot \vec r}} \\ &= \max_{\vec s \in \F_q^r}\ \norm{\set{ \vec e \mid \vec e \in \setn{B}_t \wedge \mat H \cdot \vec e = \vec s}} \\ \end{aligned}
where the last step follows from the fact that \mat H is surjective onto \F_q^r. This limits our search space from \F_q^n to \F_q^r.
\begin{aligned} \L(t) &= \max_{\vec s \in \F_q^r}\ \norm{\setn{B}_t \cap \mat H^{-1}(\vec s)} \\ &= \max_{\vec s \in \F_q^r}\ \norm{\setn{B}_t \cap (\vec e_0(\vec s) + \ker \mat H)} \\ &= \max_{\vec s \in \F_q^r}\ \norm{\setn{B}_t \cap (\mat G \cdot \vec s + \ker \mat H)} \\ \end{aligned}
where \mat G is the right inverse of \mat H, i.e., \mat H \cdot \mat G = \mat I_r. If we put \mat H in normal form \mat H = [\mat I_r \mid \mat H'], then we can choose \mat G = \begin{bmatrix} \mat I_r \\ 0 \end{bmatrix}. Then we have \mat G \cdot \vec s = [\vec s \mid \vec 0]. The set \ker \mat H is the code \setn{C} itself, so we can also write
\begin{aligned} \L(t) &= \max_{\vec s \in \F_q^r}\ \norm{\setn{B}_t \cap ([\vec s \mid \vec 0] + \setn{C})} \text{.} \end{aligned}
To maximize the size of this intersection, we can set \vec s, such that it zeros out the first r coordinates of the codewords in \setn{C}. Call the \setn{C}_r. Then we have
\begin{aligned} \L(t) &= \norm{\setn{B}_t \cap \setn{C}_r} \text{.} \end{aligned}
This is counting the number of codewords in \setn{C}_r of weight at most t.
Conjecture: For cyclic codes the list decoding sizes are identical for the code and it's dual.
Lemma 6. For an MDS code \setn{C} we have
\L_{\setn C}(t) = \L_{\setn C^\perp}(t) \text{.}
It is conjectured to holds for all cyclic codes.
Definition. The weights enumerator of a code \setn{C} is
W_{\setn{C}}(x,y) = \sum_{i=0}^n A_i x^{n-i} y^i \text{,}
where A_i = \norm{\set{\vec c \in \setn{C} \mid \wt(\vec c) = i}} is the number of codewords of weight i.
Let A_i be the number of codewords of weight i in \setn{C}_r. Then we have for an MDS code with minimum distance d = n - k -1:
A_w = \binom{n}{w} (q-1)\sum_{j=0}^{w-d} (-1)^j \binom{w-1}{j} q^{\,w-d-j}.
https://dr.ntu.edu.sg/server/api/core/bitstreams/f6ca9d42-8532-42fa-8a1a-e28f5655c1d1/content
for w > d, A_0 = 1 and A_w = 0 for w \leq d.
\begin{aligned} \L(t) &= \max_{\vec m \in \F_q^k}\ \norm{\setn{B}_t \cap \mat P^{-1}(\vec m)} \\ \end{aligned}
So now we have two interpretations of the maximum list size, each being the maximum size of the intersection of a Hamming ball with an affine subspace.
Weight distribution of affine subspaces
An affine subspace \setn{A} \subseteq \F_q^n of dimension k is a set of the form \setn{A} = \vec a_0 + \setn{U} where \vec a_0 \in \F_q^n and \setn{U} \subseteq \F_q^n is a linear subspace of dimension k. The weight distribution of \setn{A} is the vector \vec w_{\setn{A}} \in \N^{n+1} such that (\vec w_{\setn{A}})_i = \norm{\set{\vec a \in \setn{A} \mid \wt(\vec a) = i}}.
Let (\vec a, \mat G) be an affine basis of \setn{A}, i.e., \setn{A} = \set{\vec a + \vec u \mid \vec u \in \setn{U}} and \mat G is a generator matrix of \setn{U}. Then we can write
Zero offset
If \vec a = \vec 0 then the affine subspace is just a linear subspace. If it also satisfies the MDS property, then we have the following formula for its weight distribution:
Lemma. The weight distribution of a linear subspace \setn{U} \subseteq \F_q^n with minimum weight d = 1 + n - \dim{\setn{U}} (i.e. it is MDS) is given by w_0 = 1, w_i = 0 for 0 < i < d and for i \geq d:
w_i = \binom{n}{i} (q-1)\sum_{j=0}^{i-d} (-1)^j \binom{i-1}{j} q^{i-d-j} \text{.}
See MacWilliams–Sloane Thm. 11.4.6 p. 320 or Huffman-Pless Thm. 7.4.1 p. 262.
- Conjecture. The offset-zero weight distribution is an upper bound for all coset weight distributions for i \geq d.
w_d = \binom{n}{d} (q-1)
-> each coset of C of weight s has the same weight distribution.
-> Let C be a code of length n over q with A ∈ Aut(C). Let v ∈ n q. Then theweightdistributionofthecosetv +C isthesameastheweightdistributionofthecoset vA+C. Reed–Solomon Monomial automorphisms correspond to the affine group of the evaluation points.
One dimension
The main problem is that the naive algorithm iterates over q^r values. But in the one dimensional case we can do it in O(n \log n) time:
In the one dimensional case we iterate through \vec c =\vec a + n \cdot \vec b. Each coordinate is zero exactly when
c_i = a_i + n \cdot b_i = 0 \implies n = -a_i / b_i \text{.}
To compute the weight distribution, we need to count how many coordinates are zero for each n \in \F_q. This is equivalent to counting how many times each value in \F_q occurs in the list \set{-a_i / b_i \mid b_i \neq 0}. This can be efficiently done by computing \vec n, sorting the coordinates and counting repetition lengths.
We need to take care of the case b_i = 0 separately. In that case the coordinate is always a_i its contribution to the weight is computed once and the coordinate is ignored in the rest of the algorithm.
By monomial equivalence we can scale the coordinates to make b_i all \{0,-1\}.
Then n_i = a_i for non-zero b_i and we can sort and count repetitions in \vec a directly.
Conjecture: For an MDS code w_d(\setn C) = \binom{n}{d} \cdot (q - 1) in \setn{C}. It is conjectured that for MDS codes w_d(\setn C) \geq w_d(\vec v + \setn C) for all \vec v \in \F_q^n.
Conjecture. The weight distribution spectrum of an [q,n,k] RS code is independent of the evaluation points \vec x.
Evidence Has been tested up to ...
A stronger version (TODO: Test):
Conjecture. The weight distribution spectrum of an [q,n,k,d] code only depends on the parameters q,n,k,d.
Evidence Has been tested up to ...
- TODO: Cyclic codes and how RS codes are monomialy equivalent to cyclic codes.
MacWilliams identity
The weight distribution of the code \setn{C} is \vec w_{\setn{C}} \in \N^{n+1} such that (w_{\setn{C}})_i = \norm{\set{\vec c \in \setn{C} \mid \wt(\vec c) = i}}. The weight distribution of a code and its dual are related by the MacWilliams identity:
\norm{\setn{C}} \cdot \vec w_{\setn{C}^\perp} = \mat{K}^{(n,q)} \cdot \vec w_{\setn{C}} \text{,}
where \mat{K}^{(n,q)} \in \Z^{(n+1) \times (n+1)} is the q-ary Kravchuk matrix with entries given by the recurrence relation
\begin{aligned} \mat{K}_{0j} &= 1 \\ \mat{K}_{in} &= (-1)^i \cdot \binom{n}{i} \\ \mat{K}_{ij} &= \mat{K}_{i-1,j} - (q-1) \cdot \mat{K}_{i-1,j+1} + \mat{K}_{i,j+1} \text{.} \end{aligned}
-
https://www.cs.cmu.edu/~venkatg/pubs/papers/listdecoding-NOW.pdf
-
https://arxiv.org/abs/2101.12722 https://doi.org/10.3934/amc.2021042
• Andries E. Brouwer and Philippe Delsarte, “Weight distributions of MDS codes,” Report ZW 104/74, Mathematical Centre (now CWI), Amsterdam, 1974.
https://arxiv.org/abs/2101.12722
-
[WS72] MacWilliams & Sloane — The Theory of Error-Correcting Codes
-
P. G. Bonneau (1990). Weight distribution of translates of MDS codes. Combinatorica, 10(1), 103–105. doi:10.1007/bf02122700.
https://errorcorrectionzoo.org/kingdom/q-ary_digits_into_q-ary_digits
https://errorcorrectionzoo.org/c/reed_solomon https://rptu.de/channel-codes
Open problems:
- Are all MDS codes monomialy equivalent to an (extended) Reed-Solomon codes?
- How many different weight distributions are there for [q,n,k]-MDS codes?
