Gilbert–Varshamov 界

形式陈述 ​

在 $q$ 元空间 ${\mathrm{\Sigma }}^n$ 中，半径 $r$ 的 Hamming 球体积与球心无关，记为

$$V_q(n,r)=\sum _{i=0}^r(\genfrac{}{}{0ex}{}{n}{i})(q-1{)}^i.$$

令 $A_q(n,d)$ 表示长度 $n$、最小 Hamming 距离至少 $d$ 的 $q$ 元码所能拥有的最大码字数。Gilbert 界给出存在性下界

$$A_q(n,d)\ge \frac{q^n}{V_q(n,d-1)},$$

若要整数形式，可在右侧取上整。注意分母半径是 $d-1$，不是唯一译码球半径 $\lfloor (d-1)/2\rfloor$。

证明采用贪心极大码。起初 $C=\varnothing$；每次选择一个与现有所有码字距离至少 $d$ 的词加入 $C$，直到无法再加入。终止时 $C$ 的最小距离至少为 $d$。此外，以各码字为中心、半径 $d-1$ 的球必须覆盖整个 ${\mathrm{\Sigma }}^n$：若某个词 $y$ 不在这些球中，它距每个现有码字都至少为 $d$，还可加入 $C$，与极大性矛盾。因此

$$q^n\le |C|V_q(n,d-1),$$

整理即得结论。球之间可以大量重叠；证明只使用覆盖，不使用打包。

线性 Varshamov 版本需要单独陈述。一种有限长度形式是：若

$$\sum _{i=0}^{d-2}(\genfrac{}{}{0ex}{}{n-1}{i})(q-1{)}^i<q^{n-k},$$

则存在 $q$ 元线性 $[n,k,d{]}_q$ 码。它可通过逐列构造校验矩阵并避免短线性相关得到，分母与索引不同于一般非线性 Gilbert 界；两式不能在有限长度下直接混换。

对 $0\le \delta \le 1-1/q$，定义 $q$ 元熵函数

$$H_q(\delta )=\delta {\log }_q(q-1)-\delta {\log }_q\delta -(1-\delta ){\log }_q(1-\delta ).$$

利用 $V_q(n,\delta n)=q^{n(H_q(\delta )+o(1))}$，Gilbert–Varshamov 界导出：存在相对距离趋近至少 $\delta$ 的码族，其渐近率满足

$$R\ge 1-H_q(\delta ).$$

这个不等式的方向是“存在码达到至少该率”，不是对所有码的率上界；有限长度的舍入与 $o(1)$ 项也不能从渐近式中删除。

直觉 ​

把每次选中的码字周围、距离小于 $d$ 的邻居全部划为“不能再选”。每一步最多排除 $V_q(n,d-1)$ 个词，所以要覆盖总共 $q^n$ 个词，必然能完成相当多步。算法停止不是因为空间被互不相交地填满，而是因为每个剩余词都离某个已选码字太近；正是这项覆盖性质产生码大小的下界。

GV 界回答“参数区域里至少有一个码”，与 Singleton 或 Hamming 界回答“任何码都不能越过哪里”方向相反。两类界之间的空隙反映了我们对最佳码参数的未知程度，也把存在性、显式构造与译码效率分成三个问题。

例子与边界 ​

在二元长度 $3$、目标距离 $d=2$ 时，$V_2(3,1)=1+3=4$，Gilbert 界只保证存在至少 $2^3/4=2$ 个码字。偶校验码

$$\{000,011,101,110\}$$

实际有 $4$ 个码字且最小距离为 $2$。这说明下界提供保底存在性，不声称贪心计数总是紧，也不刻画最大码的唯一结构。

若误把半径改成 $\lfloor (d-1)/2\rfloor$，得到的是围绕码字的唯一译码球打包思路，并会反转计数用途。GV 证明中的半径 $d-1$ 允许球重叠，只为确保一个极大码覆盖空间；Hamming 界中的较小球必须互不相交，用来限制码字不能太多。

存在一个大码不等于拥有高效编码器或译码器。基础贪心过程可能要遍历 $q^n$ 个词，随机码也可能只能用指数时间最近邻搜索。即使渐近率达到 $1-H_q(\delta )$，有限块长常数、错误指数、算法复杂度与结构化实现仍需额外结果。

一般码与线性码版本也有边界。渐近上二者都导向相同的 GV 率曲线，但有限长度的计数条件、码字数必须为 $q^k$ 的限制和构造证明并不相同；引用数值参数时应先确定正在使用哪一版本。

推论与应用 ​

Gilbert–Varshamov 界为信道码公理库信道码Channel code把消息映为信道输入码字并从带噪输出恢复消息的编码—译码对。参数提供基准：在给定相对距离下，它证明某个正码率区域确实可达。编码理论常把显式码族的率—距离曲线与 GV 曲线比较，以判断代数结构为高效算法付出了多少参数代价。

该证明也体现概率方法公理库概率方法Probabilistic method通过证明随机选取对象具有正概率满足性质来推出确定性对象存在。和极大化论证的共同精神：可以通过计数或随机选择证明确定对象存在，却暂不展示可用对象。后续的随机线性码、级联码和算法化构造试图在保持接近存在界的同时，补上紧凑描述与高效编码译码。

参考资料

• Edgar N. Gilbert, “A Comparison of Signalling Alphabets,” Bell System Technical Journal 31(3), 1952。
• Rom R. Varshamov, “Estimate of the Number of Signals in Error Correcting Codes,” Doklady Akademii Nauk SSSR 117, 1957。
• F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977，classical bounds and asymptotics。