q 元有限长度 Johnson 界

形式陈述 ​

设 $C\subseteq {\mathrm{\Sigma }}^n$ 是字母表大小 $|\mathrm{\Sigma }|=q$ 的码，最小Hamming 距离公理库Hamming 距离Hamming distance两个等长字在对应位置不同的坐标数。至少为 $d$。对接收词 $y\in {\mathrm{\Sigma }}^n$ 和整数半径 $t$，记

$$\mathcal{L}(y,t)=C\cap B_H(y,t).$$

若 $0\le t\le (1-1/q)n$，且

$$d-2t+\frac{q}{q-1}\frac{t^2}{n}>0,$$

则 q 元有限长度 Johnson 界给出

$$|\mathcal{L}(y,t)|\le \lfloor \frac{d}{d-2t+{\displaystyle \frac{q}{q-1}}{\displaystyle \frac{t^2}{n}}}\rfloor$$

对每个 $y$ 都成立。因此 $C$ 在半径 $t$ 内是 $(t,L)$ 列表可译码公理库列表译码List decoding允许每个接收词对应一个受控候选列表，从而在组合意义上越过唯一译码半径。的，其中 $L$ 可取右侧整数上界。结论的方向是“给定最小距离，所有 Hamming 球中的码字数至多为多少”；它不是码大小上界，也不声称已经有算法能找到这些码字。

令相对距离 $\delta =d/n$、相对半径 $\rho =t/n$。当

$$0\le \delta \le 1-\frac{1}{q}$$

时，二次式

$$\delta -2\rho +\frac{q}{q-1}{\rho }^2$$

的较小零点定义 q 元 Johnson radius：

$$J_q(\delta )=\frac{q-1}{q}(1-\sqrt{1-\frac{q}{q-1}\delta }).$$

对任意固定 $\rho <J_q(\delta )$，分母保持正的常数，列表大小满足

$$L\le \frac{\delta }{\delta -2\rho +{\displaystyle \frac{q}{q-1}}{\rho }^2}.$$

若半径与 $J_q(\delta )$ 的差距只缩小到逆多项式量，该式仍给出多项式列表大小；到达零点时分母消失，本证明不再提供有限上界。有限块长必须先选整数 $d,t$ 并检查原始分母，不能只把 $t$ 写成未经取整的 $n{J}_q(\delta )$。

二元情形要代入 $q=2$，得到定义域 $0\le \delta \le 1/2$ 和

$$J_2(\delta )=\frac{1}{2}(1-\sqrt{1-2\delta }).$$

这不是把 q 元公式里的系数省略后凭外形猜出的另一条式子。对 $0<\delta <1/2$，有 $J_2(\delta )>\delta /2$，所以 Johnson 保证严格越过最小距离给出的唯一译码相对半径；它仍允许输出多个候选，并未扩大唯一译码半径。

若 $\delta >1-1/q$，上面的平方根不再为实数。这个区域受 Plotkin 型现象约束，正率渐近码族不能任意停留其中；有限小码仍可能具有更大相对距离，但必须使用相应有限长度结论，不能把 $J_q$ 公式解析延拓过去。

直觉 ​

所有候选码字都靠近同一个接收词 $y$，因而在许多坐标上必须与 $y$ 一致。另一方面，码的最小距离又强迫每对候选在至少 $d$ 个坐标上不同。这两项要求彼此拉扯：候选若太多，它们为了同时贴近中心，会积累过多共同符号，不可能继续维持两两距离。

唯一译码要求半径球互不相交，只允许列表大小为一。Johnson 界容许这些球重叠，却用平方和控制同一球的最大重叠数；只要半径尚未达到二次式的零点，重叠仍被一个显式 $L$ 压住。

例子与边界 ​

证明骨架直接在 q 元 Hamming 空间计数。固定 $y$，设球内有 $s=|\mathcal{L}(y,t)|$ 个码字；逐坐标重命名符号，可把 $y_i$ 视为基准符号。令 $e_i$ 为第 $i$ 个坐标上与 $y_i$ 不同的候选数，并记总错误出现次数

$$S=\sum _{i=1}^n{e}_i\le st.$$

在坐标 $i$，把这 $e_i$ 个非基准符号按其 $q-1$ 种取值分组。若各组大小为 $m_{i,a}$，则Cauchy–Schwarz 不等式公理库Cauchy–Schwarz 不等式Cauchy–Schwarz inequality · 柯西–施瓦茨不等式内积的绝对值不超过两向量范数之积，且等号精确刻画线性相关。给出

$$\sum _{a\ne y_i}{m}_{i,a}^2\ge \frac{e_i^2}{q-1}.$$

于是该坐标对所有无序码字对贡献的不同符号数至多

$$s{e}_i-\frac{q}{2(q-1)}{e}_i^2.$$

把坐标求和，并再次使用 $\sum _i{e}_i^2\ge S^2/n$，得到全部候选对的总距离至多

$$sS-\frac{q}{2(q-1)}\frac{S^2}{n}\le s^{2}t-\frac{q}{2(q-1)}\frac{s^2{t}^2}{n}.$$

最后一个不等式使用 $t\le (1-1/q)n$，使右侧关于 $S$ 在所需区间单调。另一方面，最小距离要求总距离至少 $(\genfrac{}{}{0ex}{}{s}{2})d$。比较上下界并整理，便得到

$$s(d-2t+\frac{q}{q-1}\frac{t^2}{n})\le d,$$

这正是有限长度列表上界。证明只计算列表必然有多大，没有枚举码字，也没有利用生成矩阵、校验矩阵或多项式结构。

Reed–Solomon 码说明结构如何补上算法。对 $[n,k,n-k+1{]}_q$ RS 码，相对距离约为 $1-R$；当字母表随块长足够大时，$J_q(1-R)$ 接近 $1-\sqrt{R}$。Guruswami–Sudan 算法利用低次数多项式插值与因式分解，在相应半径内以多项式时间找出全部候选。达到这个算法保证依赖 RS 结构，不是 Johnson 计数对任意码免费给出的译码器。

Johnson radius 也不是列表译码容量公理库列表译码List decoding允许每个接收词对应一个受控候选列表，从而在组合意义上越过唯一译码半径。。容量用码率 $R$ 与 q 元熵函数给出约 $R<1-H_q(\rho )$ 的最佳存在区域；Johnson 只用最小距离 $\delta$ 推出任意码都享有的保底半径，两条曲线通常不同。特定码族可以在 Johnson radius 之外仍保持小列表，甚至拥有更强算法。

超过 Johnson radius 后，分母非正，只能说明“最小距离这一项信息已不足”，不能断言每个码的列表立即爆炸。不过，大列表确实可能出现；对固定正码率的码族，一旦半径越过 list-decoding capacity，Hamming 球体积的平均计数会迫使某些球含有指数多个码字。应把“通用 Johnson 保证失效”“某个具体码仍可译码”与“容量以上必有指数列表”分成三层结论。

推论与应用 ​

Johnson 界把码的全局两两距离转成局部球占有数上界，是唯一译码与列表译码之间的结构桥梁。它可用于判断仅凭已知最小距离最多能承诺多大译码半径，并为代数列表译码算法提供候选数不会失控的组合保证。

在 Reed–Solomon、代数几何码和级联码分析中，Johnson radius 常作为比较基线；算法若达到或超过它，还必须分别报告运行时间、完整列表输出和所用码结构。反过来，Johnson 界成立也不代表存在紧凑码描述或多项式译码算法，工程实现不能把组合上界当作算法接口。

参考资料

• Selmer M. Johnson, “A New Upper Bound for Error-Correcting Codes,” IRE Transactions on Information Theory 8(3), 1962，pp. 203–207。
• Venkatesan Guruswami, List Decoding of Error-Correcting Codes, Springer, 2004，Johnson bounds and list-decoding algorithms。
• Venkatesan Guruswami and Madhu Sudan, “Improved Decoding of Reed–Solomon and Algebraic-Geometric Codes,” IEEE Transactions on Information Theory 45(6), 1999。
• W. Cary Huffman and Vera Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003，classical bounds in Hamming space。