《错误检测和校正-2》由会员分享,可在线阅读,更多相关《错误检测和校正-2(29页珍藏版)》请在金锄头文库上搜索。
1、MMT,YANGZHOUDAXUE,物理科学与技术学院,第十一讲、错误检测和校正,第1节 理论基础,错误的检测和校正是通过编码来实现的。 检错编码的目的是通过解码能够发现数据在传输过程中出现了错误 纠错编码不仅能够检测到错误还能够纠正过来。 因为错误是在信道传输中产生,所以纠错或检错编码属于(通信)信道编码,而压缩编码属于信源编码。,香农定理指出:当信息传输速率(R)低于信道容量时,通过编译码,就能够使错误概率为任意小。 信道容量指信道传输信息的最大能力或传输信息的最大值,单位bit/s,香农给出高斯白噪声信道的信道容量(C)公式:,W :信道带宽 PS :信号功率 N0 :噪声功率密度,香农
2、第二定理没有明确指出编译码方法。,纠(检)错码类型:,本讲只介绍几种简单的线性分组码和交织码的概念。,分组码的表示: 分组码将k个码元(一般为二进制数)组成一个信息组。例如k=3,则有000,001,111八种信息组。编码器根据信息组按某种规律产生r个码元(校验元),形成一个长n=k+r的码字,成为(n,k)分组码。n表示码长,k表示信息位的数目。 例1:重复码 规则:k=1,如果信息码字为1,则发送111。 如果信息码子为0,则发送000。 这是一个(3,1)分组码。 例2:一个(4,2)分组码(c3,c2,c1,c0),信息码字(c3,c2)可能为00,01,10,11,校验码字定义为c1
3、=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 111 1111,检错和纠错 重复码可以检出错两位和错一位的情况,可以纠正错一位的情况。 重复码译码规则: 000 0 00
4、1 0 010 0 011 1 100 0 101 1 110 1 1 奇偶校验码仅是检错码,且只能检出错奇数位的情况。,信道出错的类型,噪声对传输码元的影响独立,即每一个差错的出现与否与其前后是否有差错无关。 这样的信道称为无记忆信道。 因为和前后无关,出现错误的机会可以用独立的概率来表示(Pe)。如果仅考虑0和1,又有1错误的变成0和0错误的变成1的概率相等,则这样的信道称为BSC(Binary Symmetric Channel,二进制对称信道)。表示为下图:,若信道的错误不是独立出现,而是成串的出现,则称为有记忆信道。可以采取交织编码技术解决。 实际的信道两种错误都可能发生。,差错控制
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=9) 设除数为r+1位,例10011(r=4) 则余数最多为r位。 令:被除数=待编码的数2r,1
7、101011010000,n=k+r位 模2除法:,则:1101011010000=10011110000101+1111 有:1101011010000+1111=10011110000101 1101011011111=10011110000101 1101011011111就是CRC编码的结果,最后的1111就是CRC校验码。 解码:看收到的数据能否被10011整除。如果可以,认为没有出错;如果不能,通知发端重发。 上面的例子是一个(13,9)检错码。,第3节 混合纠错码举例,一个(7,3)码:,校验位生成规则:,合法码字:,合法码字生成规则:,G为生成矩阵,H为校验矩阵,当校验结果为0
8、,则认为没有错,否则有错,证明:,观察校验矩阵H,H的每一列都不一样 任意两列的和都不等于H的其它列 第1列加第2列等于第4列加第7列 第4,5,6列的和等于第1列 第1,4,5,6列的和等于0,出错假设:,E可能有0000001到1111111共127种情况,E称为出错图样。,校验:,有1位错:,S不为0,一定有错,且根据S的具体值知道哪一位出错。,有2位错:,S不为0,一定有错,但不知哪2位出错。 因为任意两列的和都不等于H的其它列,所以不会误认为1位错。,有3位错:,S不为0,一定有错。 会误认为第1位错,从而误纠错。,有4位错:,S为0,误认为没有错。,上例编码的检纠错能力: 1、能够
9、检出1位2位3位错。 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的基础上对行和列做交织处理。,本章小节,检错纠错编码属于信道编码。 选用什么编码算法首先需要知道信道的特性。 从信息的角度说,纠错编码是通过加大数据量来换取准确率。 交织技术的目的是为了把可能集中发生的错误分散开。 检错纠错编码可以连用。,