1、差错控制基本方法和编码要求差错控制基本方法和编码要求n为什么要进行差错控制n差错控制的基本方法n差错控制编码的基本概念n常用的简单编码n常用的线性分组码（1）差错产生的原因n数据通信系统的基本任务是高效率而无差错地传送数据。n数据信号在通信线路中传输时，难免受到来自信道内部和外部的干扰，从而引起信号的失真，导致数据传输错误。n传输出错的原因：一是信道的加性噪声；二是由于传输总特性（包括收、发滤波器和信道的特性）不理想引起的码间串扰。n噪声是影响数据传输质量的主要因素。n根据产生的原因可以将噪声分为四类：热噪声、交调噪声、串音和脉冲噪声四类。（2）噪声的类型n热噪声n是由带电粒子在导电介质中的布
2、朗运动引起的，它存在于任何工作在绝对零度以上的电路或系统中。n热噪声属于高斯白噪声，其概率密度函数满足正态分布统计特性，同时它的功率谱密度函数是均匀分布的（常数）。n热噪声的特点是：时刻存在、不可排除、幅度较小、强度与频率无关，但频谱很宽，是一类随机的噪声。噪声的类型n交调噪声n是一种附加的频率干扰。n由于通信系统的非线性，将导致进入通信系统的不同频率的信号在系统的输出端产生这些频率之间的差频信号或倍频信号及其组合，这就是交调噪声。n对于交调噪声可以通过适当的调制技术，人为地校正系统的非线性部分得到补偿。噪声的类型n串音n是一个通路的信号在相邻的另一个通路引起的干扰现象。这是由于信号线路之间的
3、电磁感应引起的有害耦合。n为了消除线路之间的有害耦合，可以将每一对线拧成一定扭绞节距的线缆。噪声的类型n脉冲噪声n是由于电火花或其他原因造成的突发振幅很大、持续时间比间隔时间短得多的离散脉冲耦合到信号通路中的干扰。n脉冲噪声也称为冲击噪声，它将引起一连串的数据比特出错，它是数据传输差错的主要根源。n脉冲噪声产生的干扰很难消除，只能采用差错控制的方法来实现可靠传输。（3）差错的类型n随机差错n指数据单元中的单比特差错。n它通常由传输信道的热噪声引起。n突发差错n指数据单元中的两个或两个以上的比特发生成串密集性的差错，第一个错误比特到最后一个错误比特之间的位数称为突发长度。n冲击噪声持续的时间通常
4、大于数据传输中每比特的发送时间，因而会引起相邻的多个数据位出错，从而导致突发差错。有差错的信道类型n按照噪声或干扰的变化规律，可把信道分为三类：n随机信道：恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。n突发信道：具有脉冲干扰的信道，是典型的突发信道。错误是成串成群出现的，即在短时间内出现大量错误。n混合信道：短波信道和对流层散射信道是混合信道的典型例子，随机差错和成串的突发差错都占有相当比例。（4）如何解决传输差错问题n提高物理信道的质量，尽量避免和减少差错：n采用电缆屏蔽措施和适当的调制解调方法n设置中继设备对信号进行整理再生和放大n加大发射功率，降
5、低接收设备本身的噪声，以提高信噪比n提高数据的健壮性，有效地进行检错和纠错：n采用信道编码技术，为数据信息增加冗余编码，形成抗干扰编码，使接收方能进行检错或纠错n配合适当的差错控制方法进行检错或纠错。第十章 差错控制n为什么要进行差错控制n差错控制的基本方法n差错控制编码的基本概念n常用的简单编码n常用的线性分组码差错控制的基本工作方式n自动反馈重发方式ARQn发端发送检错码，收端收到信码后能够检查出错误。n前向纠错方式FECn发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。n混合纠错方式HECn是FEC和ARQ方式的结合。n信息反馈方式IFn是不用编码的差错控制方式。（1）自
6、动反馈重发ARQ n自动反馈重发记作ARQ (Automatic Repeat Request )，又称自动请求重传方式。n发方按照一定的编码规则处理待发信息，构成具有检错能力的编码，发往传输信道；n收方判决传输中无错误产生，并通过反向信道把判决结果反馈给发方；n发方根据反馈的结果决定是否执行重传动作，如果接收方未正确接收，则重传信息(出错重传)n在规定的时间内，发方若未能收到应答信号(称为超时)，则可以认为传输出现差错，进而执行重传动作(超时重传)。主要的反馈重传方式 n反馈重传方式的特点是译码设备简单，对突发错误和信道干扰较严重时有效；但实时性差，主要在计算机数据通信系统中得到应用。 n常
7、用的反馈重传方式有：n发送-等待ARQ（停等协议）n连续发送ARQ（滑动窗口协议）n选择重传ARQ（2）前向纠错法FECn前向纠错方式记作FEC(Forword Error Correction)。n发送方按照一定的编码规则处理待发信息，构成具有纠正错误能力的代码(纠错码)发往传输信道；n接收方根据编码规则，检查传输差错，并自动加以纠正。n其特点是单向传输，实时性好，但译码设备较复杂。 （3）混合纠错法n混合纠错方式记作HEC(Hybrid Error Correction)是FEC和ARQ方式的结合。n发方发送具有一定纠错能力同时又具有检错能力的编码。n收方收到编码后，检查差错情况，如果错误
8、在编码的纠错能力范围以内，则自动纠错，否则经过反馈信道请求发方重发。（4）信息反馈法n信息反馈法记作IRQ (Information Repeat Request )n接收方把收到的信息代码全部送回发送方，由发送方进行差错检验。n发送方若发现传输差错，则重发信息代码，直至不再发现差错为止。几种差错控制方法比较n自动反馈重传法： n使用的编/解码设施比较简单，如果信道的质量差或干扰严重，则可能经常进入重发状态而影响通信效率。 n前向纠错法：n编/解码相对复杂，且编码的效率很低，但是无需专门的反馈信道。n主要应用于没有反馈信道的场合，或用于线路传播时间很长、要求重发在经济上不切实际的的场合。n由于
9、形成纠错码要求较多的冗余信息，当信道质量较好时，也影响了传输的效率。n混合纠错法：n编/解码相当复杂、且编码的效率很低，很少被采用。n信息反馈法：n反馈信息量太大，传输效率很低，很少被采用。第十章 差错控制n为什么要进行差错控制n差错控制的基本方法n差错控制编码的基本概念n常用的简单编码n常用的线性分组码差错控制编码的基本原理n差错控制的核心技术是信道编码技术，即采用适当的差错控制编码来传输信息。n差错控制编码的基本思想是在被传输信息中增加一些冗余码，利用附加码元和信息码元之间的约束关系加以校验，以检测和纠正错误，增加的冗余码元就称为监督码元（校验码元）。信道编码技术n对于n位的二进制码有N=
10、2n种组合。n如果这N种组合都用来传输信息，这样构成的编码并不具备抗干扰能力。n因为不管哪一位发生错误，都会使传输信息出错。n但是，若这N种组合并未完全使用，情况将会怎样呢？差错控制编码的抗干扰机理【例】考虑n=3的情形，3位二进制码有8种组合：000、001、010、011、100、101、110、111n若只用以下四个码组表示四个字母，其余的作为禁用码组：000 A011B101C110Dn则只要发生一位错误，准用码组就将变成禁用码组，接收端就能知道出错，但是不能纠错。n若只用两个码组作为有用码组000 A、111B，并将8个码组分为两个子集：000、001、010、100和011、101
11、、110、111，前者对应码组000，后者对应码组111。1.则接收端可以检测两位及以下的差错，或纠正一位的差错。【结论结论】增加监督码元的个数可提高纠增加监督码元的个数可提高纠检错能力。检错能力。抗干扰编码的理论依据n香农定理n在有噪声干扰的信道中，若信道容量为C，只要发送端以低于C的速率R发送信息（R为输入信道编码器的二进制码元速率），则一定存在一种编码方式，使数据的误码率随着码长n的增长将按指数下降到任一值。n结论n如码长及发送速率一定，可以通过增大信道容量，使误码率下降。n如信道容量及发送信息速率一定，可以通过增加码长，使误码率下降。码长、码重、码距n编码码组中的码元总位数称为码组的长
12、度，简称码长。n一个码组中，“1”码元的数目称为码组的重量，简称码重。n两个等长码组之间对应码位上码元不同的数目称为这两个码组的海明(Hamming)距离，简称码距。n一个码组集中任意两个码组之间距离的最小值称为码的最小距离。最小码距是抗干扰编码的一个重要参数，它是衡量编码检错、纠错能力的依据。【例】在前述例子中，码组集000、011、101、110的最小码距为2，而码组集000、111的最小码距为3。编码的检错和纠错能力n理论证明，编码的抗干扰能力与最小码距密切相关：n为检查出e个错误，要求最小码距为dmine+1n为纠正t个错误，要求最小码距为dmin2t+1n为纠正e个错误，同时检查出t
13、个错误，要求最小码距为dmine+t+1(et)编码效率n用差错控制编码提高通信系统的的可靠性，是以降低有效性为代价换来的。n定义编码效率R来衡量有效性：R=d/(d+r) 其中，d是信息码元的个数，r为校验码元个数 。n校验码元越长，编码的检错能力越强，编码/解码越复杂；附加的冗余信息在整个编码中所占的比例越大，传输的有效成分越低，传输的效率下降。对纠、检错码的基本要求n对纠、检错码的基本要求是: 检错和纠错能力尽量强、编码效率尽量高、编码规律尽量简单。 n实际中要根据具体指标要求，保证有一定的纠、检错能力和编码效率，并且易于实现。差错控制编码的分类n按照信息码元和监督码元之间的函数关系分为
14、：线性码和非线性码。n前者码元之间能满足一组线性方程组，后者则不然。n按照对信息元的处理方式分为：分组码和卷积码。n前者的各码元仅与本组的信息元有关；后者的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。n按照差错控制编码的用途分为：检错码和纠错码。n前者以检错为目的，不一定能纠错；而后者以纠错为目的，一定能检错。n按照码组中信息码元在编码前后是否相同分为：系统码和非系统码。分组码n分组码一般用(n,k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码长。n-k=r为每个码组中的监督码元数目。n简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元，组成码长为n
15、的码字。n在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余 2n-2k个码字未被选用，称为禁用码组。线性分组码n线性分组码是指信息码元与监督码元之间的关系可以用一组线性方程来表示的分组码。n在(n,k)分组码中，每一个监督码元都是码组中某些信息码元按模2和而得到的，线性分组码是一类重要的检/纠错码，应用很广。n本章介绍的差错控制编码均为线性分组码。第十章 差错控制n为什么要进行差错控制n差错控制的基本方法n差错控制编码的基本概念n常用的简单编码n常用的线性分组码常用的简单编码n奇偶校验码n水平奇偶校验（行校验）n垂直奇偶校验（列校验）n水平垂直奇偶校验（
16、方阵码）n定比码（恒比码）奇偶校验码 n奇偶校验码是在原信息码元后面附加一个监督码元，使得码组中“1”的个数为奇数或偶数。n因此，奇偶校验码是含一个监督码元，码重为奇数或偶数的（n,n-1）系统分组码。奇偶监督码又分为奇监督码和偶监督码。34奇偶校验码的特点 n设有n-1位信息码元为Cn-1，Cn-2，C1， 校验码为C0n对于偶校验，有10121CCCCnn00121CCCCnn 对于奇校验，有对于奇校验，有 奇偶校验码只能检测出代码序列中的奇数个错误。没有奇偶校验码只能检测出代码序列中的奇数个错误。没有纠错能力纠错能力 最小码距为最小码距为dmin=2 编码效率为编码效率为R=（n-1）/
17、n行、列监督码n奇偶校验码不能发现偶数个错误。为了改善这种情况，引入行、列监督码。n这类编码不仅对水平(行)方向的码元，而且对垂直(列)方向的码元实施奇偶校验。既可以逐行传输，也可以逐列传输。n这类编码具有较强的检测能力，适于检测突发错误，还有一定的纠错能力。水平奇偶校验（HRC） 水平奇偶校验之例 垂直奇偶校验（VRC） 垂直奇偶校验之例 水平垂直奇偶校验（LRC） n水平垂直奇偶校验码，也称为方阵校验码。它不仅对行进行奇偶校验，而且也对列进行奇偶校验。n这种方法按列传输时能发现所有长度=n+1 （n为码字长度）的突发性错误和其它错误；按行传输时能发现所有长度=m+1（m为码字个数）的突发性
18、错误和其它错误；并且具有一定的纠错能力。 水平垂直奇偶校验之例 定比码n定比码的码字中1的数目与0的数目保持恒定比例，也称为恒比码。n由于恒比码中，每个码组均含有相同数目的1和0，因此恒比码又称等重码，定1码。n这种码在检测时，只要计算接收码元中1的数目是否正确，就可判断有无差错。 定比码应用举例n我国电传通信中普遍采用3 2码，又称“5中取3”的定比码，即每个码组的长度为5，其中3个“1”。n这时可能编成的不同码组数目等于从5中取3的组合数10，这10个许用码组恰好可表示10个阿拉伯数字。而每个汉字又是以四位十进制数来代表的。n国际通用的ARQ电报通信系统采用“7中取3”的定比码。n“7中取
19、3”码可以检出所有的单比特差错和奇数个差错，但只能检出部分偶数位差错。第十章 差错控制n为什么要进行差错控制n差错控制的基本方法n差错控制编码的基本概念n常用的简单编码n常用的线性分组码循环冗余码（CRC）n循环码是一类重要的线性分组码，它除了具有线性码的一般性质外，还具有循环性，即循环码组中任一码组循环移位所得的码组仍为该循环码中的一许用码组。n循环冗余码（CRC码）是数据通信领域中最常用的一种差错检验码，其特征是信息码元和校验码元的长度可以任意选定。CRC码的原理n假定我们构成(n=7,k=3)这样的线性分组码，若已知三个信息码元为C6、C5和C4，而校验码元C3、C2、C1和C0是未知的
20、。校验码元与信息码元间的关系是根据以下四个线性关系式确立的。 3642654165054CCCCCCCCCCCCCCRC码的原理按上页编出的线性码为：信息码元信息码元码码 组组C6C5C4C6C5C4C3C2C1C000000000000010011101010010011101101110101001001110101101001111011010011111110100当我们从表中任当我们从表中任意挑选出两个码组意挑选出两个码组时，将对应比特按时，将对应比特按模模2相加，所得到相加，所得到的新码组仍然是表的新码组仍然是表中的某一码组。这中的某一码组。这说明由说明由8个码字组个码字组成的线性
21、码具有封成的线性码具有封闭性。闭性。封闭性是线性码封闭性是线性码的一个重要特性。的一个重要特性。循环冗余码的基本思想 n把要传输的数据信息当作一个报文码多项式f(x)的系数，发送时用一个标准的生成多项式G(x)来除f(x) ，将所除得余式R(x)的系数附加在报文码之后发出；n接收时用同一生成多项式G(x)来除收到的码字多项式，能除尽说明传输正确，否则说明有错。n实现：用简单的移位寄存器电路即可。码多项式 n从数学角度来看，所有的X进制数都可以用一个以X为基的多项式来表示。对于二进制数，基X=2，多项式的系数只取0、1。n对于长度为n的任一二进制码字，可以用一个x的n-1次多项式来表示。码字中每
22、个码元的值就是该多项式中的相应的系数。此多项式就成为码多项式。n如： Cn-1Cn-2C1 C0的码多项式为： Cn-1 xn-1 + Cn-2 xn-2+ C1 x1 + C0 x0 n又如：码字对应的多项式为x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的码字为101111。循环冗余码（CRC） 设：k个信息码元Cn-1，Cn-2，Cn-k对应的码多项式为f(x) ；r次的生成多项式为G(x) （n=k+r） ；n用G(x) 去除f(x) （模2运算）所得余式为R(x) ； f(x)= Cn-1 xk-1 + Cn-2 xk-2+ Cn-k x0 R(x)=Cr-1 xr
23、-1 + Cr-2 xr-2+ C0 x0 Cn-1，Cn-2，Cn-k，Cr-1，C0循环冗余编码工作原理 CRC校验码软件生成方法n设：信息代码M为，生成多项式为G(x)=x4+x3+1，n则：k=7，r=4，CRC码字长度为n=11 对应 f(x)=x6+x4+x3+1，G(x)的代码为nx4f(x)=x10+x8+x7+x4 对应的代码记为：10110010000；n采用多项式除法， 得余数为 1010 (即校验字段为1010)n发送方发出的传输编码为: 1 0 1 1 0 0 1 1 0 10 信息字段 校验字段n接收方使用相同的生成码进行校验，将接收到的字段除以生成码（二进制除法）
24、，如果能够除尽，则正确，否则出错。简化算法 例1n设信息代码 M = 1010001101，r = 5,G = 110101。n模 2 运算的结果是： 商 Q = 1101010110， 余数R = 01110。n将余数 R 作为冗余码添加在信息 M 的后面发送出去，即发送的数据是101000110101110，或 2rM + R。例1的计算过程 1101010110 Q 商 除数 P 110101 101000110100000 2rM 被除数 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 1101
25、01 01110 R 余数n 例2例3n原始数据M=1101011011G(x)=x4+x+1 的系数=10011传输码元传输码元=原始数据（左移位后）原始数据（左移位后）+余数余数 11010110111110标准CRC生成多项式G(x)nCRC-12：n G（x）= x12+x11+x3+x2+x+1nCRC-16：n G（x）= x16+x15+x2+1nCRC-CCITT：n G（x）= x16+x12+x5+1nCRC-32：n G（x）= x32+x26+x23+x22+x16+x12+x11+ x10 +x8+ x7+x5+x4 + x2+x+1 循环码的检错能力 n理论证明，C
26、RC码能查出：n全部的单个比特错误； n所有的离散的双位错（不相邻）； n全部 n-k（冗余位数）的突发性错误；n对于n-k+1位的突发性错误；检出率为1-2-(n-k-1) ；n对于多于n-k+1位的突发性错误；检出率为1-2-(n-k) ；n实验表明，如果使用16位冗余码n可以检出所有奇数位的差错及所有双位错，和长度小于16位的突发错误，还能查出99.997%的17位和99.998% 18位或更长位的突发性错误。 n传输速率为9600bps时，传输3000年才会有一个错误。海明码nHamming于1950年在美国贝尔实验室提出了海明码，是第一个用来纠错的线性分组码，被广泛地应用在数据通信和
27、数据存储系统的差错控制中。n所谓海明校验实质上是奇偶校验，是分组奇偶校验。它可以纠正一位差错。n设海明码长为n，监督码元的个数为r，海明码它利用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。海明码的特点n设码长为n，信息位为k位，监督码元的个数为r=n-k，n海明码长满足n=2r-1，r2且为正整数。给定r之后，即可确定n和k。n无论码长n为多少，海明码的最小码距为dmin=3。因此它只能纠正1位错码，通常用于前向纠错FEC的系统中1.海明码的编码效率为R=k/n=1-r/n，因此编码效率将随着码长增加而提高。海明码校验码的位权n海明码是分组奇偶校验码，每组校验位
28、P1，P2，P3，Pn的位权值为2n-1。n即所有2的幂次方的数据位就是奇偶校验位(对应编号为1, 2, 4, 8, 16, 32, 64等的位置) n其他数据位用于待编码数据. (编号为3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17等的位置) 海明码的构建n每个奇偶校验位的值代表了码字中部分数据位的奇偶性，其所在位置决定了要校验和跳过的比特位顺序：n位置1：每校验1位，跳过1位 (1,3,5,7,9,11,13,15,)n位置2：每校验2位，跳过2位 (2,3,6,7,10,11,14,15,)n位置4：每校验4位，跳过4位 (4,5,6,7,12,13,
29、14,15,20,21,22,23,)n位置8：每校验8位，跳过8位 (815,2431,4047,)nn如果全部校验的位置中有奇数个1，把该奇偶校验位置为1；如果全部校验的位置中有偶数个1，把该奇偶校验位置为0.海明校验码的生成示例n设发送信息为，把校验码P ，P2，P3，顺序插入信息码中，得海明码 PP21P3000P4101n分组：组组P1P21P3000P41011234编码，设发送与接收双方均采用奇校验，则编码，设发送与接收双方均采用奇校验，则P1 = 0，P2 = 1，P3 = 1，P4 = 1发送端发送的比特流为发送端发送的比特流为检错和纠错n接收端对海明码检错的方法就是逐个验证每一个校验位。假如有错，就累加出错的检验码元的位权。得到的就是错误信息所在的位置。n假定实际接收到的数据是 ，接收方验证每一个校验位验证，可以发现校验位P1、P2和P3的数据不正确。错误校验位的位权求和1+ 2 + 4 = 7, 表明位置7的数据出错。
