1、2022-10-6 College of Telecommunications&Information EngineeringNJUPT1/120 第四章 信道编码与调制技术2022-10-6 College of Telecommunications&Information EngineeringNJUPT2/120数字电视广播的目的是要将图像、声音和数据等信息快速、实时、高质、数字电视广播的目的是要将图像、声音和数据等信息快速、实时、高质、可靠地传输至接收端,供用户满意地收看、收听。其系统组成框图如图所示。可靠地传输至接收端,供用户满意地收看、收听。其系统组成框图如图所示。信源信源编码信道
2、编码调制解调信源解码信宿信道解码传输通道噪声干扰、多径衰落信道编码与调制技术2022-10-6 College of Telecommunications&Information EngineeringNJUPT3/1201.随机性差错:差错是随机的且相互之间是独立出现。通常由高斯白噪声引起;12位错误。2.突发性差错:由脉冲性干扰引起,在短暂的时间内出现连续的差错,而这些短暂时间之后却又存在较长的无误码区间。一、差错类型4.2 差错控制原理及信道编码的分类3.混合性差错:既存在随机差错又有突发性差错。以上两种错误性质不同,可采取不同措施处理!2022-10-6 College of Tele
3、communications&Information EngineeringNJUPT4/120二、差错控制方式2.前向纠错前向纠错(FEC)可以纠正错误可以纠正错误 发发 收收3.混合纠错混合纠错(HEC)可以发现和纠正错误可以发现和纠正错误 发发 收收 应答信号应答信号 比较:比较:译码复杂性、实时性和占用传输链路译码复杂性、实时性和占用传输链路(单向还是双向单向还是双向)1.检错重发(检错重发(ARQ)(包括停发等候重发、返回重发和选择重发)(包括停发等候重发、返回重发和选择重发)能够发现错误能够发现错误 发发 收收 应答信号应答信号ARQ:自动重复请求发送:自动重复请求发送发送端发送有
4、纠错能力的码(纠错发送端发送有纠错能力的码(纠错码),接收端收到这些纠错码后,译码),接收端收到这些纠错码后,译码器自动地纠正传输中的错误。码器自动地纠正传输中的错误。上述两种方式的结合。发端发送的码既能上述两种方式的结合。发端发送的码既能检错、又有一定的纠错能力。收端译码时检错、又有一定的纠错能力。收端译码时若发现错误个数在码的纠错能力以内,则若发现错误个数在码的纠错能力以内,则自动进行纠错;若错误个数超过了码的纠自动进行纠错;若错误个数超过了码的纠错能力,但能检测出来,则通过反馈信道错能力,但能检测出来,则通过反馈信道告知发方重发告知发方重发。2022-10-6 College of Te
5、lecommunications&Information EngineeringNJUPT5/120三、差错控制的基本原理 在信息码元之后附加一些监督码元。信息码元:又称信息序列或信息位,是发送端由信源编码给出的信息数据比特。监督码元:监督码元与信息码元之间以某种确定的规则相互关联,接收端按照既定的规则检验出关联关系,如这种规则受到破坏,将会发现错误,乃至纠正错误。2022-10-6 College of Telecommunications&Information EngineeringNJUPT6/120检错与纠错原理 n0:晴晴,1:雨雨n若若10,01。收端无法发现错。收端无法发现错误
6、误00晴晴1001110011雨雨禁用码组禁用码组n插入插入1位监督码位监督码后具有后具有检出检出1位错码位错码的能的能力力,但不能予以纠正。但不能予以纠正。许用码组许用码组许用码组许用码组2022-10-6 College of Telecommunications&Information EngineeringNJUPT7/120检错与纠错原理 000晴晴010001111000111雨雨晴晴n在只有在只有1位错码位错码的情况下的情况下,可以判决哪位是错码可以判决哪位是错码并予以并予以纠正纠正,可以可以检出检出2位或位或2位以下位以下的错码的错码。100011101110雨雨许用码组许用码
7、组许用码组许用码组禁用码组禁用码组2022-10-6 College of Telecommunications&Information EngineeringNJUPT8/120检错与纠错原理n最大似然译码:最大似然译码:将接收到的码字译码为与它将接收到的码字译码为与它的的许用码字许用码字,并并且认为这个许用码字就是它所对应的发送码字且认为这个许用码字就是它所对应的发送码字,从而从而在码字的纠错能力内实现自动纠错。在码字的纠错能力内实现自动纠错。n纠错编码之所以具有检错、纠错能力纠错编码之所以具有检错、纠错能力,是因为在是因为在信息码元之外加入了信息码元之外加入了监督码元监督码元。监督码。监
8、督码元元不载不载信息,只是用来监督信息码在传输中有无差错。信息,只是用来监督信息码在传输中有无差错。n纠错编码所提高的可靠性纠错编码所提高的可靠性,是以牺牲信道利用率是以牺牲信道利用率为代价换取的。为代价换取的。n监督码元监督码元引入引入越多,检错、纠错能力越强,越多,检错、纠错能力越强,但但信道的传输效率下降也越多。信道的传输效率下降也越多。2022-10-6 College of Telecommunications&Information EngineeringNJUPT9/120结论:结论:最小码距决定检最小码距决定检错和纠错能力错和纠错能力2022-10-6 College of T
9、elecommunications&Information EngineeringNJUPT10/120五、差错控制编码的效用 假设在随机信道中发“0”和发“1”的概率相同,在码长为n的码组中恰好发生 r 个错误的概率为:(p为误码率)371077)1(pP527101.221)2(pP837105.335)3(pP结论:采用差错控制编码,即使仅能纠正(或检测)12个错误,就能使误码率下降几个数量级。2022-10-6 College of Telecommunications&Information EngineeringNJUPT11/120纠纠错错码码随随机机误误码码纠纠错错码码突突发发
10、误误码码纠纠错错码码分分组组码码卷卷积积码码分分组组码码交交织织码码线性码线性码非线性码非线性码系统卷积码系统卷积码非系统卷积码非系统卷积码比特交织码比特交织码字节交织码字节交织码循环码循环码非循环码非循环码BCH码码RS码码奇偶校验码奇偶校验码汉明码汉明码 五、纠错码的分类2022-10-6 College of Telecommunications&Information EngineeringNJUPT12/120 五、纠错码的分类1.分组码与卷积码:分组码:将信息码元分组,为每组信息码元后面附加若干位监督码元,且监督码元仅监督本码组中的信息码元。1na2nara1ra0a K个信息位个
11、信息位r个监督位个监督位码长码长 nkr卷积码:卷积码也是先将信息序列分组,后面附加监督位,但是监督位不但与本码组的信息位有关,还与前面码组的信息位有关,或者说监督位不仅监督本码组的信息位还监督其它码组的信息位。k010 101 010 001 110 010 xxxx 101xxxx 010 xxxxrn2022-10-6 College of Telecommunications&Information EngineeringNJUPT13/120 六、纠错码的分类2.系统码与非系统码系统码:就是信息位在前,监督位在后的码字。非系统码:信息位与监督位之间无特定的位置关系。2022-10-6
12、 College of Telecommunications&Information EngineeringNJUPT14/1201.奇偶校验码奇偶校验码9.低密度校验码低密度校验码(LDPC)8.Turbo码码7.分组交织和卷积交织分组交织和卷积交织2.线性分组码线性分组码3.循环码循环码4.BCH码码5.RS码码6.卷积码和维特比卷积码和维特比(Viterbi)译码译码4.3信道编码技术2022-10-6 College of Telecommunications&Information EngineeringNJUPT15/1204.3.1 奇偶校验码偶校验00121 aaaann设信息
13、位每组长度为n-1位,增加一位监督位,n位编码构成以下约束关系 错误正确100121aaaaSnn接收端计算校正子奇偶校验可以用来检测单个或奇数个错误2022-10-6 College of Telecommunications&Information EngineeringNJUPT16/120纵向奇偶校验(LRC)用于检测突发错误11100111 11011101 00111001 1010100111100111110111010011100110101001纵向排列纵向排列原始数据原始数据11100111 11011101 00111001 10101001 10101010突发错误突
14、发错误接收方检验是否满足接收方检验是否满足LRCLRC 10101010监督码元监督码元交织编码:交织编码:针对突发性错误针对突发性错误2022-10-6 College of Telecommunications&Information EngineeringNJUPT17/120 信信 息息 码码 元元 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 1 0 1 1 0 0 0 0 监督码元监
15、督码元 0 0 1 1 1 0 0 0 0 1 0监督码元监督码元 1 0 0 1 0 1 1水平垂直奇偶校验它能发现某一行或某一列上所有奇数个错误以及长度不它能发现某一行或某一列上所有奇数个错误以及长度不大于行数(或列数)的突发错误大于行数(或列数)的突发错误2022-10-6 College of Telecommunications&Information EngineeringNJUPT18/1204.3.2 线性分组码定义:信息位和监督位之间的关系是由线性方程组约束的编码称作线性分组码,即监督码元是由信息码元的线性组合而产生。奇偶校验码就是一种效率很高的线性分组码。0121aaaaS
16、nn 这里S称为校正子,若S0,表示无错,S1表示有错误,由于只用了一位监督位a 0,因此只能表示有错与无错。若监督位增加到2位,就可增加一个监督方程式,接收时就可计算2个校正子S1和 S2,共有四种可能,除了00表示无错以外,其余3种就可以表示一位错码的的具体位置了。对于二进制编码,知道了错误的位置,就可以实现纠错了对于二进制编码,知道了错误的位置,就可以实现纠错了2022-10-6 College of Telecommunications&Information EngineeringNJUPT19/120 一般说来对于,对 r个监督位,可以计算r 个校正子,它可以指出 2的r次方减一
17、种错误图样,即2的r次方减一个错误位置,因此对于(n,k)码。要想指出一位错码的所有可能位置,则要求:rr 设分组码中(n,k)中k4,为了纠正一位错误,则 ,取r3,则n7,用 表示,用 表示由3个监督方程式计算得到的校正子,并假设这3个校正子与误码对应的关系如下表所示:3r0123456aaaaaaa123SSStiinrtiinrCC01212或对于对于纠正纠正t 个错误个错误一、线性分组码的构成:一、线性分组码的构成:rknCnr112纠正纠正1 1个错误个错误2022-10-6 College of Telecommunications&Information Engineering
18、NJUPT20/120校正子表校正子表 S1S2S3 误码位置误码位置 S1S2S3 误码位置误码位置 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 0 无错无错因此接收端计算下面3个校验关系,可确定误码的位置24561aaaaS13562aaaaS03463aaaaS2022-10-6 College of Telecommunications&Information EngineeringNJUPT21/120发送端构成偶校验关系发送端构成偶校验关系由此监督位可以由信息位的线性组合得到:由此监督位可以由信息位的线性组合得到:0000346135
19、62456aaaaaaaaaaaa346035614562aaaaaaaaaaaa许用码组许用码组信息位信息位 监督位监督位 信息位信息位 监督位监督位 0 0 0 0 0 0 0 1 0 0 0 111 0 0 0 1 0 1 1 1 0 0 1 100 0 0 1 0 1 0 1 1 0 1 0 010 0 0 1 1 1 1 0 1 0 1 1 001 0 1 0 0 1 1 0 1 1 0 0 001 0 1 0 1 1 0 1 1 1 0 1 010 0 1 1 0 0 1 1 1 1 1 0 100 0 1 1 1 0 0 0 1 1 1 1 1113456aaaa012aaa34
20、56aaaa012aaa2022-10-6 College of Telecommunications&Information EngineeringNJUPT22/120 010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa 0001001101010101100101110123456Taaaaaaa线性分组码的生成和监督矩阵监督矩阵监督矩阵TTHA0 即即 0123456aaaaaaaA 0000 100110101010110010111H其中:其中:2022-10-6 College of Telecom
21、munications&Information EngineeringNJUPT23/120 34634565634560123456aaaaaaaaaaaaaaaaaaaa TaaaaaaaaaaaaaaA 01234560123456对于所有的编码与信息位的关系:对于所有的编码与信息位的关系:,rIPH 1001101010101100101110krrIrr0HP为为 阶矩阵,阶矩阵,为为 阶单位阵阶单位阵,具有具有 形式称为典型形式的监督矩阵;形式称为典型形式的监督矩阵;线性代数理论告诉我们,典型形式的监督矩阵各行一定是线性无关的,线性代数理论告诉我们,典型形式的监督矩阵各行一定是线性
22、无关的,非典型形式的监督矩阵可以通过矩阵的初等变换化为典型形式。非典型形式的监督矩阵可以通过矩阵的初等变换化为典型形式。2022-10-6 College of Telecommunications&Information EngineeringNJUPT24/120 Gaaaaaaaa345634561101000101010001100101110001 QIGk 1101000101010001100101110001其中其中TTaaaaaaaaaaaaaaaaa 3456346356456345611111111111112022-10-6 College of Telecommuni
23、cations&Information EngineeringNJUPT25/120 GaaaaA 3456则则全部码字由信息位与生成矩阵全部码字由信息位与生成矩阵G相乘得到相乘得到Q为为K r 阶矩阵阶矩阵。I k为为k 阶单位阵阶单位阵具有典型化形式具有典型化形式 的生成矩阵称为典型生成矩阵的生成矩阵称为典型生成矩阵 QIGk,0它与典型化形式它与典型化形式 的关系为:的关系为:rIPH,0TTPQQP 或或,结论:结论:1).由典型化的生成矩阵产生的是系统码组;由典型化的生成矩阵产生的是系统码组;k 2).典型化的生成矩阵的各行也必定是线性无关的,每一行都是一个许用码组,典型化的生成矩阵
24、的各行也必定是线性无关的,每一行都是一个许用码组,k行许行许用码组进过运算可以生成用码组进过运算可以生成 2 个不同的码组,个不同的码组,非典型形式的生成矩阵经过运算也一定非典型形式的生成矩阵经过运算也一定可化为典型形式。可化为典型形式。2022-10-6 College of Telecommunications&Information EngineeringNJUPT26/120 0001101001101001101001101000G例:若线性分组码的生成矩阵为例:若线性分组码的生成矩阵为典型阵为典型阵为 00011010010111010001110001100G 100111001
25、0011100111010H监督矩阵监督矩阵三、线性分组码的特性:三、线性分组码的特性:1)任意两个许用码组之和仍为许用码组封闭性任意两个许用码组之和仍为许用码组封闭性2)码的最小距离等于非零码的最小重量码的最小距离等于非零码的最小重量。2022-10-6 College of Telecommunications&Information EngineeringNJUPT27/120四、线性分组码的伴随式译码,.,.,021rrrRnn 设发送的码组为A,接收的码组为R,,.,.,021eeeEnn 设E为传输错误图样,则则:RAETTTTTEHEHAHHEARHS )(计算校正子TTHES
26、或者对于前面(7,4)码的例子,一位错误图样为:(1000000),(0100000),(0010000),(0001000),(0000100),(0000001),(0000001)61110000001100110101010110010111HHET 2022-10-6 College of Telecommunications&Information EngineeringNJUPT28/12050110000010100110101010110010111H 01001000000100110101010110010111H .2022-10-6 College of Teleco
27、mmunications&Information EngineeringNJUPT29/120例:若接收的码组为1001101计算伴随式:002361001011001100110101010110010111HHHHHHESTT 最后一位有错,译码得:1001100校正子S只与E有关,若接收码字R中第I 位有错,那么导出的伴随式 恰好是矩阵H的第i 列相同的位置。利用伴随式不仅可以判决接收码字中是否有错,而且可以指出差错的位置。TTHES 2022-10-6 College of Telecommunications&Information EngineeringNJUPT30/1204.3
28、.3 循环码一、特点:循环码是一种具有循环移位特性的线性分组码,这类码除了具有线性分组码的一般性质外,还具有循环性质带来的其它性能和特征,并可以用不太长的码长来实现,循环码本身的特性使编译设备比较容易实现。1.码多项式码多项式:012211cxcxcxcxCnnnn )(1012 nnCCCC 0121CCCCCnn 若若 是一个码字是一个码字1210CCCCnn 则则C的每次的每次循环移位都是一个码字循环移位都是一个码字2022-10-6 College of Telecommunications&Information EngineeringNJUPT31/120)模(17x,.,1298
29、7xxxxx)1(2346236xxxxxxxx)1(23422456xxxxxxxx)1(1234525xxxxxxx)1(12343356xxxxxxx1234xxx)1(234345xxxxxxxx)1(1234446xxxxxxx序号序号 信息码信息码(7.3)循环码循环码 移位次数移位次数 码多项式码多项式0 000 0000000 1 001 0011101 02 011 0111010 13 111 1110100 24 110 1101001 35 101 1010011 46 010 0100111 57 100 1001110 6例:(7,3)循环码2022-10-6 Co
30、llege of Telecommunications&Information EngineeringNJUPT32/120按模运算规则:模按模运算规则:模n运算下,一整数运算下,一整数m等于其被等于其被n除得到的余数除得到的余数模运算中,模运算中,rqnmnrnrqnm或)(一般的讲,若一整数一般的讲,若一整数m可表示为可表示为rm 则:则:(模(模n))()()()()()()(xgxrxFxrxgxqxF模则2.按模运算2022-10-6 College of Telecommunications&Information EngineeringNJUPT33/120)(xC)(xCXi1
31、nx)()(xCxCxii结论:结论:可以证明在循环码中可以证明在循环码中,若若 是一个码长为是一个码长为n的许用码组多项式,则的许用码组多项式,则 在模在模 运算下亦是许用码组,即若有:运算下亦是许用码组,即若有:)(xCi则则 也是一个许用码组。也是一个许用码组。2456xxxx前面的(前面的(7,3)1110100码多项式码多项式35672456)(xxxxxxxxx左移一位的多项式左移一位的多项式 1356xxx1110100左移一位的码组左移一位的码组1101001对应的多项式对应的多项式13563567xxxxxxx)(模17x显然显然1111356735677xxxxxxxxx多
32、项式除法多项式除法:2022-10-6 College of Telecommunications&Information EngineeringNJUPT34/120 二、循环码的生成多项式对于线性分组码来说只要找到它的生成矩阵就可确定所有的编码码字,而它的生成矩阵的每一行都是一个许用码组,循环码的某一个码字循环移位可得到它的码字。只要找到这个码字就可以得到生成矩阵。这个码字称为生成多项式(码字)。)()()()()(0121xgxxgxxgxxgxxGk生成矩阵可写为:对于线性分组码,其生成矩阵由对于线性分组码,其生成矩阵由K K 行线性无关的码字组成行线性无关的码字组成2022-10-6
33、 College of Telecommunications&Information EngineeringNJUPT35/1202.(n,k)循环码的生成多项式循环码的生成多项式g g (x)(x)是是 的因式的因式1nx定理:定理:1.在一个在一个(n,k)循环码中,存在一个唯一的最低次码多循环码中,存在一个唯一的最低次码多项项式,式,其次数为其次数为 r=n-k,且常数项必须为且常数项必须为,即生成多项式即生成多项式1)(111xgxgxxgknknkn1nx)(xg)(xg3.若是一个若是一个(nk)次多项式,且是次多项式,且是 的因式,则的因式,则 一定能生成一个一定能生成一个(n,
34、k)循环码循环码)(xg)(xC0)(xC)(xg模4.所有码多项式必定能被整除,所有码多项式必定能被整除,即即)(xg)(xg就是说阶数小于就是说阶数小于(n-1)(n-1)能被能被 整除的每个多项式都是循环码整除的每个多项式都是循环码的许用码组,或必是的倍式的许用码组,或必是的倍式2022-10-6 College of Telecommunications&Information EngineeringNJUPT36/120 (7.k)循环码循环码(n.k)d g(x)h(x)(7.6)2(7.4)3(7.3)4(7.1)61)1)(1(1111)1)(1()1)(1(11)1)(1()
35、1(32332324234233323323或或或或xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx1nx结论:结论:(1)一个一个(n,k)循环码的每一个码多项式也必然是按模循环码的每一个码多项式也必然是按模 运算后某个运算后某个余式,即一个余式,即一个(n,k)循环码的所有码字都可以通过循环码的所有码字都可以通过k 个许用码多项式循环移位得个许用码多项式循环移位得到。到。循环码完全由其码组长度循环码完全由其码组长度n及生成多项式及生成多项式 g (x)决定决定2022-10-6 College of Telecommunications&Information Engineer
36、ingNJUPT37/120123 xxxg)(例:一个例:一个(7,4)循环码,则由生成多项式循环码,则由生成多项式 000110100110100110100110100012334245356xxxxxxxxxxxxG)(构成的生成矩阵为构成的生成矩阵为典型阵为典型阵为 00011010010111010001110001100G 1001110010011100111010H监督矩阵监督矩阵2022-10-6 College of Telecommunications&Information EngineeringNJUPT38/120三、循环码的系统码的编码实现系统码组中的最左边的系
37、统码组中的最左边的k k位是信息码元,随后是位是信息码元,随后是n nk k位的监督码元,即码多项位的监督码元,即码多项式为:式为:011011rxrxmxmxrxxmxCknknknnkkn )()()()(模(模)()()()()(xgxxmxcxxmxrknkn 因此因此)()()()()(xgxrxqxgxmxkn 有:有:m(x)x 除法求余得到除法求余得到r(x)n-k2022-10-6 College of Telecommunications&Information EngineeringNJUPT39/120系统循环码的编码步骤:1.将信息元多项式m(x)乘以xn-k成为xn
38、-km(x);2.将xn-km(x)除以生成多项式g(x)得到余式r(x),该余式就是校验元多项式,从而得到码字多项式 c(x)xn-km(x)r(x)2022-10-6 College of Telecommunications&Information EngineeringNJUPT40/120例例:已知已知(7,4)循环码的生成多项式为循环码的生成多项式为若信息码为若信息码为1001,求编码码字,求编码码字123 xxxg)(11113633 xxxxxxxC)()(因此:因此:13 xxm)(解:解:112333 xxxxxgxmxkn)()()(11112323 xxrxxxxxx)
39、(即编码码组为:即编码码组为:10010112022-10-6 College of Telecommunications&Information EngineeringNJUPT41/120 S0 S1m输入输入。S2。K1K2输出输出ef输入输入 移移 存存 器器 反馈反馈 输出输出 m S0 S1 S2 e f 0 0 0 0 0 00 0 0 0 0 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 0 0 1 1 0 0 0 0 1 1 0
40、 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 反馈反馈 e=S21+m0123 xxxg)(2022-10-6 College of Telecommunications&Information EngineeringNJUPT42/120输出输出 (n,k)循环码编码器循环码编码器10 gSn-k-12g1g。K1K2f1 kngkng 输入输入1111 xgxgxxgknknkn)(S0S02022-10-6 College of Telecommunications&Information EngineeringNJUPT43/12
41、0接收端接收到码组R(x)时,要达到解码和检错纠错的目的。由于任一码组的码元多项式T(x)都应被码元多项式g(x)整除,因此接收端可将接收码组R(x)用原始生成多项式g(x)相除。如果传输中未发生误码,接收码组与发送码组相同,即R(x)T(x),则R(x)必能被g(x)整除,无余项;如果发生误码,R(x)T(x),则R(x)被g(x)相除时会有余项出现,即四、循环码的译码四、循环码的译码2022-10-6 College of Telecommunications&Information EngineeringNJUPT44/120)()()()()(xgxExgxRxSEHRHSTT模模模模
42、 校正子计算电路校正子计算电路 错误图样识别错误图样识别 n 级级 缓缓 存存 器器输入输入纠错后输出纠错后输出1 2 .(n-k)1001110010011100111010H监督矩阵监督矩阵对于最高位错误,校正子为对于最高位错误,校正子为:)(,)(,)(xgxxExxxS模模62 2022-10-6 College of Telecommunications&Information EngineeringNJUPT45/120 a b c 七七 级级 缓缓 存存 器器纠错后输纠错后输出出门门节拍节拍 输入输入 a b c 与门与门 缓存缓存 译码译码 1 0 0 0 0 输出输出 输出输
43、出 输出输出 2 0 0 0 0 3 0 0 0 0 4 1 1 0 0 5 0 0 1 0 6 1 1 0 1 7 1 0 1 1 8 0 0 0 0 1 0 1节拍节拍 输入输入 a b c 与门与门 缓存缓存 译码译码 1 1 1 0 0 输出输出 输出输出 输出输出 2 1 1 1 0 3 0 0 1 1 4 1 0 0 0 5 0 0 0 0 6 1 1 0 0 7 1 1 1 0 8 0 0 1 1 0 1 1 9 0 0 0 0 1 1 02022-10-6 College of Telecommunications&Information EngineeringNJUPT46/
44、120用以上除法电路作为校正子计算电路时,用了一个重要的性质用以上除法电路作为校正子计算电路时,用了一个重要的性质:某码组循环移位某码组循环移位 i 次次的校正子等于原码组校正子在除法电路中循环移位的校正子等于原码组校正子在除法电路中循环移位 i 次所得的结果。次所得的结果。即即:)(,)()()(,)()()(,)()()()(,)()()(,)()(xgxSxxSxgxSxSxxgxRxxSxixSxgxRxSxgxRxxSiiiiiiii模模即:即:模模因此:因此:模模次有:次有:循环移位循环移位模模而:而:模模 0上述性质可以使得译码器需要识别得错误图样数目大为减少,因为某个可纠正错误
45、上述性质可以使得译码器需要识别得错误图样数目大为减少,因为某个可纠正错误图样图样E(x)得得 i 循环移位循环移位x E(x)也必定是可以纠正的也必定是可以纠正的.i2022-10-6 College of Telecommunications&Information EngineeringNJUPT47/120(7.4)循环码完整译码器循环码完整译码器输出输出门门5 四四 级级 缓缓 存存 器器 a b c门门1 a b c门门2门门3门门4输入输入2022-10-6 College of Telecommunications&Information EngineeringNJUPT48/1
46、20n1.引言n2.有限域n3.BCH码简述n4.BCH码的编码n5.BCH码的译码4.3.4 BCH码2022-10-6 College of Telecommunications&Information EngineeringNJUPT49/1201.引言nBCH码是一类最重要的循环码,能纠正多个随机错误,它是1959年由Bose、Chaudhuri及Hocquenghem各自独立发现的二元线性循环码,人们用他们的名字字头命名为BCH码。n在前面的讨论中,我们所做的只是构造一个码,然后计算它的最小距离,从而估计出它的纠错能力,而在BCH码中,我们将采用另外一种方法:先说明我们希望它能纠错的
47、个数,然后构造这种码。2022-10-6 College of Telecommunications&Information EngineeringNJUPT50/1202.有限域n运算自封运算自封:一个集合中的元素经过某种运算(例如加减乘除)后仍为集合中的元素时,称为运算自封。n域域:运算自封元素的集合叫做域F(Field)。n有限域:当域中元素为有限数p时,称为有限域或p元域。有限域理论是由数学家伽罗华(Galois)所创立的,因此又称为伽罗华域,并记为GF(p)。n普通代数中全体有理数的集合叫有理域,全体实数的集合叫实数域。全体复数的集合叫复数域。它们都是无限域。2022-10-6 Co
48、llege of Telecommunications&Information EngineeringNJUPT51/120n有限域中运算满足交换律:a+b=b+a,ab=b a结合律:(a+b)+c=a+(b+c),a(bc)=(ab)c分配律:a(b+c)=a b+a cn经常用到的有限域是二元域GF(2),它有两个元素“0”和“1”,其加法和乘法分别为:加法乘法加法乘法0+000*000+110*101+011*001+101*112022-10-6 College of Telecommunications&Information EngineeringNJUPT52/120n系数在系
49、数在GF(2)中的多项式叫做二元域上的多项式。中的多项式叫做二元域上的多项式。二元域上多项式的加减乘除等运算在原理上和普通二元域上多项式的加减乘除等运算在原理上和普通代数多项式的运算相同。代数多项式的运算相同。例如:对码字多项式例如:对码字多项式C(x)=cn-1xn-1+cn-2xn-2+c1x+c0有有xi+xi0,ci+ci0,ci2=ci.cici并且减法就是加法。加法符号为并且减法就是加法。加法符号为“”或简记为或简记为“+”。n既约多项式既约多项式 又称又称不可约多项式不可约多项式,它不能分解为次,它不能分解为次数更低的多项式的乘积。数更低的多项式的乘积。n例如,例如,x2+x+1
50、和和x4+x+1为不可约多项式;而为不可约多项式;而x2+1不是既约多项式,因为不是既约多项式,因为(x+1)2=x2+x+x+1=x2+12022-10-6 College of Telecommunications&Information EngineeringNJUPT53/120n和普通代数一样,对于多项式f(x),如果f(a)=0,则称a为多项式的根,例如(x+1)2的根为1。显然,既约多项式的根不能在二元域内,但是可以像实数根扩展到复数根那样,将既约多项式的根在二元域的扩展域中表示出来。n以二次既约多项式1+x+x2为例,可以把二元域中的元“0”和“1”扩充一位,表示成0(00),