经典纠错码(1)
经典纠错码的相关表示
经典纠错码的抽象定义
定义 4.1（经典纠错码）：
一个经典纠错码由以下两部分构成：
- 编码映射 $e: [K] \to [N]$，其中 $[K] = \{1, \dots, K\}$ 是信息集合，$[N] = \{1, \dots, N\}$ 是编码后的状态集合。
- 可纠正错误集合 $\mathcal{E}$，其中每个错误 $E: [N] \to [M]$ 是作用于编码状态的映射。
要求存在解码映射 $d: [M] \to [K]$，满足对所有 $x \in [K]$ 和 $E \in \mathcal{E}$：
$$ d(E(e(x))) = x. $$
此时，码字集合 $C = e([K]) \subseteq [N]$ 称为该码的码本。
理解：
- 编码 $e$ 将信息 $x$ 映射为码字 $c = e(x)$。
- 错误 $E$ 将码字 $c$ 篡改为 $E(c)$。
- 解码 $d$ 需从篡改后的状态恢复原始信息 $x$。
- 关键条件：不同码字在错误作用下不能混淆。：存在 $x \neq y$ 和 $E, F \in \mathcal{E}$ 使得 $E(e(x)) = F(e(y))$，则解码失败。
与量子纠错码的对比：
| 经典码 | 量子码 |
|---|---|
| 状态为离散集合中的元素 | 状态为希尔伯特空间中的向量 |
| 任意映射 $e, d, E$ | 映射需为线性算子（量子操作） |
| 混淆条件：$E(e(x)) \neq F(e(y))$ | 正交条件：$\langle \psi_i \| E_a^\dagger E_b \| \psi_j \rangle = 0$（对 $i \neq j$) |
| 环境学习数据无害 | 环境学习数据会破坏量子态（需额外约束 $i = j$ 条件） |
经典码的距离与纠错能力
定义 4.2（码的距离）：
设 $C \subseteq [q^n]$ 是码本（$q$ 为符号集大小，$n$ 为码长）。其距离 $d$ 定义为：
$$
d = \min \big\{ d_H(c_1, c_2) \mid c_1, c_2 \in C,\ c_1 \neq c_2 \big\},
$$
其中 $d_H$ 是汉明距离（两码字不同位置的个数）。
该码记为 $(n, K, d)_q$（$q=2$ 时简写为 $(n, K, d)$）。
几何解释：
- $d$ 是码本中任意两不同码字的最小汉明距离。
- 等价定义：$d = \min \{ w(E) \mid E(c_1) = c_2 \text{ for some } c_1 \neq c_2 \}$（$w(E)$ 为错误 $E$ 的权重）。
命题 4.1（距离的纠错意义）：
距离为 $d$ 的经典码可：
- 纠正任意错误：权重不超过 $t = \lfloor (d-1)/2 \rfloor$ 的错误。
- 纠正擦除错误：至多 $d-1$ 个位置丢失符号（已知错误位置）。
- 检测错误：权重不超过 $d-1$ 的错误。
证明：
- 纠正任意错误（权重 $\leq t$）：
- 思路：接收向量 $r$ 与真实码字 $c$ 的汉明距离 $\leq t$，需证 $r$ 唯一对应 $c$。
- 反证：假设存在另一码字 $c'$ 满足 $d_H(r, c') \leq t$，则：
$$ d_H(c, c') \leq d_H(c, r) + d_H(r, c') \leq 2t \leq d-1 < d, $$
与距离定义矛盾（因 $d_H(c, c') \geq d$）。 - 结论：以 $r$ 为中心、半径 $t$ 的汉明球仅包含唯一码字 $c$，故可解码为 $c$。
- 纠正擦除错误（至多 $d-1$ 个）：
- 思路：擦除指已知错误位置但符号丢失。设擦除位置集 $S$，$|S| = e \leq d-1$。
- 唯一性：对任意两码字 $c_1 \neq c_2$，在非擦除位置集 $S^c$ 上，$c_1$ 与 $c_2$ 必须不同（否则 $d_H(c_1, c_2) \leq e < d$，矛盾）。
- 结论：通过 $S^c$ 上的符号可唯一确定码字。
- 检测错误（权重 $\leq d-1$）：
- 思路：若接收向量 $r$ 非码字，则检测到错误。
- 唯一性：若错误权重 $w \leq d-1$，则 $d_H(r, c) = w \leq d-1$，故 $r$ 不可能是其他码字（因码字间距 $\geq d$）。
- 结论：当 $r \notin C$ 时，可断言发生错误。
示例：重复码
考虑 $(3, 2, 3)$ 重复码：
- 编码：$0 \to 000$，$1 \to 111$。
- 距离：$d_H(000, 111) = 3 = d$。
- 纠错能力：
- 纠正单比特错误（$t = \lfloor (3-1)/2 \rfloor = 1$）：
- $000 \to \{000, 100, 010, 001\}$
- $111 \to \{111, 011, 101, 110\}$
接收向量（如 $100$）唯一对应发送码字 $000$。
- 纠正双擦除错误：若丢失任意两符号，剩余符号仍可解码（如 $0?\,?$ 解码为 $000$）。
- 检测双比特错误：若接收 $110$（非码字），可检测错误发生。
- 纠正单比特错误（$t = \lfloor (3-1)/2 \rfloor = 1$）：
经典线性码
经典线性码的代数结构
定义 4.3（线性码）：
设 $C \subseteq \mathbb{Z}_2^n$ 是 $\mathbb{Z}_2^n$ 的子空间，满足：
$$
\forall x, y \in C, \quad x + y \in C
$$
则 $C$ 称为 线性码。其维度为 $k$，包含 $2^k$ 个码字，记为 $[n, k, d]$ 码（$d$ 为距离）。
生成矩阵 $G$（定义 4.4）：
- $G$ 是 $k \times n$ 矩阵，行向量为 $C$ 的基
- 编码映射：$v \in \mathbb{Z}_2^k \mapsto G^T v \in \mathbb{Z}_2^n$
- 码字判定：$x \in C \iff \exists v \in \mathbb{Z}_2^k, \, x = G^T v$
校验矩阵 $H$（定义 4.5）：
- $H$ 是 $(n-k) \times n$ 矩阵，行向量满足：
$$ Gy_i = 0 \quad (\forall i) $$ - $\{y_i\}$ 是满足条件 $G y_i = 0$ 的极大线性无关组
定理 4.3（矩阵关系）：
$$
G H^T = 0, \quad H G^T = 0
$$
证明：
- 设 $G$ 的行向量为 $g_1, \dots, g_k$，$H$ 的行向量为 $h_1, \dots, h_{n-k}$
- 由定义：$G h_j^T = 0$（因 $G y_j = 0$)
- 故 $G H^T$ 的 $(i,j)$ 元为 $g_i h_j^T = 0$，即 $G H^T = 0$
- 转置得 $H G^T = 0$
- $\text{rank}(H) = n-k$：
- $G$ 的 $k$ 个行向量线性无关
- 约束 $G y = 0$ 的解空间维数为 $n - k$
- 故极大线性无关组 $\{y_i\}$ 含 $n-k$ 个向量
距离的简化计算与纠错条件
命题 4.5（线性码距离）：
距离 $d = \min \{ \text{wt}(e) \mid e \in C, \, e \neq 0 \}$
证明：
- 一般定义：$d = \min \{ d_H(x,y) \mid x \neq y \in C \}$
- 设 $e = x + y$，由线性性 $e \in C$
- $x \neq y \iff e \neq 0$
- $d_H(x,y) = \text{wt}(x + y) = \text{wt}(e)$
- 故 $d = \min_{e \in C \setminus \{0\}} \text{wt}(e)$
定理 4.6（可纠正错误条件）：
设错误集 $\mathcal{E} \subseteq \mathbb{Z}_2^n$，则以下等价：
- $C$ 可纠正 $\mathcal{E}$
- $\forall e \neq f \in \mathcal{E}, \, e + f \notin C$
- $\forall e \neq f \in \mathcal{E}, \, H e \neq H f$
证明：
（1）⇒（2）：
- 假设 $\exists e \neq f \in \mathcal{E}$ 使 $e + f \in C$
- 取 $x \in C$，令 $y = x + (e + f) \in C$
- 则 $x + e = y + f$
- 接收向量 $r = x + e$ 无法区分：
- 若解码为 $x$（错误 $e$)
- 或解码为 $y$（错误 $f$)
（2）⇔（3）：
- $e + f \in C \iff H(e + f) = 0 \iff H e = H f$
- 因 $C = \{ x \mid H x = 0 \}$
（3）⇒（1）：
- 接收向量 $r = x + e$
- 计算症状 $s = H r = H e$
- 症状唯一确定 $e$（因 $H e \neq H f$ for $e \neq f$)
- 解码：$x = r + e$
与量子稳定子码的转换
定理 4.4（线性码→稳定子码）：
设经典线性码 $C$ 的校验矩阵为 $H$，定义量子稳定子码：
- 稳定子生成元：将 $H$ 的每行 $h_i$ 映射为 $Z$ 算子
$$ g_i = Z^{h_{i1}} \otimes \cdots \otimes Z^{h_{in}} $$ - 二进制表示：稳定子的辛表示为 $(0 \mid H)$
则：
- 基底态为 $\lvert x \rangle$（$x \in C$)
- 可纠正错误集 $\mathcal{E}_{\text{quant}} = \{ \lvert e \rangle \mid e \in \mathcal{E} \}$
证明思路：
- 基底态验证：
- $g_i \lvert x \rangle = (-1)^{h_i \cdot x} \lvert x \rangle$
- $H x = 0 \iff h_i \cdot x = 0 \quad (\forall i) \iff g_i \lvert x \rangle = \lvert x \rangle$
- 错误纠正：
- 量子症状 $\langle g_i \rangle = (-1)^{(H e)_i}$
- 经典症状 $H e$ 唯一确定 $e$ ⇒ 量子症状唯一确定错误
实例
汉明码：单比特纠错码
构造思路：
- 观察：单比特错误 $e_i$ 的症状 $s = H e_i$ 等于 $H$ 的第 $i$ 列
- 设计原则：使所有单比特错误的症状唯一
- 校验矩阵 $H$ 的列取遍所有非零二元向量
- 列数 $n = 2^r - 1$（排除全零列）
- 行数 $r$（症状长度）
定义 4.8（汉明码）：
- 参数：$[2^r - 1, 2^r - r - 1, 3]$
- 校验矩阵 $H$：$r \times (2^r - 1)$ 矩阵，列向量为所有非零 $r$-bit 向量
示例（$r=3$）：
$$
H = \begin{pmatrix}
1 & 1 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 1 & 0 & 1 & 0 \\
1 & 0 & 1 & 1 & 0 & 0 & 1
\end{pmatrix}
$$
- 列对应错误位置：
列号 二进制 错误位置 1 001 bit 1 2 010 bit 2 3 011 bit 3 4 100 bit 4 5 101 bit 5 6 110 bit 6 7 111 bit 7
生成矩阵（以 $r=3$ 为例）：
$$
G = \begin{pmatrix}
1 & 0 & 0 & 0 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 1 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 1 & 1
\end{pmatrix}
$$
- 满足 $G H^T = 0$
- 行空间维度 $k = 4$（共 $2^4 = 16$ 个码字）
纠错能力证明：
- 距离 $d=3$：
- 任意两列线性无关 ⇒ 无权重2码字
- 存在三列线性相关（如列1+列2+列3=0）⇒ 最小权重3
- 单比特纠错：
- 接收向量 $r = c + e_i$
- 症状 $s = H r = H e_i =$ 第 $i$ 列
- 唯一确定错误位置 $i$，解码 $c = r + e_i$
最优性分析：
- 可能症状数：$2^r - 1 = n$
- 单比特错误数：$n$
- 完美匹配：症状与错误一一对应，无冗余
2. 里德-穆勒码：多阶可调纠错码
构造思路：
- 几何视角：将 $n=2^m$ 个比特视为 $m$-维超立方体的顶点
- 生成元：
- 基向量 $v_i$：第 $j$ 位 = $j$ 的二进制表示的第 $i$ 位
- 乘积向量：$v_{i_1} \odot \cdots \odot v_{i_k}$（按位与）
- 阶数控制：$\mathcal{R}(r,m)$ 包含所有 $\leq r$ 个向量的乘积
定义 4.9（$\mathcal{R}(1,m)$）：
- 生成矩阵行：全1向量 + $\{v_i\}_{i=1}^m$
- 参数：$[2^m, m+1, 2^{m-1}]$
示例（$m=3$）：
$$
\begin{align*}
v_1 &= (00001111) \\
v_2 &= (00110011) \\
v_3 &= (01010101) \\
G &= \begin{pmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1
\end{pmatrix}
\end{align*}
$$
- 最小权重码字：$v_1 + v_2 = (00110011) + (00001111) = (00111100)$ 权重4
定义 4.10（$\mathcal{R}(r,m)$）：
- 生成矩阵行：所有 $\leq r$ 个 $v_i$ 的乘积（按位与）
- 参数：$[2^m, N(r,m), 2^{m-r}]$，其中 $N(r,m) = \sum_{i=0}^r \binom{m}{i}$
示例（$\mathcal{R}(2,3)$）：
- 新增生成元：$v_1v_2, v_1v_3, v_2v_3$
$$ \begin{align*} v_1v_2 &= (00000011) \\ v_1v_3 &= (00000101) \\ v_2v_3 &= (00010001) \\ G &= \left[\begin{array}{c} \vec{1}^T \\ v_1 \\ v_2 \\ v_3 \\ v_1v_2 \\ v_1v_3 \\ v_2v_3 \end{array}\right] \end{align*} $$ - 总维度 $N(2,3) = 1 + 3 + 3 = 7$，距离 $2^{3-2} = 2$
定理 4.8（距离 $d=2^{m-r}$ 的归纳证明）：
基例：
- $\mathcal{R}(1,m)$：距离 $2^{m-1}$（定理 4.7）
- $\mathcal{R}(r,r)$：最小码字 $v_1\cdots v_r$ 权重 $1 = 2^{r-r}$
归纳假设：
- $\mathcal{R}(r-1,m)$ 距离 $2^{m-r+1}$
- $\mathcal{R}(r,m)$ 距离 $2^{m-r}$
Claim 4.9：$\mathcal{R}(r,m+1)$ 距离 $2^{m+1-r}$
证明：
设非零码字 $c \in \mathcal{R}(r,m+1)$，分解：
$$
c = c_0 + v_1 \cdot d \quad (c_0 \in \mathcal{R}(r,m), \, d \in \mathcal{R}(r-1,m))
$$
按 $v_1$ 取值分区间：
- 前 $2^m$ 位（$v_1=0$）：仅 $c_0$ 贡献
- 后 $2^m$ 位（$v_1=1$）：$c_0 + d$
情况分析：
- $c_0 = 0$：
- 后 $2^m$ 位为 $d \in \mathcal{R}(r-1,m)$，权重 $\geq 2^{m-r+1}$
- 总权重 $\geq 2^{m-r+1} = 2^{(m+1)-r}$
- $d = 0$：
- 前后 $2^m$ 位均为 $c_0$，权重各 $\geq 2^{m-r}$
- 总权重 $\geq 2 \times 2^{m-r} = 2^{m-r+1}$
- $c_0 \neq 0, d \neq 0$：
- 前 $2^m$ 位：$c_0$ 权重 $\geq 2^{m-r}$
- 后 $2^m$ 位：$c_0 + d \in \mathcal{R}(r,m)$ 权重 $\geq 2^{m-r}$
- 总权重 $\geq 2^{m-r} + 2^{m-r} = 2^{m-r+1}$
量子化
汉明码的量子化：
- 经典 $[7,4,3]$ 汉明码 → 量子 Steane 码 $[7,1,3]$
- 构造：
$$ \text{稳定子} = \langle X^H, Z^H \rangle \quad \text{（经典 } H \text{ 映射为 } Z \text{ 和 } X \text{ 算子）} $$ - 可纠正任意单量子比特错误
RM码的量子化：
- $\mathcal{R}(r,m)$ → 量子 RM 码 $\mathcal{QR}(r,m)$
- 构造：
$$ \mathcal{QR}(r,m) = \mathcal{R}(r,m) \times \mathcal{R}(r,m)^\perp \quad \text{(CSS 构造)} $$ - 参数：$[[2^m, k, d]]$ 其中 $k = \binom{m}{r} - \binom{m}{r-1}$