新通信原理第11章27-28讲

1、第第1111章章 差错控制编码差错控制编码 由发送端的信道编码器在信息码元序列中增加一些由发送端的信道编码器在信息码元序列中增加一些监督码元监督码元，这些监督码元和信码之间有一定的关系，使，这些监督码元和信码之间有一定的关系，使接收端可以利用这种关系由信道译码器来发现或纠正可接收端可以利用这种关系由信道译码器来发现或纠正可能存在的错码。在信息码元序列加入监督码元就称为能存在的错码。在信息码元序列加入监督码元就称为差差错控制编码错控制编码，有时也称为有时也称为纠错编码纠错编码 对于不同类型的信道，应采用不同的差错控制技术。差错控制对于不同类型的信道，应采用不同的差错控制技术。差错控制方法，常用以

2、下三种：方法，常用以下三种： （1）检错重发法）检错重发法 （2）前向纠错法）前向纠错法 （3）反馈校验法）反馈校验法 111 线性分组码线性分组码 把要传送的把要传送的信息每信息每k k位分为一组位分为一组, ,送入编码器产生一个送入编码器产生一个n n位码位码长的码组长的码组。其中，。其中，n-kn-k=r=r，为每码组中的，为每码组中的监督码元监督码元数目。在分数目。在分组码中，监督码元仅与所在码组的信息码元有关，且二者之间组码中，监督码元仅与所在码组的信息码元有关，且二者之间是通过预定的线性关系联系起来的。因此，也称为是通过预定的线性关系联系起来的。因此，也称为线性分组码线性分组码。

3、在分组码中，把在分组码中，把1 1的数目称为的数目称为码组的重量码组的重量，简称简称码重码重 把两个码组对应位上数字把两个码组对应位上数字0 0，1 1不同的位数定义为两码组的距离，不同的位数定义为两码组的距离，称为称为汉明（汉明（HammingHamming）距离）距离, ,简称简称码距码距 所有码字之间汉明距离的最小值称为所有码字之间汉明距离的最小值称为最小码距最小码距 线性分组码线性分组码具有下面的性质具有下面的性质: : （1）任意两个码字之模任意两个码字之模2 2和仍为一个码字和仍为一个码字, ,即具有即具有封闭性封闭性. （2）码的）码的最小距离最小距离等于非零码的等于非零码的最小

4、重量最小重量.以以(7,4)码为例来说明如何构造这种线性分组码码为例来说明如何构造这种线性分组码 0123456CCCCCCC表示这表示这7个码元个码元 码长码长N=7; 信息分组信息分组k=4监督码元可按下面方程组计算：监督码元可按下面方程组计算： 346035614562CCCCCCCCCCCC信息位信息位监督位监督位对应码字对应码字信息信息位位监督位监督位对应码对应码字字00000000000000100011110001110001011000101110011001001100001010100101011010010101001000111100011110101100110110

5、010100110010011011000011100001010110101011011101010110101001100110110011111010011101000111000011100011111111111111每给出一个每给出一个4 4位的信息组，就可以编码输出一个位的信息组，就可以编码输出一个7 7位的码字位的码字： 上式的监督方程可上式的监督方程可以改写为以改写为： 000034613562456CCCCCCCCCCCC进一步，写成矩阵形式为进一步，写成矩阵形式为 ：0001001101010101100101110123456CCCCCCC记作：记作： TTHC0H称为

6、称为监督矩阵监督矩阵 （n-k）X n QIH 若把监督方程补充为下列方程若把监督方程补充为下列方程:34603561456233445566CCCCCCCCCCCCCCCCCCCC或或 :0TCH可改写为矩可改写为矩阵形式阵形式:345601234561101101101111000010000100001CCCCCCCCCCC3456CCCCGCTTGCCCCC3456G是一个是一个n X k阶阶生成矩阵生成矩阵 线性分组码的线性分组码的生成矩阵生成矩阵和和监督矩阵监督矩阵有着密切的关系有着密切的关系：TkkQIPIGrTrIPQIH1101000001010001100101110001

7、G例中（例中（7，4）线性码的）线性码的生成矩阵生成矩阵为：为： 线性分组码线性分组码由生成矩阵由生成矩阵G G生成生成(n,k(n,k) )线性码，传送后可以用监督线性码，传送后可以用监督矩阵矩阵H H来检验收到的码字是否满足监督方程来检验收到的码字是否满足监督方程 发送码组C在传输过程中可能发生误码，设接收到的码组为： 021rrrRnn则收发码组之差为： 021eeeCREnn1,2 , 110nicrcreiiiii因此， R=C+E TTTTEHCHHECRHS)(由于， 所以， 0TCHTEHS S称为接收码组R的校正子 由此可见校正子由此可见校正子S S只与错误图样只与错误图样E

8、 E有关，可以用校验子有关，可以用校验子S S作为判别错误作为判别错误的参量，如果的参量，如果S=0S=0，则接收到的是正确码字，若，则接收到的是正确码字，若 ，则说明，则说明R R中存在中存在着差错。着差错。0S线性分组码的线性分组码的最小距离（或最小重量）最小距离（或最小重量）直接关系到码的直接关系到码的检错和检错和纠错能力纠错能力。也即。也即(n,k(n,k) )线性码的检错和纠错能力主要由该码的最线性码的检错和纠错能力主要由该码的最小码距决定。小码距决定。 （a a）在一个码组内检测）在一个码组内检测e e个误码，要求最小码距个误码，要求最小码距1min ed（b b）在一个码组内纠正

9、）在一个码组内纠正t t个误码，要求最小码距个误码，要求最小码距12min td（c c）在一个码组内同时纠正）在一个码组内同时纠正t t个误码，检测个误码，检测e e个误码，个误码， 要求最小码距要求最小码距 1minetd 编码效率：定义编码效率：定义编码效率编码效率R R来衡量有效性来衡量有效性: :R R= =k/nk/n 其中其中, , k k是信息元的个数，是信息元的个数，n n为码长。为码长。 对纠错码的基本要求是对纠错码的基本要求是: : 检错和纠错能力尽量强；检错和纠错能力尽量强； 编码效编码效率尽量高；编码规律尽量简单。率尽量高；编码规律尽量简单。 实际中要根据具体指标要求

10、，实际中要根据具体指标要求， 保证有一定纠、保证有一定纠、 检错能力和编码效率，并且易于实现检错能力和编码效率，并且易于实现11.2 常用的几种简单分组码常用的几种简单分组码奇偶监督码奇偶监督码是在原信息码后面是在原信息码后面附加一个监督元附加一个监督元， 使得码组使得码组中中“1”的个数是奇数或偶数。或者说，它是含一个监督元，的个数是奇数或偶数。或者说，它是含一个监督元，码重为奇数或偶数的码重为奇数或偶数的(n,n-1)系统分组码。系统分组码。偶数监督码是使码组中偶数监督码是使码组中“1”的个数为的个数为偶数偶数，即：，即： 0021CCCNN奇数监督码是使码组中奇数监督码是使码组中“1”的

11、个数为的个数为奇数奇数，即：，即：1021CCCNN奇偶监督码的编码效率奇偶监督码的编码效率R为为 :NNR/ ) 1(1奇偶监督码奇偶监督码 2二维奇偶校验监督码：又称矩阵码二维奇偶校验监督码：又称矩阵码 1100101000001000011010011110000111001110000010101010101110001111003 3重复码：重复码：就是将信息重复传几次，只要正确传输的次数就是将信息重复传几次，只要正确传输的次数多于传错的次数，就可用少数服从多数的原则排除差错多于传错的次数，就可用少数服从多数的原则排除差错 4 4正反码：正反码：正反码是一种简单的能够纠正错码的编码。

12、其正反码是一种简单的能够纠正错码的编码。其中的监督位数目与信息位数目相同，监督码元是信息码元中的监督位数目与信息位数目相同，监督码元是信息码元相同（是信息码的反复）或者相反（是信息码的反码），相同（是信息码的反复）或者相反（是信息码的反码），则由信息码中则由信息码中1 1的个数而定。的个数而定。5汉明码：汉明码：汉明码是一种能够纠正一个错码或检两位错汉明码是一种能够纠正一个错码或检两位错且且效率较高的线性分组码。效率较高的线性分组码。TEHS S称为接收码组R的校正子,有 种状态对纠正一位差错码来说，要求监督关系的解能表示（n+1）种意义: 112rknrr2以汉明码(7,4)码为例来说明 0

13、123456CCCCCCC表示这7个码元 码长N=7; 信息分组k=4，r=3346035614562CCCCCCCCCCCC100110101010110010111HS1 S2 S3错误位置错误位置S1 S2 S3错误位置错误位置0 0 10 1 01 0 00 1 1C0C1C2C31 0 11 1 01 1 10 0 0C4C5C6无错无错校正子与错码对应关系校正子与错码对应关系5汉明码：汉明码：汉明码是一种能够纠正一个错码或检两位错汉明码是一种能够纠正一个错码或检两位错且且效率较高的线性分组码。效率较高的线性分组码。TEHS 113 循环码循环码 循环码是线性分组码的一个重要分支。循

14、环码有许多特殊循环码是线性分组码的一个重要分支。循环码有许多特殊的代数性质，基于这些性质，循环码有较强的纠错能力，而的代数性质，基于这些性质，循环码有较强的纠错能力，而且其编码和译码电路很容易用移位寄存器实现，因而在且其编码和译码电路很容易用移位寄存器实现，因而在F FECEC系统中得到了广泛的应用。系统中得到了广泛的应用。循环码最显著的特点是循环性循环码最显著的特点是循环性，即循环码中任一码组循环移位以后，仍为码中的一个码组。即循环码中任一码组循环移位以后，仍为码中的一个码组。 表表 、(7,3)循环汉明码循环汉明码在代数理论中，为了便于计算，常用在代数理论中，为了便于计算，常用码多项式表示

15、码字码多项式表示码字。( (n,kn,k) )循环码的码字，循环码的码字，其码多项式其码多项式( (以降幂顺序排列以降幂顺序排列) )为为02211)(cxcxcxCnnnnC(xC(x) )的的i i次循环移位码多项式次循环移位码多项式是原码多项式是原码多项式C(xC(x) )乘乘 除以除以 的余式，即的余式，即： 1nx) 1(mod)()(niixxCxxC 循环码的构成关键是循环码的构成关键是生成多项式生成多项式。(n,k(n,k) )循环码可以由循环码可以由它的一个它的一个n-kn-k码多项式码多项式g(xg(x) )来确定。且所有码多项式都是多来确定。且所有码多项式都是多项式项式g

16、 g( (x x) )的倍式，则称的倍式，则称g(xg(x) )为该码的为该码的生成多项式生成多项式。循环码生成多项式循环码生成多项式及及生成矩阵：生成矩阵：ix循环码的循环码的生成多项式生成多项式有以下性质：有以下性质： (a)(a)g(xg(x) )是唯一的（是唯一的（n-kn-k）次多项式，并且它的次数是最低的。）次多项式，并且它的次数是最低的。(b)(b)g(xg(x) )是的是的 因子，即：因子，即： 这里，这里，h(xh(x) )称为称为监督多项式监督多项式。1nx)()(1xgxhxn（n,k）dg(x)h(x)(7,6)(7,4)(7,.3)(7,1)2347x+1x3+x+1

17、(x3+x+1)(x+1)(x3+x+1)( x3+x2+1)(x3+x+1)( x3+x2+1)( x3+x2+1) (x+1)( x3+x2+1)x+1（7,k)7,k)循环码循环码例如例如(7,3)(7,3)循环码，循环码，n n=7, =7, k k=3, =3, r r=4,=4,其生成多项式及生成矩阵分别为其生成多项式及生成矩阵分别为 循环码的生成矩阵常用多项式的形式来表示循环码的生成矩阵常用多项式的形式来表示 )()()()()(21xgxxgxgxxgxxGkk1)(111xgxgxxgrrr 循环码的编码过程如下：循环码的编码过程如下：(a)(a)用用 乘乘m(xm(x) )

18、(b)(b)用用g(xg(x) ) 除除 ，得到商式得到商式Q(xQ(x) )和余式和余式r(xr(x) )(c) (c) 输出码组输出码组C(xC(x) )为为：knx)(xmxkn)()()()()(xgxrxQxgxmxkn)()()(xrxmxxCkn表 、(7,3)循环码的编码过程D0D1D2D3门1门2输入信息组输出码字1关于循环码的译码方法，接收端需要进行检错和纠错关于循环码的译码方法，接收端需要进行检错和纠错 在接收端可以将接收码组在接收端可以将接收码组R(x)用用g(x)去除去除 D0D1D2D37级缓存器接收码组B输出码组A&图 、 (7,3)循环码译码电路 434

19、 BCH码码 BCHBCH码码是一类是一类特殊的循环码特殊的循环码，它的纠错能力强，它的纠错能力强，能纠正能纠正多个随机错误多个随机错误。BCHBCH码的构造方便，编码简单，译码也较易码的构造方便，编码简单，译码也较易实现，在移动通信的信道环境中已得到广泛的应用实现，在移动通信的信道环境中已得到广泛的应用 设设n n是码长，是码长，k k为信息位数，为信息位数，t t是能纠正的错码数，是能纠正的错码数，d d是最小码距。是最小码距。对于任意给定的正整数对于任意给定的正整数m m和和t t, ,二元二元BCHBCH码具有下列参数：码具有下列参数：码长：码长： ；监督位数监督位数： 最小距离：最小

20、距离： 12mnmtkn12min td当给定当给定m或码长或码长n及纠错能力及纠错能力t时，时， BCH的的生成多项式生成多项式g(x)就随之确定就随之确定 特殊循环码：格雷码特殊循环码：格雷码GolayGolay，它是能纠正三个随机错误的，它是能纠正三个随机错误的（2323，1212）码，其容易解码，实际中使用的比较多。）码，其容易解码，实际中使用的比较多。 1)(23561011xxxxxxxg1)(567911xxxxxxxg其生成多项式：其生成多项式：或：或： 卷积码卷积码与分组码的区别在于本组的码元与分组码的区别在于本组的码元不仅与当前输入不仅与当前输入的的k k个信息有关，而且还

21、与以前个信息有关，而且还与以前m m个时刻输入的信息有关个时刻输入的信息有关。卷积码的纠错能力随着卷积码的纠错能力随着m m的增加而增大，而差错率随着的增加而增大，而差错率随着m m的的增加而指数下降。增加而指数下降。 11.4 卷卷 积积 码码 与与 交交 错错 编编 码码 在编码效率与设备复杂性相同的前提下，在编码效率与设备复杂性相同的前提下，卷积码的性卷积码的性能优于分组码能优于分组码 ; ;采用维特比译码技术的卷积码是一种非常有采用维特比译码技术的卷积码是一种非常有前途的信道编码。在前途的信道编码。在卫星通信、微波通信以及数字移动通卫星通信、微波通信以及数字移动通信中广泛被采用。信中广

22、泛被采用。1.卷积码的基本概念卷积码的基本概念m1m2数据输入码字输出S1S2S3C1C2图 、 卷积码(2,1,2)编码器输入编码器的一个信息元输入编码器的一个信息元k=1,k=1,编码器输出由两个码元编码器输出由两个码元n=2n=2组成的一个码组，称之为组成的一个码组，称之为子码子码 每个子码中的码元不仅与此时刻的信息元有关，而且还每个子码中的码元不仅与此时刻的信息元有关，而且还与前与前m=2m=2个时刻的信息元有关，称个时刻的信息元有关，称m m为为编码存储编码存储 称称N=m+1N=m+1为为编码约束度编码约束度。表示编码过程中相互约束的子码个数。表示编码过程中相互约束的子码个数 常把

23、卷积码记作常把卷积码记作(n,k,m(n,k,m) )，它的编码效率为，它的编码效率为 。 nkR/1 1） 码树图码树图 a1100abb0110cdc0011abd1001cd0010a1101ba0011a1100abb0110cdc0011abd1001cd1101c0010db1001a1100数码起点状态a00b01c10d11上半部下半部数码1101卷积码的描述：可以有多种不同的表示方法，如：卷积码的描述：可以有多种不同的表示方法，如：生成矩阵、生成矩阵、生成多项式，码树法，状态图法和网格图法生成多项式，码树法，状态图法和网格图法等可根据译码方法等可根据译码方法的不同采用不同的表

24、示法的不同采用不同的表示法 2） 状态图状态图a00b01c10d11cbad0101111100100010图 、(2,1,2)码的状态图 输入为1输入为03）网格图网格图 图 、 (2,1,2)码的格图 a00起点aaaaaabbbccccbbcbddddd000000000000000000100101010101010110101010111111111111101010100101输入为1输入为02 2、卷积码的、卷积码的维特比译码维特比译码卷积码译码方法有两类：卷积码译码方法有两类：一类是一类是大数逻辑译码大数逻辑译码，又称，又称门限译码门限译码；另一类是另一类是概率译码概率译码，

25、概率译码又分为，概率译码又分为维特比译码维特比译码和和序列译码序列译码两种。两种。 采用概率译码的一种基本思想采用概率译码的一种基本思想是是：把已接收序列与所有：把已接收序列与所有能够发送的序列做比较，选择其中码距最小的一个序列能够发送的序列做比较，选择其中码距最小的一个序列作为发送序列。作为发送序列。 维特比译码维特比译码则则对概率译码进行了简化，以至成为了一种实对概率译码进行了简化，以至成为了一种实用化的概率算法，它并不是在网格图上一次比较所有可能用化的概率算法，它并不是在网格图上一次比较所有可能的条路径（序列），而是接收一段、计算和比较一段，选的条路径（序列），而是接收一段、计算和比较一

26、段，选择一段有最大似然可能的码段，从而达到整个序列是一个择一段有最大似然可能的码段，从而达到整个序列是一个最大似然值的序列最大似然值的序列。 图79起点d80100(4)cba700(3)6500(3)4300(3)200(2)10 00(1)级11(1)11(3)11(3)11(3)10(2)10(4)00(3)01(3)01(3)10(3)10(3)10(3)01(1)01(1)01(5)00(2)11(2)收码01011010010001解码11010000图 、 维特比译码格图维特比维特比VitebiVitebi译码的基本思想译码的基本思想就是将接收序列就是将接收序列R R与网格图上的路径的每个与网格图上的路径的每个分支进行比较，然后分支进行比较，然后留下与留下与R R距离最小的路径距离最小的路径，称为，称为幸存路径幸存路径。而去掉。而去掉其余可能的路径，并将这些幸存路径逐分支地延长并存储起来，其余可能的路径，并将这些幸存路径逐分支地延长并存储起来，幸存路幸存路径的数目等于状态数径的数目等于状态数。由于这种方法较早地丢弃了那些不可能的路径，。由于这种方法较早地丢弃了那些不可能的路径，从而减轻了译码的工作量从而减轻了译码的工作量。 3交织编码（交