从 Shannon 的随机码到可实现的码

Shannon 证明了：只要速率低于容量，就存在把错误率压到零的码。但证明里的码本是随机抽出来的，有 $2^{Rn}$ 条码字，逐条存储是指数级；解码要计算收到的向量与每条码字的距离，同样是指数级。更糟的是，最近码字解码对一般线性码是 NP 难的，所以不存在大幅优于遍历的通用算法。

于是任务变成：找结构特殊、解码高效的码。

历史上有两条线索：

• 1948 年 Shannon 证明存在性；
• 1950 年 Hamming 给出第一个可实现的纠错码。

本讲先讲最简单的 Hamming(7,4) 码——4 位消息编成 7 位、纠正 1 位错误——再抽象成线性码与 Hamming 码族，最后给出综合解码。

注意朴素的「4 位一组」方案有局限：若要传一百万位、错误率百分之一，总会有某个 4 位块里出现 2 个错误，超出纠错能力。我们需要能一次纠正更多错误的码，那是下一讲 Reed–Solomon 码的内容。

时间轴

维恩图构造：(7,4) 码

取 4 个消息位 $a,b,c,d$，加 3 个校验位 $e,f,g$。画三个两两相交的圆，让每个消息位落在特定区域：

• 圆 1：$b,c,d,f$；
• 圆 2：$a,b,d,e$；
• 圆 3：$a,c,d,g$。

校验位的取值规则：每个圆内 1 的个数为偶数（异或和为 0）。于是

$$e=a\oplus b\oplus d,\qquad f=b\oplus c\oplus d,\qquad g=a\oplus c\oplus d .$$

码字写成 $(a,b,c,d,e,f,g)$。

编码例子

消息 $(1,0,1,1)$：

• $e=1\oplus0\oplus1=0$；
• $f=0\oplus1\oplus1=0$；
• $g=1\oplus1\oplus1=1$。

得到码字 $(1,0,1,1,0,0,1)$。三个圆的校验都是偶数，成立。

纠错例子

把第 2 位（$b$）翻转，收到 $(1,1,1,1,0,0,1)$。重新算三个圆的奇偶性：

• 圆 1（$b,c,d,f$）：$1+1+1+0=1$，奇数，出错；
• 圆 2（$a,b,d,e$）：$1+1+1+0=1$，奇数，出错；
• 圆 3（$a,c,d,g$）：$1+1+1+1=0$，偶数，正常。

出错的位必须同时属于圆 1 和圆 2、且不属于圆 3。两个错误圆的交集是 $\{b,d\}$，去掉圆 3 中含的 $d$，只剩 $b$。所以翻转的是第 2 位，改回来即可。

这就是「校验和定位」的几何版本：每个错误位在各圆中的归属模式不同，三个圆的结果（三个比特）唯一地指出错误位置。

线性码

把上面的构造抽象成代数。设 $F$ 是一个域（本讲主要是 $\mathbb F_2=\{0,1\}$）。线性码 $C\subseteq F^n$ 是满足以下条件的向量集合：

• 若 $c_1,c_2\in C$，则 $c_1+c_2\in C$；
• 若 $c_1\in C$、$\alpha\in F$，则 $\alpha c_1\in C$。

也就是说，任何线性组合仍是码字。取 $\alpha=0$ 立刻得到：每个线性码都包含全零向量。

维恩图构造满足线性性：若两个向量各自使三个圆的和为 0，则它们的和也使每个圆的和为 $0+0=0$。

生成矩阵

由线性代数，任何线性码都有一组基。把这组基按行排成矩阵 $G$（$k\times n$），码就是 $G$ 所有行的线性组合：

$$C=\{mG:\ m\in F^k\}.$$

$G$ 称为生成矩阵，$m$ 是消息（长度 $k$ 的行向量），$c=mG$ 是码字（长度 $n$）。编码因此是一次矩阵乘法：消息中为 1 的那些位置对应的行相加。

(7,4) 码的生成矩阵

按上面的异或公式，四个单位消息对应的码字是

$$G= \begin{bmatrix} 1&0&0&0&1&0&1\\ 0&1&0&0&1&1&0\\ 0&0&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{bmatrix}.$$

每一行的后三位正是该消息位出现在哪些校验位里。验证第一行：$a$ 出现在 $e$ 和 $g$ 中，所以后三位是 $1,0,1$。

消息 $(1,1,1,0)$ 的码字是前三行之和：

$$(1,1,1,0,0,0,0).$$

校验矩阵

校验矩阵 $H$ 满足

$$GH^{T}=0 .$$

它的每一行给出一个校验方程：码字与每一行的内积为 0，等价于「对应的圆内 1 的个数为偶数」。

把 $G$ 写成 $[I_k\mid P]$（前 $k$ 列是单位矩阵，$P$ 是 $k\times(n-k)$ 的校验部分），则

$$H=\big[-P^{T}\mid I_{n-k}\big]$$

满足 $GH^T=0$。验算如下：$G H^{T}=[I\mid P]\begin{bmatrix}-P\\ I\end{bmatrix}=-P+P=0$。在 $\mathbb F_2$ 中 $-P=P$，符号可以省略；在其他域上则不能。

对本讲的 (7,4) 码：

$$H= \begin{bmatrix} 1&1&0&1&1&0&0\\ 0&1&1&1&0&1&0\\ 1&0&1&1&0&0&1 \end{bmatrix}.$$

第一列 $(1,0,1)$ 对应位置 1（$a$ 参与 $e$ 与 $g$），第二列 $(1,1,0)$ 对应位置 2（$b$ 参与 $e$ 与 $f$），依此类推。

注意 $H$ 的列恰好是 $\mathbb F_2^3$ 的全部非零向量，顺序不同而已。这个事实是后面「完美码」的关键。

重量与距离

对 $v\in F^n$：

• Hamming 重量 $w(v)$：非零坐标的个数；
• Hamming 距离 $d_H(v,w)$：两个向量不同坐标的个数。

距离就是差的重量：$d_H(v,w)=w(v-w)$。若两个坐标相同，差为 0；不同则差非零。

Hamming 距离满足三角不等式，因此是一个度量。

码的最小距离定义为不同码字间距离的最小值：

$$d=\min_{c_1\ne c_2}d_H(c_1,c_2).$$

对线性码，它可以简化成最小非零重量：

$$d=\min_{c\ne0}w(c).$$

理由：$d_H(c_1,c_2)=w(c_1-c_2)$，而线性码对减法封闭，$c_1-c_2$ 跑遍所有非零码字。

纠错能力由最小距离决定

定理。 最小距离为 $d$ 的码可以纠正

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

个错误。

证明。 反设不能纠正 $t$ 个错误。那么存在一个收到的向量 $\tilde c$，以及两个不同码字 $c_1\ne c_2$，使得

$$d_H(\tilde c,c_1)\le t, \qquad d_H(\tilde c,c_2)\le t .$$

由三角不等式，

$$d_H(c_1,c_2)\le d_H(c_1,\tilde c)+d_H(\tilde c,c_2)\le 2t\le d-1<d,$$

这违反「$d$ 是不同码字间的最小距离」。$\square$

直观上，以每个码字为中心、半径 $t$ 的「球」互不相交。收到的向量若在某个球内，就能唯一地判定原本的码字；若落在两个球的交界附近，就无法判定。

$t=\lfloor(d-1)/2\rfloor$ 是能保证的唯一纠错个数：$d=3$ 时 $t=1$，$d=7$ 时 $t=3$。

一般的 Hamming 码族

(7,4) 码不是孤例。固定整数 $s\ge2$，取

$$n=2^s-1, \qquad k=2^s-1-s .$$

构造 $G=[I_k\mid P]$：$P$ 的每一列取遍所有长度为 $s$、至少含两个 1 的非零向量。

为什么恰好有 $k$ 列？长度为 $s$ 的二进制串共 $2^s$ 个，去掉全零（1 个）和恰含一个 1 的（$s$ 个），剩下 $2^s-1-s$ 个。而 $n=k+s$ 正是「消息位 + 校验位」的总数。

• $s=3$：$k=4$，$n=7$，就是 (7,4) 码；
• $s=4$：$k=11$，$n=15$，即 (15,11) 码；
• $s=5$：$k=26$，$n=31$。

最小距离为 3。 证明分三种情况：

1. 单行：单位矩阵部分贡献 1 个 1，$P$ 的对应列至少含两个 1，所以重量至少 3。
2. 两行之和：单位矩阵部分恰有 2 个 1；$P$ 部分是两列不同的向量之和，因为两列不同，异或结果非零，至少 1 个 1。总重量至少 3。
3. 三行及以上之和：单位矩阵部分已经有至少 3 个 1，重量至少 3。

所以 $d=3$，纠正 $\lfloor(3-1)/2\rfloor=1$ 个错误。

这也说明了为什么 $P$ 的列必须互不相同：若两列相同，它们之和为 0，两行之和的重量会降到 2，最小距离变成 2，只能检错、不能纠错。

综合解码

有了 $G$ 与 $H$，编码与解码都很简洁。

编码

$$c=mG .$$

综合

发送 $c$，信道引入错误向量 $e$，收到

$$\tilde c=c+e .$$

计算综合（syndrome）

$$\sigma=\tilde c\,H^{T}=(mG+e)H^{T}=mGH^{T}+eH^{T}=eH^{T}.$$

第一步用了 $GH^T=0$，所以 综合只依赖错误 $e$，与消息 $m$ 无关。这就是「综合」这个名字的来源：它像症状一样，只反映出了什么错。

从综合到错误

一般线性码没有高效的通用算法从 $\sigma$ 反推 $e$——这正是前面说的 NP 难问题的另一面。但对 Hamming 码非常简单。

Hamming 码只纠 1 位错误，所以只需考虑重量为 1 的 $e$。若 $e$ 在第 $j$ 位为 1，则

$$eH^{T}=H^{T}\text{ 的第 }j\text{ 列}.$$

也就是说：综合直接等于 $H$ 的第 $j$ 列。而 $H$ 的列是全部非零 $s$ 位向量，互不相同，所以查表即可定位错误位置，再把那一位翻转。

解码例子

用 (7,4) 码发送 $m=(1,1,1,0)$，编码得 $c=(1,1,1,0,0,0,0)$。

假设第 6 位翻转，收到 $\tilde c=(1,1,1,0,0,1,0)$。计算综合：

$$\sigma=\tilde c H^{T}=(0,1,0).$$

在 $H$ 中找 $(0,1,0)$：它是第 6 列。所以错误在第 6 位，翻转后恢复 $(1,1,1,0,0,0,0)$，前 4 位就是消息 $(1,1,1,0)$。

整个过程只需一次矩阵乘法与一次查表，耗时 $O(n\cdot(n-k))$，与码长成多项式关系——与随机码本的指数级遍历形成鲜明对比。

完美码

定义。 一个纠正 $t$ 位错误的码称为完美码，若每个综合都对应某个重量不超过 $t$ 的错误向量。

等价的说法：以码字为中心、半径 $t$ 的 Hamming 球恰好铺满整个空间，既不重叠也不留空隙。

对二进制 Hamming 码：

• 综合有 $2^s$ 种（长度 $s$ 的比特串）；
• 零综合对应无错误，共 1 种；
• 其余 $2^s-1=n$ 种各对应一个位置的单比特错误。

数目恰好吻合，所以 Hamming 码是完美码。

一般地，一个 $t$ 纠错的 $q$ 元完美码必须满足球填充条件

$$\sum_{L=0}^{t}\binom{n}{L}(q-1)^L=q^{\,n-k}.$$

左边是半径 $t$ 的球的大小（按重量 $L$ 分层计数），右边是空间除以码字数的商。等式成立意味着球恰好铺满。

除了 Hamming 码，二进制情形下另一个解是 $n=23$、$t=3$：

$$\binom{23}{0}+\binom{23}{1}+\binom{23}{2}+\binom{23}{3} =1+23+253+1771=2048=2^{11},$$

对应 $(23,12,7)$ 的 Golay 码，它与有限单群等深刻结构有关。三元域上还有 $(11,6,5)$ 的三元 Golay 码。完美码非常稀少，这也说明不能指望靠「完美」来解决所有纠错需求。

本节结论

• 随机码本不可实现，最近码字解码一般是指数级甚至 NP 难，需要结构化的线性码。
• 线性码对加法与数乘封闭，含全零向量，可用生成矩阵 $G$ 描述，编码为 $c=mG$。
• 校验矩阵 $H$ 满足 $GH^T=0$；综合 $\sigma=\tilde cH^T=eH^T$ 只依赖错误。
• 最小距离 $d$ 决定纠错能力：可纠 $\lfloor(d-1)/2\rfloor$ 个错误；线性码的 $d$ 等于最小非零重量。
• Hamming 码：$n=2^s-1$、$k=2^s-1-s$、$d=3$，纠 1 位错误；其校验矩阵的列取遍所有非零 $s$ 位向量。
• Hamming 码解码就是「综合等于哪一列」，代价多项式级。
• Hamming 码是完美码：$2^s$ 个综合恰好对应「无错误 + $n$ 个单比特错误」；二进制完美码只有 Hamming 码与 Golay 码。

理解检验

1. 用维恩图构造说明：为什么 (7,4) 码能定位 1 位错误，而不能纠正 2 位错误？

参考答案：三个校验圆给出 3 个校验比特，每个错误位置对应一种「落在哪些圆里」的归属模式。7 个位置（4 消息 + 3 校验）的归属各不相同，所以 3 个校验比特足以唯一确定单个错误的位置——这相当于校验矩阵的 7 列两两不同。

不能纠正 2 位错误的原因是：两个不同的双位错误可能产生相同的校验结果。例如翻转位置 $x$ 与 $y$，其校验结果是两列之和；若存在另一对 $x',y'$ 使两列之和相同，就无法区分。更根本地，该码最小距离为 3，按定理只能纠 $\lfloor(3-1)/2\rfloor=1$ 位。

2. 线性码为什么一定包含全零向量？由此说明最小距离为什么等于最小非零重量。

参考答案：线性码对数乘封闭。取任意 $c\in C$ 与标量 $0$，则 $0\cdot c=\mathbf 0\in C$。

于是对任意两个不同码字 $c_1\ne c_2$，差 $c_1-c_2$ 也在 $C$ 中且非零（线性码对加法逆元封闭）。而 $d_H(c_1,c_2)=w(c_1-c_2)$，所以「不同码字间的距离」与「非零码字的重量」取的是同一组数值，两者的最小值相等。

3. 证明：最小距离为 $d$ 的码可以纠正 $\lfloor(d-1)/2\rfloor$ 个错误。

参考答案：设 $t=\lfloor(d-1)/2\rfloor$，则 $2t\le d-1$。反设存在收到的向量 $\tilde c$ 与两个不同码字 $c_1,c_2$，使 $d_H(\tilde c,c_1)\le t$ 且 $d_H(\tilde c,c_2)\le t$。

由三角不等式，

$$d_H(c_1,c_2)\le d_H(c_1,\tilde c)+d_H(\tilde c,c_2)\le2t\le d-1<d,$$

与「$d$ 是不同码字间的最小距离」矛盾。所以 $\tilde c$ 至多落在一个码字的半径-$t$ 球内，解码唯一。

4. 对 $(7,4)$ 码，写出生成矩阵的第四行，并说明它的每一位从何而来。

参考答案：第四行对应消息位 $d$，为 $(0,0,0,1,1,1,1)$。

前四位是单位矩阵部分，只有第 4 位是 1。后三位是 $d$ 参与的校验：从维恩图看，$d$ 位于三个圆的公共区域，出现在 $e=a\oplus b\oplus d$、$f=b\oplus c\oplus d$、$g=a\oplus c\oplus d$ 三个式子中，所以后三位全是 1。

这也解释了为什么 $d$ 对应的行重量是 4：它是唯一落在中心区域的比特。

5. 为什么 Hamming 码族要求校验矩阵的列两两不同？如果两列相同会发生什么？

参考答案：两列相同意味着存在两个位置，它们参与完全相同的校验组合。单比特错误发生在这两个位置之一时，综合相同，无法判断是哪一个，纠错失败。

从距离看：若 $H$ 的第 $i$、$j$ 列相同，则单位消息 $e_i+e_j$ 的码字满足 $H(e_i+e_j)^T=0$，说明它落在码中，重量为 2（因为生成矩阵的对应两行之和的重量可能降到 2）。于是最小距离至多是 2，只能检测 1 位错误，不能纠正。

Hamming 码的构造正是取遍所有非零列，既保证两两不同，又用满了 $s$ 位向量，从而成为完美码。

6. 综合 $\sigma=\tilde cH^T$ 为什么与发送的消息无关？这一点对解码有什么意义？

参考答案：

$$\sigma=\tilde cH^{T}=(c+e)H^{T}=cH^{T}+eH^{T}.$$

而 $c=mG$，故 $cH^T=mGH^T=0$。所以 $\sigma=eH^T$，只依赖错误向量。

意义在于：解码器不需要先猜测消息，也不需要搜索所有码字。它只根据「错误长什么样」来定位并纠正错误，纠正后再除以 $G$（或直接取消息位）得到原始消息。这把一个看似需要遍历码本的问题，化成了一个查表问题。

7. 对 $(7,4)$ 码，若收到 $(1,1,1,0,0,1,0)$，求综合并完成解码。

参考答案：校验矩阵为

$$H= \begin{bmatrix} 1&1&0&1&1&0&0\\ 0&1&1&1&0&1&0\\ 1&0&1&1&0&0&1 \end{bmatrix}.$$

计算 $\tilde cH^T$：第一行内积 $=1+1+0+0+0+0+0=0$；第二行 $=0+1+1+0+0+1+0=1$；第三行 $=1+0+1+0+0+0+0=0$。综合为 $(0,1,0)$。

在 $H$ 中查找该列：第 6 列为 $(0,1,0)$。所以错误在第 6 位。翻转后得到 $(1,1,1,0,0,0,0)$，前 4 位即消息 $(1,1,1,0)$。

8. 什么是完美码？用球填充条件说明 Hamming 码为什么完美，并解释为什么完美码很少。

参考答案：完美码指每个综合都对应某个重量不超过 $t$ 的错误，等价于以码字为中心、半径 $t$ 的球恰好铺满整个空间，不重叠也不留空。

球填充条件是

$$\sum_{L=0}^{t}\binom{n}{L}(q-1)^L=q^{n-k},$$

左边是球的体积，右边是空间大小除以码字数。对二进制 Hamming 码，$t=1$，左边为 $1+n=1+(2^s-1)=2^s$，右边为 $q^{n-k}=2^s$，恰好相等。

完美码稀少，是因为这是一个非常紧的丢番图方程：$n$、$t$、$q$ 都要恰好配合。二进制情形只有 Hamming 码与 Golay 码 $(23,12,7)$，三元情形多一个 $(11,6,5)$ 的 Golay 码。大多数参数下球必然有重叠或空隙。

与前后课的关系

上一讲用随机码本证明了容量可达，但码本指数大、解码 NP 难；本讲给出第一类可实现的结构化码：线性码用矩阵描述码本，Hamming 码用综合实现多项式时间的单比特纠错。

Hamming 码的局限是最小距离只有 3，只能纠 1 位错误；码长越长，单块里出现多个错误的概率越高。下一讲 Reed–Solomon 码用有限域上的多项式求值构造码字，把最小距离提高到 $n-k+1$，并用错误定位多项式实现多错误纠正。

更后面，课程会转向密码学与秘密共享，那里线性代数的语言会再次出现。

From Shannon's random codes to implementable ones

Shannon proved that below capacity there exists a code driving the error to zero. But his codebook is drawn at random: $2^{Rn}$ codewords, exponential storage, and decoding compares the received vector against every codeword, also exponential. Worse, nearest-codeword decoding for a general linear code is NP-hard, so no generic algorithm is substantially better than scanning.

The task therefore becomes: find structured codes with efficient decoding.

Two historical markers:

• 1948: Shannon proves existence;
• 1950: Hamming gives the first implementable error-correcting code.

This lecture starts with the simplest, Hamming(7,4) — four message bits encoded into seven, correcting one bit — then abstracts to linear codes and the Hamming family, and finishes with syndrome decoding.

The naive "blocks of four" scheme has a limit: to send a million bits at a one-percent error rate, some block of four will contain two errors and fail. Codes correcting many errors at once are needed; that is the Reed–Solomon lecture.

Timeline

The (7,4) code from three circles

Take four message bits $a,b,c,d$ and add three parity bits $e,f,g$. Draw three mutually overlapping circles and place the message bits in specific regions:

• circle 1: $b,c,d,f$;
• circle 2: $a,b,d,e$;
• circle 3: $a,c,d,g$.

The rule is: each circle contains an even number of 1s (its XOR is zero). Hence

$$e=a\oplus b\oplus d,\qquad f=b\oplus c\oplus d,\qquad g=a\oplus c\oplus d .$$

A codeword is $(a,b,c,d,e,f,g)$.

Encoding example

For the message $(1,0,1,1)$:

• $e=1\oplus0\oplus1=0$;
• $f=0\oplus1\oplus1=0$;
• $g=1\oplus1\oplus1=1$.

The codeword is $(1,0,1,1,0,0,1)$, and all three parity checks are even.

Correcting an error

Flip the second bit $b$: receive $(1,1,1,1,0,0,1)$. Recompute the parity of each circle:

• circle 1 ($b,c,d,f$): $1+1+1+0=1$, odd, fails;
• circle 2 ($a,b,d,e$): $1+1+1+0=1$, odd, fails;
• circle 3 ($a,c,d,g$): $1+1+1+1=0$, even, passes.

The error must lie in both failing circles and outside the passing one. Circles 1 and 2 intersect in $\{b,d\}$; removing $d$ (which lies in circle 3) leaves $b$. So the second bit is wrong and is flipped back.

This is parity checking in geometric form: every position has a distinct pattern of circle membership, so the three parity results identify the error position uniquely.

Linear codes

Abstract the construction. Let $F$ be a field (here mostly $\mathbb F_2=\{0,1\}$). A linear code $C\subseteq F^n$ satisfies:

• if $c_1,c_2\in C$, then $c_1+c_2\in C$;
• if $c_1\in C$ and $\alpha\in F$, then $\alpha c_1\in C$.

Every linear combination of codewords is again a codeword. Taking $\alpha=0$ shows every linear code contains the all-zero vector.

The Venn construction is linear: if two vectors make all three circle sums zero, their sum does too, since $0+0=0$.

Generator matrix

By linear algebra, any linear code has a basis. Put the basis vectors as rows of a $k\times n$ matrix $G$; the code is the set of all linear combinations of rows:

$$C=\{mG:\ m\in F^k\}.$$

$G$ is a generator matrix, $m$ is the message (a row vector of length $k$), and $c=mG$ is the codeword (length $n$). Encoding is one matrix multiplication: add the rows where the message has a 1.

The (7,4) generator matrix

From the XOR formulas, the codewords of the four unit messages are

$$G= \begin{bmatrix} 1&0&0&0&1&0&1\\ 0&1&0&0&1&1&0\\ 0&0&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{bmatrix}.$$

Each row's last three entries record which parity bits that message bit enters. Row one: $a$ appears in $e$ and $g$, so the tail is $1,0,1$.

The message $(1,1,1,0)$ encodes to the sum of the first three rows:

$$(1,1,1,0,0,0,0).$$

Parity-check matrix

A parity-check matrix $H$ satisfies

$$GH^{T}=0 .$$

Each row of $H$ is one parity equation: the codeword's inner product with that row is zero, i.e. the corresponding circle has an even number of 1s.

Writing $G=[I_k\mid P]$ (identity block then parity block), the matrix

$$H=\big[-P^{T}\mid I_{n-k}\big]$$

works, since $GH^{T}=[I\mid P]\begin{bmatrix}-P\\ I\end{bmatrix}=-P+P=0$. Over $\mathbb F_2$, $-P=P$, so signs can be dropped; over other fields they cannot.

For the (7,4) code,

$$H= \begin{bmatrix} 1&1&0&1&1&0&0\\ 0&1&1&1&0&1&0\\ 1&0&1&1&0&0&1 \end{bmatrix}.$$

Column one is $(1,0,1)$ for position 1 ($a$ enters $e$ and $g$); column two is $(1,1,0)$ for position 2 ($b$ enters $e$ and $f$), and so on.

The columns of $H$ are exactly the seven nonzero vectors of $\mathbb F_2^3$, merely reordered. That fact is what makes Hamming codes perfect.

Weight and distance

For $v\in F^n$:

• the Hamming weight $w(v)$ is the number of nonzero coordinates;
• the Hamming distance $d_H(v,w)$ is the number of coordinates where they differ.

Distance is the weight of the difference: $d_H(v,w)=w(v-w)$, since equal coordinates contribute 0 and unequal ones contribute a nonzero difference.

Hamming distance satisfies the triangle inequality, hence is a metric.

The minimum distance of a code is

$$d=\min_{c_1\ne c_2}d_H(c_1,c_2).$$

For a linear code it reduces to the minimum nonzero weight:

$$d=\min_{c\ne0}w(c).$$

Indeed $d_H(c_1,c_2)=w(c_1-c_2)$, and since the code is closed under subtraction, $c_1-c_2$ ranges over all nonzero codewords.

Minimum distance determines correction

Theorem. A code of minimum distance $d$ corrects

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

errors.

Proof. Suppose it cannot. Then some received vector $\tilde c$ lies within distance $t$ of two distinct codewords $c_1\ne c_2$:

$$d_H(\tilde c,c_1)\le t, \qquad d_H(\tilde c,c_2)\le t .$$

The triangle inequality gives

$$d_H(c_1,c_2)\le d_H(c_1,\tilde c)+d_H(\tilde c,c_2)\le 2t\le d-1<d,$$

contradicting the definition of $d$. $\square$

Geometrically, the balls of radius $t$ around distinct codewords are disjoint. A received vector inside one ball has a unique owner; near an overlap it would not. The value $t=\lfloor(d-1)/2\rfloor$ is exactly what can be guaranteed: $d=3$ gives $t=1$, $d=7$ gives $t=3$.

The general Hamming family

(7,4) is one member. Fix $s\ge2$ and set

$$n=2^s-1, \qquad k=2^s-1-s .$$

Build $G=[I_k\mid P]$ where the columns of $P$ run through all length-$s$ binary vectors with at least two 1s.

Why exactly $k$ columns? There are $2^s$ binary strings of length $s$; remove the all-zero string (one) and the unit vectors (s), leaving $2^s-1-s$. And $n=k+s$ is the number of message plus parity positions.

• $s=3$: $k=4$, $n=7$ — the (7,4) code;
• $s=4$: $k=11$, $n=15$ — the (15,11) code;
• $s=5$: $k=26$, $n=31$.

The minimum distance is 3. Three cases:

1. A single row: the identity block contributes one 1, and the corresponding column of $P$ has at least two 1s, so the weight is at least 3.
2. A sum of two rows: the identity block has exactly two 1s; the parity part is the XOR of two distinct columns, which is nonzero, so at least one more 1. Weight at least 3.
3. A sum of three or more rows: the identity block alone has at least three 1s.

So $d=3$ and $\lfloor(3-1)/2\rfloor=1$ error is corrected.

This also explains why the columns of $P$ must be distinct: two equal columns would XOR to zero, dropping the weight of that two-row sum to 2 and the minimum distance to 2, which detects but cannot correct.

Syndrome decoding

With $G$ and $H$, encoding and decoding are clean.

Encoding

$$c=mG .$$

Syndrome

Send $c$, let the channel add an error vector $e$, and receive

$$\tilde c=c+e .$$

The syndrome is

$$\sigma=\tilde c\,H^{T}=(mG+e)H^{T}=mGH^{T}+eH^{T}=eH^{T}.$$

The first term vanishes because $GH^T=0$, so the syndrome depends only on $e$, not on the message. That is why it is called a syndrome: like a symptom, it reports only what went wrong.

From syndrome to error

For a general linear code there is no efficient universal way to invert $\sigma\mapsto e$ — the other face of the NP-hardness mentioned earlier. For Hamming codes it is trivial.

A Hamming code corrects one bit, so only weight-one errors matter. If $e$ has its 1 in position $j$, then

$$eH^{T}=H^{T}\text{'s }j\text{-th column}.$$

So the syndrome is literally column $j$ of $H$. Since the columns are all nonzero vectors and therefore distinct, a lookup locates the error, which is then flipped.

Decoding example

Send $m=(1,1,1,0)$, encoded as $c=(1,1,1,0,0,0,0)$.

Suppose position 6 flips, so $\tilde c=(1,1,1,0,0,1,0)$. Compute

$$\sigma=\tilde cH^{T}=(0,1,0).$$

In $H$, the vector $(0,1,0)$ is column 6. The error is in position 6; flipping it recovers $(1,1,1,0,0,0,0)$, whose first four bits are the message $(1,1,1,0)$.

The whole procedure is one matrix multiplication and one lookup, costing $O(n(n-k))$ — polynomial in the block length, in sharp contrast with scanning an exponential codebook.

Perfect codes

Definition. A $t$-error-correcting code is perfect if every syndrome corresponds to some error of weight at most $t$.

Equivalently, the Hamming balls of radius $t$ around the codewords tile the whole space: no overlaps, no gaps.

For a binary Hamming code:

• there are $2^s$ syndromes (binary strings of length $s$);
• the zero syndrome corresponds to no error;
• the remaining $2^s-1=n$ syndromes correspond to single-bit errors at the $n$ positions.

The counts match exactly, so Hamming codes are perfect.

In general, a $t$-correcting $q$-ary perfect code must satisfy the sphere-packing condition

$$\sum_{L=0}^{t}\binom{n}{L}(q-1)^L=q^{\,n-k}.$$

The left side is the volume of a radius-$t$ ball (counted layer by layer), the right side the space size divided by the number of codewords. Equality means the balls tile perfectly.

Beyond Hamming codes, the binary solution with $n=23$, $t=3$ is

$$\binom{23}{0}+\binom{23}{1}+\binom{23}{2}+\binom{23}{3} =1+23+253+1771=2048=2^{11},$$

the $(23,12,7)$ Golay code, connected to finite simple groups and other deep structures. Over $\mathbb F_3$ there is the $(11,6,5)$ ternary Golay code. Perfect codes are extremely rare, so one cannot rely on perfection for all correction needs.

What this lecture establishes

• Random codebooks are unimplementable and nearest-codeword decoding is generally exponential or NP-hard; structured linear codes are needed.
• A linear code is closed under addition and scalar multiplication, contains zero, and is described by a generator matrix $G$ with $c=mG$.
• A parity-check matrix satisfies $GH^T=0$, and the syndrome $\sigma=\tilde cH^T=eH^T$ depends only on the error.
• Minimum distance $d$ gives correction of $\lfloor(d-1)/2\rfloor$ errors; for linear codes $d$ is the minimum nonzero weight.
• Hamming codes have $n=2^s-1$, $k=2^s-1-s$, $d=3$, and correct one error; their parity-check columns are all nonzero $s$-bit vectors.
• Hamming decoding is "which column equals the syndrome", costing polynomial time.
• Hamming codes are perfect: $2^s$ syndromes match "no error plus $n$ single-bit errors"; the only binary perfect codes are Hamming and Golay.

Comprehension check

1. Using the Venn construction, why can the (7,4) code locate one error but not correct two?

Reference answer: The three parity circles produce three check bits, and each position has a distinct pattern of circle membership. The seven positions (four message, three parity) have seven distinct patterns, so three check bits identify a single flipped position — equivalently, the seven columns of the parity-check matrix are distinct.

Two errors cannot be corrected because two different pairs may yield the same check result: flipping positions $x,y$ gives the XOR of two columns, and another pair $x',y'$ could give the same XOR, making them indistinguishable. More fundamentally, the minimum distance is 3, so the theorem guarantees only $\lfloor(3-1)/2\rfloor=1$.

2. Why must a linear code contain the all-zero vector? Use this to show that minimum distance equals minimum nonzero weight.

Reference answer: A linear code is closed under scalar multiplication. For any $c\in C$ and scalar $0$, $0\cdot c=\mathbf 0\in C$.

For distinct codewords $c_1\ne c_2$, the difference $c_1-c_2$ is a nonzero codeword (closure under additive inverses). Since $d_H(c_1,c_2)=w(c_1-c_2)$, the set of pairwise distances equals the set of weights of nonzero codewords, so their minima agree.

3. Prove that a code of minimum distance $d$ corrects $\lfloor(d-1)/2\rfloor$ errors.

Reference answer: Let $t=\lfloor(d-1)/2\rfloor$, so $2t\le d-1$. Suppose some received vector $\tilde c$ is within distance $t$ of two distinct codewords $c_1,c_2$. The triangle inequality gives

$$d_H(c_1,c_2)\le d_H(c_1,\tilde c)+d_H(\tilde c,c_2)\le2t\le d-1<d,$$

contradicting the minimality of $d$. Hence $\tilde c$ lies in at most one radius-$t$ ball, and decoding is unique.

4. For the (7,4) code, write the fourth row of the generator matrix and explain each entry.

Reference answer: The row for message bit $d$ is $(0,0,0,1,1,1,1)$.

The first four entries are the identity block, with only the fourth equal to 1. The last three record which parity bits $d$ enters: in the Venn diagram $d$ lies in the central region and appears in $e=a\oplus b\oplus d$, $f=b\oplus c\oplus d$, and $g=a\oplus c\oplus d$, so all three are 1.

This is also why that row has weight 4: $d$ is the only bit in the centre.

5. Why must the columns of a Hamming parity-check matrix be distinct? What goes wrong otherwise?

Reference answer: Equal columns mean two positions participate in exactly the same set of checks. A single-bit error at either position produces the same syndrome, so the decoder cannot tell which one occurred, and correction fails.

In distance terms: if columns $i$ and $j$ of $H$ coincide, then $H(e_i+e_j)^T=0$, so $e_i+e_j$ lies in the code with weight 2 (the code is the kernel of $H$). The minimum distance is then at most 2, which detects one error but cannot correct it.

The Hamming construction takes all nonzero columns: distinct by construction, exactly exhausting the $s$-bit vectors, which is what makes the code perfect.

6. Why is the syndrome $\sigma=\tilde cH^T$ independent of the message? What does that buy the decoder?

Reference answer:

$$\sigma=\tilde cH^{T}=(c+e)H^{T}=cH^{T}+eH^{T},$$

and $c=mG$, so $cH^T=mGH^T=0$. Hence $\sigma=eH^T$, depending only on the error.

The decoder therefore does not need to guess the message or search codewords. It locates and corrects the error from the error's own signature, then reads off the message. A problem that seemed to require scanning the codebook becomes a lookup.

7. Decode the received word $(1,1,1,0,0,1,0)$ for the (7,4) code.

Reference answer: With

$$H= \begin{bmatrix} 1&1&0&1&1&0&0\\ 0&1&1&1&0&1&0\\ 1&0&1&1&0&0&1 \end{bmatrix},$$

compute $\tilde cH^T$: row one gives $1+1+0+0+0+0+0=0$; row two gives $0+1+1+0+0+1+0=1$; row three gives $1+0+1+0+0+0+0=0$. The syndrome is $(0,1,0)$.

Column 6 of $H$ is $(0,1,0)$, so the error is at position 6. Flipping it yields $(1,1,1,0,0,0,0)$, whose first four bits are the message $(1,1,1,0)$.

8. What is a perfect code? Use the sphere-packing condition to explain why Hamming codes are perfect, and why perfect codes are rare.

Reference answer: A perfect code has every syndrome correspond to an error of weight at most $t$, equivalently the radius-$t$ Hamming balls around codewords tile the space with no overlap or gap.

The sphere-packing condition is

$$\sum_{L=0}^{t}\binom{n}{L}(q-1)^L=q^{n-k},$$

the ball volume on the left, the space size divided by the code size on the right. For binary Hamming codes with $t=1$, the left side is $1+n=1+(2^s-1)=2^s$, matching $q^{n-k}=2^s$.

Perfect codes are rare because this is a very tight Diophantine equation in $n$, $t$, and $q$. Over the binary alphabet only Hamming codes and the $(23,12,7)$ Golay code qualify; over $\mathbb F_3$ there is additionally the $(11,6,5)$ ternary Golay code. For most parameters the balls must overlap or leave gaps.

Relation to neighbouring lectures

The previous lecture used random codebooks to prove capacity is achievable, but the codebook is exponential and decoding NP-hard; this lecture gives the first implementable structured family: linear codes describe the codebook with a matrix, and Hamming codes decode single-bit errors in polynomial time via the syndrome.

The limitation is minimum distance 3 — only one error. The next lecture constructs Reed–Solomon codes from polynomial evaluations over finite fields, raising the minimum distance to $n-k+1$ and correcting many errors with an error-locator polynomial.

Later the course turns to cryptography and secret sharing, where linear algebra returns in a different guise.