数据通信第三章

第三章差错控制数据通信要求信息传输具有高度的可靠性，即要求误码率足够低。然而，误码是不可避免的。造成误码的原因很多，但主要原因可以归结为两个方面:123.1差错控制的基本概念及原理信道不理想造成的符号间干扰——使接受波形发生畸变采样判决时会造成码间干扰。可通过均衡方法改善消除。噪声对信号的干扰——噪声叠加在接受波形上。消除噪声干扰产生误码的方法就是进行差错控制。3.1.1差错控制的基本概念1.差错分类

危害数据传输的噪声有两类：一类是随机噪声：包括热噪声、散弹噪声以及传输媒介引起的噪声等，引起随机差错；另一类是脉冲噪声：是指突然发生的噪声，包括雷电、开关引起的瞬态变化以及机电交换机的拨号脉冲等，引起突发差错。随机差错，又称独立差错，它是指那些独立地、稀疏地和互不相关地发生的差错。存在这种差错的信道称为无记忆信道或随机信道。产生的原因：随机噪声突发差错是指一串串，甚至是成片出现的差错，差错之间有相关性，差错出现是密集的。产生突发错误的信道称为有记忆信道或突发信道。产生的原因：脉冲噪声2.差错控制的基本思路差错控制的核心是抗干扰编码，或差错控制编码，简称纠错编码，也称信道编码。差错控制的基本思路是：

在发送端被传送的信息码序列（本身无规律）的基础上，按照一定的规则加入若干监督码元后进行传输，这些加入的码元与原来的信息码序列之间存在着某种确定的约束关系。在接收数据时，检验信息码元与监督码元之间的既定的约束关系，如该关系遭到破坏，则收端可以发现传输中的错误，乃至纠正错误。信息码（k）+监督码（r）=码组（n）加的监督码越多，差错控制能力越强3.差错控制的方法在数据通信系统中，差错控制一般可以分为4种类型。如图3-1所示:（1）检错重发检错重发简称（ARQ：自动重发请求）。这种差错控制方式在发送端对数据序列进行分组编码（如数据帧），加入一定多余码元使之具有一定的检错能力，成为能够发现错误的码组。接收端收到码组后按一定的规则进行有无差错的判决并把判决结果通过反向信道送回发送端，如有差错，发送端把前面发出的信息重新传送一次，直到接收端认为正确接收到信息为止。能够实现差错检测和差错恢复以及流量控制的功能。处理传输差错的重发技术有：差错检测技术；确认帧技术；否认帧技术；差错重发技术；超时重发技术。在具体实现检错重发系统时,通常有3种形式,即停等ARQ、返回重发ARQ和选择重发ARQ。Stop-and-WaitARQ

基本思路：停等ARQ是指发送端发送一帧数据并启动定时器，不能继续发送后续帧，而是等待接收方的确认帧或否认帧。接收端收到数据帧后经过检验如果没有发现差错，则向发送方返回一确认帧（ACK），再处理数据帧并交给上层，发送端收到ACK后认为该帧数据成功传输，取出下一帧再发送；如果接收方经过检验，发现有差错，则向发送端返回一否认帧（NAK），并丢弃出错帧，发送端收到NAK则认为传输出差错，则取出缓冲区里原来的数据进行重发。分为四种情况讨论：

a.数据在传输的过程中没有出现差错；

b.数据在传输过程中出现差错；

c.数据帧丢失情况；

d.确认帧（否认帧）丢失的情况。发收ACK0正确发收NAK0错误重发发收重发超时重发正确发收重发正确ACK0超时重发正确重复帧(1)(2)(3)(4)01000000连续ARQ

基本思路：发送端连续地发送一系列的数据帧，而暂时不需要等待前面所发数据帧的确认便发送下一帧。连续ARQ把等待时间利用起来，传输效率大大提高。传输信道是不可靠的，如果已经连续发送到链路上的数据帧中，某一帧数据发生了差错或丢失，在发送端发现已近出现差错之前，很多后续帧就会达到接收端，接收端应当丢弃出错数据帧，同时还必须保证发送顺序交给上层，因此，接收端对后续正确的数据帧处理方式决定了发送端的重发机制，可将连续的ARQ分为返回重发ARQ和选择性重发ARQ。返回重发012312345发6WT=7012312345收6WR=1丢弃等待1号帧交上层处理一般地，当差错检测发现第I帧错误，则接收方给出否认帧信息，并丢弃出错帧及后续帧。发送方退回到第I帧，重发第I帧及I帧的后续帧。选择性重发012314567发0WT>1012314567收0WR>1暂存缓存等待1号帧一起交上层处理ACK3③ARQ的优缺点●需反向信道，实时性差。●ARQ方式在信息码后面所加的监督码不多，所以信息传输效率较高。●译码设备较简单（2）前向纠错（FEC）①FEC的思路

前向纠错系统中，发送端的信道编码器将输入数据序列变换成能够纠正错误的码，接收端的译码器根据编码规律检验出错误的位置并自动纠正。②FEC的优缺点●不需要反向信道，实时性好。●缺点是所选择的纠错码必须与信道的错码特性密切配合，否则很难达到降低错码率的要求；●译码设备复杂；而要求附加的监督码也较多，传输效率就低。(3)混合纠错检错（HEC）

①HEC的思路

混合纠错检错方式是前向纠错方式和检错重发方式的结合。在这种系统中，发送端发出同时具有检错和纠错能力的码，接收端收到码后，检查错误情况，如果错误少于纠错能力，则自行纠正；如果干扰严重，错误很多，超出纠正能力，但能检测出来，则经反向信道要求发端重发。

②HEC的优缺点

混合纠错检错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷，因而近年来，在数据通信系统中采用较多。(4)信息反馈（IRQ）①IRQ的思路

信息反馈方式(IRQ)在发送端不进行纠错编码，接收端把收到的数据序列全部由反向信道送回发端，发端自己比较发送的数据序列与送回的数据序列，从而发现是否有错误，并把认为错误的数据序列的原数据再次传送，直到发端没有发现错误为止。②IRQ的优缺点●这种方式的优点是不需要纠错、检错的编译器，设备简单。●缺点是需要和前向信道相同的反向信道，实时性差。●发送端需要一定容量的存储器以存储发送码组，环路时延越大，数据速率越高，所需存储容量越大。3.1.2差错控制的基本原理1.差错控制的原理

纠错编码之所以具有检错和纠错能力，是因为在信息码之外附加了监督码，即码的检错和纠错能力是用信息量的冗余度来换取的。加入监督码越多，码的检错、纠错能力越强，但信息传输效率下降也越多。在纠错编码中将信息传输效率也称为编码效率，定义为

k为信息位长度，n为编码的总长度，n-k为监督元的长度。R越大编码效率越高，它是衡量码性能的一个重要参数2.汉明距离与检错和纠错能力的关系（1）几个概念码组的重量——码组中非零码元的数目为码组的重量，简称码重。码距——把两个码组中对应码位上具有不同二进制码元的个数定

义为两码组的距离，简称码距。汉明距离——在一种编码中，任意两个许用码组间距离的最小值，称为这一编码的汉明距离，以表示。3.差错控制编码的分类(1)按码组的功能分,有检错码和纠错码。(2)按监督码与信息码元之间的关系分,有线性码和非线性码。(3)按照对信息码元处理方法的不同分,有分组码和卷积码。(4)按照信息码元在编码前后是否保持原来的形式不变——可划分为系统码和非系统码。（5）按纠正差错的类型——可分为纠正随机错误的码和纠正突发错误的码。（6）按照每个码元取值来分——可分为二进制码与多进制码。3.2简单的差错控制编码3.2.1奇偶监督码1.基本概念

这是一种最简单的检错码,又称奇偶校验码。其编码规则是先将所要传输的数据码元分组,在每组数据后面附加一位监督位,使得该组码连同监督位在内的码组中的“1”的个数为偶数(称为偶校验)或奇数(称为奇检验),在接收端按同样的规律检查,如发现不符就说明产生了差错,但是不能确定差错的具体位置,即不能纠错。设码组长度为n，表示为(

)，其中前n-1位为信息码元，第n位为监督位a0。偶检验的监督关系在奇校验的监督关系2.检错能力(1）只能检测奇数个错误，而不能检测出偶数个错误。（2）适合检测随机差错。3.2.1水平奇偶监督码

水平奇偶监督码的构成思路是：将信息码序列按行排成方阵，每行后面加一个奇或偶监督编码，即每行为一个奇偶监督码组(见表3-2，以偶监督为例)，但发送时则按列的顺序传输：111011100110000…10101，接收端仍将码元排成与发送端一样的方阵形式，然后按行进行奇偶校验。注意：通常能查出不大于列长个比特的错误。3.2.2二维奇偶监督码

二维奇偶监督码是将水平奇偶监督码推广而得，又称水平垂直奇偶监督码、行列监督码和方阵码。它的方法是在水平监督基础上对表3-2方阵中每一列再进行奇偶校验，就可得表3-3（以偶监督为例）所示的方阵。发送是按列或按行的顺序传输。接收端重新将码元排成发送时方阵形式，然后每行、每列都进行奇偶校验。注意：能查出所有奇数个比特的错误。能查出部分偶数个比特的错误。具有一定的纠错能力。3.3汉明码及线性分组码3.3.1汉明码汉明码是1950年由美国贝尔实验室提出来的，是第一个设计用来纠正错误的线性分组码，汉明码及其变型已广泛应用于数字通信和数据存储系统中作为差错控制码。

1.纠错码的监督位与码组长度的关系若码长为n信息位数为k，则监督位数r。如果希望用r个监督位构造出r个监督关系式来指示一位错码的种可能位置，则要求2.(7,4)汉明码设分组码(n，k)中k＝4。为了纠正一位错码，要求监督位数。若取，则。我们用表示这7个码元，用表示三个监督关系式中的校正子，则的值与错码位置的对应关系可以规定如表4-4所列，构成监督关系，在发送端编码时，信息位和的值决定于输入信号。而监督位和应根据信息位的取值按监督关系来确定，

按照上述监督关系所构成的线性分组码就是(7,4)汉明码。（3）（7，4）汉明码的汉明距离及编码效率①汉明距离汉明码属于线性分组码，根据线性分组码的性质可以求出（7，4）汉明码的汉明距离。因此由式(3-2)和（3-3）可知，这种码能纠正一个错码或检测两个错码。②编码效率（7，4）汉明码的编码效率为3.3.2线性分组码1.线性分组码的概念线性码是指监督码元与信息码元之间满足一组线性方程的码；分组码是监督码元仅对本码组中的码元起监督作用，或者说监督码元仅与本码组的信息码元有关。既是线性码又是分组码的编码就叫线性分组码。2.线性分组码的主要性质(1)封闭性所谓封闭性，是指一种线性分组码中的任意两个码组之逐位模2和仍为这种码中的另一个许用码组。(2)码的最小距离等于非零码的最小重量线性分组码的生成矩阵线性分组码的编码生成矩阵的典型化线性分组码的监督矩阵监督矩阵与生成矩阵之间的关系3.4循环码循环码是线性分组码中一类重要的码。3.4.1循环码的循环特性1.码的多项式若码组，则相应的多项式表示为

2.循环码的循环特性循环码的循环性是指循环码中任一许用码组经过循环移位后(将最右端的码元移至左端，或反之)所得到的码组仍为它的一个许用码组。表3-6给出一种(7，3)循环码的全部码组，由此表可直观看出这种码的循环性。例如，表中的第2码组向右循环移一位即得到第5码组，第2码组向左循环移一位即得到第3码组。

（7，3）循环码的一种码组3.4.2循环码的生成多项式和生成矩阵1.生成多项式g(x)2.生成矩阵G由循环码的生成多项式g(x)可得到生成矩阵G(x)，为典型的生成矩阵为可以通过线性变换将非典型的生成矩阵转换为典型的生成矩阵，具体方法是：任意几行模二加取代某一行。3.4.3循环码的编码方法1.CRC编码方法设：要发送的信息码字多项式为：M(x)

双方协议规定的生成多项式为：G(x)通信系统中，常见的生成多项式标准有：CRC－12=x12+x11+x3+x2+x1+1CRC－16=x16+x15+x2+1CRC-32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+1CRC－CCITT=x16+x12+x5+1编码步骤：

(1)用生成多项式的最高位乘以M(x)：xn-kM(x)(2)用(1)的结果除以G(x)(3)所得余数R(x)即为CRC的冗余码。3.4.4循环码的解码方法2.CRC译码方法

xn-kM(x)

G(x)=Q(x)余数为：R(x)xn-kM(x)=Q(x)G(x)+R(x)有：xn-kM(x)+R(x)=Q(x)G(x)CRC校验码：编码后的数据流3.5卷积码3.5.1卷积码的基本概念1.卷积码的概念在分组码中，任何一段规定时间内编码器产生的n个码元的一