第七章-差错控制编码课件.ppt

1、CCEE第七章第七章 差错控制编码差错控制编码数字通信原理数字通信原理重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理主要内容主要内容7.1 概述概述 7.2 差错控制编码分类差错控制编码分类 7.3 线性分组码线性分组码 7.5 BCH码码7.6 交织码交织码7.8 纠错编码的性能纠错编码的性能7.7 卷积码卷积码7.4 循环码循环码 7.10 检错编码检错编码7.9 网格编码调制网格编码调制重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理7.1 概述概述从通信系统的研究角度从通信系统的研究角度希望系统可靠性好、传输差错率低希望系统可靠性好、传输差错率低希望系

2、统容量大希望系统容量大 香农公式得到的信道编码理论香农公式得到的信道编码理论当信道中的传输速率小于或等于信道容量当信道中的传输速率小于或等于信道容量C C时，必定存时，必定存在某种编译码方式可以实现信号在信道中的无误传输。在某种编译码方式可以实现信号在信道中的无误传输。反之，如果传输速率反之，如果传输速率R R大于信道容量大于信道容量C C时，不可能实现时，不可能实现信号在信道中的无误传输。信号在信道中的无误传输。在信道容量确定的情况下，可以进行带宽与信噪比的在信道容量确定的情况下，可以进行带宽与信噪比的互换互换 重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理7.1 概述概述

3、差错控制编码差错控制编码纠错编码纠错编码在信息序列上附加上一些监督码元，利用这些在信息序列上附加上一些监督码元，利用这些冗余的码元，使原来不规律的或规律性不强的冗余的码元，使原来不规律的或规律性不强的原始数字信号变为有规律的数字信号；原始数字信号变为有规律的数字信号；差错控制译码则利用这些规律性来鉴别传输过差错控制译码则利用这些规律性来鉴别传输过程是否发生错误，或进而纠正错误。程是否发生错误，或进而纠正错误。信道编码是用增加数码，利用信道编码是用增加数码，利用“冗余冗余”来来提高抗干扰能力的，即以降低信息传输速提高抗干扰能力的，即以降低信息传输速率为代价来减少错误，或者说是用削弱有率为代价来减

4、少错误，或者说是用削弱有效性来增强可靠性。效性来增强可靠性。重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理主要内容主要内容7.1 概述概述 7.2 差错控制编码分类差错控制编码分类 7.3 线性分组码线性分组码 7.5 BCH码码7.6 交织码交织码7.8 纠错编码的性能纠错编码的性能7.7 卷积码卷积码7.4 循环码循环码 7.10 检错编码检错编码7.9 网格编码调制网格编码调制重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理7.2 差错控制编码分类差错控制编码分类数据错误的类型数据错误的类型 差错控制方式差错控制方式 差错控制编码的分类差错控制编码的分类

5、 差错控制编码的基本原理差错控制编码的基本原理 重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理数据错误的类型数据错误的类型随机差错：随机差错：某个码元的出错具有独立性，与前后码元无某个码元的出错具有独立性，与前后码元无关关突发差错突发差错成群的差错，其差错持续时间称为突发错的成群的差错，其差错持续时间称为突发错的长度。突发差错之间有一定的相关性，一个长度。突发差错之间有一定的相关性，一个差错往往要影响到后面的一串字。差错往往要影响到后面的一串字。重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理7.2 差错控制编码分类差错控制编码分类数据错误的类型数据错误的类型

6、 差错控制方式差错控制方式 差错控制编码的分类差错控制编码的分类 差错控制编码的基本原理差错控制编码的基本原理 重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理差错控制方式差错控制方式前向纠错方式（前向纠错方式（FECFEC）在发端采用某种在解码时能纠正一定程度传输差错的、在发端采用某种在解码时能纠正一定程度传输差错的、较复杂的编码方法，接收端在收到的信码中不仅能发较复杂的编码方法，接收端在收到的信码中不仅能发现错码，而且还能够纠正错误。现错码，而且还能够纠正错误。自动请求重传（自动请求重传（ARQARQ）在发端发送能够发现错误的码，收端则根据编码规则在发端发送能够发现错误的码

7、，收端则根据编码规则将收到的信码进行判决，若收端认为有错，则控制重将收到的信码进行判决，若收端认为有错，则控制重发指令，通过反馈信道告诉发端发指令，通过反馈信道告诉发端 混合纠错方式（混合纠错方式（HECHEC）混合纠错方式是前两种方式的结合混合纠错方式是前两种方式的结合少量错码，接收端自动进行纠错少量错码，接收端自动进行纠错大量错码，接收端请求重传大量错码，接收端请求重传重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理7.2 差错控制编码分类差错控制编码分类数据错误的类型数据错误的类型 差错控制方式差错控制方式 差错控制编码的分类差错控制编码的分类 差错控制编码的基本原理差错

8、控制编码的基本原理 重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理差错控制编码的分类差错控制编码的分类按照信道编码的不同功能分类按照信道编码的不同功能分类检错码和纠错码检错码和纠错码按照信息码元和监督码元之间的检验关系分类按照信息码元和监督码元之间的检验关系分类线性和非线性码。线性和非线性码。按照信息码元和监督码元之间的约束方式不同而分类按照信息码元和监督码元之间的约束方式不同而分类分组码和卷积码分组码和卷积码按照信息码元在编码后是否保持原来的形式分类按照信息码元在编码后是否保持原来的形式分类系统码和非系统码系统码和非系统码按照纠正错误的类型不同分类按照纠正错误的类型不同分类

9、纠正随机错误码和纠正突发错误码纠正随机错误码和纠正突发错误码按照信道编码所采用的数学方法不同分类按照信道编码所采用的数学方法不同分类代数码、几何码和算术码代数码、几何码和算术码重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理7.2 差错控制编码分类差错控制编码分类数据错误的类型数据错误的类型 差错控制方式差错控制方式 差错控制编码的分类差错控制编码的分类 差错控制编码的基本原理差错控制编码的基本原理 重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理差错控制编码的基本原理差错控制编码的基本原理基本概念：基本概念：码长：码字中码元的数目；码长：码字中码元的数目；汉明

10、重量：一个码字中非零码元的个数，称为汉明重量：一个码字中非零码元的个数，称为汉明重量；汉明重量；汉明距离：两个码字之间对应位取值不同的个汉明距离：两个码字之间对应位取值不同的个数，称为它们之间的汉明距离数，称为它们之间的汉明距离d d最小汉明距离：在码字集合中全体码字之间汉最小汉明距离：在码字集合中全体码字之间汉明距离的最小数值，表示为明距离的最小数值，表示为d dminmin。抗干扰能力与最小码距之间的关系抗干扰能力与最小码距之间的关系 重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理抗干扰能力与最小码距之间的关系抗干扰能力与最小码距之间的关系如果码集中码如果码集中码字间的最

11、小码字间的最小码距满足：距满足：则该码集中的则该码集中的码字具有检测码字具有检测e e个错码的能力个错码的能力如果码集中码如果码集中码字间的最小码字间的最小码距满足：距满足：则该码集中的则该码集中的码字具有纠正码字具有纠正t t个错码的能力个错码的能力 min1deeABd0min21dt1d0BtAt1d0BtAt如果码集中码字如果码集中码字间的最小码距满间的最小码距满足：足：则该码集中的码则该码集中的码字具有纠正字具有纠正t t个错个错码，检测码，检测e e个错码个错码的能力的能力 min1dteet 重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理编码效率编码效率在信道编

12、码过程中，监督位越多纠错能力在信道编码过程中，监督位越多纠错能力就越强，但编码效率就越低。若码字中信就越强，但编码效率就越低。若码字中信息位数为息位数为k k，监督位数为，监督位数为r r，码长，码长n=n=k+rk+r。1cnrkrRnnn 重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理主要内容主要内容7.1 概述概述 7.2 差错控制编码分类差错控制编码分类 7.3 线性分组码线性分组码 7.5 BCH码码7.6 交织码交织码7.8 纠错编码的性能纠错编码的性能7.7 卷积码卷积码7.4 循环码循环码 7.10 检错编码检错编码7.9 网格编码调制网格编码调制重庆大学通信

13、工程学院重庆大学通信工程学院数字通信原理数字通信原理7.3 线性分组码线性分组码 123重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理分组码是一组固定长度的码组，可表示为分组码是一组固定长度的码组，可表示为(n,kn,k)把信源输出的信息序列按把信源输出的信息序列按k k个相继码元分为一组个相继码元分为一组（信息组），并按一定规则对每一个信息组增加（信息组），并按一定规则对每一个信息组增加r=r=n-kn-k个校验码元，加到信息位之后，组成长度为个校验码元，加到信息位之后，组成长度为n n的新的码字，用的新的码字，用r r个监督位实现检错与纠错。个监督位实现检错与纠错。线性分

14、组码的主要性质：线性分组码的主要性质：封闭性：任意两准用码之和（对于二进制码这个和的封闭性：任意两准用码之和（对于二进制码这个和的含义是模二和）仍为一准用码；含义是模二和）仍为一准用码；码组间的最小码距等于非零码的最小汉明重量。码组间的最小码距等于非零码的最小汉明重量。重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理7.3 线性分组码线性分组码 123重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理7,4nk校验码与信息码之间的关系校验码与信息码之间的关系265416530643aaaaaaaaaaaa列线性方程组列线性方程组010011010010101100

15、010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa化为矩阵化为矩阵0001011001110101011101000123456aaaaaaa0000010101000111011101110123456aaaaaaa记为记为TTT=0 =0H AAH或重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理TTT=0 =0H AAH或111010011010101011001H校验矩阵校验矩阵TTT=0 =0 H AAH或分解分解1110 1001101 0101011 001 rHP ITQP1000111010011000101010

16、001011 kGI Q生成矩阵生成矩阵6543a a a aAG由生成矩阵可得整个码组由生成矩阵可得整个码组=TrrTkkHP IQ IGI QI P校验矩阵与校验矩阵与生成矩阵的关系生成矩阵的关系重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理7.3 线性分组码线性分组码 123重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理19501950年由汉明提出纠正单一随机错误的线年由汉明提出纠正单一随机错误的线性分组码，称汉明码性分组码，称汉明码 特点特点码长码长21rn 最小汉明距离最小汉明距离min3d信息位数信息位数21rkr 纠错能力纠错能力1t 监督位数

17、监督位数编码效率编码效率,3rnk r21121rrrKrRnn 表示方式表示方式,21,21rrn kr 重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理编码器和译码器编码器和译码器编码器编码器译码器译码器重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理主要内容主要内容7.1 概述概述 7.2 差错控制编码分类差错控制编码分类 7.3 线性分组码线性分组码 7.5 BCH码码7.6 交织码交织码7.8 纠错编码的性能纠错编码的性能7.7 卷积码卷积码7.4 循环码循环码 7.10 检错编码检错编码7.9 网格编码调制网格编码调制重庆大学通信工程学院重庆大学通信

18、工程学院数字通信原理数字通信原理7.4 循环码循环码1234重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理循环码是线性分组码中的一种，具有线性循环码是线性分组码中的一种，具有线性分组码的特性分组码的特性 循环码的数学特征循环码的数学特征1.1.封闭性，指循环码的码组中任两个码组之和封闭性，指循环码的码组中任两个码组之和（mod 2mod 2）必定为该码组集合中的一个码组。）必定为该码组集合中的一个码组。2.2.循环性，指循环码中任一码组循环一位（将循环性，指循环码中任一码组循环一位（将最右端的码移至左端或反之）以后，仍为该最右端的码移至左端或反之）以后，仍为该码组中的一个码组

19、，码组中的一个码组，循环码的码多项式循环码的码多项式 121210nnnnT xaxaxa xa重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理7.4 循环码循环码1234重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理(n,Kn,K)循环码有循环码有2 2K K个不同的码组个不同的码组用用g(xg(x)表示其中前表示其中前(K-1)(K-1)位皆为零的码组位皆为零的码组g(xg(x)、xg(xxg(x)、x x2 2g(x)g(x)、x xk-1k-1g(x)g(x)都是码组都是码组k k个码组是线性无关的，可以用来构成循环码个码组是线性无关的，可以用来构成循

20、环码的生成矩阵的生成矩阵G G 循环码的生成矩阵循环码的生成矩阵G G：12()()()()()kkxg xxg xG xxg xg x重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理n=7n=7，k=3k=3，n-kn-k=4=4唯一的一个唯一的一个(n-kn-k)次多项式代表的码组是第二码次多项式代表的码组是第二码组组00101110010111相对应的码多项式即生成多项式相对应的码多项式即生成多项式g(xg(x)=x)=x4 4+x+x2 2+x+1+x+1循环码表循环码表001011101011101011100)()()()(2xgxxgxgxxG变为典型阵变为典型阵

21、1001011()01011100010111G x重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理产生循环码的关键在产生循环码的关键在于求得生成矩阵于求得生成矩阵 求生成矩阵的关键在求生成矩阵的关键在于寻找一个适当的生于寻找一个适当的生成多项式成多项式g(xg(x)。任一循环码多项式任一循环码多项式T(xT(x)都是都是g(xg(x)的倍式，可的倍式，可写成写成:生成多项式生成多项式g(xg(x)本身本身也是一个码组，即有也是一个码组，即有:码组码组T(xT(x)为一为一(n-kn-k)次多项式，所以次多项式，所以x xk kT(xT(x)为一为一n n次多项次多项式，而且式

22、，而且x xk kT(xT(x)在在模（模（x xn n+1+1）运算下亦）运算下亦为一码组，可写成为一码组，可写成:T xh xg x Txg x 11knnx TxT xQ xxx()1Q x 1knx TxxT x 1()nkxg xxh x 重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理长为长为n n的循环码的生成多项式的循环码的生成多项式g(xg(x)必定是必定是(x(xn n+1)+1)中的一个中的一个(n-kn-k)次因式。次因式。(x(x7 7+1)+1)可以分解为：可以分解为：(7(7，3)3)循环码的生成多项式循环码的生成多项式g(xg(x)必定是上式必定

23、是上式中一个中一个(n-kn-k)=4)=4次的因子次的因子 1()nkxg xxh x 73231111xxxxxx 32423432111111xxxxxxxxxxxx重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理7.4 循环码循环码1234重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理(n,kn,k)循环码是由生成多项式循环码是由生成多项式g(xg(x)产生产生g(xg(x)的最高次幂为的最高次幂为r=r=n-kn-k，如果输入信息序列以多项式如果输入信息序列以多项式I(xI(x)表示，由于信息码元表示，由于信息码元为为k k个，个，I(xI(x)的最

24、高次幂为的最高次幂为k-1 k-1 x xn-kn-kI(xI(x)的最高次幂为的最高次幂为(n-k)+(k-1)=n-1(n-k)+(k-1)=n-1商式商式Q(xQ(x)的最高次幂为的最高次幂为(n-1)-(n-k)=k-1(n-1)-(n-k)=k-1；余式余式R(xR(x)的最高次幂为的最高次幂为n-k-1=r-1n-k-1=r-1。Q(xQ(x)的幂次与码组中校验码元数减的幂次与码组中校验码元数减1 1相对应相对应R(xR(x)的幂次与码组中校验码元数减的幂次与码组中校验码元数减1 1相对应相对应 n kxI xR xQ xg xg x重庆大学通信工程学院重庆大学通信工程学院数字通信

25、原理数字通信原理 F(xF(x)经过除法运算后所编成循环码的多项式经过除法运算后所编成循环码的多项式F(xF(x)是一个是一个(n-1)(n-1)次多项式次多项式x xn-kn-kI(xI(x)对应于输入信息序列对应于输入信息序列R(xR(x)对应于校验序列对应于校验序列循环码编码步骤循环码编码步骤1.1.用用x xn-kn-k乘乘I(xI(x)，在信息码后面加上，在信息码后面加上r=n-Kr=n-K个个“0”0”。2.2.用生成多项式用生成多项式g(xg(x)除除x xn-kn-kI(xI(x)，得到商式和余式，得到商式和余式3.3.编出码组，即联合编出码组，即联合R(xR(x)和和x xn

26、-kn-kI(xI(x)得到码多项式得到码多项式 n kxI xQ x g xR x n kF xxI xR xQ x g x重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理举例举例 【例例】生成多项式生成多项式g(xg(x)=x)=x4 4+x+1+x+1，n=15n=15，k=11,k=11,对对I(xI(x)=11101010001=x)=11101010001=x1010+x+x9 9+x+x8 8+x+x6 6+x+x4 4+1+1进行进行(15,11)(15,11)循环编码循环编码 15 111098641413121084+1n kxI xxxxxxxxxxxxx

27、 4109876421g x Q xxxxxxxxxxx长除法得商式和余式长除法得商式和余式 14131210843n kF xxI xR xxxxxxxx得新编码组得新编码组F=111010100011010数字序列数字序列重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理 在移存器工作的前在移存器工作的前1515拍中，开关拍中，开关K K倒向下，在移存倒向下，在移存器工作的前器工作的前4 4拍中，输出端一直是拍中，输出端一直是0 0，接着以后的，接着以后的1111拍，即拍，即5-155-15拍，拍，F(xF(x)=)=x xn-kn-kI(xI(x)，直接输出信，直接输出信息

28、位。息位。除法器中完成除法器中完成x xn-kn-kI(x)/g(xI(x)/g(x)的运算，移存器工作的运算，移存器工作的第的第1515拍结束时，除法器中存储的就是余式拍结束时，除法器中存储的就是余式R(xR(x)，即校验位。第即校验位。第1616拍开始，开关拍开始，开关K K倒向上边，一方面倒向上边，一方面切断反馈线，一方面在切断反馈线，一方面在16-1916-19拍中，将除法器所存拍中，将除法器所存的余式的余式(即校验位即校验位)送出送出重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理实际应用中往往采用后向编码器实际应用中往往采用后向编码器 编码的工作过程：编码的工作过程

29、：1.1.各级移位寄存器清各级移位寄存器清“0”0”，控制门，控制门1 1开，门开，门2 2关；关；2.2.11 11 位信息数字依次从输入端输入编码电路；同时送入信道，在每位信息数字依次从输入端输入编码电路；同时送入信道，在每加入一位信息数字时，各级移位寄存器移位一次。当加入一位信息数字时，各级移位寄存器移位一次。当11 11 位信息数位信息数字都输入移位寄存器后，移位寄存器中字都输入移位寄存器后，移位寄存器中 4 4位数字即为监督数字；位数字即为监督数字；3.3.控制门控制门1 1关，门关，门2 2开，寄存器中的存数（监督数字）依次移出，送开，寄存器中的存数（监督数字）依次移出，送入信道。

30、入信道。1111位信息数字和位信息数字和4 4位监督数字组成一个码字。位监督数字组成一个码字。重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理7.4 循环码循环码1234重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理任一多项式任一多项式T(xT(x)都能被都能被g(xg(x)整除，整除，可以利用接收到的码组可以利用接收到的码组P(xP(x)去除以原生成去除以原生成多项式多项式g(xg(x)进行检错进行检错当传输中没有发生错码时，接收码组和发送码当传输中没有发生错码时，接收码组和发送码组相同，能被组相同，能被g(xg(x)整除。整除。若有差错，只要差错不超过检错

31、范围，则接收若有差错，只要差错不超过检错范围，则接收码组必不能被码组必不能被g(xg(x)整除。整除。只要根据余式是否为零就可以判断码字中有无只要根据余式是否为零就可以判断码字中有无错误错误重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理译码步骤译码步骤梅吉特循环码译码器梅吉特循环码译码器 循环码译码电路的工作过程循环码译码电路的工作过程 重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理译码步骤译码步骤1.1.由接收到的码多项式由接收到的码多项式P(xP(x)计算校正子（伴计算校正子（伴随式）多项式随式）多项式R RE E(x(x)；2.2.由校正子由校正子R

32、RE E(x(x)确定错误图样确定错误图样E(xE(x)；3.3.将错误图样将错误图样E(xE(x)与与P(xP(x)相加，纠正错误。相加，纠正错误。第第1 1步运算和检错译码类似，也就是求解步运算和检错译码类似，也就是求解P(xP(x)整除整除g(xg(x)的余式，第的余式，第3 3步也很简单。步也很简单。因此，纠错码译码器的复杂性主要取决于因此，纠错码译码器的复杂性主要取决于译码过程的第译码过程的第2 2步。步。重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理译码步骤译码步骤梅吉特循环码译码器梅吉特循环码译码器 循环码译码电路的工作过程循环码译码电路的工作过程 重庆大学通信

33、工程学院重庆大学通信工程学院数字通信原理数字通信原理梅吉特循环码译码器梅吉特循环码译码器循环码通用译码器的组成：循环码通用译码器的组成：伴随式计算电路：可根据实际情况选取不同的伴随式电路。伴随式计算电路：可根据实际情况选取不同的伴随式电路。错误图样检测器：错误图样检测器是一个组合逻辑电路，其作用是将伴随错误图样检测器：错误图样检测器是一个组合逻辑电路，其作用是将伴随式译为错误图样。工作原理：式译为错误图样。工作原理：当且仅当错误图样是一个可纠的错误图样，并且此错误图样包含最高阶位上的当且仅当错误图样是一个可纠的错误图样，并且此错误图样包含最高阶位上的一个错误时，伴随式计算电路计算得到的伴随式才

34、使检测电路输出为一个错误时，伴随式计算电路计算得到的伴随式才使检测电路输出为“1”1”。即如果错误图样检测器输出为即如果错误图样检测器输出为“1”1”，则认为最高阶位上接收符号是错误的，则认为最高阶位上接收符号是错误的，应该予以纠正；如果检测器输出为应该予以纠正；如果检测器输出为“0”0”，则认为最高阶位上接收符号是正确，则认为最高阶位上接收符号是正确的，不必纠正。的，不必纠正。对于码组中任何位置上的错误，通过码组和伴随式同时循环移位，当错误符号对于码组中任何位置上的错误，通过码组和伴随式同时循环移位，当错误符号移到移到最高阶位上时，伴随式则使检测器输出为移到移到最高阶位上时，伴随式则使检测器

35、输出为“1”1”，将其错误纠正。，将其错误纠正。通过循环移位后，能使可纠错误图样中的全部错误都得到纠正。通过循环移位后，能使可纠错误图样中的全部错误都得到纠正。接收矢量缓存器和模接收矢量缓存器和模2 2和纠错电路。和纠错电路。重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理译码步骤译码步骤梅吉特循环码译码器梅吉特循环码译码器 循环码译码电路的工作过程循环码译码电路的工作过程 重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理循环码译码电路的工作过程循环码译码电路的工作过程1.1.将接收矢量移入伴随式计算电路，计算出伴随将接收矢量移入伴随式计算电路，计算出伴随式；同

36、时将接收矢量移入缓存器。式；同时将接收矢量移入缓存器。2.2.伴随式写入错误图样检测器，并在检测器中循伴随式写入错误图样检测器，并在检测器中循环移位，同时将接收矢量移出缓存器。环移位，同时将接收矢量移出缓存器。3.3.当检测器输出当检测器输出“1”1”时，表示缓存器此时输出符时，表示缓存器此时输出符号是错误的，并将错误纠正；同时检测器输出号是错误的，并将错误纠正；同时检测器输出反馈到伴随式计算电路的输入端，去修改伴随反馈到伴随式计算电路的输入端，去修改伴随式，从而消除错误对伴随式所产生的影响。式，从而消除错误对伴随式所产生的影响。4.4.当接收矢量全部移出缓存器，该接收矢量纠错当接收矢量全部移

37、出缓存器，该接收矢量纠错完毕。完毕。5.5.若最后伴随式寄存器中为全若最后伴随式寄存器中为全“0”0”，则表示错误，则表示错误全部被纠正，否则检出了不可纠的错误图样。全部被纠正，否则检出了不可纠的错误图样。重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理主要内容主要内容7.1 概述概述 7.2 差错控制编码分类差错控制编码分类 7.3 线性分组码线性分组码 7.5 BCH码码7.6 交织码交织码7.8 纠错编码的性能纠错编码的性能7.7 卷积码卷积码7.4 循环码循环码 7.10 检错编码检错编码7.9 网格编码调制网格编码调制重庆大学通信工程学院重庆大学通信工程学院数字通信原

38、理数字通信原理7.5 BCH码码BCHBCH码是循环码的一个重要子类，具有纠多码是循环码的一个重要子类，具有纠多个随机错误的能力个随机错误的能力BCHBCH码有严密的代数结构，是目前研究得最码有严密的代数结构，是目前研究得最为透彻的一类码。为透彻的一类码。生成多项式生成多项式g(xg(x)与最小码距之间有密切关与最小码距之间有密切关系，可以根据所要求的纠错能力系，可以根据所要求的纠错能力t t，构造出，构造出BCHBCH码，码，译码比较容易实现，是线性分组码中应用译码比较容易实现，是线性分组码中应用最为普遍的一类码。最为普遍的一类码。重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信

39、原理本原循环码的特点本原循环码的特点本原码的特点：本原码的特点：码长为码长为2m-12m-1，m m为正整数；为正整数；生成多项式是由若干生成多项式是由若干m m阶或以阶或以m m的因子为最高阶的因子为最高阶的多项式相乘而构成的。的多项式相乘而构成的。要确定要确定(2m-1(2m-1，k)k)循环码是否存在，只需判断循环码是否存在，只需判断2m-1-k2m-1-k阶的生成多项式是否能由阶的生成多项式是否能由x2m-1+1x2m-1+1的因的因式构成。式构成。重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理本原本原BCH码码若循环码的生成多项式具有如下形式：若循环码的生成多项式具

40、有如下形式：t t纠错个数纠错个数mi(xmi(x)最小多项式最小多项式LCMLCM取最小公倍式取最小公倍式由此生成的循环码称为由此生成的循环码称为BCHBCH码码最小码距最小码距d2t+1d2t+1纠纠t t个错误个错误码长码长为为n=2m-1n=2m-1或者或者2m-12m-1的因子。的因子。码长为码长为n=2m-1n=2m-1的的BCHBCH码称为本原码称为本原BCHBCH码码狭义狭义BCHBCH码。码。码长为码长为2m-12m-1因子的因子的BCHBCH码称为非本原码称为非本原BCHBCH码。码。g(xg(x)有有t t个因子，且每个因子的最高阶次为个因子，且每个因子的最高阶次为m m

41、，因此监督码因此监督码元最多为元最多为mtmt位。位。)(,),(),()(1231xmxmxmLCMxgt重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理BCH码的构成码的构成纠正纠正t t个错误的本原个错误的本原BCHBCH码的生成多项式：码的生成多项式：最小码距为最小码距为d=2t+1d=2t+1纠正单个错误的本原纠正单个错误的本原BCHBCH码，就是循环汉明码。码，就是循环汉明码。)()()()(1231xmxmxmxgt本本原原BCHBCH码码表表重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理BCH码的构成码的构成取表中的取表中的(15(15，5)5

42、)码，将它的码，将它的8 8进制生成多进制生成多项式写成二进制形式有项式写成二进制形式有010 100 110 111010 100 110 111，则可写出它的生成多项式：则可写出它的生成多项式：可从低位到高位逐位写出。可从低位到高位逐位写出。g(x)g(x)可写成它可写成它的最小公倍形式：的最小公倍形式：1)(245810 xxxxxxxg1)1)(1)(1()1(),1(),1()(,),(),()(24581022344223441231xxxxxxxxxxxxxxxxxxxxxxLCMxmxmxmLCMxgt重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理戈雷码戈雷码

43、(23(23，12)12)码是一个特殊的非本原码是一个特殊的非本原BCHBCH码，称码，称为戈雷为戈雷(GolayGolay)码码。该码码距为。该码码距为7 7，能纠正，能纠正3 3个随机错误，其生成多项式为：个随机错误，其生成多项式为：它的反多项式它的反多项式x x1111+x+x1010+x+x6 6+x+x4 4+x+x2 2+1+1也是生成也是生成多项式。容易验证，这是一个完善码，它多项式。容易验证，这是一个完善码，它的监督位得到了最充分的利用。的监督位得到了最充分的利用。1)(567911xxxxxxxg重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理扩展扩展BCH码

44、码BCHBCH码的码长为奇数。码的码长为奇数。在实际中，为了得到偶数码长，并增加其在实际中，为了得到偶数码长，并增加其检错性能，可以在检错性能，可以在BCHBCH码的生成多项式中乘码的生成多项式中乘上一个上一个(x+1)(x+1)因式，从而得到因式，从而得到(n+1(n+1，k+1)k+1)扩扩展展BCHBCH码，其码长为偶数。码，其码长为偶数。扩展扩展BCHBCH码相当于在码相当于在BCHBCH码上加上一个全校码上加上一个全校验位，扩展后码距增加验位，扩展后码距增加1 1。扩展扩展BCHBCH码不再具有循环性。码不再具有循环性。也可构成缩短也可构成缩短BCHBCH码。码。重庆大学通信工程学院

45、重庆大学通信工程学院数字通信原理数字通信原理主要内容主要内容7.1 概述概述 7.2 差错控制编码分类差错控制编码分类 7.3 线性分组码线性分组码 7.5 BCH码码7.6 交织码交织码7.8 纠错编码的性能纠错编码的性能7.7 卷积码卷积码7.4 循环码循环码 7.10 检错编码检错编码7.9 网格编码调制网格编码调制重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理7.6 交织码交织码定义：实际通信系统中常常存在突发性错误。突发错误一般定义：实际通信系统中常常存在突发性错误。突发错误一般是一个错误序列。纠正突发错误的通常采用交织编码。是一个错误序列。纠正突发错误的通常采用交

46、织编码。基本思路：基本思路：将将i i个能纠个能纠t t个错的分组码个错的分组码(n(n，k)k)中的码元比特排列成中的码元比特排列成i i行行n n列的方阵。列的方阵。每个码元比特记作每个码元比特记作B(iB(i，n)n)。遇连续。遇连续j j个比特的突发错误，个比特的突发错误，jtjt，错误，错误数远大于纠错能力数远大于纠错能力t t，无法正确纠错。，无法正确纠错。交织后，总的比特数不变，传输次序由原来的交织后，总的比特数不变，传输次序由原来的B(1,1),B(1,2),B(1,1),B(1,2),B(1,3)B(1,3)B(1,n),B(2,1),B(2,2),B(2,3)B(1,n),

47、B(2,1),B(2,2),B(2,3)B(2,n),B(2,n),B(i,1),B(i,2),B(i,3)B(i,1),B(i,2),B(i,3)B(i,nB(i,n)转变为转变为B(1,1),B(2,1),B(3,1)B(1,1),B(2,1),B(3,1)B(i,1),B(1,2),B(2,2),B(3,2)B(i,1),B(1,2),B(2,2),B(3,2)B(i,2)B(i,2)B(1,n),B(2,n),B(1,n),B(2,n),B(3,n),B(3,n),B(i,nB(i,n)的次序。突发错误图样落在分组码的纠错能力范围的次序。突发错误图样落在分组码的纠错能力范围内，可以正确

48、纠错错误。内，可以正确纠错错误。码组数码组数i i称为交织度，用这种方法构造的码称为交织码。称为交织度，用这种方法构造的码称为交织码。重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理图样说明图样说明重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理主要内容主要内容7.1 概述概述 7.2 差错控制编码分类差错控制编码分类 7.3 线性分组码线性分组码 7.5 BCH码码7.6 交织码交织码7.8 纠错编码的性能纠错编码的性能7.7 卷积码卷积码7.4 循环码循环码 7.10 检错编码检错编码7.9 网格编码调制网格编码调制重庆大学通信工程学院重庆大学通信工程学院数

49、字通信原理数字通信原理卷积码卷积码123重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理 卷积码的形成基础：使卷积码的形成基础：使n n、k k较小，又要纠较小，又要纠错能力大，考虑增加前后码组的相关性错能力大，考虑增加前后码组的相关性在任意给定时间单元内，编码器的在任意给定时间单元内，编码器的n n个输出个输出不仅与本时间单元的不仅与本时间单元的k k个输入码有关，而且个输入码有关，而且和前和前N=m+1N=m+1个时间单元的输入码元有关个时间单元的输入码元有关m m编码的记忆，表明输入的信息组在编码器编码的记忆，表明输入的信息组在编码器中需要存储的单位时间数中需要存储的单位

50、时间数N N约束度约束度(L+mL+m)译码的约束度译码的约束度(L+m)L+m)n n译码的约束长度。译码的约束长度。重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理卷积码卷积码123重庆大学通信工程学院重庆大学通信工程学院数字通信原理数字通信原理(n,k,mn,k,m)卷积码的编码卷积码的编码器器k k个输入端个输入端n n个输出端个输出端编码率编码率:R Rc c=k/nk/n每一个输入码字与本每一个输入码字与本码字时间单元内的输码字时间单元内的输入信息比特和前两个入信息比特和前两个时间单元内的输入信时间单元内的输入信息比特有关息比特有关输出序列的相邻码字输出序列的相邻码