信道编码纠错码课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,信道编码纠错码,*,单击此处编辑母版标题样式,*,信道编码纠错码,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信道编码,第,6,章,1,信道编码纠错码,6.1,纠错编译码的基本原理与分析方法,6.2 线性分组码,6.3 卷积码,内容,2,信道编码纠错码,信源编码,提高数字信号,有效性,将信源的模拟信号转变为数字信号,降低数码率,压缩传输频带(数据压缩),信道编码,提高数字通信,可靠性,数字信号在信道的传输过程中,由于实际,信道,的,传输特性不理想,以及存在加性,噪声,在接收端往往会产生,误码,。,编码,3,信道编码纠错码,6.1 纠错编译码的基本原理与分析方法,4,信道编码纠错码,6.1.1 差错和差错控制系统分类,差错率,是衡量传输质量的重要指标之一,它有几种不同的定义。,码元差错率/符号差错率,指在传输的,码元,总数中发生差错的码元数所占的比例(平均值),简称,误码率,。,是指,信号,差错概率,比特差错率 /比特误码率,：,在传输的,比特,总数中发生差错的比特数所占比例,是指,信息,差错概率,对,二进制,传输系统,符号差错等效于比特差错;对多进制系统,一个符号差错对应多少比特差错却难以确定,5,信道编码纠错码,差错率,根据不同的应用场合对差错率有不同的要求:,在电报传送时,允许的比特差错率约为:,10,4,10,5,；,计算机数据传输,一般要求比特差错率小于:,10,8,10,9,；,在遥控指令和武器系统的指令系统中,要求有更小的误比特率或码组差错率,6,信道编码纠错码,差错图样,为定量地描述信号的差错,定义,差错图样E,E=CR,(模M ),最常用的二进制码可当作特例来研究,其差错图样等于收码与发码的模2加,即,E = CR,或,C = RE,设发送的码字,C,1 1 1 1 1 1 1 1 1 1,接收的码字,R,1 0 0 1 0 0 1 1 1 1,差错的图样,E,0 1 1 0 1 1 0 0 0 0,差错图样中的“1”既是符号差错也是比特差错,差错的个数叫,汉明距离,。,0:传输中无错,1:传输中有错,7,信道编码纠错码,差错图样,随机差错,：,差错是,相互独立,的,不相关,存在这种差错的信道是无记忆信道或随机信道,突发差错,：,指,成串,出现的错误,错误与错误间有相关性,一个差错往往要影响到后面一串字,E,:,0 0 1 0 0 1 0 0 0 0 0 0,1 0 0 1 1 1 0 0 0 0 0 0 0,突发长度= 4,突发长度= 6,8,信道编码纠错码,纠错码分类,从功能角度讲,差错码分为检错码和纠错码,检错码,：用于发现差错,纠错码,：能自动纠正差错,纠错码与检错码在理论上没有本质区别,只是应用场合不同,而侧重的性能参数也不同。,9,信道编码纠错码,纠错码分类,按照对信息序列的处理方法,有,分组码,和,卷积码,分组码：,将,k,个信息码元分成一组,由这,k,个码元按照一定规则产生,r,个监督码元,组成长度n = k + r的码字,卷积码,：,先将信息序列分组,不同的是编解码运算不仅与本组信息有关,而且还与,前面若干组有关,。,k,k,010 101 010 001 110,010xxxx 101xxxx 010 xxxx,r,n,r,10,信道编码纠错码,纠错码分类,按照码元与原始信息位的关系,分为,线性码,：所有码元均是原始信息元的,线性组合,编码器不带反馈回路。,非线性,码,：码元并不都是信息元的线性组合,可能还与前面已编的码元有关,编码器可能含反馈回路。,由于非线性码的分析比较困难,早期实用的纠错码多为线性码,但当今发现的很多好码恰恰是非线性码。,11,信道编码纠错码,纠错码分类,按照适用的差错类型,分成:,纠随机差错码:,用于随机差错信道,其纠错能力用码组内允许的独立差错的个数来衡量。,纠突发差错码:,针对突发差错而设计,其纠错能力主要用可纠突发差错的最大长度来衡量,12,信道编码纠错码,差错控制系统分类,前向纠错(FEC),：,发送端的信道编码器将信息码组编成具有一定,纠错能力,的码。,接收端信道译码器对接收码字进行译码,若传输中产生的差错数目在码的纠错能力之内时,译码器对差错进行定位并加以纠正。,13,信道编码纠错码,差错控制系统分类,自动请求重发(ARQ)：,发端发送,检错码,，,收端译码器判断当前码字传输是否出错；,当有错时按某种协议通过一个,反向信道,请求发送端重传已发送的码字(全部或部分)。,14,信道编码纠错码,差错控制系统分类,混合纠错(HEC)：,是FEC与ARQ方式的结合。,发端发送同时具有自动纠错和检测能力的码组,收端收到码组后,检查差错情况,如果差错在码的纠错能力以内,则自动进行纠正。,如果信道干扰很严重,错误很多,超过了码的纠错能力,但能检测出来,则经反馈信道请求发端重发这组数据。,信息反馈(IRQ)：,收端把收到的数据,原封不动地通过反馈信道送回到发端,发端比较发的数据与反馈来的数据,从而发现错误,并且把错误的消息再次传送,直到发端没有发现错误为止。,15,信道编码纠错码,检错与纠错原理,0,:晴,1,:雨,若10,01。收端无法发现错误,00,晴,10,01,11,00,11,雨,能发现,一个,错误,禁用码组,插入,1位监督码,后具有,检出1位错码,的能力,但不能予以纠正。,16,信道编码纠错码,检错与纠错原理,000,晴,010,001,111,000,111,雨,晴,在只有,1位错码,的情况下,可以判决哪位是错码并予以,纠正,可以,检,出2位,或2位以下的错码。,100,011,101,110,雨,17,信道编码纠错码,检错与纠错原理,最大似然译码：,将接收到的码字译码为与它,差别最小,的,许用码字,并且认为这个许用码字就是它所对应的发送码字,从而在码字的纠错能力内实现自动纠错。,纠错编码之所以具有检错、纠错能力,是因为在信息码元之外加入了,监督码,。监督码不载信息,只是用来监督信息码在传输中有无差错。,纠错编码所提高的可靠性,是以牺牲信道利用率为代价换取的。,监督码,引入,越多,检错、纠错,能力,越强,但信道的传输效率下降也越多。,18,信道编码纠错码,信道编码,在被传输信息中附加一些,冗余码,即,监督码元,利用附加码元与信息码元间的,约束关系,加以校验,以,检测和纠正错误,。,信源,编码,减少,了,冗余度,冗余度是随机的、无规律的,信道,编码,增加,了,冗余度,冗余度是特定的、有规律的,故可利用其在接收端进行检错和纠错。,信道编码,19,信道编码纠错码,传输,冗余比特,必然要动用,冗余的资源,。,时间,：,比如一个比特重复发几次,或一段消息重复发几遍,或根据收端的反馈重发受损信息组。,频带,：,插入冗余比特后传输效率下降,若要保持有用信息的速率不变,方法之一是增大符号传递速率(波特率),结果就占用了更大的带宽。,功率,：,采用多进制符号,用8进制ASK符号代替4进制ASK符号来传送2比特信息,可腾出位置另传1冗余比特。,8进制ASK符号的平均功率肯定比4进制时要大,这就是动用冗余的功率资源来传输冗余比特。,设备复杂度,：,加大码长,采用网格编码调制,是在功率、带宽受限信道中实施纠错编码的有效方法,代价是算法复杂度的提高,需动用设备资源。,20,信道编码纠错码,信道编码的基本思想,信道编码,按一定规则给数字序列,m,增加一些,多余,的码元,使不具有规律性的信息序列,m,变换为具有某种规律性的数码序列,C,；,码序列中的,信息序列码元,与,多余码元,之间是,相关,的；,信道译码器利用这种,预知的,编码规则译码。检验接收到的数字序列,R,是否符合既定的,规则,从而发现,R,中是否有错,或者纠正其中的差错；,根据,相关性,来检测/,发现,和,纠正,传输过程中产生的差错就是信道编码的基本思想。,21,信道编码纠错码,码距与检错、纠错能力,纠错编码的,检错纠错能力,要取决于码组的,码距,码距越大,检错、纠错能力越强。,汉明距离,：,二个码组对应码位码元不同的个数。,最小码距d,min,：,一个码组的集合中任意二个码组间的最小汉明距离。,码重W,：,码组中非0的数目。,22,信道编码纠错码,码距与检错、纠错能力,定理：若纠错码的最小距离为,d,min,，,可以检测出任意小于等于,l,=,d,min,1,个差错,可以纠正任意小于等于 个差错,可以,检测,出任意小于等于,l,同时纠正,小于等于,t,个差错，,其中,l,、,t,满足：,l,+,t,d,min1,t,l,23,信道编码纠错码,检错、纠错能力,为检查出,个错误，要求最小码距为,为纠正 个错误，要求最小码距为,为纠正 个错误，同时检查出 个错误，要求最小码距为,24,信道编码纠错码,纠错检错示意图,25,信道编码纠错码,编码效率,编码效率,：,一个组中信息所占的比重,k：信息码元的数目,n：编码组码元的总数目 n = k+ r,r：监督码元的数目,26,信道编码纠错码,信道编码,第,6,章,27,信道编码纠错码,6.1,纠错编译码的基本原理与分析方法,6.2 线性分组码,6.3 卷积码,内容,28,信道编码纠错码,信源编码,提高数字信号,有效性,将信源的模拟信号转变为数字信号,降低数码率,压缩传输频带(数据压缩),信道编码,提高数字通信,可靠性,数字信号在信道的传输过程中,由于实际,信道,的,传输特性不理想,以及存在加性,噪声,在接收端往往会产生,误码,。,编码,29,信道编码纠错码,6.1 纠错编译码的基本原理与分析方法,30,信道编码纠错码,6.1.1 差错和差错控制系统分类,差错率,是衡量传输质量的重要指标之一,它有几种不同的定义。,码元差错率/符号差错率,指在传输的,码元,总数中发生差错的码元数所占的比例(平均值),简称,误码率,。,是指,信号,差错概率,比特差错率 /比特误码率,：,在传输的,比特,总数中发生差错的比特数所占比例,是指,信息,差错概率,对,二进制,传输系统,符号差错等效于比特差错;对多进制系统,一个符号差错对应多少比特差错却难以确定,31,信道编码纠错码,差错率,根据不同的应用场合对差错率有不同的要求:,在电报传送时,允许的比特差错率约为:,10,4,10,5,；,计算机数据传输,一般要求比特差错率小于:,10,8,10,9,；,在遥控指令和武器系统的指令系统中,要求有更小的误比特率或码组差错率,32,信道编码纠错码,差错图样,为定量地描述信号的差错,定义,差错图样E,E=CR,(模M ),最常用的二进制码可当作特例来研究,其差错图样等于收码与发码的模2加,即,E = CR,或,C = RE,设发送的码字,C,1 1 1 1 1 1 1 1 1 1,接收的码字,R,1 0 0 1 0 0 1 1 1 1,差错的图样,E,0 1 1 0 1 1 0 0 0 0,差错图样中的“1”既是符号差错也是比特差错,差错的个数叫,汉明距离,。,0:传输中无错,1:传输中有错,33,信道编码纠错码,差错图样,随机差错,：,差错是,相互独立,的,不相关,存在这种差错的信道是无记忆信道或随机信道,突发差错,：,指,成串,出现的错误,错误与错误间有相关性,一个差错往往要影响到后面一串字,E,:,0 0 1 0 0 1 0 0 0 0 0 0,1 0 0 1 1 1 0 0 0 0 0 0 0,突发长度= 4,突发长度= 6,34,信道编码纠错码,纠错码分类,从功能角度讲,差错码分为检错码和纠错码,检错码,：用于发现差错,纠错码,：能自动纠正差错,纠错码与检错码在理论上没有本质区别,只是应用场合不同,而侧重的性能参数也不同。,35,信道编码纠错码,纠错码分类,按照对信息序列的处理方法,有,分组码,和,卷积码,分组码：,将,k,个信息码元分成一组,由这,k,个码元按照一定规则产生,r,个监督码元,组成长度n = k + r的码字,卷积码,：,先将信息序列分组,不同的是编解码运算不仅与本组信息有关,而且还与,前面若干组有关,。,k,k,010 101 010 001 110,010xxxx 101xxxx 010 xxxx,r,n,r,36,信道编码纠错码,纠错码分类,按照码元与原始信息位的关系,分为,线性码,：所有码元均是原始信息元的,线性组合,编码器不带反馈回路。,非线性,码,：码元并不都是信息元的线性组合,可能还与前面已编的码元有关,编码器可能含反馈回路。,由于非线性码的分析比较困难,早期实用的纠错码多为线性码,但当今发现的很多好码恰恰是非线性码。,37,信道编码纠错码,纠错码分类,按照适用的差错类型,分成:,纠随机差错码:,用于随机差错信道,其纠错能力用码组内允许的独立差错的个数来衡量。,纠突发差错码:,针对突发差错而设计,其纠错能力主要用可纠突发差错的最大长度来衡量,38,信道编码纠错码,差错控制系统分类,前向纠错(FEC),：,发送端的信道编码器将信息码组编成具有一定,纠错能力,的码。,接收端信道译码器对接收码字进行译码,若传输中产生的差错数目在码的纠错能力之内时,译码器对差错进行定位并加以纠正。,39,信道编码纠错码,差错控制系统分类,自动请求重发(ARQ)：,发端发送,检错码,，,收端译码器判断当前码字传输是否出错；,当有错时按某种协议通过一个,反向信道,请求发送端重传已发送的码字(全部或部分)。,40,信道编码纠错码,差错控制系统分类,混合纠错(HEC)：,是FEC与ARQ方式的结合。,发端发送同时具有自动纠错和检测能力的码组,收端收到码组后,检查差错情况,如果差错在码的纠错能力以内,则自动进行纠正。,如果信道干扰很严重,错误很多,超过了码的纠错能力,但能检测出来,则经反馈信道请求发端重发这组数据。,信息反馈(IRQ)：,收端把收到的数据,原封不动地通过反馈信道送回到发端,发端比较发的数据与反馈来的数据,从而发现错误,并且把错误的消息再次传送,直到发端没有发现错误为止。,41,信道编码纠错码,检错与纠错原理,0,:晴,1,:雨,若10,01。收端无法发现错误,00,晴,10,01,11,00,11,雨,能发现,一个,错误,禁用码组,插入,1位监督码,后具有,检出1位错码,的能力,但不能予以纠正。,42,信道编码纠错码,检错与纠错原理,000,晴,010,001,111,000,111,雨,晴,在只有,1位错码,的情况下,可以判决哪位是错码并予以,纠正,可以,检,出2位,或2位以下的错码。,100,011,101,110,雨,43,信道编码纠错码,检错与纠错原理,最大似然译码：,将接收到的码字译码为与它,差别最小,的,许用码字,并且认为这个许用码字就是它所对应的发送码字,从而在码字的纠错能力内实现自动纠错。,纠错编码之所以具有检错、纠错能力,是因为在信息码元之外加入了,监督码,。监督码不载信息,只是用来监督信息码在传输中有无差错。,纠错编码所提高的可靠性,是以牺牲信道利用率为代价换取的。,监督码,引入,越多,检错、纠错,能力,越强,但信道的传输效率下降也越多。,44,信道编码纠错码,信道编码,在被传输信息中附加一些,冗余码,即,监督码元,利用附加码元与信息码元间的,约束关系,加以校验,以,检测和纠正错误,。,信源,编码,减少,了,冗余度,冗余度是随机的、无规律的,信道,编码,增加,了,冗余度,冗余度是特定的、有规律的,故可利用其在接收端进行检错和纠错。,信道编码,45,信道编码纠错码,传输,冗余比特,必然要动用,冗余的资源,。,时间,：,比如一个比特重复发几次,或一段消息重复发几遍,或根据收端的反馈重发受损信息组。,频带,：,插入冗余比特后传输效率下降,若要保持有用信息的速率不变,方法之一是增大符号传递速率(波特率),结果就占用了更大的带宽。,功率,：,采用多进制符号,用8进制ASK符号代替4进制ASK符号来传送2比特信息,可腾出位置另传1冗余比特。,8进制ASK符号的平均功率肯定比4进制时要大,这就是动用冗余的功率资源来传输冗余比特。,设备复杂度,：,加大码长,采用网格编码调制,是在功率、带宽受限信道中实施纠错编码的有效方法,代价是算法复杂度的提高,需动用设备资源。,46,信道编码纠错码,信道编码的基本思想,信道编码,按一定规则给数字序列,m,增加一些,多余,的码元,使不具有规律性的信息序列,m,变换为具有某种规律性的数码序列,C,；,码序列中的,信息序列码元,与,多余码元,之间是,相关,的；,信道译码器利用这种,预知的,编码规则译码。检验接收到的数字序列,R,是否符合既定的,规则,从而发现,R,中是否有错,或者纠正其中的差错；,根据,相关性,来检测/,发现,和,纠正,传输过程中产生的差错就是信道编码的基本思想。,47,信道编码纠错码,码距与检错、纠错能力,纠错编码的,检错纠错能力,要取决于码组的,码距,码距越大,检错、纠错能力越强。,汉明距离,：,二个码组对应码位码元不同的个数。,最小码距d,min,：,一个码组的集合中任意二个码组间的最小汉明距离。,码重W,：,码组中非0的数目。,48,信道编码纠错码,码距与检错、纠错能力,定理：若纠错码的最小距离为,d,min,，,可以检测出任意小于等于,l,=,d,min,1,个差错,可以纠正任意小于等于 个差错,可以,检测,出任意小于等于,l,同时纠正,小于等于,t,个差错，,其中,l,、,t,满足：,l,+,t,d,min1,t,l,49,信道编码纠错码,编码效率,编码效率,：,一个组中信息所占的比重,k：信息码元的数目,n：编码组码元的总数目 n = k+ r,r：监督码元的数目,50,信道编码纠错码,检错码,奇偶校验码(,n,，,n,-1)(,k,+1，,k,),偶校验码字,51,信道编码纠错码,6.1 概述,误码分类,随机信道,噪声引入的随机误码，均匀分布,突发信道,由干扰、快衰落引起的突发误码,如何减少误码？,从信源编码看，误码引起的性能恶化尽可能小，容错技术,从传输看，可采用抗干扰能力强的调制方式，信道特性不理想可采用均衡。特别需要差错控制技术。数字通信中，要求误码率10,8,以下，必须采用差错控制。,52,信道编码纠错码,二元码产生误码的情况,53,信道编码纠错码,6.1.1 差错控制分类,需要双向信道，和前向信道有相同的通信容。,引入较大的停顿（不实时）。,可以纠正任何错误。,1.,反馈检验法,54,信道编码纠错码,2. 检错重发法（ARQ）,自动请求重发,也需要反向信道，但容量可以降低，也会引入停顿,55,信道编码纠错码,3. 前向纠错（FEC）,不需要双向信道,不会引入停顿,靠纠错编码,56,信道编码纠错码,4. 混合纠错（HEC）,需要反馈信道,可能会引入停顿,靠纠错编码和检错码,57,信道编码纠错码,6.1.2 差错控制编码的基本原理,如用三位二进制编码来代表八个字母,000 A100E,001 B101F,010C110G,011D111H,不管哪一位发生错误，都会使传输字母错误,如用三位字母传四个字母,000 A011B101 C110D,发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。,58,信道编码纠错码,差错控制编码,如用三位字母传二个字母,000 A 111B,检二个错误，纠正一个错误。,结论,具有检错或纠错的码组，其所用的比特数必须大于信息码组原来的比特数,引入余度。,59,信道编码纠错码,码重、码距,码重(weight),一,个码组中“1”的数目,码距(distance),两个码组之间对应位置上1、0不同的位数，又叫汉明(Hamming)距。,10 1 1 0 码重：3,01 1 0 0 2,距离：3,60,信道编码纠错码,检错、纠错能力,为,检查出,个错误，要求最小码距为,为纠正 个错误，要求最小码距为,为纠正 个错误，同时检查出 个错误，要求最小码距为,61,信道编码纠错码,62,信道编码纠错码,6.1.3. 差错控制编码分类,按功能分,检错码,纠错码,纠删码,（发现不可纠正的错误时，可发出指示或删除）,按信息码元和监督码元之间的校验关系分,线性码,非线性码,按信息码元和监督码元之间的约束方式分,分组码,卷积码,63,信道编码纠错码,香农理 纠错码的理论基础,香农定理,存在噪声干扰的信道，若信道容量为C，只要发送端以低于C的速率R发送信息（R为输入到编码器的二进制码元速率），则一定存在一种编码方式，使编码的错误概率随着码长n的增加将按指数下降到任一的值，即,P120,结论,如码长及发送信息速率一定，可以通过增大信道容量，使P减小。,如在信道容量及发送信息速率一定，可以通过增加码长，使错误概率下降。,64,信道编码纠错码,分组码,表示： (n,k),n : 帧长k/n : 编码效率,特点,监督码只用来监督本帧中的信息位,分类,线性码 信息码与监督码之间为线性关系,非线性码 不存在线性关系,65,信道编码纠错码,奇偶监督码,偶监督,奇监督,如果以上关系被破坏，则出现错误，因此能检查出奇数个错误，但不能检测偶数个错误。,最小码距为,d,min,=2,这种码检错能力不高，采用什么方法提高呢？,66,信道编码纠错码,水平奇偶监督码和水平垂直监督码,又叫 二维奇偶监督码,水平奇偶监督码,检码字按行排成方阵，每行采用奇偶监督码，发送时按列的顺序传送，接收时仍将码字排列成发送时方阵形式，然后按行进行奇偶校验。,在不增加冗余度时，不仅发现某一行上奇数个错误，而且也能发现不大于方阵行数的突发错误。,水平垂直奇偶监督码,不仅对行进行奇偶校验，而且也对列进行奇偶校验。,67,信道编码纠错码,分组码 (1),分组码的监督方程,矩阵形式,6.2 线性分组码,68,信道编码纠错码,分组码 (2),监督矩阵,H矩阵称为典型形式，各行一定是线性无关的。而一个非典型形式的经过运算可以化成典型形式，通过监督矩阵可以知道监督码和信息码的监督关系。,69,信道编码纠错码,分组码 (3),生成矩阵,，通过生成矩阵可以得到生成码组。,如果输入码组为 0011,70,信道编码纠错码,分组码 (4),由这种方式得到的生成矩阵称为典型生成矩阵，由它产生的分组码必定为系统码，也就是信息码字保持不变，监督位附加其后，每行一定是线性无关的，每行都是一个生成码组。,71,信道编码纠错码,汉明码,汉明码监督位为 位，因此它可以组成 种可能情况，其中一个为无错。因此可以监督码位共,要纠正一个错误，必须满足,最小码距,如果 r 位监督位所组成的校正子码组与误码图样一一对应，这种码组称为完备码（取等号时）,72,信道编码纠错码,扩展汉明码,如果在汉明码基础上，再加上一位对所有码字进行校验的监督位,监督码字由,r,位增加到,r,+1 位,信息位不变,码长 码结构,纠 1 位错，检测 2 位错,如 （8，4），（16，11）,73,信道编码纠错码,扩展汉明码矩阵,如 (7,4) (8,4),74,信道编码纠错码,缩短汉明码,(n,k) (n-s, k-s),如 (15,11) (12,8),监督矩阵 Hs 是将原 H 的前 3 列 去掉,缩短汉明码的最小码距至少和原来码的码距相同，因为监督位没有变。,75,信道编码纠错码,能纠 t 个错误的(n,k)应满足,取等号时为完备码,不同结构的线性码其纠错能力不同，能力和dmin 有关，dmin 越大越好。,76,信道编码纠错码,最小码距界限,上界： 汉明界， 普洛特金界,下界： 吉尔伯特界,问题： 给定码长与编码效率，寻找 dmin,例： dmin=5, 码长=63 的分组码设计,从汉明界得，,因此信息位最多可以取,77,信道编码纠错码,最小码距界限,通过吉尔伯特界求下界,线性码,k 越接近 52， 效率越高。,78,信道编码纠错码,6.3 循环码 (Cyclic code),1957 年发现,特点,线性分组码,循环性任一许用码字经过循环移位后，得到的码组仍为一个许用码组,如 是循环码的一许用码组,则 也是一许用码组,79,信道编码纠错码,码多项式表示,码组,码多项式,码组,码多项式,左移一位,左移 位,80,信道编码纠错码,循环码性质,为许用码组，则 也是许用码组,性质,若 是长度为n的循环码组，则,在按模 进行运算后，也是一个循环码组，也就是 用 多项式除后所得之余式，即为所求的码组。,81,信道编码纠错码,循环码例子,码组,左移 3 位,去除 得余式,如 左移 3 位后，得,是许用码组,82,信道编码纠错码,循环码生成多项式g(D),g(D) 是 D的 (n-k) 次即r 次多项式,信息多项式为M(D),k 位，(k-1)次多项式,83,信道编码纠错码,Theo.一个(n,k) 的二进制循环码可以看成是唯一由它的生成多项式产生，即,如(7,3)循环码，n=7, k=3, r=4,如果信息位为 010， M(D)=D,生成码为 0111010,循环码生成多项式g(D),84,信道编码纠错码,生成矩阵 G(D),由于 k 位信息位共有 个码组，都可用此法产生，如果现有信息码,生成 k 个码字，且这 k 个码字都线性无关，用这 k 个码字作为一个矩阵G 的 k行,构成生成矩阵 G(D),85,信道编码纠错码,循环码,(7,3) 循环码,86,信道编码纠错码,生成矩阵和监督矩阵,这样构成的循环码并非是系统码,系统码的生成矩阵典型形式,非系统码, 系统码,生成矩阵,监督矩阵,87,信道编码纠错码,非系统码, 系统码,系统码的码多项式为,例如，(7,4)码，1011,88,信道编码纠错码,非系统码, 系统码,89,信道编码纠错码,寻找生成多项式,Theo. 循环码的生成多项式必须能除尽,h(D)是监督多项式,例：要构成(7,3)循环码，求g(D).,解：g(D)应为4阶,生成(7,6)循环码,生成(7,1)循环码,90,信道编码纠错码,循环码的编码器,原理：按系统码的生成方式,以(7,4)码为例,91,信道编码纠错码,循环码的译码器,译码比编码复杂得多,译码三步,伴随式S的计算,由S得到错误图样,纠正,92,信道编码纠错码,伴随式的计算,发送码组,接收码组,误差码组,校正子只与 E 有关，根本是计算校正子,93,信道编码纠错码,6.4 BCH码,即约多项式,一个 m 次多项式不能被二元域上任何二次数小于的，但大于0的多项式除尽，如 是即约的。,本原多项式,若m次多项式P(x)除尽的 的最小正整数 n 满足 ，就称为本原的。,如 能除尽 ，但除不尽 的。,如 ： 是即约的，但不是本原的，因它能除尽,。,94,信道编码纠错码,6.4.1 本原循环码,由本原多项式构成的码称为本原码。,特点,码长为,它的生成多项式是由若干m阶或以m的因子为最高阶的多项式相乘而构成。,要判定(n,k) 的循环码是否存在，只需要判断 n-k 阶的生成多项式是否能由 D,n,+1的因式构成。,95,信道编码纠错码,循环码例子,生成多项式的阶次为 r, 该生成多项式是否是 的因此。,一个m阶即约多项式一定能除尽,如，m5，共有6个5阶即约多项式。,再加上 因子， 是以上7个多项式的乘积。,96,信道编码纠错码,6.4.2 BCH 码的生成多项式,如果循环码形式的形式为,为纠错个数 ， 为最小多项式，,为最小公倍数,最小码距,码长为 的BCH码称为 本BCH码（侠义）,码长为 则称为非本原BCH码,97,信道编码纠错码,BCH 码,由于g(D)有t个因式，且每个因式的最高次为m，因此监督码元最多有mt位。,对于纠t 个错误的本原BCH码，其生成多项式,纠单个错误的本原BCH码字为汉明码。,表1113给出了 n5的本原BCH码。,1114给出了部分非本原BCH码。,98,信道编码纠错码,BCH 码例子,纠正 3 个错误，码长为15的BCH码,解：n=15, m=5 查表11-12得，,233707,这是(15,5)码。,99,信道编码纠错码,重要的BCH码 (23,12),表1114中最重要的BCH码是(23,12),称为格雷码，码间为7，能纠正3个错误。,生成多项式,在实际通信系统中，所要求的n、k并不是码表中所推荐的值，在这时我们可以采用缩短或扩展的方式加以修正，也就是通过增加信息符号或校验符号来增加码组长度，或减少信息和校验位来减少码组长度。,100,信道编码纠错码,BCH码,如 BCH码的码长为奇数，而有时需要偶数码长，这时可以在原BCH码生成多项式中乘以（D+1)因子，从而得到（n+1,k）扩展BCH码，这时相当于在原BCH码上加一个全校验位，从而将码距增加1，这时的码字不具有循环性。,如果BCH码不是2,m,-1或它的因式，这时可以采用缩短的方式，去掉s位信息，(n-s , k-s),101,信道编码纠错码,RS码 Reed-Solomon,非二进制BCH码，输入以符号来考虑,假定每组有 K 个符号，每个符号用m比特，输入信息将是 Km 比特。,102,信道编码纠错码,RS码,RS码适合于纠正突发错误，纠正的错误图样有,对于一个长度为 符号的RS码，每个符号都可以看成是有限域 中的一个元素，如RS码的最小码距为d符号，则生成多项式,103,信道编码纠错码,6.5 纠正和检测突发错误的分组码交织码interleaved,在水平垂直监督码中将信息码排列成方阵，然后对行和列分别进行检验，可以达到检测突发错误的目的。,如果方阵中行码是能纠 t 个随机错误，交织后能纠t个长度为i的突发错误。i称为交织深度。,104,信道编码纠错码,循环码构成交织码,采用循环码构成交织码时，可以不采用方阵就能实现编码。,假设交织码每行为 循环码，其生成多项式为 ， 可以除尽 ，如交织深度为 其交织码为 ,其生成多项式为,可以除尽 ，所以,也是循环码。,105,信道编码纠错码,循环码构成交织码 (续),如，循环码(7,4)， 其生成多项式为,构成交织深度为3 的(21,12)交织码。,交织码的生成多项式为,它也是循环码，可以用循环码的方式构成。在发送端可以不排成方阵，但是在译码时，必须将码字排列成 阵列，然后分别独立的对每行码字进行译码。,106,信道编码纠错码,交织码 之小结,为了进一步提高纠错能力，可以在交织阵列中不仅对每行进行纠错编码，而且也对每列进行纠错编码，这种形式的交织码称为乘积码。,若乘积码的行码和列码 分别能纠长度超过 的突发错误，则乘积码能纠正长度为,的突发错误。,交织一般都带固有延时，在语音中交织的延时不要超过40ms。,107,信道编码纠错码,