有噪声的信道可能改变发送的字。冗余只有在合法字之间相距足够远时才有用;否则同一个接收字可能来自两个不同消息。我们先精确描述这种距离,再用线性代数定位单个错误。
定义
定义 1.1.1
(汉明距离、重量与最小距离)
对 ,汉明(Hamming)距离 是它们不同的坐标数,重量 是非零坐标数。因此 。二元码 是 的非空子集;至少有两个码字时,其最小距离定义为
距离满足三角不等式:在 不同的每个坐标, 或 必有一对不同。数坐标便得 。
定理 1.1.2
(纠错半径)
对非负整数 ,至少含两个码字的码能以唯一最近邻译码纠正所有至多 位错误,当且仅当 。
证明
(球互不相交,相交时取中间的字)
设 ,发送码字 ,收到 且 。对任何其他码字 ,三角不等式给出
所以 是离 最近的唯一码字。反过来,若两个码字在 个坐标不同,将第一个码字其中 个不同坐标改为第二个的值,得到的字 与两者距离分别为 和 ,均不超过 。 可由任一码字经至多 位错误得到,而译码器只输出一个字,所以没有译码器能对这两种发送情况都保证正确。
证明透视
因子二从哪里来
正方向只用一次三角不等式,以发送字作中间点:从至少 的间隔中扣去 位错误,剩下至少 ,仍然胜过 。反方向需要一个同时离两个码字都不超过 的接收字。关键一步是改动 个不同坐标中的 个,得到距离 与 。两者都不超过 当且仅当 ,而这样的 存在当且仅当 ;平均分配 总在这个范围内。“至少两个码字”的假设只是为了使 有定义;只有一个字的码无需译码。
对非负整数 ,检错的门槛不同:恰当的条件是 ,此时所有非零的至多 位错误都能被发现。发现接收字不合法不等于能找回原字。例如重复码 距离为三,可检出两位错误并纠正一位错误,却不能保证纠正两位错误。
定理/命题
定义 1.1.3
(线性码、生成矩阵与校验矩阵、伴随式)
二元线性码是子空间 ; 码维数为 ,故有 个码字。生成矩阵 的行构成 的基底,行消息 编码为 。校验矩阵 满足 。接收字 的伴随式是 。
非零线性码的最小距离等于非零码字的最小重量:不同码字之差恰好遍历非零码字,因为每个非零码字也可写成它与零之差。若接收字为 ,其伴随式为 ,与发送码字无关。于是可用常见错误图样建表,将伴随式对应到修正方式。但不同错误图样可以具有同一伴随式,单凭它不能证明实际发生了哪一个错误。
考虑二元 码,其校验矩阵的列依次为七个不同的非零二元三维向量:
前三列为单位矩阵,故秩为三,核的维数为四。没有重量一的非零核向量,因为没有零列;也没有重量二的,因为列彼此不同。第一、二、四列之和为零,因此 是重量为三的码字。最小距离恰为三,能纠正一位错误。
例题 1.1.4
(在七位码中纠正一位错误)
若收到 ,其伴随式为第 1、4 列之和 ,即第 2 列。单错误规则翻转第 2 位,得到 。若实际发生两位错误,这个规则可能输出其他码字;纠错半径定理只保证至多一位错误时纠正成功。
球填充与参数限制
二元空间中半径为 的球有 个字:只需选择翻转的位置。这些球互不相交,便限制了任何纠错码的大小。
定理 1.1.5
(汉明界)
若长度为 的二元码 能纠正所有至多 位错误,则
证明
(计数“码字及其球中一个字”的配对)
把每对“码字及其半径 球中的一个字”对应到后者。这些球互不相交:若一个字离两个码字都不超过 ,它可由其中任一个发送而来,便不能对两者都正确译码。因此不同的对不能对应到同一接收字。配对共有 个,它们单射到 个可能的接收字。
上述例子满足 ,故半径一的球恰好划分整个空间。这个等式是计数结论,不表示实际错误一定不超过一位。
快速检查
(长度为五、有八个码字的二元码能否纠正所有单错误?)
以 套用汉明界。
解答 · 答案
不能。汉明界要求 ,但 。
练习
快速检查
(对上面的七位码,假设至多发生一位错误,译码 。)
计算伴随式,并与 的各列比较。
解答 · 答案
伴随式是第 3 列 。翻转第 3 位得到 ,它是合法码字;由假设及最小距离三,它是距离接收字至多一的唯一可能发送字。
伴随式表的局限
反例模式
伴随式不能确定所有错误
两个错误向量 的伴随式相同,当且仅当 ,等价于 。因此仅凭伴随式,无法区分同一个陪集中的错误。对于七位码,错误 与 的伴随式相同。若发送零码字后发生前一种错误,单错误译码器反而翻转第二位,输出 。这虽是合法码字,却不是发送字。这是两个错误导致译码失败的具体例子。
若 校验矩阵满秩,线性映射 满射,故有 个伴随式。每个伴随式类有 个向量:若 具有该伴随式,则类中每个向量都可唯一写成 ,其中 。每类的最小重量代表称为陪集首领。减去一个陪集首领就是最近码字译码: 是码字当且仅当 与 伴随式相同,而它与 的距离为 的重量。若最小重量代表不止一个,可以规定如何选择,但不能因此声称唯一译码。
快速检查
(为什么七位例子中两个重量为一的不同错误不能具有相同的非零伴随式?)
重量一的向量的伴随式是什么?
解答 · 答案
重量一的向量的伴随式等于 中相应的列。七列互不相同且均非零,所以单错误的位置可由伴随式确定。这个结论不适用于重量至少为二的错误。
例题详解
定理 1.1.6
(由相关的列读出最小距离)
对含非零码字的二元线性码 ,最小距离等于和为零的最少列数。即使两列相等,也要按列所在位置分别计数。
证明
(乘以一个字就是选取列)
恰好把 的非零坐标所对应的列相加。因此 等价于这些列之和为零,选中的列数正是 的重量。线性码的最小距离是非零码字的最小重量,对非零 取最小值即得结论。
这个判别法将搜索码字转化为检查列的线性关系。零列给出重量一的码字;两条相等的列给出重量二的码字。反过来,若少于 条的任意列都线性无关,则没有重量小于 的非零码字。但若要断言最小距离恰为 ,还须展示 条线性相关的列。七位矩阵的前三列线性无关,但第一、二、四列之和为零。
概念视角组合
重量为三的码字就是 Fano 平面的直线
把 的七列看作 Fano 平面的七个点;其直线是 中由不同非零向量组成的三元组 。由上述定理,重量为三的码字恰好是三个和为零的不同列,也就是一条直线。每条直线包含 个点对中的三个,而每个点对恰在一条直线上,因此共有 条直线,即恰有 个重量为三的码字。码字 对应直线 。
常见错误
(只检查一组列而非全部)
不能仅凭七位矩阵前三列线性无关就断言距离为四:必须检查所有三列组合才能排除重量三,而第 1、2、4 列正是一组线性相关的三列。
例题 1.1.7
(单一的整体校验位)
考虑校验矩阵 ,其核由偶重量的二元四维向量组成。唯一一行非零,故核的维数为三;没有零列,而任意两列之和为零,所以距离为二。例如 与 的距离为二。此码能检出任何单错误,却不能唯一纠正所有单错误。收到 时,既可能发送 并翻转第一位,也可能发送 并翻转第二位。
此例也说明校验与定位不同。单比特伴随式显示接收字是否为奇重量;非零伴随式表明发生了奇数次翻转,却不指出四个位置中的哪一个被翻转。偶数次翻转可能给出零伴随式,因此接收字通过校验并不能证明没有错误。
仔细计数译码球
码字 的半径 球由所有与它相差至多 个坐标的字组成。当 时,恰有 个字与它距离为 ,因为每个二元坐标只有一个可替换的值。对 求和便得汉明界中的球大小。若 ,球就是整个空间,求和可以在 处停止。
汉明界取等号意味着这些球覆盖空间,但并不意味着任意高重量错误都能纠正。七位例子中的每个接收字都恰属于一个半径一的球;由两位错误产生的字虽然也在某个球内,其球心却可能不是发送字。
快速检查
(某二元线性码校验矩阵的列依次为 。求维数及最小距离。)
先求 的秩,再找和为零的最少列数。
解答 · 答案
前两列说明矩阵秩为二,故核的维数为 。没有零列,排除重量一;第三、四列相等,故 是重量二的码字。因此最小距离为二。结论同时需要下界和达到下界的例子。
从生成矩阵构造校验矩阵
若二元生成矩阵为系统形式 ,则可以取
确实,由于特征为二,,故每个生成的码字均在 中。单位矩阵块使 的秩为 ,由秩—零化度定理其核维数为 。 包含 ,所以其行空间维数也为 。两个同维空间之间已有包含关系,故它们相等。这里的加号依赖特征二;一般域上应取 。
例题 1.1.8
( 码的校验矩阵)
令 。此处 ,故 。其核是偶重量二元三维向量。生成矩阵两行线性无关,四个码字为 ;非零码字重量均为二,因此最小距离为二。一个校验位增加了冗余,能检出单错误,但依纠错半径定理不能纠正所有单错误。
常见错误
常见错误
(一对距离为三的码字不证明距离为三)
最小距离是整个码的性质,不是某一对码字的性质。找到距离三的一对只能证明最小距离至多为三;要证明恰为三,还须排除所有更小距离。对线性码可改查非零码字的重量,但这个简化依赖减法封闭,对任意子集不成立。
常见错误
(伴随式为零不等于没有错误)
非零伴随式说明接收字不是码字;零伴随式只说明它属于码。未被发现的错误可能把一个码字变成另一个码字。事实上,给发送字加上任意非零码字仍得到码字,因此伴随式为零。此类事件有多可能,要看此处尚未指定的信道模型。