通信原理西安电子科技大学黄葆华第二版第10章课件.ppt

1、第第10章章 信道编码信道编码 信道编码与差错控制信道编码与差错控制 几种简单的差错控制编码几种简单的差错控制编码 线性分组码线性分组码 循环码循环码 卷积码卷积码10.1 信道编码与差错控制信道编码与差错控制信道编码信道编码是按一定的规律给信息增加冗余度，使不带规律的原始数字信息变换为具有一定规律的数字信息。信道译码信道译码则是利用这些规律性来鉴别是否发生错误，进而则是利用这些规律性来鉴别是否发生错误，进而纠正错误。纠正错误。信道编码就是在发送端被传输的信息码元序列中，以一定的编码规则附加一些监督码元监督码元，接收端利用该规则进行译码，译码的结果可以发现错误或纠正错误。如何实现呢？如何实现呢

2、？10.1.1 信道编码的基本概念及差错控制编码的基本思想信道编码的基本概念及差错控制编码的基本思想10.1.2 差错控制方式差错控制方式对于不同类型的信道，应采用不同的差错控制技术。常用的差错控制方式主要有以下3种，如图10-1所示。图图10-1 3种差错控制方式比较种差错控制方式比较纠错码纠错码前向纠错记作FEC，又称自动纠错。在这种系统中，发端发送纠错码，收端译码器自动发现并纠正错误。FEC的特点是不需要反向信道，实时性好，FEC适合于要求实时传输信号的系统，但编码、译码电路相对较复杂。检错重发记作ARQ，又叫自动请求重发。在这种系统中，发端发送检错码，通过正向信道送到收端，收端译码器检

3、测收到的码字中有无错误。如果接收码字中无错误，则向发送端发送确认信号ACK，告诉发送端此码字已正确接收；如果收到的码字中有错误，收端不向发送端发送确认信号ACK，发送端等待一段时间后再次发送此码字，一直到正确接收为止。ARQ的特点是需要反向信道，编、译码设备简单。ARQ适合于不要求实时传输但要求误码率很低的数据传输系统。混合纠错记作HEC，是FEC与ARQ的混合。发端发送纠、检错码(纠错的同时检错)，通过正向信道送到收端，收端对错误能纠正的就自动纠正，纠正不了时就等待发送端重发。HEC同时具有FEC的高传输效率，ARQ的低误码率及编码、译码设备简单等优点。但HEC需要反向信道，实时性差，所以不

4、适合于实时传输信号。10.1.3 差错控制编码的分类差错控制编码的分类(1)按照差错控制编码功能的不同，可将差错控制编码分为检错码、纠错码和纠删码。检错码仅能检测误码；纠错码仅可纠正误码；纠删码则兼有纠错和检错能力。(2)按照信息码元与附加的监督码元之间的检验关系，可将差错控制编码分为线性码线性码与非线性码。(3)按照信息码元和监督码元之间约束方式的不同，可将差错控制编码分为分组码分组码与卷积码卷积码两类。在分组码中，编码后的码元序列每n位分为一组，其中包括k个信息码元和r个附加的监督码元，即n=k+r。每组的监督码元仅与本组的信息码元有关，而与其它码组的信息码元无关。卷积码则不同，虽然编码后

5、也划分为码组，但监督码元不仅与本组信息码元有关，而且还和其它码组的信息码元有关。(4)按照信息码元在编码后是否保持原来的形式，可将差错控制编码分为系统码系统码和非系统码。10.2 几种简单的差错控制编码几种简单的差错控制编码10.2.1 码长、码重与码距和编码效率码长、码重与码距和编码效率(1)码长:码字中码元的数目。(2)码重:码字中1的数目，一般用W表示。(3)码距:两个等长码字之间对应位不同的数目称为这两个码字的汉明(Hamming)距离，简称码距，用d表示。(4)最小码距:在码字集合中全体码字之间距离的最小数值。nk(5)编码效率:信息码元数与码长之比定义为编码效率。注：可求两个码字模

6、2加后新码字的码重。10.2.2 纠纠/检错能力与最小码距的关系检错能力与最小码距的关系在编码的码组集合中，任何两个可用码组之间距离的最小值称为最小码距dmin。dmin越大，说明两个码字之间的差别越大，检错和纠错能力也就越强。(1)一种编码的最小码距一种编码的最小码距d d0 0的大小直接关系着这种编码的检错的大小直接关系着这种编码的检错和纠错能力。为和纠错能力。为检测检测e e个错码，要求最小码距个错码，要求最小码距 d d0 0 e+1 e+1。(2)为了为了纠正纠正t t个错码，要求最小码距个错码，要求最小码距d d0 02t+12t+1。(3)为纠正为纠正t t个错码，同时检测个错码

7、，同时检测e e个错码，要求最小码距：个错码，要求最小码距：)(10teted 在在偶数监督码偶数监督码中，无论信息位多少，监督位只有中，无论信息位多少，监督位只有1位，它使码组中位，它使码组中(包包括监督码括监督码)“1”的数目为偶数，即满足下式条件的数目为偶数，即满足下式条件(监督方程监督方程)0021aaann式中式中a0为监督位，其他位为信息位。为监督位，其他位为信息位。这种编码能够这种编码能够检测检测奇数个错码。奇数个错码。10.2.3 奇偶监督码奇偶监督码1021aaann 奇数监督码奇数监督码与偶数监督码相似，只不过其码组中与偶数监督码相似，只不过其码组中(包括监督码包括监督码)

8、“1”的数目为奇数。编码时满足以下条件：的数目为奇数。编码时满足以下条件：只能检测出该码组是否有只能检测出该码组是否有奇数奇数个错码，不能检测偶数个错码，也不能找出错码个错码，不能检测偶数个错码，也不能找出错码的具体位置。的具体位置。10.2.4 二维奇偶监督码二维奇偶监督码（方阵码）（方阵码）二维奇偶监督码的构成：它是先把奇偶监督码的若干码组排二维奇偶监督码的构成：它是先把奇偶监督码的若干码组排成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位，如下图所示。位，如下图所示。012101212021222110111211cccc

9、aaaaaaaaaaaannmmmnmnnnnn 图中图中a01 a02 a0m为为m行奇偶监督码中的行奇偶监督码中的m个个监督位监督位。cn-1 cn-2 c1 c0为按列进行第二次编码所增加的监督位，它为按列进行第二次编码所增加的监督位，它们构成了一们构成了一监督位行监督位行。这种编码有可能检测这种编码有可能检测偶数个错码偶数个错码。但是分布在矩形的四个顶点。但是分布在矩形的四个顶点的偶数个错码无法检测。的偶数个错码无法检测。1 1 0 0 1 00 1 0 1 0 10 0 0 0 1 01 1 1 1 1 01 0 0 1 0 0监督码元(奇监督)监督码元(奇监督)10.2.5 恒比码

10、恒比码在恒比码中，每个码组均含有相同数目的在恒比码中，每个码组均含有相同数目的“1”（和（和“0”）。）。这种码在检测时，只要计算接收码组中这种码在检测时，只要计算接收码组中“1”的数目是否对，就知道有无错码。的数目是否对，就知道有无错码。若码长为若码长为n，码重为，码重为w，则此码的码字个数为，则此码的码字个数为wnC，禁用码字数为，禁用码字数为wnnC-2目前我国电传通信目前我国电传通信中普遍采用中普遍采用3 3：2 2码码(n=5(n=5，w=3)w=3)，该码，该码共有共有1010个许用码字，个许用码字，用来传送用来传送1010个阿拉个阿拉伯数字，如表所示。伯数字，如表所示。10.3

11、线性分组码线性分组码既是线性码又是分组码的码称为线性分组码。监督码元仅与本组信息码元有关的码称为分组码，监督码元与信息码元之间的关系可以用线性方程表示的码称为线性码。如(7，3)分组码码字用A=a6a5a4a3a2a1a0表示，前三位表示信息码元，后四位表示监督码元，4505614562463aaaaaaaaaaaaa(10-1)编码器的工作就是根据收到的信息码元，按编码规则计算监督码元，然后将由信息码元和监督码元构成的码字输出。线性分组码有一个重要特点：封闭性封闭性。码字集中任意两个码字对应位模2加后，得到的码字仍然是该码字集中的一个码字。线性分组码(n,k)的最小码距为d0=Wmin(Ai

12、)Ai(n,k),i0(10-2)图图10-2 (7,3)码的码字表最小码距d d0 0=4=4。10.3.1 线性分组码的编码线性分组码的编码00000451562456346aaaaaaaaaaaaa(10-3)0000 10001100100011001011100011010123456aaaaaaa(10-4)写成矩阵形式有TTAH0(10-5)1000110010001100101110001101H(10-6)(10-6)式称为此(7,3)分组码的监督矩阵。H的秩为r，等于监督码元的个数。这r行线性无关H=PIr即：1000010000100001 110011111101rIP

13、4505614562463aaaaaaaaaaaaa00000451562456346aaaaaaaaaaaaa(10-7)4564560123110011111101aaaPaaaaaaa两边求转置 TPaaaaaaa4560123令G=IkPT即：101110011100100111001G(10-8)6543210654a a a a a a aa a aG单位矩阵系统码编码后信息码元的位置不改变典型生成矩阵注：注：A=MGHPGA编码编码过程过程：若M=0 0 1，由上式计算可得：A=0 0 1101110011100100111001=0 0 1 1 1 0 1例例10.2 奇、偶监

14、督码是另一类简单的线性分组码，用(n,n-1)表示，长度为n的码字中信息码元为n-1个，只有1位监督码元。求长度为4的偶监督码的监督矩阵H和生成矩阵G。解：解：设长度为4的偶监督码的码字为A=a3a2a1a0，其中前3位表示信息码元，最后1位表示监督码元。(4，3)偶监督码中监督码元与信息码元满足如下关系此方程用矩阵表示为 0 11110123aaaa00123aaaaH=1 1 1 1=PI1P=1 1 1监督矩阵为其中1100101010013TPIG由A=MG可求得码字（如表10-1所示）。表10-110.3.2 线性分组码的译码线性分组码的译码设发送端发送码字A=an-1an-2a1a

15、0，此码字在传输中可能由于干扰引入错误，设接收码字B=bn-1bn-2b1b0，则发送码字和接收码字之差为B-A=E，E是码字A在传输中产生的错码矩阵，E=en-1en-2e1e0。如果A在传输过程中第i位发生错误，则ei=1，反之，则ei=0。若发送码字A=1001110，接收码字B=1001100，则错码矩阵E=0000010。错码矩阵通常称为错误图样错误图样。TTAH0由AHT=0当B=A时，有BHT=00为1行r列的全“0”矩阵。当BA时，说明传输过程中发生了错误，此时0)(TTTTTHEHEHAHEAHB令矩阵S=BHT=EHT称S为伴随式伴随式，伴随式S是个1行r列的矩阵，r是线性

16、分组码中监督码元的个数。两边求转置B-A=E以(7，3)码为例，具体说明线性分组码的译码过程。由S=BHT=EHT求出错误图样E与伴随式S之间的关系，并把它保存在译码器中。(1)由(7，3)线性分组码编码结论可知，此码最小码距d0=4，能纠正纠正码字中任意一位一位错误，码长为7的码字中错1位的情况有7种，即码字中错1位的错误图样有7种。如码字第一位发生错误，错误图样为E=10000001110100001000010000110111110011110000006THES由上式可看出，伴随式S6等于HT中的第一行。由此可求出错1位的7种错误图样所对应的伴随式，它们刚好对应HT中的7行。错误图样

17、与伴随式之间的对应关系如表10-2所示。表10-2(2)当译码器工作时，首先计算接收码字B的伴随式S，然后查表10-2得错误图样E。如接收码字为B=1100111，用式S=BHT=EHT求出其伴随式为0111010000100001000011011111001111100111THBS1110查表10-2得错误图样E=1000000，可知接收码字B中第一位有错误。(3)最后用错误图样纠正接收码字中的错误。A=B+E=1 1 0 0 1 1 1+1 0 0 0 0 0 0=0100111即：111001111101010011100001000010000100001S验证：错误消除译码译码过

18、程：(1)求S=BHT；(2)E；(3)A=B+E。(纠错)思考：思考：试验证（5,1）重复码最多能纠2位错误。重复码重复码是最简单的一类线性分组码。重复码是将1位信息编码成n位都相同的码字，用(n,1)表示。如(5，1)重复码的两个码字为：“00000”和“11111”。10.4 循环码循环码 若线性分组码的任一码字循环移位所得的码字仍在该码字集中，则此线性分组码称为循环码循环码。表10-3W=001426735W=4eg:(n,1)重复码是一个循环码。左移一位在讨论循环码时，常用代数多项式来表示循环码的码字，这种多项式称为码多项式。对于(n,k)循环码的码字，其码多项式的一般形式为 012

19、211.)(axaxaxaxAnnnnxxxxxA236)(码字中各位码元的数值是其码多项式中相应各项的系数值(0或1)。码字A=1001110的码多项式10.4.1 循环码的编码循环码的编码循环码完全由其码字长度n及生成多项式g(x)所决定。循环码中，除全“0”码字外，次数最低的码字多项式称为生成多项式。如(7，3)循环码中，生成多项式为g(x)=x4+x3+x2+1(n,k)循环码的生成多项式g(x)具有如下三个三个特性：(1)g(x)是xn+1的一个因子。(2)g(x)是r=n-k次多项式。(3)g(x)的常数项为1。表10-4x7+1=(x+1)(x3+x+1)(x3+x2+1)如寻找

20、(7，3)循环码，首先对x7+1进行因式分解，有它满足生成多项式的三个条件，所以(7，3)循环码的一个生成多项式为g(x)=x4+x3+x2+1此生成多项式可生成表10-4中所列的循环码。用多项式来表示生成矩阵的各行，则生成矩阵可写成)()(.)()()(21xgxxgxgxxgxxGkk(7，3)循环码，n=7，k=3，r=4，其生成多项式及生成矩阵分别为1)(234xxxxg1)()()()(23434524562xxxxxxxxxxxxgxxgxgxxG即101110001011100010111G(10-9)a)用生成多项式也可产生系统码的码字，系统循环码的码多项式可表示为A(x)=x

21、n-kM(x)+xn-kM(x)前一部分代表信息码元组，后一部分用 表示，是xn-kM(x)被g(x)除得的余式，它代表监督码元组。如(7，3)循环码，设信息M=110，则M(x)=x2+xxn-kM(x)=x4M(x)=x6+x5(10-10)求循环码码字的方法：当g(x)=x4+x3+x2+1时，求得余式为xn-kM(x)=x4M(x)=x6+x5=x3+1由式(10-10)得码多项式为A(x)=x6+x5+x3+1此码多项式对应的码字为“1101001”，是系统码系统码的码字，前三位是信息码元，后四位是监督码元。编码前后信息码元保持原样不变。利用多项式除法电路求xn-kM(x)除以g(x

22、)的余式，即可产生(n,k)系统循环码。g(x)=x4+x3+x2+1时，(7，3)循环码的编码器如图10-3所示：图图10-3 (7，3)循环码编码器D0D1D2D3是四级移位寄存器四级移位寄存器，反馈线的连接与g(x)的非非0系数系数相对应。编码时，首先将四级移存器清零。三位信息码元输入时，门1断开，门2接通，直接输出信息元。第3个移位脉冲后，D0D1D2D3中数据为除法余数，就是输入信息的监督码元。第47次移位时，门2断开，门1接通，输出监督元。表10-5b)由于循环码也是线性分组码，所以前面介绍过的线性分组码的编码方法同样适用于循环码。A=MG其中，M是信息矩阵；G是(10-9)式所示

23、的生成矩阵，但是它不是典型的生成矩阵。故由其得到的码字不是系统码字。101110001011100111001G101110001011100010111G1011100111001001110013TPIG(10-11)由由(10-11)式即可求出系统码字。式即可求出系统码字。101111100111TP其中 41011000111010011000100110001rHPIPI有了监督矩阵H，就可以用线性分组码的译码方法对循环码进行译码。10.4.2 循环码的译码循环码的译码A(x)=M(x)g(x)信息矩阵为M=mk-1 mk-2 m1 m0其中，M(x)=mk-1xk-1+mk-2xk

24、-2+m1x+m0为信息多项式。S(x)=B(x)如果接收的码字B(x)有错误，则g(x)不能整除接收码字多项式。则定义伴随多项式S(x)为：(10-12)B(x)=A(x)+e(x)e(x)为差错多项式 S(x)=A(x)+e(x)=e(x)伴随多项式只与差错多项式有关。伴随多项式只与差错多项式有关。(10-13)(10-14)发送码字生成多项式循环码的译码过程：(1)根据式(10-14)算出伴随式S(x)，将e(x)与S(x)的对应关系列成译码表；(2)当收到一个码字B(x)后，根据式(10-12)算出伴随式S(x)，对照译码表找到e(x)；(3)利用式(10-13)求出发送码字A(x)，

25、即A(x)=B(x)-e(x)。10.5 卷积码卷积码10.5.1 卷积码的编码卷积码的编码卷积码与线性分组码不同，每个(n,k)码字(通常称其为子码，码字长度较短)内的n个码元不仅与该码字内的信息码元有关，而且还与前面m个码字内的信息码元有关。卷积码常用(n,k,m)表示。m为编码存储，它反映了输入信息码元在编码器中需要存储的时间长短；N=m+1为编码约束度，它是相互约束的码字个数；nN为编码约束长度，它是相互约束的码元个数。图10-4 (2，1，2)卷积码编码电路1ja，2ja对应两个移位寄存器对应两个移位寄存器在图10-4所示的电路中，当输入信息10011时，求输出码字序列。表表10-6

26、11222jjjjjjjaaaaaaa子码中的两个码元与输入信息码元间的关系为编码存储m=2，约束度N=m+1=3，约束长度nN=6。(10-15)10.5.2 卷积码的图形描述卷积码的图形描述卷积码编码器的工作过程常用三种等效的图形来描述，这三种图形分别是：状态图、码树图和格状图。下面以图10-4所示的(2，1，2)卷积编码器为例，介绍这三种图形。1.状态图状态图图10-4所示的编码电路是个典型的米勒型(Mealy)时序逻辑电路。共有四个不同的状态：aj-1aj-2=00，10，01，11，可以将这四个状态分别用a、b、c和d来表示。由(10-15)式可求出输出序列如表10-7所示。表表10

27、-7表表10-710-7的图形表示就是的图形表示就是(2(2，1 1，2)2)卷积编码器的状态图，如图卷积编码器的状态图，如图10-510-5所示。所示。图10-5 (2，1，2)卷积编码器的状态图输入信息序列输入信息序列为为10011实线表示实线表示输入为输入为0 0虚线表示虚线表示输入为输入为12.码树图码树图图图10-6 (2，1，2)卷积码的码树图卷积码的码树图第三级开始四个状态全部出现第三级开始四个状态全部出现3.格状图格状图图图10-7 (2，1，2)卷积码的格状图卷积码的格状图bcabd第三级第三级输入信息序列输入信息序列为为1001110011小结：（1）差错控制方式的分类；（2）掌握线性分组码的概念；（3）会求线性分组码的生成矩阵、监督矩阵及码字的求解；（4）理解循环码的概念；（5）理解循环码的编码电路及译码过程；（6）了解卷积码的编码原理及三种图形描述方法。