第7章差错控制编码和m序列

第7章差错控制编码和m序列第一页，共51页。7.1概

述

差错控制编码，又称为信道编码、可靠性编码、抗干扰编码或纠错码，它是提高数字信号可靠性的有效方法之一。它产生于20世纪50年代初，发展到70年代趋向成熟。第二页，共51页。7.1.1信道编码在数字通信中，根据不同的目的，编码可分为信源编码和信道编码。信源编码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码。信道编码是为了降低误码率，提高数字通信的可靠性而采取的编码。为了提高系统的抗干扰性能，可以加大发射功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还可以采用信道编码技术。第三页，共51页。7.1.2差错控制方式常用的差错控制方式有3种：检错重发、前向纠错和混合纠错，第四页，共51页。图7-1差错控制方式第五页，共51页。1．检错重发方式检错重发又称自动请求重传方式，记作ARQ（AutomaticRepeatRequest）。如果发现错误，则通过反向信道把这一判决结果反馈给发端，然后，发端把收端认为错误的信息再次重发，从而达到正确传输的目的。其特点是需要反馈信道，译码设备简单，对突发错误和信道干扰较严重时有效，但实时性差，主要在计算机数据通信中得到应用。第六页，共51页。2．前向纠错方式前向纠错方式记作FEC（ForwardErrorCorrection）。发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。其特点是单向传输，实时性好，但译码设备较复杂。第七页，共51页。3．混合纠错方式混合纠错方式记作HEC（HybridErrorCorrection）是FEC和ARQ方式的结合。发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力，但能检测出来，则经过反馈信道请求发端重发。这种方式具有自动纠错和检错重发的优点，可达到较低的误码率。第八页，共51页。7.1.3纠错码的分类（1）根据纠错码各码组信息元和监督元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。（2）根据上述关系涉及的范围，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。（3）根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。第九页，共51页。7.1.4纠错编码的基本原理1．分组码分组码一般可用(n，k)表示。简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元，组成长为n的码字。在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余2n-2k个码字未被选用，称为禁用码组。第十页，共51页。码重和码距在分组码中，非零码元的数目称为码字的汉明重量，简称码重。例如，码字10110，码重w=3。两个等长码组之间相应位取值不同的数目称为这两个码组的汉明（Hamming）距离，简称码距。例如110000与10011之间的距离d=3。码组集中任意两个码字之间距离的最小值称为码的最小距离，用d0表示。最小码距是码的一个重要参数，它是衡量码检错、纠错能力的依据。第十一页，共51页。2．检错和纠错能力若分组码码字中的监督元在信息元之后，而且是信息元的简单重复，则称该分组码为重复码。它是一种简单实用的检错码，并有一定的纠错能力。例如（2，1）重复码，两个许用码组是00与11，d0=2，收端译码，出现01、10禁用码组时，可以发现传输中的一位错误。如果是（3，1）重复码，两个许用码组是000与111，d0=3；当收端出现两个或三个1时，判为1，否则判为0。此时，可以纠正单个错误，或者该码可以检出两个错误。第十二页，共51页。码的最小距离d0直接关系着码的检错和纠错能力；任一(n，k)分组码，若要在码字内：（1）检测e个随机错误，则要求码的最小距离d0≥e+1；（2）纠正t个随机错误，则要求码的最小距离d0≥2t+1；（3）纠正t个同时检测e(≥t)个随机错误，则要求码的最小距离d0≥t+e+1。第十三页，共51页。3．编码效率用差错控制编码提高通信系统的可靠性，是以降低有效性为代价换来的。我们定义编码效率R来衡量有效性：R=k/n其中，k是信息元的个数，n为码长。对纠错码的基本要求是：检错和纠错能力尽量强；编码效率尽量高；编码规律尽量简单。际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。第十四页，共51页。7.2常用的几种编码技术码

1．奇偶监督码奇偶监督码是在原信息码后面附加一个监督元，使得码组中“1”的个数是奇数或偶数。或者说，它是含一个监督元，码重为奇数或偶数的(n，n-1)系统分组码。奇偶监督码又分为奇监督码和偶监督码。第十五页，共51页。2．行列监督码

第十六页，共51页。3．恒比码

码字中1的数目与0的数目保持恒定比例的码称为恒比码。由于恒比码中，每个码组均含有相同数目的1和0，因此恒比码又称等重码，定1码。这种码在检测时，只要计算接收码元中1的数目是否正确，就知道有无错误。第十七页，共51页。我国邮电部门电传机传输汉字通信中普遍采用3:2码，又称“5中取3”的恒比码，这是5单位数字保护电报码。我国每个汉字用4位阿拉伯数字表示，每个阿拉伯数字用5个比特的码字表示。由于阿拉伯数字只有10个，因此从32中可能的码字中挑出=10个1的个数为3个的码字作为阿拉伯数字的编码方式。第十八页，共51页。7.2.2线性分组码现以（7，4）分组码为例来说明线性分组码的特点。设其码字为A=［a7a5a4a3a2a1a0］，其中前4位是信息元，后3位是监督元，可用下列线性方程组来描述该分组码，产生监督元。第十九页，共51页。7.2.3循环码循环码除了具有线性码的一般性质外，具有许多特殊的代数性质，如还具有循环性、并且简化译码算法，目前发现的大部分线性码与循环码有密切关系。循环码还有易于实现的特点，很容易用带反馈的移位寄存器实现其硬件。由于循环码具有码的代数结构清晰、性能较好、编译码简单和易于实现的特点，因此在目前的计算机纠错系统中所使用的线性分组码几乎都是循环码。它不仅可以用于纠正独立的随机错误，而且也可以用于纠正突发错误。第二十页，共51页。在代数理论中，为了便于计算，常用码多项式表示码字。(n，k)循环码的码字，其码多项式（以降幂顺序排列）为A(x)=an-1xn-1+an-2xn-2+a1x+a0第二十一页，共51页。表7-3（7，3）循环码

第二十二页，共51页。1．生成多项式如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式。在(n，k)循环码中任意码多项式A(x)都是最低次码多项式的倍式。如表7-3的（7，3）循环码中，g(x)=A1(x)=x4+x3+x2+1其他码多项式都是g(x)的倍式，即A0(x)=0*g(x)A2(x)=(x+1)*g(x)A3(x)=x*g(x)…A7(x)=x2*g(x)第二十三页，共51页。2．监督多项式为了便于对循环码编译码，通常还定义监督多项式，令第二十四页，共51页。3．编码方法和电路在编码时，首先要根据给定的(n，k)值选定生成多项式g(x)，即应在xn+1的因式中选一r=n-k次多项式作为g(x)。设编码前的信息多项式m(x)为：循环码的码多项式可表示为A(x)=xr*m(x)+R(x)第二十五页，共51页。图7-3（7，3）循环码编码电路

第二十六页，共51页。表7-4（7，3）循环码的编码过程

第二十七页，共51页。图7-4（7，3）循环码译码电路第二十八页，共51页。7.2.4卷积码1．基本概念卷积码又称为连环码，是1955年提出来的一种纠错码，它和分组码有明显的区别。（n，K）线性分组码中，本组r=n-k个监督元有关，与其他各组无关，也就是说分组码编码器本身并无记忆性。卷积码则不同，每个（n，k）码段（也称为子码，通常较短）内的n个码元不仅与该码段内的信息元有关，而且与前面m段的信息元有关。通常称m为编码存储。卷积码通常用符号（n，m，k）表示。第二十九页，共51页。图7-5卷积码（2，1，2）编码器

第三十页，共51页。输出码字C由下式确定C1=S1⊕S2⊕S3C2=S1⊕S3第三十一页，共51页。2．卷积码的描述和译码方法卷积码常用的描述方法有矩阵法、图解法。矩阵法太复杂，图解法直观。常用的图解法有3中：树图、状态图和格图。卷积码的译码方法有代数译码法和概率译码法。前者是利用生成多项式来译码，最大的方法是大数逻辑译码。后者又有两种方法：维特比译码和序列译码。目前，概率译码已成为卷积译码的最主要的方法。第三十二页，共51页。7.3m

序列m序列又叫作伪随机序列、伪噪声（PN）码或伪随机码。可以预先确定并且可以重复实现的序列称为确定序列。既不能预先确定又不能重复实现的序列称为随机序列。具有随机特性，貌似随机序列的确定序列称为伪随机序列。M序列是目前广泛使用的一种伪随机序列。第三十三页，共51页。7.3.1m序列的产生1．线性反馈移位寄存器m序列是由带线性反馈的移位寄存器产生的周期最长的一种二进制序列。线性反馈移位寄存器的一般结构如图7-6所示。它由n级移位寄存器、若干模二加法器组成线性反馈逻辑网络和时钟脉冲产生器（省略未画出来）连接而成。图中移位寄存器的状态用ai表示(i=0，1，…，n-1)，ci表示移位寄存器反馈线的连接状态，相当于反馈系数，ci=1表示此线接通，参与反馈逻辑运算，ci=0表示此线断开，不参与运算，c0=cn=1。第三十四页，共51页。图7-6线性反馈移位寄存器

第三十五页，共51页。2．m序列产生器用4级线性反馈移位寄存器产生的m序列，其周期为p=24-1=15，其特征多项式f(x)是4次本原多项式，能整除(x15+1)。先将(x15+1)分解因式，使各因式为既约多项式，再寻找f(x)。其中4次既约多项式有3个，但（x4+x3+x2+x+1）能整除（x5+1），故它不是本原多项式，因此找到两个4次本原多项式。（x4+x+1）和（x4+x3+1）。由其中任何一个都可以产生m序列。用f(x)=（x4+x+1）构成的m序列产生器如图7-7所示。第三十六页，共51页。设4级移位寄存器的初始状态为0001。C4=c1=c0=1，c3=c2=0。输出序列{ak}的周期长度为15。如表7-6所示的输出序列。第三十七页，共51页。表7-6{ak}输出序列

第三十八页，共51页。第3级和第4级的模二和的运算结果反馈到第1级。初始状态下，除了第3级为1外，其他3级均为0。随着移位时钟节拍，各级移位寄存器的状态发生转移，在第15节拍时，移位寄存器的状态与第0拍的状态（初始状态）相同，因此，从第16节拍开始必定重复第1～15节拍的过程。表明了移位寄存器具有周期性，其周期长度为15。输出序列：a4=1111第三十九页，共51页。对于n=4的移位寄存器共有24=16种不同状态。上述序列中出现了除全0以外状态的所有状态，因此是可能得到的最长周期序列。只要移位寄存器的初始状态不是全0，就能得到周期长度为15的序列。其实，从任何一级寄存器所得到的序列都是周期为15的序列，只不过节拍不同而已，这些都是最长线性反馈移位寄存器序列。第四十页，共51页。7.3.2m序列的性质M序列的周期数总是奇数。m序列每一周期中1的个数比0的个数多1个。由于p=2n-1为奇数，因而在每一周期中1的个数为(p+1)/2=2n-1为偶数，而0的个数为(p-1)/2=2n-1-1为奇数。上例中p=15，1的个数为8，0的个数为7。当p足够大时，在一个周期中1与0出现的次数基本相等。这就是m序列的一个最重要的特性---均衡性。第四十一页，共51页。7.3.3m序列的应用m序列在通信领域有广泛的应用，它可以用在扩频通信、卫星通信的码分多址，数字数据通信中的加密、加扰、同步、误码率测量等领域中。1．扩展频谱通信扩频通信是将待传送的基带信号在频域上扩展到很宽的频带，远远大于原来的信号带宽；在接收端再把已扩展的信号变换到原来的频带上，恢复出原来的基带信号。第四十二页，共51页。扩展频谱技术的理论基础是山农公式。对于加性白高斯噪声的连续信道，其信道容量C与信道传输带宽B及信噪比S/N之间的关系可以用下式表示这个公式表明，在保持信息传输速率不变的条件下，信噪比和带宽之间具有互换关系。第四十三页，共51页。扩频系统有以下特点：（1）具有选择地址能力；（2）信号的功率谱密度很低，有利于信号的隐蔽；（3）有利于加密，防止窃听；（4）抗干扰性强；（5）抗衰落能力强；（6）可以进行高分辨率的测距。扩频通信系统的工作方式有：直接序列扩频、跳变频率扩频、跳变时间扩频和混合式扩频。以上3种工作方式是基本的工作方式，最常用的是直扩方式和跳频方式两种。第四十四页，共51页。2．码分多址（CDMA）通信多址系统是指多个用户通过一个共同的信道交换消息的通信系统。传统的信号划分方式有频分复用和时分复用，相对应有频分多址系统和时分多址系统。码分多址系统是一种新的多址方式，它给每个用户分配一个多址码，以次来区