错误检测和校正

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

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

3、如果信息码字为1，则发送111。 如果信息码子为0，则发送000。 这是一个（3，1）分组码。 例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 00

4、1 0011 010 0101 011 0110 100 1001 101 1010 110 1100 111 1111 检错和纠错 重复码可以检出错两位和错一位的情况，可以纠正错一位的情况。 重复码译码规则： 000 0 001 0 010 0 011 1 100 0 101 1 110 1 1 111奇偶校验码仅是检错码，且只能检出错奇数位的情况。 信道出错的类型 噪声对传输码元的影响独立，即每一个差错的出现与否与 其前后是否有差错无关。 这样的信道称为无记忆信道。 因为和前后无关，出现错误的机会可以用独立的概率来表 示（Pe）。如果仅考虑0和1，又有1错误的变成0和0错误的变 成1的概率

5、相等，则这样的信道称为BSC（Binary Symmetric Channel，二进制对称信道）。表示为下图： 1 0 1 0 1-Pe Pe Pe 1-Pe 若信道的错误不是独立出现，而是成串的出现，则称为有 记忆信道。可以采取交织编码技术解决。 实际的信道两种错误都可能发生。 差错控制系统分类 一、前向纠错（FEC）方式 FEC(Forward Error Control)方式是发端发送能够纠错的码， 收端通过译码器纠正这些错误。例如重复码。但不能保证百分之 百纠错。 二、重传反馈（ARQ）方式 ARQ(Automatic Repeat Request)方式是发端发送能够检错 的码，收端发

6、现有错误时，给发端发送一个出错信号要求重发。 例如奇偶校验码。也不能保证百分之百检错。 三、混合纠错（HEC）方式 HEC(Hybird Error Control)方式是上述两种方式的结合。 发送端发送的码即能检错，又能纠错。译码器如果发现错误可以 纠正就自动纠正，如果错误不能纠正，则通知发端重发。 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，

7、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=9） 设除数为r+1位，例10011(r=4) 则余数最多为r位。 令：被除数=待编码的数2r，1101011010000，n=k+r位 模2除法： 110000101 10011 1101011010000 10011 010011 010011 00000010100 10011 0011100 10011 1111 则：1101011010000=10011110000101+1111

8、有：1101011010000+1111=10011110000101 1101011011111=10011110000101 1101011011111就是CRC编码的结果，最后的1111就是CRC校验码。 解码：看收到的数据能否被10011整除。如果可以，认为没有出错； 如果不能，通知发端重发。 上面的例子是一个（13，9）检错码。 第3节 混合纠错码举例 一个（7，3）码： 2103210 (, ,)m m m c c c c 320 2210 121 010 cmm cmmm cmm cmm 校验位生成规则： 合法码字： 0000000 0011101 0100111 0111010

9、 1001110 1010011 1101001 1110100 2103210 , ,m m m c c c c 合法码字生成规则： 2103210 210 210 , 1001110 , 0100111 0011101 , mmmcccc mmm mmmG G为生成矩阵 320 2210 121 010 cmm cmmm cmm cmm 203 2102 211 100 0 0 0 0 mmc mmmc mmc mmc 22 11 00 33 22 11 00 0 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 m

10、m mm mm Hcc cc cc cc H为校验矩阵，当校验结果为0，则认为没有错，否则有错 证明： 4 3 3 4 0 0 T T HG GH 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 H 观察校验矩阵H H的每一列都不一样 任意两列的和都不等于H的其它列 第1列加第2列等于第4列加第7列 第4，5，6列的和等于第1列 第1，4，5，6列的和等于0 2 1 0 3 2 1 0 m m m cE c c c 出错假设： E可能有0000001到1111111共127种情况，E称为出错图样。 2 1 0 3 2 1 0 0

11、0 () 0 0 m m m HcEH EH ES c c c 校验： 有1位错： 1000000 0100000 0010000 0 , 0 , 0 , 1 , 0 , 0 , 0 0000100 0000010 0000001 E 1011000 1011000 1110100 1110100, 1100010 1100010 0110001 0110001 SHEE S不为0，一定有错，且根据S的具体值知道哪一位出错。 有2位错： 1 1 0 0 0 0 0 E 1 1011000 0 1110100 0 1100010 1 0110001 SHEE 0 0 0 1 0 0 1 E 1

12、1011000 0 1110100 0 1100010 1 0110001 SHEE S不为0，一定有错，但不知哪2位出错。 因为任意两列的和都不等于H的其它列，所以不会误认为1位错。 有3位错： 1 1011000 1 1110100 1 1100010 0 0110001 SHEE 0 0 0 1 1 1 0 E 1 1011000 1 1110100 1 1100010 0 0110001 SHEE S不为0，一定有错。 会误认为第1位错，从而误纠错。 1 0 0 0 0 0 0 E 有4位错： 0 1011000 0 1110100 0 1100010 0 0110001 SHEE 1 0 0 1 1 1 0 E S为0，误认为没有错。 上例编码的检纠错能力： 1、能够检出1位2位3位错。 2、能够纠正1位错。 3、能够对2位错不误纠正。 4、对3位错会误纠。 5、对4位错会误检。 S等于H中和错误图样相对应的列之和。 可以从H得出编码的纠错能力。 该码可以用于HCE方式。 在实际应用中，比特差错经常成串发生，而信道编码仅在检 测和校正单个差错和不太长的差错串时才最有效。 为了纠正这些成串发生的比特差错，交织技术对已编码的信 号按一定规则重新排列，解交织后突发性错误在位置上被分散， 使其类似于独立发生的随机错误。 交织编码和纠错编码连用。一般来说，在发端先对数