《数字通信》课件第11章

11.1差错控制的基本概念11.2几种差错控制编码

11.1.1差错控制的基本方式

按照噪声或干扰的变化规律，可将信道分为三类，即随机信道、突发信道和混合信道。恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。具有脉冲干扰的信道是典型的突发信道，错误是成串成群出现的，即在短时间内出现大量错误。11.1差错控制的基本概念差错控制的根本目的是发现传输过程中出现的差错并加以纠正。差错控制基于两种思想：一是通过抗干扰编码，使得系统接收端译码器能发现错误，并能准确地判断错误的位置，从而自动纠正它们；二是在系统接收端仅能发现错误，但不知差错的确切位置，无法自动纠错，必须通过请求发送端重发等方式来达到纠正错误的目的。

1.差错控制编码概述

差错控制编码的作用是使被传输的信息具有检错和纠错能力，其基本思路就是在被传送的信息码序列中按照一定的规则加入监督码元。

2.差错控制编码中的基本术语

1)码长

编码码组的码元总位数称为码组的长度，简称码长。

2)码重

码组中，“1”码元的数目称为码组的重量，简称码重。

3)码距

两个等长码组之间对应位上码元不同的数目称为这两个码组的距离，简称码距。

对码距有以下几方面的要求：

(1)为检测e个错码，要求最小码距为dmax≥e+1,如图11.1(a)所示。

(2)为纠正t个错码，要求最小码距为dmin≥2t+1，如图11.1(b)所示。

(3)为纠正t个错码，同时检测e个错码(e>t),要求最小码距为dmin≥t+e+1，如图11.1(c)所示。图11.1对码距的要求

4)汉明距离

在一种编码中，任意两个码组间距离的最小值，称为这一编码的最小码距，或称为这一编码的汉明(Hamming)距离，用dmin表示。例如，在3位码组中，当8种码组都作为许用码组时，任意两码组间的最小距离为1，记作dmin=1。对于n=3的编码组，可以在三维空间中说明码距的几何意义，如图11.2所示。图11.2汉明距离

5)纠检结合

在某些情况下，要求对于出现较频繁但错码数很少的码组，按前向纠错方式工作；同时对一些错码数较多的码组，在超过该码的纠错能力后，能自动按检错重发方式工作，以降低系统的总误码率。这种方式就是“纠检结合”。

3.差错控制的基本工作方式

差错控制的基本工作方式有4种：前向纠错、检错重发、混合纠错检错和反馈校验。

常用的差错控制方式一般有下面4种类型，如图11.3所示。图11.3差错控制的基本工作方式

(a)前向纠错(FEC)；(b)检错重发(ARQ);(c)混合纠错检错(HEC);(d)反馈校验

1)前向纠错方式

前向纠错方式简称FEC。在FEC系统中，发端将输入数据序列按某种规则变换成能够纠正错误的码，接收端则按照商定的译编码规律，在收到信码后自动检测错码，且能够确定错码的位置并自动纠正，如图11.3(a)所示，从中可以看出，FEC系统仅有一条单向传输线路。

2)检错重发方式

检错重发简称ARQ，是数据通信中常用的一种差错控制方式，有时也称为自动重发请求。其示意图如图11.3(b)所示。

3)混合纠错检错方式

混合纠错检错方式(HEC)是前向纠错方式和检错重发方式的结合，如图11.3(c)所示。

4)反馈校验

反馈校验方式又称回程校验，如图11.3(d)所示。

反馈校验的优点是不需要纠错、检错的编解码器，设备简单；

缺点是需要有双向信道，实时性差，且每一信码都相当于至少传送了两次，所以传输效率低。11.1.2纠错编码分类

数字信号在传输中往往由于各种原因，使得在传送的数据流中产生误码。通过信道编码这一过程，对数码流进行相应的处理，使系统具有一定的纠错能力和抗干扰能力，可极大地避免码流传送中误码的发生。所以纠错检错码亦称为抗干扰码。抗干扰码大致有以下几种分类方式:

(1)按照差错控制编码的用途不同，可分为检错码、纠错码。

(2)按照信息码元和监督码元之间的函数关系，可分为线性码和非线性码。

(3)按码元之间的约束关系，可分为分组码和卷积码两类。

分组码是将信息序列以每k个码元分组，通过编码器在每k个码元后按照一定的规则产生r个监督码元，组成长度为n=k+r的码组，每一码组中的r个监督码元仅监督本码组中的信息码元，而与别组无关。分组码一般用符号(n，k)表示，其结构规定为图11.4所示的形式。分组码又可分为循环码和非循环码两类。图11.4分组码的结构卷积码是把信源输出的信息序列，以每k0个码元分段，通过编码器输出长为n0(n0＞k0)的一段码。但该段码的(n0-k0)个监督码元不仅与本段码信息码元有关，而且还与前面m-1段的信息码元有关，前后形成了约束关系。卷积码一般用(n0，k0，m)表示。

(4)按照信息码元在编码前后是否保持原来的形式不变，可分为系统码和非系统码。

(5)按照纠(检)错误的类型，可分为纠(检)随机错误码、纠(检)突发错误码和既能纠(检)随机错误又能纠(检)突发错误码。

(6)按照每个码元的取值可分为二进制码和多进制码。11.1.3编码效率

1.编码效率

用差错控制编码提高通信系统的可靠性，是以降低有效性为代价的。可定义编码效率来衡量有效性，编码效率指一个码组中信息位所占的比重，用R来表示。

其中，k为信息码元的数目(信息位长度)；n为编码组码元的总数(编码后码组长度：n=(k+r)；r为监督码元的数目(监督位长度)。

2.常用的几种简单编码

1)奇偶监督码

奇偶监督码是在原信息码后面附加一个监督码元，使得码组中“1”的个数是奇数或偶数，或者说，它是含一个监督码元，码重为奇数或偶数的(n，n-1)系统分组码。

2)行列监督码

奇偶监督码不能发现偶数个错误。为了改善这种情况，引入行列监督码。

3)恒比码

码字中“1”的数目与“0”的数目保持恒定比例的码称为恒比码。由于恒比码中，每个码组均含有相同数目的“1”和“0”，因此恒比码又称为等重码或定“1”码。

4)群计数码

群计数码是将信息码元分组后，计算每组码元中“1”的个数，然后将这个数目的二进制表示作为监督码元，一起送往发送端。11.2.1奇偶校验码

1.奇偶校验码的编码规则

奇偶校验码(监督码)是一种检错码，属于分组码。

校验码的构成是在n-1位信息位后加入1位校验位，形成n位传输码。

校验码的编码规则是：最后加入的校验码应该使n位传输码中“1”的个数为偶数(称为偶校验)或奇数(称为奇校验)。11.2几种差错控制编码在偶校验时，应满足以下条件：

an-1an-2

an-3

…

a1

a0=0

在奇校验时，应满足以下条件：

an-1

an-2

an-3

…

a1

a0=1

例如，用2位二进制数来表示晴天、多云、阴天、下雨四种天气现象。同时，按照偶校验规则插入监督位，形成表格如表11.1所示。表11.1偶校验监督码

2.垂直奇偶校验码

垂直奇偶校验码是在b7位表示字符的数据位后再附加第b8位校验位，表11.2以ASCII码的数字0～9为例说明垂直奇偶校验码的编码。接收端根据收到的b1～b7重新计算奇偶校验码元，将其与收到的b8相比较。如相同则无错，否则存在错误。

表11.2垂直奇偶校验

3.水平奇偶校验码

将要进行奇偶校验的码元序列按行排成方阵，每行为一组奇偶校验码(见表11.3)，但发送时则按列的顺序传输，接收端仍将码元排成发送时的方阵形式，然后按行进行奇偶校验。水平奇偶校验码可发现某一行上所有奇数个错误及所有长度小于等于方阵中行数的突发错。

表11.3水平奇偶校验码

4.二维奇偶校验码

二维奇偶校验码又称行列校验码或方阵码，其方法是在水平监督的基础上对表11.3所列方阵中每一列再进行奇偶校验，就可得到表11.4所示的方阵。发送是按列顺序传输的。表11.4二维奇偶校验码二维奇偶校验码的功能如下：

(1)能发现某行或某列上的奇数个错误和长度不大于行数(或列数)的突发错误。

(2)有可能检测出偶数个错码。

(3)可以纠正一些错误。

(4)检错能力强，又有一定纠错能力，且实现容易，因此得到广泛应用。11.2.2汉明码及线性分组码

1.由奇偶校验码想到的问题

奇偶校验码事实上是一种简单而常用的线性分组码，分为奇校验和偶校验。其特点是：无论信息码元有多少，监督码元只有一位。在偶校验中，监督码元的加入使得每个码字中“1”的数目为偶数；在奇校验中，监督码元的加入使得每个码字中“1”的数目为奇数。比如偶校验，由于使用了一位监督位a0，故它就能和信息an-1an-2an-3…a1

一起构成一个代数式

S=an-1

an-2

…

a1

a0

上式称为监督关系式,S称为校正子。在接收端解码时，实际上就是在计算S的值。若S=0，就认为无错；若S=1，则认为有错。一个S只有0和1两种取值，只能代表有错和无错两种信息，而不能指出错码的位置。如果监督位增加一位，即变成两位，则将会增加一个监督关系式，接收时按照两个监督关系式就可计算出两个校正子，记作S1和S2。S1，S2共有四种组合，即00，01，10，10，故能表示四种不同的信息。若用其中一种表示无错，则其余三种就有可能被用来指示一位错码的3处不同位置。

同理，r个校正子有2r种组合，可以用其中一种表示无错，其余(2r-1)种指示一个错码的(2r-1)个可能的位置。一般来说，若码长为n，信息位数为k，则监督位数r=n-k。若用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求

2r-1≥n

或2r≥k+r+1

该式称为汉明码必要条件。

2.汉明码

汉明码是1950年由Hamming提出的一种能纠正单个错误而且编码效率较高的线性分组码，是一种(n,k)线性分组码，它的最小码距dmin=3。关于线性分组码的分析方法全部适用于汉明码。它不仅性能好，而且编译码电路非常简单，易于工程实现，因此是工程中常用的一种纠错码。

前面已经指出，如果希望用r个监督码元构造的(n,k)线性分组码能够纠正一位错码，则要求2r-1≥n。设(n,k)线性分组码中k=4，为了纠正一位错码，则要求监督位数r≥3，码组为汉明码时取等号,则码字长度n=k+r=7。

(7，4)汉明码的许用码组如表11.5所示。表11.5(7，4)汉明码的许用码组

【例11.1】

设分组码(n,k)中k=4。为了纠正一位错码，要求监督位数r≥3，取等号，则n=k+r=7。用a6a5a4a3a2a1a0表示这7个码元，用S1S2S3表示3个监督关系式中的校正子，则S1S2S3对错码位置的编码如表11.6所示。表11.6校正子与错码的位置由表11.6可知，仅当发生一个错码，其位置在a2、a4、a5或a6，校正子S1为1，否则为0。这就意味着a2、a4、a5和a6四个码元构成偶数监督关系，即构成以下公式：同理a1、a3、a5和a6及a0、a3、a4和a6也分别构成偶数监督关系：(11－1)(11－2)(11－3)发送端编码时，监督位应使(11－1)~式(11－3)式中的S1,S2，S3均为0，于是有

已知信息位，就可算出监督位。解出监督位的值为

3.线性分组码

所谓线性码，是指信息码元与监督码元之间的关系可以用一组线性方程来表示。而分组码则表示将k个信息码元划分为一组，然后根据一定的编码规则由这k个信息码元产生r个监督码元，构成由n=k+r个码元组成的码字。

线性分组码(n,k)为系统码的结构如图11.5所示，码字的前k位为信息码元，与编码前原样不变，后r位为监督码元。一个n长的码字可以用矢量c来表示。图11.5(n，k)线性分组码为系统码的结构

1)监督矩阵

线性分组码是指分组码中信息码元和监督码元是用线性方程联系起来的一种差错控制码。类似于例11.1中的

汉明码，其校正子公式就是一组线性方程。现将它改写为再写成矩阵形式为可以看出，H的行数就是监督关系式的数目，它等于监督码元的数目r，而H的列数就是码长n，这样H为r×n阶矩阵。AT

即为编码器输出的码元组(an-1an-2…a1a0)。

矩阵H可以分成两部分H=[P

Ir]

2)生成矩阵

我们也可以把类似于例11.1中的监督位线性方程组写成矩阵形式：可以看出，公式右边第一个矩阵即为P。对上式两侧做矩阵转置，得要得到整个码组，将Q的左边加上一个k×k阶单位方阵，就构成一个新的矩阵G，即G=[IkQ]=

G称为生成矩阵，因为由它可以产生码组，即有

A=［a6a5…a1a0］=［a6a5a4a3］G

式(11－4)表明，如果找到了码的生成矩阵G，则编码的方法就完全确定了。具有［IkQ］形式的生成矩阵称为典型生成矩阵。

【例11.2】

设(7，4)线性码的生成矩阵为G＝

解：根据G=［IkQ］可知：Q=所以当信息位为0001时，其监督位为010。

4.线性分组码的主要性质

(1)封闭性。

(2)码的最小距离等于非零码的最小重量。

(3)监督关系。

11.2.3循环码

循环码是另一种线性分组码，所以，它具有线性码的一般性质，另外还具有循环性。码组中任一码组循环移位(左移或右移)所得的码组仍为该循环码中的一个许用码组。

从表11.7中可以直观地看出这种码组的循环性。表11.7(7,3)循环码的一种码组

1.码多项式

循环码可用多种方式进行描述。在代数编码理论中，通常用多项式去描述循环码，它把码字中各码元当做是一个多项式的系数，即把一个长为n的码字A=(an-1,an-2,…,a1,a0)用一个多项式表示为A(X)=(an-1xn-1,an-2xn-2,…,a1x1,a0x0)，称A(X)为码字A的码多项式。其中，x仅是码元位置的标记。例如，表中的第5码组可以表示为

A(X)=(0x6+1x5+0x4+1x3+1x2+0x1+0x0)

2.码多项式的按模运算

整数运算中有模运算，若一整数可以表示为

式中,Q为整数。在模运算下，有

m≡p(模n)

比如，在模2运算中，有

1+1=10≡0

1+10=10≡1

若一任意多项式F(X)被一个n次多项式N(X)除，得到商式Q(X)和一个次数小于n的余式R(X)，即

或

F(X)=Q(X)N(X)+R(X)

则写为

F(X)≡R(X)(模N(X))如表11.7中，码组6的多项式为x6+x4+x3+x2，其码长n=7，假定j=2，

则

x2(x6+x4+x3+x2)=x8+x6+x5+x4=x4+x2+x+1

而x4+x2+x+1正是码组2的多项式，其值为0010101。

可见，一个长为n的(n,k)循环码，它必是按模(xn+1)运算的一个余式。

3.循环码的生成多项式和生成矩阵

1)生成多项式

一个(n,k)循环码有2k个不同的码组，若所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式，或者说g(x)是所有码多项式个许用码组，即为所要求的码组。如表11.7中的10100即为最基本的码组，通过它的移位，可以得到所有码组。

2)生成矩阵

循环码的生成矩阵可以很容易地由生成多项式得到，常用矩阵的形式表示。根据循环码的特性，可由一个码字的循环移位得到其他非“0”码字。取前(k-1)位皆为“0”的码多项式g(x)，经过(k-1)次循环，得到k个多项式：

g(x),x1g(x),x2g(x),x3g(x),…,xk-1g(x)这些多项式显然是互相独立的，将其写成矩阵形式：G(x)=

4.循环码的编码方法

循环码引人注目的特点一是由于循环码固有的代数结构，从而可以找到各种简单实用的译码方法，二是可以很容易地用移位寄存器实现编码。

设码多项式A(x)=mn-1xn-1+mn-2xn-2+…+m1x+m0，其中系数mi∈{0,1}。

其中，在典型的码多项式中，信息位占n-1到n-k位的高k位；而从幂次n-k-1位到0位的系数均为0。信息位的码多项式为

mk-1xn-1+mk-2xn-2+…+m1x+m0=mk(x)

若用g(x)除信息位的码多项式，可得式中，r(x)为幂次小于(n-k)的余式。

式(11－5)可改写成

mk(x)+r(x)=Q(x)g(x)(11－6)

式(11－6)表明，多项式mk(x)+r(x)为g(x)的倍式，则mk(x)+r(x)必定是由g(x)生成的循环码中的码字，而r(x)为该码字的监督码元所对应的多项式。由此，可得到循环码的编码原则如下:

(1)根据给定的(n,k)值选定生成多项式g(x)。

(2)典型的码多项式实际上就是在信息码后附上(n-k)个“0”。

(3)用g(x)除mk(x)，得到商Q(x)和余式r(x)，即可编出码组：

A(x)=mk(x)+r(x)

【例11.3】

用生成多项式g(x)=x4+x3+1产生m(x)=x7+x6+x5+x2+x

对应的循环码组。

解

(1)用xn-k乘m(x),得

xn-km(x)=x4(x7+x6+x5+x2+x)=x11+x10+x9+x6+x5

(2)用g(x)除xn-km(x)，得余式r(x),即

(3)联合xn-km(x)和r(x),得到系统码多项式A(x)为

A(x)=x11+x10+x9+x6+x5+x2+x

得到码组A=111001100110。

5.解码方法在接收端可以将接收码组R(x)用原生成多项式g(x)去除，当余项r(x)为零时，无错码，当r(x)不为零时，有错码。循环码解码示意图如图11.6所示。图11.6循环码解码示意图11.2.4卷积码

卷积码(连环码)是一种非分组码，由埃里亚斯(Elias)于1955年最早提出，主要应用于前向纠错(FEC)数据通信系统中。

1.卷积码的基本概念

在分组码中，监督码元仅与本组的信息码元有关。卷积码常用符号(n，k，m)表示。其中，n为码长，k为码组中信息码元的个数，m为相互关联的码组的个数。其编码效率为R=k/n。卷积码的编码器是由一个有k个输入位(端)、n个输出位(端)，且具有m节移位寄存器所构成的有限状态的有记忆系统，通常称它为时序网络。

图11.7所示为卷积码编码器原理框图。若输入信息序列为u=u0u1u2…，则对应输出的两个码字序列为

c1=c10c11c12…

c2=c20c21c22…

其相应的编码方程可写为

c1=u*g1

c2=u*g2

其中“*”表示卷积运算，g1、g2表示编码器的两个脉冲冲激响应。图11.7卷积码编码器原理框图

2.卷积码编码器

图11.8所示是码长为3、信息码元为1、相互关联的码组数为2的(3,1,2)卷积码编码器。图11.8(3,1,2)卷积码编码器每一个单位时间，输入一个信息码元mi，且移位寄存器内的数据往右移一位。编码器有3个输出:一个输出是输入信息码元mi的直接输出；另外两个输出为监督码元pi1、pi2是输入mi与前两个单位时间送入的信息元mi-1、mi-2按照一定规则通过运算得到的。

卷积码码字中的每一个子码ci=(mi,pi1,pi2)最左边k0(这里k0=1)个码元是输入的信息码元，其余的是监督码元，这是系统码的形式。

3.卷积码的图形描述

卷积码不是分组码，但仍属于线性码，同样可以用矩阵的方法描述，但较抽象。常采用图解的方法直观描述其编码过程，常用的图解法有3种，即树状图、状态图和网格图。1)卷积码的树状图描述

以上图所示的(3,1,2)卷积码编码器为例来说明其工作过程。图11.9给出了卷积码的树状图。已知输入信息序列，由树状图就可以得到输出序列。当输入码元是“0”时，则由节点出发走上支路；当输入码元是“1”时，则由节点出发走下支路。例如当输入编码器的信息序列为0100…时，输出的序列为000101101010…。图11.9卷积码的树状图

2)卷积码的状态图描述

卷积码编码器是一个有限状态机，因此可以用状态转移图来描述。图11.10所示的是该(2，1，2)卷积编码器的状态图。图11.10(2,1,2)卷积码对应的状态转移图

3)卷积码的网格图描述

网格图也称网络图或篱笆图，它由状态图在时间上展开而得到。

由于树状图随路径长度L的增加，终端分支数呈指数增长，故对于大的L不可能画出编码树。把树的每一层上同类节点归并压缩，可得到网格图。(2,1,2)卷积码对应的网格图如图11.11所示。图11.11(2,1,2)卷积码对应的网格图11.2.5网格编码调制(TCM)

采用编码和调制相结合统一进行设计的方法，就是网络编码调制技术(TrellisCodedModulation，TCM)。它是利用编码效率为n/(n+1)的卷积码，将每一码段映射为2n+1个调制信号集中的一个信号，使信号点之间相互依赖。它有以下两个基本特点。

(1)在信号空间中的信号点数目比无编码的调制情况下对应的信号点数目要多，这些增加的信号点使编码有了冗余，而不牺牲带宽。

(2)采用卷积码的编码规则，使信号点之间引入相互依赖关系。在接收端采用维特比算法执行最大似然检测。编码网格状图中的每一条支路对应于一个子集，而不是一个信号点。检测的第一步是确定每个子集中的信号点，在欧氏距离意义下，这个子集是最靠近接收信号的子集。

图11.12描述了最简单的传输2比特码字的8PSK四状态TCM编码方案。它采用了效率为1/2的卷积码编码器，对应的格图如图11.13所示。图11.128PSK四状态TCM编码方案图11.138PSK四状态TCM编码格图

1.TCM提出的背景

为了适应电信工程中在模拟电话线上高速拨号上网传送数据的需求，即研究限带(0～4kHz)高速数据传输的要求，Ungerboeck提出了网络编码调制(TCM)的新概念。

(1)信号的抗干扰性能主要取决于调制后信号在欧氏空间的距离大小。

(2)一维调制MASK抗干扰性不如二维调制的MPSK和MQAM，因为在二维欧氏空间中信号点的距离比在一维欧氏空间中的大。

(3)在不增加总信号平均功率的条件下，信号点间的欧氏距离越来越密，这时要想进一步增加抗干扰性能，必须利用信道纠错码增大信号空间的维数，以进一步扩大信号点间的欧氏距离。

2.两类距离的概念

根据上面的分析，在调制中其抗干扰性主要取决于调制后信号点在欧氏空间中距离的大小，即被调信号在欧氏空间中的距离越大，其抗干扰性也就越强。

3.Ungerboeck子集划分理论

1982年，Ungerboeck对多进制情况下的两类距离的不一致性进行了深入的研究，并在此基础上提出了“子集划分”理论。

4.TCM的实现

从上面的讨论可以看出，TCM是通过扩展信号的星座图的大小，而不是利用传统的扩展频带来获取编码增益的，故其频谱效率高，称为高效编码调制。

这类最佳分割具有以下两个特点：

(1)星座中的所有信号点数大于未编码同类调制所需的信号点数，通常是信号点扩大1倍，扩大后多余的信号点为纠错编码提供了冗余度。

(2)采用卷积码在信号点之间引入某种依赖性，只有某些信号点序列是允许出现的，这些允许信号点序列可以模型化为网格结构，故称为网格编码调制。

5.TCM的应用

基于Ungerboeck对高效TCM的研究成果，很快将这一技术应用于模拟电话线(0～4kHz)的限带高速、高效数据传输中。1986年ITU－T通过了以Wei提出的8状态(3，2，4)非线性二维码为基础的V.32和V.33标准，后来又通过了仍以Wei提出的另一种以16状态(3，2，5)线性四维码为基础的V.34标准。11.2.6滑窗协议

现在需要解决的问题是：数据信息在信道上传输一旦检测出错误，如何纠正。在数字通信的许多场合经常采用的是自动重发方案，简称ARQ。

1.停等式ARQ

停等式ARQ的工作原理如图11.14所示。图11.14停等式ARQ的工作原理发送端利用正向信道发送码组1，当接收端收到后，经检验未发生错误，则在规定的停留时间TD内利用反向信道向发端发回确认信号ACK，表明已经接收完毕并无误。若接收端收到的码组经检验是错误码组(比如码组2接收错)，发送端收到NAK后重发码组2。

停等式ARQ因为在发送码组之间有停留时间TD，所以信道利用率低，但工作原理相对简单，因此在数字通信中仍有应用。

2.退回N步ARQ

在退回N步ARQ方式中，发送端可不等待应答信号到达而连续发送N帧数据，且每发完一帧后，都启动超时定时器，若发送方收到第一帧的确认帧，则继续发送第N+1帧，若接收到一否认帧或超时定时器到时仍未收到对方应答，则重发自该帧起的所有数据帧，即重发前N帧。有10帧数据需要传