界是编码理论的地形图:上界说"什么不可能",下界说"什么存在"。汉明界用球填充论证给出冗余度的下限,Singleton 界用删除论证给出距离的上限,Gilbert–Varshamov 界则用计数论证证明好码(码率与相对距离同时为正)随机地大量存在。取等者各有专名:饱和汉明界的叫完美码,达到 Singleton 界的叫 MDS 码(Reed–Solomon 是其典范)。量子码一侧有一整套平行的界,是本类词条与量子侧的直接对照点。

汉明界:球填充上界

以每个码字为中心、半径 的汉明球必须两两不相交——若两球相交,交点到两中心的距离都 ,由三角不等式两码字距离 ,矛盾。 元空间中半径 的球体积为

不相交的球总体积不能超过全空间,对线性码 即得汉明界:

渐近形式(, 固定):,其中 为 元熵函数。取等 = 完美码:汉明码全族 (见hamming-codes)、二元 Golay 码 (球体积 恰饱和)、奇数长二元重复码;据 Handbook 引述的分类定理,二元/三元非平凡完美码仅此两类Albert & Faist 2026 (arXiv)。

Singleton 界:删除论证

对任意(不必线性)的 元码:删去任意固定的 个坐标后,余下码字必须两两不同——若两码字在剩余 个坐标上相同,则它们的距离至多 ,矛盾。 个坐标最多区分 个不同向量,故

渐近形式 。论证只用了”距离大 ⇒ 删坐标仍可区分”,这就是擦除信道视角:能纠 个擦除的码必须把信息完整装进任意 个坐标。取等 = MDS 码(maximum distance separable):距离—码率帕累托前沿上的每个点都有码,无任何冗余浪费;Reed–Solomon 码是其典范构造(见reed-solomon)Reed & Solomon 1960 (J. SIAM)。据 Handbook 引述的 MDS 猜想:非平凡 MDS 码长度 (素域情形已获证,一般素数幂情形仍开放)Albert & Faist 2026 (arXiv)。

Gilbert–Varshamov 界:存在性下界

前两条界限制”码不可能太好”,GV 界则保证”不太坏的码大量存在”:存在 线性码使

计数证明(greedy 版):逐个放置码字,每放一个就以它为中心把半径 的球划为禁区。放满 个码字后禁区总体积至多 ;只要它小于 ,就总还有合法位置。于是码字数可达

渐近地 (熵函数估计),取对数即得 。∎(线性版把”逐个放码字”换成”逐个选基向量”,结论相同。)

意义:固定 时 有正常数下界——好码(good code)随机地、大量地存在。但随机码没有结构:伴随式译码需要指数查表,编码矩阵是稠密随机矩阵。此后编码理论的构造史,就是”结构化地逼近 GV 界或绕开它”的历史:BCH/RS 是代数结构换译码效率,级联用两级结构换复杂度(见concatenated-classical),而 Sipser–Spielman 的扩张码第一次给出显式构造的渐进好码(见expander-codes),LDPC 则用稀疏性同时拿到好码与线性时间译码(见ldpc-classical)Sipser & Spielman 1994 (FOCS)。

上界与下界之间的地带

把三条界放到 平面上:GV 下界曲线 之下”存在”,汉明上界 与 Singleton 界 之上”不存在”,两者之间的地带在一般情形仍未关闭。对特定族能更紧:MDS 码挤在 Singleton 线上,LDPC 的密度演化阈值则把”可达”推进到容量线(见channel-capacity)。

量子对照

量子码有一整套平行的界:量子汉明界(子空间维数计数)、量子 Singleton 界 (给出量子 MDS 码概念)、量子 GV 界(好量子码存在性)。简并性使量子侧更微妙——简并码可以”逃出”量子汉明界,见quantum-bounds与degeneracy。

延伸阅读