Gilbert–Varshamov 界

形式陈述 ​

设整数 $q\ge 2$、$n\ge 1$，并取 $1\le d\le n$。在 $q$ 元空间 ${\mathrm{\Sigma }}^n$ 中，整数半径 $0\le r\le n$ 的 Hamming 球体积与球心无关，记为

令 $A_q(n,d)$ 表示长度 $n$、最小 Hamming 距离理路Hamming 距离Hamming distance等长字中不同坐标的数量；由逐位比较、三角不等式和 Hamming 球解释检错与唯一纠错半径。至少 $d$ 的 $q$ 元码所能拥有的最大码字数。Gilbert 界给出存在性下界

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

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

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

线性 Varshamov 版本取素数幂 $q$、整数 $1\le k\le n$ 和 $2\le d\le n$。一种有限长度形式是：若

则存在长度 $n$、维数 $k$、最小距离至少为 $d$ 的 $q$ 元线性码理路线性码Linear code有限域向量空间中的线性子空间作为码字集合的信道码。，不要求距离恰等于 $d$。逐列选取 $H\in {\mathbb{F}}_q^{(n-k)\times n}$ 时，避开已有列中至多 $d-2$ 列的线性组合；候选禁区的大小不超过上述和式，所以每次仍有可选列。这样任意至多 $d-1$ 列线性无关，$\ker H$ 中每个非零向量的重量至少为 $d$。又因 $\mathrm{rank}H\le n-k$，秩–零化度定理理路秩–零化度定理Rank–nullity theorem有限维线性映射的定义域维数等于核维数与像维数之和。保证核的维数至少为 $k$，取其中任一 $k$ 维子空间即得结论。$d=1$ 时任意 $k$ 维子空间即可。分母与索引不同于一般 Gilbert 界，两式不能在有限长度下直接混换。

固定 $q$，对 $0\le \delta \le 1-1/q$，以 $0{\log }_{q}0=0$ 的连续延拓约定定义 $q$ 元熵函数

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

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