从 Hamming 码到多项式

Hamming 码的最小距离只有 3，只能纠正 1 位错误。码块变长后，一块里出现两个错误的概率迅速上升，单错纠错就不够用了。需要一种距离随码长增长的码。

这一讲的思路来自一条古老的代数事实：

域上次数不超过 $d$ 的非零多项式，至多有 $d$ 个根。

把消息编码成多项式在若干点上的取值，两个不同多项式就不可能在很多点上相同——差值多项式的根数给出了距离的下界。这就是 Reed–Solomon 码。

时间轴

构造：把消息写成多项式

设有限域为 $\mathbb F_q$（本讲可用 $\mathbb Z_p$，实际应用多用 $\mathbb F_{2^8}$）。消息是一串系数

$$m_0,m_1,\dots,m_{k-1}\in\mathbb F_q ,$$

对应多项式

$$p(x)=m_0+m_1x+\cdots+m_{k-1}x^{k-1},$$

次数不超过 $k-1$。

选 $n$ 个互不相同的求值点 $\alpha_1,\dots,\alpha_n\in\mathbb F_q$，码字定义为

$$c=\big(p(\alpha_1),\,p(\alpha_2),\,\dots,\,p(\alpha_n)\big).$$

本讲取 $\alpha_i=i$，即 $0,1,\dots,n-1$。

两个前提不能省：

• $n\le q$，否则域里没有 $n$ 个不同元素；
• 求值点互不相同，否则两个不同多项式可能在同一点取同值，距离论证失效。

线性性与生成矩阵

求值对系数是线性的：若 $p$ 对应 $c$、$p'$ 对应 $c'$，则 $p+p'$ 对应 $c+c'$。所以 RS 码是线性码。

生成矩阵的第 $j$ 行是「$m_j=1$、其余为 0」对应的码字，即在各点上的 $x^j$ 取值：

$$G= \begin{bmatrix} 1&1&1&\cdots&1\\ 0&1&2&\cdots&n-1\\ 0&1&4&\cdots&(n-1)^2\\ \vdots&\vdots&\vdots&&\vdots\\ 0&1&2^{k-1}&\cdots&(n-1)^{k-1} \end{bmatrix}.$$

所有运算在 $\mathbb F_q$ 中进行。例如 $q=13$ 时，$27\bmod13=1$，矩阵里的数不会无限增大。

这是一个 Vandermonde 矩阵：每列是求值点的幂次。由于求值点互不相同，它列满秩。消息 $m$ 的码字就是 $mG$，第 $i$ 个分量正是 $p(\alpha_i)$。

最小距离：$n-k+1$

定理。 RS 码的最小距离为

$$d=n-k+1 .$$

证明。 码字是 $(p(0),p(1),\dots,p(n-1))$，其中 $p$ 是次数不超过 $k-1$ 的多项式。

若 $p$ 不是零多项式，它至多有 $k-1$ 个根，所以 $p(0),\dots,p(n-1)$ 中至多有 $k-1$ 个等于 0。因此非零码字的 Hamming 重量至少是

$$n-(k-1)=n-k+1 .$$

这个下界可以达到（取适当的 $p$ 使根恰好落在 $k-1$ 个求值点上），所以 $d=n-k+1$。$\square$

能纠多少错

由最小距离定理，可纠错误数为

$$t=\left\lfloor\frac{d-1}{2}\right\rfloor=\left\lfloor\frac{n-k}{2}\right\rfloor .$$

等价地，要纠正 $e$ 个错误，需要

$$n-k\ \ge\ 2e .$$

例如 $(255,223)$ 的 RS 码：$n-k=32$，可纠 16 个符号错误。

这个距离达到了 Singleton 界 $d\le n-k+1$，因此 RS 码是 MDS 码（maximum distance separable）：在给定 $n$、$k$ 下，距离已经最大，不可能更好。

注意这里的「错误」以符号为单位，不是比特。一个符号是 $\mathbb F_q$ 的一个元素，在 $\mathbb F_{2^8}$ 中就是一个字节。

解码定理

收到的是带有错误的向量

$$\tilde c=(r_0,r_1,\dots,r_{n-1}),$$

其中多数位置满足 $r_i=p(i)$，少数不满足。

设错误位置为 $i_1,\dots,i_l$，$l\le e$。定义两个多项式：

• 错误定位多项式 $f(x)=\prod_{j=1}^{l}(x-i_j)$，次数为 $l\le e$；
• $q(x)=p(x)f(x)$，次数不超过 $(k-1)+e=k+e-1$。

定理。 对每个求值点 $i\in\{0,1,\dots,n-1\}$，

$$q(i)=r_i\,f(i).$$

证明。 分两种情况。

情况一：$i$ 是错误位置。 此时 $f(i)=0$，右边 $r_if(i)=0$。左边 $q(i)=p(i)f(i)=0$。等式成立。

情况二：$i$ 不是错误位置。 此时 $r_i=p(i)$，于是

$$q(i)=p(i)f(i)=r_if(i).$$

等式也成立。$\square$

这个定理看起来只是恒等式，但它把「哪些位置错了」这个离散问题，变成了「找一对多项式」的代数问题——而后者可以用线性代数求解。

用线性代数解码

把 $q$ 与 $f$ 按系数展开：

$$q(x)=q_0+q_1x+\cdots+q_{k+e-1}x^{k+e-1}, \qquad f(x)=f_0+f_1x+\cdots+f_ex^{e}.$$

对每个 $i=0,\dots,n-1$，方程 $q(i)=r_if(i)$ 写开是

$$\sum_{j=0}^{k+e-1}q_j\,i^j = r_i\sum_{j=0}^{e}f_j\,i^j .$$

把未知量移到同一边：

$$\sum_{j=0}^{k+e-1}q_j\,i^j-\sum_{j=0}^{e}\big(r_i\,i^j\big)f_j=0 .$$

这是关于未知系数 $q_0,\dots,q_{k+e-1},f_0,\dots,f_e$ 的线性方程。未知量个数是

$$(k+e)+(e+1)=k+2e+1,$$

方程个数是 $n$。取临界情形 $n=k+2e$，于是未知量比方程多一个。

线性方程组有非零解（齐次方程组，变量多于方程）。由于生成矩阵是满秩的 Vandermonde 矩阵，可以证明这些方程也满秩，解空间是一维的。

为了定出唯一解，利用 $f$ 的首项系数：若恰好有 $e$ 个错误，$\deg f=e$，可以归一化 $f_e=1$。代入后解唯一。

最后

$$p(x)=\frac{q(x)}{f(x)},$$

做多项式除法就恢复出原始多项式，其系数就是消息。

实际错误的个数少于 $e$ 时

上面的归一化假设了 $l=e$。若实际错误更少，$f$ 的次数低于 $e$，$f_e=0$，直接归一化会失败。

处理办法有两种：对 $l=0,1,\dots,e$ 逐个尝试并检验；或使用更精巧的算法（Berlekamp–Massey、Euclid 算法），它们能自动确定实际次数。本讲的线性代数解法胜在概念简单，效率不是最优。

串接码：让 RS 真正实用

单用 RS 码有一个硬限制： $n\le q$。在 $\mathbb F_{2^8}$ 中 $n\le256$，且可纠错误数最多是 $(n-k)/2<n/2$。若每个字节都可能出错，错误率超过一半就无法纠正。

具体算一下。设比特错误率 10%，一个字节（8 位）出错的概率是

$$1-(1-0.1)^8=1-0.9^8\approx0.57 .$$

而 RS 码最多容忍 $53/256\approx0.207$ 的符号错误率。$0.57>0.207$，外层 RS 码直接面对比特错误会失败。

两级编码

解决办法是串接两层码：先用内码把每个符号保护起来，再用 RS 码保护符号序列。

内码：查编码表，取 $(19,8,7)$ 码——8 位消息编成 19 位，最小距离 7，可纠 3 位错误。

外码：$\mathbb F_{2^8}$ 上的 RS 码，$n=256$、$k=150$、$e=53$。

编码顺序：

1. 消息按 8 位分组，得到 150 个字节，共 $150\times8=1200$ 比特；
2. 用 RS 外码编码成 256 个字节；
3. 每个字节再用内码编成 19 位，共 $256\times19=4864$ 比特。

解码顺序相反：先对每个 19 位块查表纠正至多 3 位错误，得到 256 个字节；再用 RS 解码纠正至多 53 个字节错误。

效果

一个 19 位块出现 4 个及以上错误的概率（即内码失败概率）约为

$$1-\sum_{j=0}^{3}\binom{19}{j}(0.1)^j(0.9)^{19-j}\approx0.115 .$$

经过内码后，每个字节仍有约 11% 的概率是错的。256 个字节中错误数的期望约 29 个，远低于可纠的 53 个；由二项分布尾界，超过 53 个的概率约 $10^{-60}$。

代价是带宽：1200 比特变成 4864 比特，约 4 倍。由 Shannon 容量 $1-H(0.1)\approx0.53$，理想码只需约 2 倍。相差不到一倍，在 1970 年代已经足够好，RS 码因此使用了三十多年——CD、DVD、深空通信、二维码里都能见到它。

本节结论

• RS 码把消息写成次数 $\le k-1$ 的多项式，在 $n\le q$ 个不同点上求值作为码字。
• 它是线性码，生成矩阵是 Vandermonde 矩阵，列满秩。
• 非零多项式至多 $k-1$ 个根，故最小距离 $d=n-k+1$，达到 Singleton 界，是 MDS 码。
• 可纠 $\lfloor(n-k)/2\rfloor$ 个符号错误。
• 解码定理：取错误定位多项式 $f=\prod(x-i_j)$ 与 $q=pf$，则对所有求值点 $q(i)=r_if(i)$。
• 这些等式是系数的线性方程组，未知量比方程多一个，归一化 $f_e=1$ 后唯一；解出后 $p=q/f$。
• $n\le q$ 与 $e<n/2$ 的限制使单层 RS 无法应对高比特错误率；串接 $(19,8,7)$ 内码后，10% 误码率下失败概率约 $10^{-60}$。

理解检验

1. 为什么「次数不超过 $k-1$ 的多项式至多有 $k-1$ 个根」能推出最小距离 $n-k+1$？

参考答案：两个不同码字对应两个不同多项式 $p_1\ne p_2$。它们的差 $p_1-p_2$ 是次数不超过 $k-1$ 的非零多项式，至多有 $k-1$ 个根。因此 $p_1-p_2$ 在 $n$ 个求值点中至多有 $k-1$ 个为 0，也就是两个码字至多在 $k-1$ 个位置上相同，至少在

$$n-(k-1)=n-k+1$$

个位置上不同。所以任意两个码字的 Hamming 距离至少是 $n-k+1$。取 $p_2=0$（零多项式也是合法码字），这个下界可以取到，故最小距离恰为 $n-k+1$。

2. $(255,223)$ 的 RS 码能纠正多少个符号错误？为什么不能再多？

参考答案：$d=n-k+1=255-223+1=33$，可纠

$$\left\lfloor\frac{d-1}{2}\right\rfloor=\left\lfloor\frac{32}{2}\right\rfloor=16$$

个符号错误。

不能再多的原因：若想纠 17 个错误，需要 $d\ge2\cdot17+1=35$，但 Singleton 界给 $d\le n-k+1=33$，矛盾。Singleton 界对任何码都成立，RS 码已经达到它，所以在给定的 $n$、$k$ 下距离不可能更大。

3. 为什么生成矩阵是 Vandermonde 矩阵，它为什么满秩？

参考答案：第 $j$ 行是各求值点上 $x^j$ 的取值，即 $(1^j,2^j,\dots,(n-1)^j)$（按本讲的取点）。把这些行竖排，每列是以求值点为底、幂次递增的向量，正是 Vandermonde 结构。

列满秩（前 $k$ 行构成的方阵行列式非零）的原因是：Vandermonde 行列式

$$\prod_{i<j}(\alpha_j-\alpha_i)$$

在求值点互不相同时不为零。因此任意 $k$ 个求值点上的取值都线性无关，矩阵秩为 $k$。这也是为什么求值点必须互不相同。

4. 在解码定理中，$f$ 与 $q$ 是怎么定义的？为什么 $q(i)=r_if(i)$ 对所有求值点都成立？

参考答案：$f(x)=\prod_{j=1}^{l}(x-i_j)$，其中 $i_1,\dots,i_l$ 是错误位置；$q(x)=p(x)f(x)$。

分两种情况验证：

• 若 $i$ 是错误位置，则 $f(i)=0$，两边都是 0；
• 若 $i$ 不是错误位置，则 $r_i=p(i)$，于是 $q(i)=p(i)f(i)=r_if(i)$。

两种情况下等式都成立。这个恒等式的价值在于：右边 $r_i$ 是已知的接收值，左边 $q$、$f$ 是待求多项式，于是所有 $i$ 上的等式组成一个关于系数的线性方程组。

5. 方程组有 $k+2e+1$ 个未知量、$n=k+2e$ 个方程，变量比方程多，为什么还能唯一确定 $f$ 与 $q$？

参考答案：齐次线性方程组在变量多于方程时必有非零解，且解空间维数至少为 1。可以证明这些方程满秩，所以解空间恰好一维——所有解都是某个非零解的整体倍数。

$f$ 与 $q$ 同时乘以常数不影响 $q(i)=r_if(i)$，所以需要额外条件定标。当实际错误数恰为 $e$ 时，$\deg f=e$，首项系数 $f_e\ne0$，归一化 $f_e=1$ 就把倍数固定住，得到唯一解。

若实际错误少于 $e$，则 $f_e=0$，这个归一化不成立，需要逐个尝试 $l$ 或改用 Berlekamp–Massey 等算法。

6. 为什么单层 RS 码在 10% 比特误码率下会失败？串接码如何解决？

参考答案：$\mathbb F_{2^8}$ 中一个符号是一个字节。比特错误率 10% 时，字节出错概率为

$$1-0.9^8\approx0.57 .$$

而 RS 码的可纠错误比例是 $e/n=(n-k)/(2n)<1/2$；例如 $53/256\approx0.207$。$0.57$ 远大于 $0.207$，外层码无法处理。

串接码先用 $(19,8,7)$ 内码把每个字节编成 19 位、纠 3 位错误，把 19 位块失败的概率压到约 11%；这个失败率对应到字节层只有 11%，低于 $20.7\%$ 的 RS 纠错能力，外层 RS 于是能够工作。

7. RS 码已经达到 Singleton 界（MDS），为什么还说它达不到 Shannon 容量？

参考答案：两个界针对的优化对象不同。Singleton 界 $d\le n-k+1$ 固定了 $n$、$k$，只问「在这个码长与维数下距离最大能到多少」；RS 码达到它，因此在这一意义下最优。

Shannon 容量回答的是另一件事：当 $n\to\infty$、字母表规模随之增长时，可靠传输能达到的最大速率。要达到容量，需要 $q$ 随 $n$ 增长并使用长码；而 RS 码受 $n\le q$ 限制，传统构造下 $q$ 与 $n$ 同阶，且解码复杂度随 $n$ 上升，无法逼近容量。串接码把差距缩小到常数倍，真正接近容量要等 turbo、LDPC、极化码。

8. 串接码的内码为什么可以用查表解码？这在 1977 年的硬件上意味着什么？

参考答案：$(19,8,7)$ 内码只有 $2^8=256$ 条码字，但收到的可能是任意 $2^{19}\approx524288$ 个 19 位串。可以预先把每个可能的接收串映射到最近的码字，做成一张约 50 万条的查找表；解码时直接查表，时间 $O(1)$。

代价是存储。现代计算机轻松容纳 50 万条表项，但 1977 年的 Voyager 探测器内存极为有限，不可能存下整张表。实际系统要么改用更小的内码（减少表项），要么改用解码极简的 Hamming 码（性能略差），要么采用其他结构化方案。课程没有给出 Voyager 的具体做法，只指出它必然在存储与性能之间做了折中。

与前后课的关系

上一讲 Hamming 码用校验矩阵实现单比特纠错，距离固定为 3；本讲用多项式求值把距离提高到 $n-k+1$，代价是运算搬到有限域、解码变成解线性方程组。

两讲合起来构成线性码的两条主线：校验（Hamming，综合解码）与代数构造（RS，错误定位多项式）。后续的 BCH 码、代数几何码都沿着后一条路走；串接码与迭代解码则通向 turbo 码与 LDPC 码。

本讲是编码理论单元的收尾。课程之后转向密码学与秘密共享——那里会再次看到有限域、多项式与线性代数，但目标从「对抗噪声」变成「对抗对手」。

From Hamming codes to polynomials

Hamming codes have minimum distance 3 and correct one bit. As blocks grow longer, the chance of two errors in one block rises quickly, so single-error correction is no longer enough. A code whose distance grows with the block length is needed.

The idea comes from an old algebraic fact:

A nonzero polynomial of degree at most $d$ over a field has at most $d$ roots.

Encode the message as the values of a polynomial at several points. Two different polynomials then cannot agree at many points — the root bound on their difference gives a distance lower bound. That is a Reed–Solomon code.

Timeline

Construction: the message as a polynomial

Let the field be $\mathbb F_q$ (any $\mathbb Z_p$ works; practice uses $\mathbb F_{2^8}$). The message is a list of coefficients

$$m_0,m_1,\dots,m_{k-1}\in\mathbb F_q ,$$

defining

$$p(x)=m_0+m_1x+\cdots+m_{k-1}x^{k-1},$$

of degree at most $k-1$.

Choose $n$ distinct evaluation points $\alpha_1,\dots,\alpha_n\in\mathbb F_q$ and define the codeword

$$c=\big(p(\alpha_1),\,p(\alpha_2),\,\dots,\,p(\alpha_n)\big).$$

This lecture takes $\alpha_i=i$, i.e. $0,1,\dots,n-1$.

Two requirements cannot be dropped:

• $n\le q$, since a field with $q$ elements has no more than $q$ distinct points;
• the points must be distinct, otherwise two different polynomials could agree at a shared point and the distance argument collapses.

Linearity and the generator matrix

Evaluation is linear in the coefficients: if $p\mapsto c$ and $p'\mapsto c'$, then $p+p'\mapsto c+c'$. So RS codes are linear.

The $j$-th row of the generator matrix is the codeword of "coefficient $m_j=1$, all others zero", namely the values of $x^j$ at the points:

$$G= \begin{bmatrix} 1&1&1&\cdots&1\\ 0&1&2&\cdots&n-1\\ 0&1&4&\cdots&(n-1)^2\\ \vdots&\vdots&\vdots&&\vdots\\ 0&1&2^{k-1}&\cdots&(n-1)^{k-1} \end{bmatrix}.$$

All arithmetic is in $\mathbb F_q$. For $q=13$, for instance, $27\bmod13=1$, so entries never grow without bound.

This is a Vandermonde matrix: each column holds the powers of one evaluation point. Since the points are distinct, it has full column rank. The codeword of $m$ is $mG$, whose $i$-th entry is exactly $p(\alpha_i)$.

Minimum distance: $n-k+1$

Theorem. The minimum distance of the RS code is

$$d=n-k+1 .$$

Proof. A codeword is $(p(0),p(1),\dots,p(n-1))$ with $\deg p\le k-1$.

If $p$ is nonzero, it has at most $k-1$ roots, so at most $k-1$ of $p(0),\dots,p(n-1)$ vanish. Hence every nonzero codeword has Hamming weight at least

$$n-(k-1)=n-k+1 .$$

The bound is attained (choose $p$ with roots at $k-1$ evaluation points), so $d=n-k+1$. $\square$

How many errors can be corrected

By the minimum-distance theorem,

$$t=\left\lfloor\frac{d-1}{2}\right\rfloor=\left\lfloor\frac{n-k}{2}\right\rfloor .$$

Equivalently, correcting $e$ errors requires

$$n-k\ \ge\ 2e .$$

For a $(255,223)$ RS code, $n-k=32$, so 16 symbol errors can be corrected.

This meets the Singleton bound $d\le n-k+1$, so RS codes are MDS (maximum distance separable): for fixed $n$ and $k$, the distance cannot be larger.

Note that an "error" here is a symbol, an element of $\mathbb F_q$ — one byte in $\mathbb F_{2^8}$ — not a bit.

The decoding theorem

The received vector is

$$\tilde c=(r_0,r_1,\dots,r_{n-1}),$$

where most positions satisfy $r_i=p(i)$ and a few do not.

Let the error positions be $i_1,\dots,i_l$ with $l\le e$, and define

• the error-locator polynomial $f(x)=\prod_{j=1}^{l}(x-i_j)$, of degree $l\le e$;
• $q(x)=p(x)f(x)$, of degree at most $(k-1)+e=k+e-1$.

Theorem. For every evaluation point $i\in\{0,1,\dots,n-1\}$,

$$q(i)=r_i\,f(i).$$

Proof. Two cases.

If $i$ is an error position, then $f(i)=0$, so the right side is $0$; the left side is $q(i)=p(i)f(i)=0$. Equal.

If $i$ is not an error position, then $r_i=p(i)$, so

$$q(i)=p(i)f(i)=r_if(i).$$

Equal again. $\square$

The identity looks trivial, but it converts a discrete question — which positions are wrong — into an algebraic one: find a pair of polynomials. The latter can be solved by linear algebra.

Decoding by linear algebra

Expand $q$ and $f$ by coefficients:

$$q(x)=q_0+q_1x+\cdots+q_{k+e-1}x^{k+e-1}, \qquad f(x)=f_0+f_1x+\cdots+f_ex^{e}.$$

For each $i=0,\dots,n-1$, the equation $q(i)=r_if(i)$ reads

$$\sum_{j=0}^{k+e-1}q_j\,i^j = r_i\sum_{j=0}^{e}f_j\,i^j .$$

Moving everything to one side:

$$\sum_{j=0}^{k+e-1}q_j\,i^j-\sum_{j=0}^{e}\big(r_i\,i^j\big)f_j=0 .$$

This is linear in the unknown coefficients $q_0,\dots,q_{k+e-1},f_0,\dots,f_e$. There are

$$(k+e)+(e+1)=k+2e+1$$

unknowns and $n$ equations. At the critical rate $n=k+2e$, there is one more unknown than equation.

A homogeneous system with more unknowns than equations has a nonzero solution. Because the generator matrix is a full-rank Vandermonde matrix, one shows these equations also have full rank, so the solution space is exactly one-dimensional.

To pin down the scale, use the leading coefficient of $f$: if exactly $e$ errors occurred, $\deg f=e$, so normalize $f_e=1$. The solution is then unique.

Finally,

$$p(x)=\frac{q(x)}{f(x)},$$

and polynomial division recovers the message coefficients.

When fewer than $e$ errors occur

The normalization assumed $l=e$. If fewer errors occurred, $\deg f<e$ and $f_e=0$, so normalizing $f_e=1$ fails.

One fix is to try $l=0,1,\dots,e$ in turn and check consistency; another is to use a more refined algorithm (Berlekamp–Massey or the Euclidean algorithm) that determines the actual degree. The linear-algebra method is conceptually simple but not the most efficient.

Concatenated codes: making RS practical

A single RS code has a hard limit: $n\le q$. Over $\mathbb F_{2^8}$, $n\le256$, and the correctable fraction $(n-k)/(2n)<1/2$. If every symbol may be wrong, an error rate above one half cannot be handled.

Concretely, let the bit error rate be 10%. A byte of eight bits is wrong with probability

$$1-(1-0.1)^8=1-0.9^8\approx0.57 .$$

An RS code tolerates at most $53/256\approx0.207$ symbol errors. Since $0.57>0.207$, the outer RS code cannot face raw bit errors directly.

Two layers

Concatenate an inner code that protects each symbol with an outer RS code that protects the symbol sequence.

Inner code: from a code table, the $(19,8,7)$ code — eight message bits into nineteen, minimum distance 7, correcting three bit errors.

Outer code: an RS code over $\mathbb F_{2^8}$ with $n=256$, $k=150$, $e=53$.

Encoding proceeds as:

1. split the message into bytes: 150 bytes, i.e. $150\times8=1200$ bits;
2. encode with the RS outer code into 256 bytes;
3. encode each byte with the inner code into 19 bits, giving $256\times19=4864$ bits.

Decoding reverses this: table-decode each 19-bit block (up to three bit errors), obtaining 256 bytes; then RS-decode up to 53 byte errors.

Performance

The probability that a 19-bit block has four or more errors — the inner-code failure probability — is about

$$1-\sum_{j=0}^{3}\binom{19}{j}(0.1)^j(0.9)^{19-j}\approx0.115 .$$

After inner decoding, each byte is still wrong with probability about 11%. Among 256 bytes the expected number of errors is about 29, well below the correctable 53, and a binomial tail bound puts the probability of exceeding 53 at roughly $10^{-60}$.

The cost is bandwidth: 1200 bits become 4864, about a factor of four. Shannon's capacity $1-H(0.1)\approx0.53$ says an ideal code would need only about a factor of two. Being within a factor of two was good enough in the 1970s, and RS codes stayed in service for decades — in CDs, DVDs, deep-space links, and QR codes.

What this lecture establishes

• An RS codeword is a degree-$\le k-1$ polynomial evaluated at $n\le q$ distinct points.
• It is linear, with a full-column-rank Vandermonde generator matrix.
• A nonzero polynomial has at most $k-1$ roots, so $d=n-k+1$; RS codes meet the Singleton bound and are MDS.
• They correct $\lfloor(n-k)/2\rfloor$ symbol errors.
• The decoding theorem uses the error locator $f=\prod(x-i_j)$ and $q=pf$, giving $q(i)=r_if(i)$ at every point.
• These identities are linear in the coefficients; with one more unknown than equation, normalizing $f_e=1$ yields a unique solution, and $p=q/f$.
• The constraints $n\le q$ and $e<n/2$ make a single layer insufficient at high bit error rates; concatenating the $(19,8,7)$ inner code brings the failure probability at 10% bit errors to about $10^{-60}$.

Comprehension check

1. How does "a polynomial of degree at most $k-1$ has at most $k-1$ roots" imply minimum distance $n-k+1$?

Reference answer: Two distinct codewords come from two distinct polynomials $p_1\ne p_2$. Their difference $p_1-p_2$ is nonzero of degree at most $k-1$, so it has at most $k-1$ roots. Hence among the $n$ evaluation points it vanishes at most $k-1$ times, meaning the two codewords agree in at most $k-1$ positions and differ in at least

$$n-(k-1)=n-k+1 .$$

So every pair of codewords has distance at least $n-k+1$. Taking $p_2=0$ (the zero polynomial is a codeword) attains the bound, so the minimum distance is exactly $n-k+1$.

2. How many symbol errors can a $(255,223)$ RS code correct, and why not more?

Reference answer: $d=n-k+1=33$, so

$$\left\lfloor\frac{d-1}{2}\right\rfloor=\left\lfloor\frac{32}{2}\right\rfloor=16$$

symbol errors.

Correcting 17 would require $d\ge2\cdot17+1=35$, but the Singleton bound gives $d\le n-k+1=33$, a contradiction. The Singleton bound holds for every code, and RS codes attain it, so no code with these $n$ and $k$ can do better.

3. Why is the generator matrix Vandermonde, and why is it full rank?

Reference answer: Row $j$ lists the values of $x^j$ at the evaluation points, $(1^j,2^j,\dots,(n-1)^j)$ in this lecture's ordering. Stacking the rows, each column holds increasing powers of one point — the Vandermonde structure.

It has full column rank because the Vandermonde determinant of any $k$ distinct points is

$$\prod_{i<j}(\alpha_j-\alpha_i)\ne0 .$$

Hence values at any $k$ distinct points are linearly independent and the rank is $k$. This is precisely why the evaluation points must be distinct.

4. In the decoding theorem, how are $f$ and $q$ defined, and why does $q(i)=r_if(i)$ hold at every point?

Reference answer: $f(x)=\prod_{j=1}^{l}(x-i_j)$ where $i_1,\dots,i_l$ are the error positions, and $q(x)=p(x)f(x)$.

Two cases:

• at an error position, $f(i)=0$, so both sides are zero;
• elsewhere $r_i=p(i)$, so $q(i)=p(i)f(i)=r_if(i)$.

The identity matters because the right side uses the known received values $r_i$ while the left side involves the unknown polynomials, so the equations over all $i$ form a linear system in their coefficients.

5. The system has $k+2e+1$ unknowns but only $n=k+2e$ equations. Why is the solution still unique?

Reference answer: A homogeneous system with more unknowns than equations always has a nonzero solution, and here the solution space has dimension at least one. The equations have full rank, so the space is exactly one-dimensional: every solution is a scalar multiple of one nonzero solution.

Multiplying both $f$ and $q$ by a constant leaves $q(i)=r_if(i)$ unchanged, so a scale must be fixed externally. When exactly $e$ errors occurred, $\deg f=e$ and $f_e\ne0$; normalizing $f_e=1$ fixes the multiple and makes the solution unique.

If fewer than $e$ errors occurred, $f_e=0$ and this normalization fails, so one tries each $l$ or uses Berlekamp–Massey.

6. Why does a single RS code fail at a 10% bit error rate? How does concatenation fix it?

Reference answer: Over $\mathbb F_{2^8}$ a symbol is a byte, and at a 10% bit error rate a byte is wrong with probability

$$1-0.9^8\approx0.57 .$$

An RS code corrects a fraction $(n-k)/(2n)<1/2$ of symbols; for the example, $53/256\approx0.207$. Since $0.57$ far exceeds $0.207$, the outer code is overwhelmed.

Concatenation first encodes each byte with the $(19,8,7)$ inner code, correcting three bit errors and reducing the failure probability of a 19-bit block to about 11%. That 11% byte error rate is below the RS threshold of $20.7\%$, so the outer code can finish the job.

7. RS codes attain the Singleton bound (MDS). Why do they still fall short of Shannon capacity?

Reference answer: The two bounds optimize different things. The Singleton bound $d\le n-k+1$ fixes $n$ and $k$ and asks for the largest possible distance at that length and dimension; RS codes attain it and are optimal in that sense.

Shannon capacity asks a different question: as $n\to\infty$ with a growing alphabet, what is the largest rate at which reliable communication is possible? Attaining capacity needs $q$ growing with $n$ and very long codes, while RS codes require $n\le q$; in the classical construction $q$ and $n$ are comparable and decoding cost grows with $n$, so capacity is out of reach. Concatenation narrows the gap to a constant factor; turbo, LDPC, and polar codes close it.

8. Why can the inner code be decoded by table lookup? What did that mean for 1977 hardware?

Reference answer: The $(19,8,7)$ inner code has only $2^8=256$ codewords, but a received block can be any of $2^{19}\approx524288$ nineteen-bit strings. One can precompute a table mapping each possible received string to its nearest codeword; decoding is then a single lookup, $O(1)$ time.

The cost is memory. A modern computer holds half a million entries trivially, but the 1977 Voyager hardware had very little memory and could not store the whole table. Real systems either used a smaller inner code (fewer entries), or a Hamming inner code (trivial decoding, slightly worse performance), or some other structured scheme. The lecture does not state Voyager's exact choice, only that it must have traded memory against performance.

Relation to neighbouring lectures

Hamming codes from the previous lecture use a parity-check matrix for single-bit correction with distance fixed at 3; this lecture uses polynomial evaluation to raise the distance to $n-k+1$, at the cost of working over finite fields and decoding via a linear system.

Together they mark the two main lines of linear codes: checking (Hamming, syndrome decoding) and algebraic construction (RS, error-locator polynomials). BCH and algebraic-geometry codes follow the second line, while concatenation and iterative decoding lead to turbo and LDPC codes.

This closes the coding-theory unit. The course then turns to cryptography and secret sharing, where finite fields, polynomials, and linear algebra reappear — but the adversary is no longer noise, it is an opponent.