线性码

线性码（linear code）是经典编码理论的基本对象：码字不再是一张任意清单，而是有限域向量空间 GF(q)^n 的一个子空间。这一"加法封闭"的约束换来了全部代数结构——生成矩阵与校验矩阵互为对偶、最小距离化作最小重量、译码化作解线性方程。汉明码、Reed–Solomon 码、BCH 码、LDPC 码全部是线性码，而量子 CSS 码的两套校验矩阵正是两个经典线性码的校验矩阵。Hamming 1950 年的第一个纠错码 [7,4,3] 就是它的第一个实例。

子空间、生成矩阵与校验矩阵

一个 $q$ 元 $[n,k]$ 线性码是 ${\mathbb{F}}_q^n$ 的 $k$ 维子空间 $\mathcal{C}$，$R=k/n$ 称为码率。取 $\mathcal{C}$ 的一组基排成 $k\times n$ 矩阵 $G$（生成矩阵），编码即线性映射

$\mathbf{c}=\mathbf{m}G,\mathbf{m}\in {\mathbb{F}}_q^k.$

校验矩阵（parity-check matrix）$H$ 定义 $\mathcal{C}$ 为 $H$ 的零空间：$\mathbf{x}\in \mathcal{C}⟺H{\mathbf{x}}^{\mathsf{T}}=0$，等价地 $G{H}^{\mathsf{T}}=0$。定义对偶码 ${\mathcal{C}}^{\perp }=\{\mathbf{v}:\mathbf{v}\cdot \mathbf{c}=0\forall \mathbf{c}\in \mathcal{C}\}$。由维数公式 $\dim \mathcal{C}+\dim {\mathcal{C}}^{\perp }=n$，可证 $H$ 恰好”补满”对偶码：

• $G{H}^{\mathsf{T}}=0$ 说明 $H$ 的每一行与 $G$ 的每一行正交，即 $H$ 的行空间 $\subseteq {\mathcal{C}}^{\perp }$；
• 若 $H$ 有 $n-k$ 个线性无关行（总可如此选取），其行空间维数为 $n-k$，恰等于 $\dim {\mathcal{C}}^{\perp }$，故行空间等于对偶码，且 $\mathcal{C}=({\mathcal{C}}^{\perp }{)}^{\perp }$——码与对偶码互为校验关系Albert & Faist 2026 (arXiv)。

系统形与编码电路

对 $G$ 做行初等变换（不改变行空间、即不改变码）可化为系统形 $G=[I_k\mid P]$，此时 $H=[-P^{\mathsf{T}}\mid I_{n-k}]$（二元域上 $-P^{\mathsf{T}}=P^{\mathsf{T}}$）。直接验证 $G{H}^{\mathsf{T}}=I_k(-P)+P{I}_{n-k}=0$。系统形下码字自带信息位：$\mathbf{c}=(\mathbf{m},\mathbf{m}P)$，校验位只是信息位的线性组合——这正是汉明码把校验位放在固定位置的做法Hamming 1950 (Bell Syst. Tech. J.)。

最小距离等于最小重量

汉明距离 $d(\mathbf{x},\mathbf{y})$ 是逐位不同的坐标数，重量 $\mathrm{wt}(\mathbf{x})=d(\mathbf{x},0)$。码的最小距离定义为 $d(\mathcal{C})={\min }_{\mathbf{c}\ne {\mathbf{c}}^{\prime }}d(\mathbf{c},{\mathbf{c}}^{\prime })$。对线性码有

$\boxed{d(\mathcal{C})=\underset{\mathbf{c}\in \mathcal{C},\mathbf{c}\ne 0}{\min }\mathrm{wt}(\mathbf{c})}$

证明（两行）：一方面 $d(\mathbf{c},{\mathbf{c}}^{\prime })=\mathrm{wt}(\mathbf{c}-{\mathbf{c}}^{\prime })$，而线性性保证 $\mathbf{c}-{\mathbf{c}}^{\prime }\in \mathcal{C}$，故每个码字对给出一个非零码字；另一方面固定任一 ${\mathbf{c}}^{\prime }$，映射 $\mathbf{c}\mapsto \mathbf{c}-{\mathbf{c}}^{\prime }$ 是 $\mathcal{C}$ 到自身的双射，故每个非零码字都作为差出现。两组对象相同，最小值相等。∎

这条定理把搜索范围从 $q^{2k}$ 个码字对压到 $q^k-1$ 个非零码字，更重要的是给出对偶刻画：$\mathbf{c}\ne 0$ 且 $H{\mathbf{c}}^{\mathsf{T}}=0$ 意味着 $H$ 中以 $\mathbf{c}$ 的支撑为指标的列线性相关，故 $d(\mathcal{C})$ 等于 $H$ 中最小线性相关列组的大小。后续词条里 LDPC 码与 qLDPC 码的距离分析走的都是这条路。纠错能力由 $t=\lfloor (d-1)/2\rfloor$ 给出：任意两个码字的汉明球互不相交，落入正确球内的接收向量必被唯一译回。

伴随式与伴随式译码

发送 $\mathbf{c}$、信道加错 $\mathbf{e}$（模 $q$ 加法下的错误向量），接收 $\mathbf{y}=\mathbf{c}+\mathbf{e}$。计算伴随式（syndrome）

$\mathbf{s}=H{\mathbf{y}}^{\mathsf{T}}=H{\mathbf{c}}^{\mathsf{T}}+H{\mathbf{e}}^{\mathsf{T}}=H{\mathbf{e}}^{\mathsf{T}},$

第三步用了 $\mathbf{c}\in \mathcal{C}$——伴随式只依赖错误而不依赖发送内容，“测错误不测信息”的经典原型，量子纠错的综合征提取在结构上与此完全同构。译码策略：在陪集 $\mathbf{y}+\mathcal{C}$ 中找最可能（最小重量）的错误向量，把 $\mathbf{y}$ 减去它即得码字；标准阵列把 ${\mathbb{F}}_q^n$ 按 $\mathcal{C}$ 的陪集列表、每陪集记录一个陪集首领，就是这一策略的查表实现。汉明码是唯一”伴随式直接读出错误位置”的特例（见hamming-codes）；一般线性码的陪集首领计算没有快速算法，这正是代数码（reed-solomon、bch-codes）与稀疏图码（ldpc-classical）各自发展专用译码算法的原因。

通往量子码

线性码的矩阵语言几乎原封不动地进入量子纠错：CSS 码取两个经典校验矩阵 $H_X,H_Z$ 并要求 $H_X{H}_Z^{\mathsf{T}}=0$（见css-codes）；稳定子码把 $n$ 比特 Pauli 群商掉相位后看成 ${\mathbb{F}}_2^{2n}$，稳定子生成元组就是一张 $(n-k)\times 2n$ 的”校验矩阵”，其零空间（辛正交意义下）即码空间（见stabilizer-formalism）。量子码参数 $[[n,k,d]]$ 的双方括号记号正是在经典 $[n,k,d]$ 记号上加了一层量子标记（见code-parameters）。

延伸阅读

• hamming-codes
• galois-fields
• classical-bounds
• css-codes
• code-parameters