q 元有限长度 Johnson 界

形式陈述

设 $n\ge1$ 、 $q\ge2$ 为整数， $C\subseteq\Sigma^n$ 是至少含两个码字、字母表大小 $|\Sigma|=q$ 的码，最小Hamming 距离至少为整数 $1\le d\le n$ 。对接收词 $y\in\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 \left\lfloor \frac{d} {d-2t+\dfrac{q}{q-1}\dfrac{t^2}{n}} \right\rfloor

对每个 $y$ 都成立。因此 $C$ 在半径 $t$ 内是 $(t,L)$ 列表可译码的，其中 $L$ 可取右侧整数上界。结论的方向是“给定最小距离，所有 Hamming 球中的码字数至多为多少”；它不是码大小上界，也不声称已经有算法能找到这些码字。

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

0\le\delta\le1-\frac1q

时，二次式

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

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

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

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

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

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

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

J_2(\delta) =\frac12\left(1-\sqrt{1-2\delta}\right).

这不是把 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)|$ 个码字。 $s=0$ 时结论立即成立，以下取 $s\ge1$ 。逐坐标重命名符号，可把 $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 不等式给出

\sum_{a\ne y_i}m_{i,a}^2 \ge\frac{e_i^2}{q-1}.

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

se_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^2t-\frac{q}{2(q-1)}\frac{s^2t^2}{n}.

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

s\left(d-2t+\frac{q}{q-1}\frac{t^2}{n}\right)\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 也不是列表译码容量。容量用码率 $R$ 与 q 元熵函数给出约 $R<1-H_q(\rho)$ 的最佳存在区域；Johnson 只用最小距离 $\delta$ 推出任意码都享有的保底半径，两条曲线通常不同。特定码族可以在 Johnson radius 之外仍保持小列表，甚至拥有更强算法。

在上述 $0\le\delta\le1-1/q$ 的范围内，并仍将半径限制为 $0\le\rho\le1-1/q$ 时，达到或超过 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。

形式陈述 ​

形式陈述