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

第10章

信道编码

信道编码与差错控制几种简单的差错控制编码线性分组码循环码卷积码10.1信道编码与差错控制

信道编码是按一定的规律给信息增加冗余度，使不带规律的原始数字信息变换为具有一定规律的数字信息。信道译码则是利用这些规律性来鉴别是否发生错误，进而纠正错误。信道编码就是在发送端被传输的信息码元序列中，以一定的编码规则附加一些监督码元，接收端利用该规则进行译码，译码的结果可以发现错误或纠正错误。如何实现呢？10.1.1

信道编码的基本概念及差错控制编码的基本思想10.1.2

差错控制方式

对于不同类型的信道，应采用不同的差错控制技术。常用的差错控制方式主要有以下3种，如图10-1所示。图10-1

3种差错控制方式比较纠错码前向纠错记作FEC，又称自动纠错。在这种系统中，发端发送纠错码，收端译码器自动发现并纠正错误。FEC的特点是不需要反向信道，实时性好，FEC适合于要求实时传输信号的系统，但编码、译码电路相对较复杂。检错重发记作ARQ，又叫自动请求重发。在这种系统中，发端发送检错码，通过正向信道送到收端，收端译码器检测收到的码字中有无错误。如果接收码字中无错误，则向发送端发送确认信号ACK，告诉发送端此码字已正确接收；如果收到的码字中有错误，收端不向发送端发送确认信号ACK，发送端等待一段时间后再次发送此码字，一直到正确接收为止。ARQ的特点是需要反向信道，编、译码设备简单。ARQ适合于不要求实时传输但要求误码率很低的数据传输系统。

混合纠错记作HEC，是FEC与ARQ的混合。发端发送纠、检错码(纠错的同时检错)，通过正向信道送到收端，收端对错误能纠正的就自动纠正，纠正不了时就等待发送端重发。HEC同时具有FEC的高传输效率，ARQ的低误码率及编码、译码设备简单等优点。但HEC需要反向信道，实时性差，所以不适合于实时传输信号。10.1.3差错控制编码的分类(1)按照差错控制编码功能的不同，可将差错控制编码分为检错码、纠错码和纠删码。检错码仅能检测误码；纠错码仅可纠正误码；纠删码则兼有纠错和检错能力。(2)按照信息码元与附加的监督码元之间的检验关系，可将差错控制编码分为线性码与非线性码。(3)按照信息码元和监督码元之间约束方式的不同，可将差错控制编码分为分组码与卷积码两类。在分组码中，编码后的码元序列每n位分为一组，其中包括k个信息码元和r个附加的监督码元，即n=k+r。每组的监督码元仅与本组的信息码元有关，而与其它码组的信息码元无关。卷积码则不同，虽然编码后也划分为码组，但监督码元不仅与本组信息码元有关，而且还和其它码组的信息码元有关。(4)按照信息码元在编码后是否保持原来的形式，可将差错控制编码分为系统码和非系统码。10.2几种简单的差错控制编码10.2.1

码长、码重与码距和编码效率(1)码长:码字中码元的数目。(2)码重:码字中1的数目，一般用W表示。(3)码距:两个等长码字之间对应位不同的数目称为这两个码字的汉明(Hamming)距离，简称码距，用d表示。(4)最小码距:在码字集合中全体码字之间距离的最小数值。(5)编码效率:信息码元数与码长之比定义为编码效率。注：可求两个码字模2加后新码字的码重。10.2.2

纠/检错能力与最小码距的关系在编码的码组集合中，任何两个可用码组之间距离的最小值称为最小码距dmin。dmin越大，说明两个码字之间的差别越大，检错和纠错能力也就越强。(1)一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力。为检测e个错码，要求最小码距d0≥e+1。

(2)为了纠正t个错码，要求最小码距d0≥2t+1。(3)为纠正t个错码，同时检测e个错码，要求最小码距：

在偶数监督码中，无论信息位多少，监督位只有1位，它使码组中(包括监督码)“1”的数目为偶数，即满足下式条件(监督方程)式中a0为监督位，其他位为信息位。这种编码能够检测奇数个错码。10.2.3奇偶监督码

奇数监督码与偶数监督码相似，只不过其码组中(包括监督码)“1”的数目为奇数。编码时满足以下条件：只能检测出该码组是否有奇数个错码，不能检测偶数个错码，也不能找出错码的具体位置。10.2.4

二维奇偶监督码（方阵码）

二维奇偶监督码的构成：它是先把奇偶监督码的若干码组排成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位，如下图所示。

图中a01a02

…a0m为m行奇偶监督码中的m个监督位。cn-1cn-2

…c1c0为按列进行第二次编码所增加的监督位，它们构成了一监督位行。这种编码有可能检测偶数个错码。但是分布在矩形的四个顶点的偶数个错码无法检测。

11

0

0

10

01

0

1

01

00

0

0

10

11

1

1

10

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

10.3线性分组码既是线性码又是分组码的码称为线性分组码。监督码元仅与本组信息码元有关的码称为分组码，监督码元与信息码元之间的关系可以用线性方程表示的码称为线性码。如(7，3)分组码码字用A=［a6a5a4a3a2a1a0］表示，前三位表示信息码元，后四位表示监督码元，(10-1)

编码器的工作就是根据收到的信息码元，按编码规则计算监督码元，然后将由信息码元和监督码元构成的码字输出。线性分组码有一个重要特点：封闭性。码字集中任意两个码字对应位模2加后，得到的码字仍然是该码字集中的一个码字。线性分组码(n,k)的最小码距为d0=Wmin(Ai)Ai∈(n,k),i≠0(10-2)图10-2

(7,3)码的码字表最小码距d0=4。10.3.1线性分组码的编码(10-3)(10-4)写成矩阵形式有(10-5)(10-6)(10-6)式称为此(7,3)分组码的监督矩阵。H的秩为r，等于监督码元的个数。这r行线性无关H=［PIr］即：(10-7)两边求转置令G=［IkPT］即：(10-8)单位矩阵系统码编码后信息码元的位置不改变典型生成矩阵注：A=M·G编码过程：若M=[001]，由上式计算可得：A=[001]=[0011101]例10.2奇、偶监督码是另一类简单的线性分组码，用(n,n-1)表示，长度为n的码字中信息码元为n-1个，只有1位监督码元。求长度为4的偶监督码的监督矩阵H和生成矩阵G。解：设长度为4的偶监督码的码字为A=［a3a2a1a0］，其中前3位表示信息码元，最后1位表示监督码元。(4，3)偶监督码中监督码元与信息码元满足如下关系此方程用矩阵表示为H=［1111］=［PI1］P=［111］监督矩阵为其中由A=M·G可求得码字（如表10-1所示）。表10-110.3.2线性分组码的译码设发送端发送码字A=［an-1an-2…a1a0］，此码字在传输中可能由于干扰引入错误，设接收码字B=［bn-1bn-2…b1b0］，则发送码字和接收码字之差为B-A=E，E是码字A在传输中产生的错码矩阵，E=［en-1en-2…e1e0］。 如果A在传输过程中第i位发生错误，则ei=1，反之，则ei=0。若发送码字A=［1001110］，接收码字B=［1001100］，则错码矩阵E=［0000010］。错码矩阵通常称为错误图样。由A·HT=0当B=A时，有B·HT=00为1行r列的全“0”矩阵。当B≠A时，说明传输过程中发生了错误，此时令矩阵S=B·HT=E·HT称S为伴随式，伴随式S是个1行r列的矩阵，r是线性分组码中监督码元的个数。两边求转置B-A=E以(7，3)码为例，具体说明线性分组码的译码过程。由S=B·HT=E·HT求出错误图样E与伴随式S之间的关系，并把它保存在译码器中。(1)由(7，3)线性分组码编码结论可知，此码最小码距d0=4，能纠正码字中任意一位错误，码长为7的码字中错1位的情况有7种，即码字中错1位的错误图样有7种。如码字第一位发生错误，错误图样为E=［1000000］由上式可看出，伴随式S6等于HT中的第一行。由此可求出错1位的7种错误图样所对应的伴随式，它们刚好对应HT中的7行。错误图样与伴随式之间的对应关系如表10-2所示。表10-2(2)当译码器工作时，首先计算接收码字B的伴随式S，然后查表10-2得错误图样E。如接收码字为B=［1100111］，用式S=B·HT=E·HT求出其伴随式为［1110］查表10-2得错误图样E=［1000000］，可知接收码字B中第一位有错误。(3)最后用错误图样纠正接收码字中的错误。A=B+E=［1100111］+［1000000］=［0100111］即：验证：错误消除译码过程：(1)求S=B·HT

；(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)循环码的码字，其码多项式的一般形式为码字中各位码元的数值是其码多项式中相应各项的系数值(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)如寻找(7，3)循环码，首先对x7+1进行因式分解，有它满足生成多项式的三个条件，所以(7，3)循环码的一个生成多项式为g(x)=x4+x3+x2+1此生成多项式可生成表10-4中所列的循环码。用多项式来表示生成矩阵的各行，则生成矩阵可写成(7，3)循环码，n=7，k=3，r=4，其生成多项式及生成矩阵分别为即(10-9)a)用生成多项式也可产生系统码的码字，系统循环码的码多项式可表示为A(x)=xn-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)的余式，即可产生(n,k)系统循环码。g(x)=x4+x3+x2+1时，(7，3)循环码的编码器如图10-3所示：图10-3

(7，3)循环码编码器D0D1D2D3是四级移位寄存器，反馈线的连接与g(x)的非0系数相对应。编码时，首先将四级移存器清零。三位信息码元输入时，门1断开，门2接通，直接输出信息元。第3个移位脉冲后，D0D1D2D3中数据为除法余数，就是输入信息的监督码元。第4~7次移位时，门2断开，门1接通，输出监督元。表10-5b)由于循环码也是线性分组码，所以前面介绍过的线性分组码的编码方法同样适用于循环码。A=M·G其中，M是信息矩阵；G是(10-9)式所示的生成矩阵，但是它不是典型的生成矩阵。故由其得到的码字不是系统码字。(10-11)由(10-11)式即可求出系统码字。其中∴有了监督矩阵H，就可以用线性分组码的译码方法对循环码进行译码。10.4.2循环码的译码A(x)=M(x)g(x)信息矩阵为M=［mk-1mk-2…m1

m0］其中，M(x)=mk-1xk-1+mk-2xk-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)，即A(x)=B(x)-e(x)。10.5卷积码10.5.1卷积码的编码卷积码与线性分组码不同，每个(n,k)码字(通常称其为子码，码字长度较短)内的n个码元不仅与该码字内的信息码元有关，而且还与前面m个码字内的信息码元有关。卷积码常用(n,k,m)表示。m为编码存储，它反映了输入信息码元在编码器中需要存储的时间长短；

N=m+1为编码约束度，它是相互约束的码字个数；n