动机
码以可能消息的数量换取码字之间的分离度。球填充解释了为什么可靠的纠错需要消耗空间。用更大的球进行覆盖则解释了为什么相当大的分离集合是存在的。当所要求的相对距离很大时,对码字对进行计数提供了另一类障碍。
这些论证回答的是不同的问题。上界限制每一个码。下界存在性保证至少有一个码,而往往没有可用的译码器。显式构造可能优于该下界保证,而并不与之矛盾。我们将始终保持这些方向清晰可辨,包括从有限码长过渡到渐近码率的时候。
计数论证起初只需要有限字母表。线性存在性证明还需要有限域,但它不会假设非零码字相互独立、随机矩阵满秩,也不会假设存在有效的搜索算法。
定义
定义 1.3.1
(码、球与码率)
设字母表有 个符号。长度为 的码是其 重笛卡尔(Cartesian)幂的一个子集 ,其大小为 。当 时,其最小 Hamming 距离 是不同码字之间距离的最小值。我们把有限参数的陈述限制在整数 以及距离至少为 的码上。
记
这是半径为 的球中的字的个数:选出被改变的位置,并在每个位置从 个替换符号中选一个。每个球心对应的球大小相同。码率为 。对于 上维数为 的线性码,这变为 。
定义 1.3.2
( 元熵函数)
对 ,定义
端点处的值由连续性给出。其导数为 ,因此它在 上递增,并在右端点达到 1。这一单调性限制在体积估计中很重要。
定理/命题
定理 1.3.3
(有限的填充与覆盖界)
每个长度为 、距离至少为 的码都满足
存在距离至少为 的码,使得 。第一个不等式是 Hamming 界,第二个是 Singleton 界,存在性陈述则是 Gilbert 覆盖论证。
定理 1.3.4
(一个线性存在性保证)
当 为素数幂时,令 。对任意满足 的整数 ,存在 上维数至少为 、距离至少为 的线性码。当 时该和为零,允许取 。
定理 1.3.5
(Plotkin 的码字对计数界)
令 。若 ,则每个这样的码都满足
整数形式的码大小可以由右端的下取整来界定。该假设是严格的:在等号处,所示分母为零,此论证不给出有限的大小界。
证明思路或证明
不相交的小球与覆盖的大球
证明
(不相交的球、打孔与极大码)
令 。若某个字同时属于两个不同码字的半径 的球,则由三角不等式,这两个码字的距离至多为 。因此这些球两两不相交,其总大小不能超过 ,这就证明了 Hamming 界。这一计数证明的是一种限制;它并不实现译码器。
对于 Singleton 界,删去任意 个坐标位置。若两个码字在其余坐标上相同,则它们至多在被删去的位置上不同,这与距离至少为 矛盾。因此这一删去坐标的映射(打孔映射)是单射,取值于其余的 个字。这一论证不要求线性性。
对于存在性,从没有任何字开始,反复添加一个与每个已选字的距离都至少为 的字,直到无法再添加为止。有限性保证过程终止。所得的码在包含关系下是极大的。于是环境空间中的每个字都必须落在某个已选码字的距离 之内,否则它还可以被添加。这些球覆盖整个环境空间;允许重叠。它们的总大小至少等于其并集的大小,从而 。
证明透视
同一个并集比较指向两个方向
对于不相交的小球,大小之和等于并集,且至多为环境空间的大小。对于较大的覆盖球,大小之和至少等于并集,而并集就是整个环境空间。存在性证明依赖于在包含关系下的极大性,而不是找到可能的最大码。枚举整个环境空间一般需要关于码长呈指数级多的步骤。
随机校验排除射影意义下的低权方向
证明
(对低权方向用并集界)
现在使用 。选取 矩阵 ,各元独立均匀取值。对每个固定的非零向量 ,某一行与 的点积在 中是均匀分布的:选取 的一个非零坐标,对该行的其余元素取条件,并利用剩余元素上的双射。各行独立,故 。
的非零标量倍数具有完全相同的为零事件。权小于 的非零向量分成若干一维子空间,每个子空间含 个具有相同权的非零向量。这样的方向恰有 个。在每个方向中选取一个代表。并集界表明,某个方向被 映为零的概率至多为 。因此至少存在一个不使任何方向被映为零的 ,其核中没有权小于 的非零向量。
核是维数为 的线性码。这里没有使用满秩假设。不同代表所对应的事件不必独立;并集界并不需要独立性。此外 ,故总存在某个允许的 ,尽管较弱的选择可能只保证零维码。对于仅含一个字的线性码,距离陈述直接意味着不存在权小于 的非零字。
成功的存在性论证仍留下算法任务
假设我们真的抽取一个矩阵。检验其秩很容易,可通过消元完成,但这并不检验距离条件。若要直接验证并集界所用的性质,我们需要检查没有低权射影代表落在其核中。它们的数目正是 所计数的量,可随码长指数增长。因此该证明给出了存在好矩阵的正概率,但没有给出可以低成本验证所观察到的矩阵为好矩阵的证书。
重复试验并不能消除这一区别。若对 作更强的选择,使并集界的失败概率估计至多为二分之一,则独立抽取的若干矩阵中至少有一个是好的这一事件就很可能发生。识别哪个样本具有所需的最小距离仍将是一个额外的计算问题。有效的编码器也不能解决这一问题:一旦求得核的一组基底,编码就只是线性组合,而最近码字译码提出的是另一类搜索问题。
这里有一个有用的结构单调性。好线性核的任何子码都保持同样的距离下界保证,因为去掉字不会引入新的低权非零字。若其维数超过所需的消息维数,可以选取由较小一组基底所张成的子空间。这一观察使存在性证明能够提供方便的码率,而不必假装所有冗余校验都是独立的,或某个特定维数被恰好强制。
概念视角代数
线性码的 Singleton 界就是秩的计数
对 上的线性 码,设校验矩阵 的秩为 。一个权为 的非零码字就是 的 列之间的非平凡线性相关。距离至少为 因此表示任意 列都线性无关,于是 。这再次给出 ,但现在读作关于列秩的陈述,而不是关于删除坐标。
统计所有坐标上的不一致
证明
(逐个坐标统计不一致)
对固定的坐标,令 为携带符号 的码字个数。在该坐标上不一致的无序对数为
因为 ,且 Cauchy–Schwarz 不等式给出 。对 个坐标求和。另一方面, 个不同的对中,每一对至少在 个坐标上不一致。因此 。约去正数 并整理,得 。只有当 时,除法才是合理的。
证明透视
同一数量的两种计数
证明把同一数量数了两次:由一对码字及它们不一致的一个坐标组成的组合。上界计数只用到每个坐标上各符号的频数之和为 ;Cauchy–Schwarz 不等式表明符号均匀分布时不一致的对数最多。下界计数只用到距离。比较式 右边是 ,左边却是 ,正是这个量级为 的差距给出 的上界。当 时,不等式对所有 都成立,推不出任何结论。在精确的例子中两种计数都取等号:每个坐标都均匀分布,每对码字的距离都恰为四。
把球的大小转换为熵指数
对 ,令 。项 是参数为 的二项概率分布的最大项之一,这可由相邻项之比看出。在它的 项中,某个最大项的概率至少为 。因此
对于反向估计,另设 。对 ,比值 至多为其在 处的值。把每个体积求和项表示为其二项概率乘以这一比值再乘以 ,然后利用概率之和至多为一,得 。在 时,两个有用的估计都可由体积为一直接得出。
固定 与目标相对距离 。令 。覆盖估计与体积上界给出码率至少为 的码。线性界也是如此:取使 的最小 ,则 ,除去本来就平凡的零和情形。于是对一列线性码有 。
反之,对任何相对最小距离趋于 的码,Hamming 不等式中的球下界给出 。 项随码长趋于零;它们并不允许丢掉有限长度下的取整,也不允许声称任一边界是精确的最优码率。若固定的相对距离严格大于 ,Plotkin 界给出有界的码大小,从而码率趋于零。等号情形 需要进一步论证,不能靠除以零得到。
例题详解
例题 1.3.6
(界可能留下真实的间隙)
对二元长度 7、距离 3, 且 ,故 Hamming 界给出 。覆盖存在性界使用 ,保证 。线性论证中 ,故 保证维数至少为二,即至少四个字。二元 Hamming 码有十六个字,达到上界。它的存在改进了这两个下界保证;并不使它们失效。
例题 1.3.7
(高距离下紧的码字对计数)
在 的七个非零向量上,对全部八个二元线性型求值。非零线性型在其中四个向量上取一,故所得线性码长度为七,有八个字,距离为四。Plotkin 界给出 ,且可以达到。这里码字对证明中的坐标平衡是精确的:每个非零求值点在全部码字上看到四个零值和四个一值。
例题 1.3.8
(渐近保证不等于构造速度)
在二元相对距离 时,熵约为 。所证明的存在性论证给出码率至少趋近 的线性码。Hamming 渐近上界约为 。这些是带有间隙的下限与上限约束,而不是对一个已被确定的最优值的两个估计。随机校验证明本身并不提供对每个候选矩阵的多项式时间验证器,也不提供有效译码器。
反例与常见错误
反例模式
极大性弱于最大性
对二元长度三且所需距离为二, 是极大的:其余每个字都在它某个成员的距离一之内。但 有四个字且距离要求相同。因此贪心论证可能停在比最优码更小的码上。其覆盖证明仍适用于这个较小的码。
常见错误
(线性保证需要域)
线性存在性定理要求有域;合数大小、以模运算定义的字母表不是域,均匀点积这一步便会失效。以模 整数为例,乘积 只取值 与 ,所以若向量 唯一的非零元素是 ,均匀随机行与 的点积并不均匀分布。
常见错误
(在 Hamming 界中误用覆盖半径)
Hamming 上界用的是半径 的球;半径 属于存在性界,那里不等式方向相反。两者混用会得出错误的限制。对二元长度七、距离三,若用 ,便得 ,但二元 Hamming 码有十六个字,距离为三。
距离保证只能通过不相交的球来控制最坏情形下的纠错。它并不会把极大填充构造变成快速的最近码字过程。
练习
快速检查
(对三元、长度为四、距离为三的码,计算 Hamming 与 Singleton 上界。)
解答 · 答案
纠错半径为一,球的大小为 。Hamming 界给出 。Singleton 界给出 。两个上界相等并不是存在性证明,尽管长度为四的三元 Hamming 码(有九个字、距离为三)确实达到这些参数。
快速检查
(解释为什么半径 的球覆盖并不与半径 的不相交球相矛盾。)
解答 · 答案
不相交球的半径,其两倍严格小于 。覆盖半径 一般更大;该半径的球可能大量重叠。极大性保证它们的并集覆盖所有的字,而该比较中并没有用到不相交性。
快速检查
(在随机校验证明中,为什么应当把非零标量倍数归为一组,又为什么不需要两两独立?)
解答 · 答案
非零标量倍数具有相同的核成员事件,所以把整个方向只计一次可改进充分界。对任意有限个事件,无论相互依赖如何,并集的概率至多为各概率之和。只需要用于计算单个向量概率的行独立性。
快速检查
(对二元长度十、距离六应用 Plotkin 界。若距离为五,哪里会失效?)
解答 · 答案
此处 ,正的分母为 ,得 。距离为五时分母为零;整理后的不等式只写成 ,不界定任何大小。代入所示分式是无效的。
快速检查
(下界 是否断言每个足够大的具有该距离的码都有该码率?)
解答 · 答案
该论证构造或证明了至少存在一列适当的码。较小的子集保持距离,但码率可以低得多。因此不能把存在性下界读作对具有相同最小分离度的每个码的码率下界。