错误检测和校正

1、MMTMMTYANGZHOUDAXUE物理科学与技术学院物理科学与技术学院第十一讲、错误检测和校正第十一讲、错误检测和校正第1节 理论基础 错误的检测和校正是通过编码来实现的。 检错编码的目的是通过解码能够发现数据在传输过程中出现了错误 纠错编码不仅能够检测到错误还能够纠正过来。 因为错误是在信道传输中产生，所以纠错或检错编码属于（通信）信道编码，而压缩编码属于信源编码。信源信源编码信道编码调制信道解调信道译码信源译码信宿噪声源 香农定理指出：当信息传输速率（R）低于信道容量时，通过编译码，就能够使错误概率为任意小。 信道容量指信道传输信息的最大能力或传输信息的最大值，单位bit/s，香农给出

2、高斯白噪声信道的信道容量（C）公式：20log (1)(/ )sPCWbit sWNW ：信道带宽PS :信号功率N0 :噪声功率密度香农第二定理没有明确指出编译码方法。纠（检）错码类型：本讲只介绍几种简单的线性分组码和交织码的概念。分组码的表示： 分组码将k个码元（一般为二进制数）组成一个信息组。例如k=3，则有000，001，111八种信息组。编码器根据信息组按某种规律产生r个码元（校验元），形成一个长n=k+r的码字，成为（n,k）分组码。n表示码长，k表示信息位的数目。例1：重复码 规则：k=1，如果信息码字为1，则发送111。 如果信息码子为0，则发送000。 这是一个（3，1）分组

3、码。例2：一个（4，2）分组码（c3,c2,c1,c0），信息码字(c3,c2)可能为00，01，10，11，校验码字定义为c1=c2,c0=c3+c2。则码字可能为：0000，0111，1001，1110。例1和例2中的发送码字为合法码字，如果接受端收到非法码字则说明发生错误。例3：奇偶校验码 规则：在k个信息源后加上1位校验元，使得n=k+1个码元中0(1)的个数为奇（偶）数个。例如一个（4，3）码，使0的个数为偶数个，则：Messages codewords 000 0000 001 0011 010 0101 011 0110 100 1001 101 1010 110 1100 11

4、1 1111检错和纠错重复码可以检出错两位和错一位的情况，可以纠正错一位的情况。重复码译码规则：000 0001 0010 0011 1100 0101 1110 1 1奇偶校验码仅是检错码，且只能检出错奇数位的情况。信道出错的类型 噪声对传输码元的影响独立，即每一个差错的出现与否与其前后是否有差错无关。 这样的信道称为无记忆信道。 因为和前后无关，出现错误的机会可以用独立的概率来表示（Pe）。如果仅考虑0和1，又有1错误的变成0和0错误的变成1的概率相等，则这样的信道称为BSC（Binary Symmetric Channel，二进制对称信道）。表示为下图：10101-PePePe1-Pe

5、若信道的错误不是独立出现，而是成串的出现，则称为有记忆信道。可以采取交织编码技术解决。 实际的信道两种错误都可能发生。差错控制系统分类一、前向纠错（FEC）方式 FEC(Forward Error Control)方式是发端发送能够纠错的码，收端通过译码器纠正这些错误。例如重复码。但不能保证百分之百纠错。二、重传反馈（ARQ）方式 ARQ(Automatic Repeat Request)方式是发端发送能够检错的码，收端发现有错误时，给发端发送一个出错信号要求重发。例如奇偶校验码。也不能保证百分之百检错。三、混合纠错（HEC）方式 HEC(Hybird Error Control)方式是上述两

6、种方式的结合。发送端发送的码即能检错，又能纠错。译码器如果发现错误可以纠正就自动纠正，如果错误不能纠正，则通知发端重发。 CRC,奇偶校验码和重复码都不属于这类编码。第2节 CRC（Cyclic Redundancy Code）检错编码基本思想：1、除法被除数x，除数y，商z，余数C。有： x=yz+c x-c=yz所以，x-c肯定可以被y整除。2、二进制数的模2加减法定义：0+0=0，1+0=1，0+1=1，1+1=0 0-0=0，1-0=1，0-1=-1=1，1-1=0可以看到模2加法和减法是一样的。由模2加减法可以定义模2的乘除法。编码： 设待编码的数据为k位，例110101101（k=

7、9） 设除数为r+1位，例10011(r=4) 则余数最多为r位。 令：被除数=待编码的数2r，1101011010000，n=k+r位 模2除法：11000010110011 11010110100001001101001101001100000010100100110011100100111111则：1101011010000=10011110000101+1111有：1101011010000+1111=10011110000101 1101011011111=100111100001011101011011111就是CRC编码的结果，最后的1111就是CRC校验码。解码：看收到的数据能

8、否被10011整除。如果可以，认为没有出错；如果不能，通知发端重发。上面的例子是一个（13，9）检错码。第3节 混合纠错码举例一个（7，3）码：2103210(, ,)m m m c c c c3202210121010cmmcmmmcmmcmm校验位生成规则：合法码字：000000000111010100111011101010011101010011110100111101002103210, , ,m m m c c c c合法码字生成规则：2103210210210,1001110, 01001110011101,mmmccccmmmmmmGG为生成矩阵3202210121010cmm

9、cmmmcmmcmm20321022111000000mmcmmmcmmcmmc2211003322110001 0 1 1 0 0 001 1 1 0 1 0 001 1 0 0 0 1 000 1 1 0 0 0 1mmmmmmHccccccccH为校验矩阵，当校验结果为0，则认为没有错，否则有错证明：4 33 400TTHGGH1 0 1 1 0 0 01 1 1 0 1 0 01 1 0 0 0 1 00 1 1 0 0 0 1H 观察校验矩阵HH的每一列都不一样任意两列的和都不等于H的其它列第1列加第2列等于第4列加第7列第4，5，6列的和等于第1列第1，4，5，6列的和等于0210

10、3210mmmcEccc出错假设：E可能有0000001到1111111共127种情况，E称为出错图样。210321000()00mmmHcEH EH ESccc校验：有1位错：1000000010000000100000 , 0 , 0 , 1 , 0 , 0 , 0000010000000100000001E 1011000101100011101001110100,1100010110001001100010110001SHEE S不为0，一定有错，且根据S的具体值知道哪一位出错。有2位错：1100000E 11011000011101000110001010110001SHEE 000

11、1001E 11011000011101000110001010110001SHEE S不为0，一定有错，但不知哪2位出错。因为任意两列的和都不等于H的其它列，所以不会误认为1位错。有3位错：11011000111101001110001000110001SHEE 0001110E 11011000111101001110001000110001SHEE S不为0，一定有错。会误认为第1位错，从而误纠错。1000000E 有4位错：01011000011101000110001000110001SHEE 1001110E S为0，误认为没有错。上例编码的检纠错能力：1、能够检出1位2位3位错。

12、2、能够纠正1位错。3、能够对2位错不误纠正。4、对3位错会误纠。5、对4位错会误检。S等于H中和错误图样相对应的列之和。可以从H得出编码的纠错能力。该码可以用于HCE方式。 在实际应用中，比特差错经常成串发生，而信道编码仅在检测和校正单个差错和不太长的差错串时才最有效。 为了纠正这些成串发生的比特差错，交织技术对已编码的信号按一定规则重新排列，解交织后突发性错误在位置上被分散，使其类似于独立发生的随机错误。 交织编码和纠错编码连用。一般来说，在发端先对数据进行纠错编码，然后再进行交积处理。第4节 交织编码技术交织的原理图：光盘用到的编码技术：CRC码RS码：也是一个（n,k）线性分组码。但是它有纠正(n-k)/2个错误的能力。CIRC码：RS编码和交织技术相结合形成CIRC码，用在CD-ROM中。RSPC码:基本思想用两次RS编码对数据矩阵的行和列编码，使得误码率进一步降低。ECC码:在RSPC的基础上对行和列做交织处理。n检错纠错编码属于信道编码。n选用什么编码算法首先需要知道信道的特性。n从信息的角度说，纠错编码是通过加大数据量来换取准确率。n交织技