离散数学课件 9.4 应用

离散数学

Discrete

Mathematics第九章

代数系统9.1代数运算及性质9.2代数系统9.3几个典型的代数系统9.4应用29.4应用第5章图

纠错码的纠错能力纠错码的选择3离散数学基本概念4各类计算机终端设备普遍采用数字信号进行通信，但通信过程中有时会出现差错，如受到电磁干扰或温度、灰尘的影响。解决这类问题通常分两步：一是检错，即判断所接收到的数据是否有错；二是纠错，在出错的时候能够进行纠正。定义9.29由0和1组成的串称为字（word），一些字的集合称为码（code），码中的字称为码字（codeword）。不在码中的字称为废码（invalid）。码中的每个二进制信号0或1称为码元（codeletter）。纠错码的纠错能力5

纠错码的纠错能力6

纠错码的纠错能力7定义9.32一个码C中所有不同码字的汉明距离的极小值为码C的最小汉明距离，记为dmin(C)。

例如，dmin(S2)=1，dmin(S3)=1，dmin(C2)=2，dmin(C3)=3。

关于编码的最小距离与其纠错能力之间的关系，有下述结论：（1）一个码C能检查出不超过k个错误的充分必要条件是dmin(C)≥k+1。（2）一个码C能纠正k个错误的充分必要条件是dmin(C)≥2k+1。对C2={00，11}，因dmin(C2)=2=1+1，故C2可检查出单个错误；对C3={001，110}，因为dmin(C3)=3=2×1+1，所以C3可纠正单个错误。而S1,S2分别包含了长度为2、3的所有码字，dmin(S2)=1，dmin(S3)=1，从而S2，S3既不能检查错误也不能纠正错误。纠错码的选择8

汉明码（HammingCode）是一种经典的线性分组纠错码，由理查德•汉明（RichardHamming）于1950年提出，主要用于检测和纠正单个比特错误。它在计算机内存、通信系统和存储设备中广泛应用，是理解纠错码理论的入门基础。例9.10设有编码S4，中每个码字为a1a2a3a4，若增加三位校验位a5，a6，a7，从而使它成为长度为7的码字a1a2a3a4a5a6a7，其中校验位a5，a6，a7应满足如下方程：也就是要满足纠错码的选择9例9.10因此，a1，a2，a3，a4一旦确定，则校验a5，a6，a7可根据上述方程唯一确定。这样，我们由S4就可以得到一个长度为7的编码C，如表9.8所示。这种编码C能发现一个错误，并能纠正一个错误。因为如果C中码字发生单错，则上述三个方程必定至少有一个等式不满足；当C中码字发生单错后，不同的字位错误可使方程中不同的等式不成立，方程中a1~a7三个等式的八种组合可对应七个码的错误以及正确无误的码字。纠错码的选择10例9.10为了讨论方便，在此建立三个谓词：这三个谓词的真假与对应等式是否成立相一致。

如果a4出错，则必有P1为真，P2,P3为假，反之亦然。依此类推，可得到如表9.9所示的纠错对照表，从表中可以看出这种编码C能纠正一个错误。纠错码的选择11例9.10我们将这个例子加以抽象，首先将方程（9.5）~（9.7）表示为矩阵形式其中X=(a1,a2,a3,a4,a5,a6,a7),0’=(0,0,0)，XT,分别是X，0’的转置矩阵，这里加法运算为模2加法。可以看出，一个编码可由矩阵H确定，而它的纠错能力可由H的特性决定。纠错码的选择12

纠错码的选择13定义9.34群码G={X|H·XT=

}称为由H生成的群码，而G中的每一个码字，称为由生成的码字，矩阵H称为一致校验矩阵。关于一致校验矩阵有如下结论：（1）一致校验矩阵H生成一个重量为p的码字的充分必要条件是在H中存在p个列向量，它们的按位加为0’。（2）由H生成的群码最小距离等于H中列向量按位加为0’的最小向量数。

这个结论建立了最小距离与列向量数之间的联系，由此可知一个群码的纠错能力可由其一致校验矩阵H中列向量按位加0’的最小列向量数决定。故只要选取适当的H就可使其生成的码达到预定的纠错