差错控制课件

差错控制(信道编码)

差错控制的方式采用检错码的差错控制采用纠错码的差错控制不用编码的差错控制关于帧或分组顺序的差错控制*网络基础数据通信中的实际情况*网络基础通信信道中的噪声通信信道中的噪声分为热噪声和冲击噪声。热噪声是由传输媒体的电子热运动产生的，其特点是时刻存在，幅度小，干扰强度与频率无关，但频谱很宽，属于随机噪声。由热噪声引起的差错属于一种随机差错。冲击噪声是由外界电磁干扰引起的，与热噪声相比，冲击噪声的幅度较大，是引起差错的主要原因。冲击噪声持续时间与数据传输中每个比特的发送时间相比，可能较长，因而冲击噪声引起的相邻多个数据位出错呈突发性。冲击噪声引起的传输差错称为突发差错。*网络基础差错产生的原因在通信过程中出现的传输差错，是由随机差错和突发差错共同构成的，而造成差错可能的原因包括：在数据通信中，信号在物理信道上的线路本身的电气特性随机产生的信号幅度、频率、相位的畸形和衰减；电气信号在线路上产生反射噪声的回波效应；相邻线路之间的串线干扰；大气中的闪电、电源开关的跳火、自然界磁场的变化以及电源的波动等外界因素。*网络基础差错的控制在数据通信中，原发送信息，不具备抗干扰性能，如果引入冗余度后，就可以使新的码组具有一定的抗干扰能力。例如，两个码元构成四种码组00、01、10、11，无法检错，而使用三个码元，有用码组为000、011、101和110；目前差错控制常采用冗余编码方案，检测和纠正信息传输中产生的错误。冗余编码思想就是：把要发送的有效数据在发送时按照所使用的某种差错编码规则加上控制码（冗余码），当信息到达接收端后，再按照相应的校验规则检验收到的信息是否正确。差错控制的基本工作方式前向纠错方式FEC发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。特点是单向传输，实时性好，但译码设备较复杂。检错重发方式ARQ发端发送检错码，收端收到信码后能够检查出错误。混合纠错方式HEC是FEC和ARQ方式的结合。信息反馈方式IF收端将接收的消息原封不动地送回发端，由发端将反馈信息和原发送信息进行比较，发现错误进行重发，其优点是方法和设备简单，无需纠（检）错编译系统。差错控制的基本工作方式对于不同类型的信道，应采用不同的差错控制技术，否则就将事倍功半。

检错重发可用于双向数据通信，前向纠错则用于单向数字信号的传输，例如广播数字电视系统，因为这种系统没有反馈通道。检错重发（ARQ）典型系统检错重发方式的原理方框图常用的检错重发系统有三种，即停发等候重发、返回重发和选择重发。*网络基础检错重发（ARQ）1、检错重发（ARQ）（1）思路发送端对数据序列进行分组编码，加入一定的码元使之具有一定的检错能力，成为能够发现错误的码组。接收端收到码组后，按一定规则对其进行有无错误的判别，并把判决结果（应答信号）通过反向信道送回发送端。如有错误，发送端把前面发出的信息重新传送一次，直到接收端认为已正确接收到信息为止。（2）重发方式（3种形式）：·停发等候重发·返回重发·选择重发*网络基础连续ARQ协议工作原理发送方发完一帧后，不必停下来等待对方的应答，可以连续发送若干帧；如果在发送过程中收到接收方的肯定应答，可以继续发送；若收到对其中某一帧的否认帧，则使用某种ARQ方式重发数据；优点连续发送提高了信道利用率；连续ARQ协议包括选择ARQGo-Back-NARQ*网络基础ARQ*网络基础选择ARQ与Go-Back-N的比较采用选择ARQ方式时，由于接收到的数据帧有可能是乱序的，因此，接收端必须提供足够的缓存先将每个数据帧保存下来，然后对数据帧重新排序。但由于该方式仅重发出错的数据帧，因此，信道利用率高。对于Go-Back-N方式，接收到的数据帧是按顺序排列的，因而接收端不需要太多的缓存，但由于发送端要将出错数据之后的已发送数据帧重新发送，致使信道利用率相对较低。*网络基础三种重发方式的比较

停发等候重发返回重发选择重发发送方式停止等待发送连续发送连续发送传输效率最低比较高最高控制方法简单比较简单比较复杂缓冲存储器发送端有发送端有发送和接收端都要求有成本低比较低比较高*网络基础ARQ的优缺点（3）ARQ的优缺点·需反向信道，实时性差。

·编码效率较高。·译码设备较简单。

*网络基础前向纠错（FEC）2、前向纠错（FEC）思路前向纠错系统中，发送端的信道编码器将输入数据序列变换成能够纠正错误的码，接收端的译码器根据编码规律检验出错误的位置并自动纠正。优点：不需要反向信道，实时性好。缺点：1、所选择的纠错码必须与信道的错码特性密切配合，否则很难达到降低错码率的要求；2、为了纠正较多的错码，译码设备复杂；3、要求附加的监督码也较多，传输效率较低。*网络基础例1：某数据通信系统采用停发等候重发的差错控制方式，请在下图的“？”处填入ACK、NAK或码组号。

*网络基础例2：某数据通信系统采用选择重发的差错控制方式，发送端要向接收端发送7个码组（序号0∽6），其中1号码组出错，请在下图中的空格里填入正确的码组号。

*网络基础例3：某数据通信系统采用返回重发的差错控制方式，发送端要向接收端发送8个码组（序号0∽7），其中1号码组出错，请在下图中的空格里填入正确的码组号。

差错控制编码的基本原理差错编码的基本思想是在被传输信息中增加一些冗余码，利用附加码元和信息码元之间的约束关系加以校验，以检测和纠正错误，增加冗余码的个数可增加纠检错能力。信息码元、监督码元

信息码元又称信息序列或信息位，这是发端由信源编码后得到的被传送的信息数据比特，通常以k表示。监督码元又称监督位或附加数据比特，这是为了检纠错码而在信道编码时加入的判断数据位。通常以r表示，即为：

n=k+r或r=n－k经过分组编码后的码又称为(n,k)码，即表示总码长为n位，其中信息码长(码元数)为k位，监督码长(码元数)为r=n－k。通常称其为长为n的码字(或码组、码矢)。

码长、码重、码距编码码组的码元总位数称为码组的长度，简称码长。码组中，“1”码元的数目称为码组的重量，简称码重。两个等长码组之间对应位上码元不同的数目称为这两个码组的距离，简称码距。码距又称汉明距。通常用d表示。各码组之间距离最小值称为最小码距，通常用d0表示。*网络基础最小码距与检纠错能力的关系

①在一个码组内为了检测e个误码，要求最小码距应满足：

d0≥e＋1

②在一个码组内为了纠正t个误码，要求最小码距应满足：

d0≥2t＋1

③在一个码组内为了纠正t个误码，同时能检测e个误码(e＞t)，要求最小码距应满足：

d0≥e＋t＋1；*网络基础差错编码差错检测编码：奇偶校验码；水平垂直奇偶校验码；恒比码CRC循环冗余码等；差错纠错编码：汉明码；卷积码；*网络基础奇偶校验码采用奇偶校验法，在每个字符的数据位传输之前，先检测并计算奇偶校验位，然后将其附加在后；根据采用的奇偶校验位是奇数还是偶数，推出一个字符包含“1”的数目，接收机重新计算收到字符的奇偶校验位，并确定该字符是否出现传输差错；若每个字符只采用一个奇偶校验位时，只能发现单个比特差错，如果有两个或两个以上比特出错，奇偶校验位无效；异步传输和面向字符的同步传输均采用奇偶校验技术；多用于计算机内部数据校验。

*网络基础循环冗余码CRCCRC是一种较为复杂的校验方法，它先将要发送的信息数据与一个通信双方共同约定的数据进行除法运算，并根据余数得出一个校验码，然后将这个校验码附加在信息数据帧之后发送出去。接收端接收数据后，将包括校验码在内的数据帧再与约定的数据进行除法运算，若余数为“0”，就表示接收的数据正确，若余数不为“0”，则表明数据在传输的过程中出错。*网络基础循环冗余校验码(CRC)所谓循环码是这样一组代码,其中任一有效码字经过循环移位后得到的码字仍然是有效码字,不论是右移或左移,也不论移多少位。例如,若(an-1an-2…a1a0)是有效码字,则(an-2an-3…a0an-1),(an-3an-4…an-1an-2),…,等都是有效码字。循环冗余校验码是一种循环码,它有很强的纠错检错能力,而且硬件实现很容易,在局域网中有广泛的应用。它所约定的校验规则是：让校验码能为某一约定代码所除尽；如果除得尽，表明代码正确；如果除不尽，余数将指明出错位所在位置。*网络基础CRC校验码编码过程取k位信息码，再将其左移r位，得到k+r位二进制码；用生成码去模2除（异或）该二进制码，得到r为余数。该余数即为所得校验码；将该校验码加在原信息码后，就构成待传输的k+r位CRC码（信息码加校验码）。※模2运算:

用模2运算进行加法时不进位，减法和加法是一样的。例如：1111＋1010＝0101*网络基础CRC码的译码过程接收端译码要求有两个：检错和纠错。检错：原理和操作都很简单。以生成多项式G(x)对应的代码去模2除收到的代码，即T’(x)对应的代码，若余数为0，则说明传输过程无差错，否则有差错。*网络基础编码：信息序列对应的码多项式为K(x)＝x6+x3+1xr.K(x)＝x9+x6+x3，对应的代码为1001001000(相当于信息码左移3位)选生成多项式G(x)＝x3+x2+1，对应的码多项式为1101

应用举例*网络基础100100100011011101

10001101

10101101

11111101

10001101

10101101

1111111011余数运算演示：*网络基础编码结果：得到检验序列111。因此传输的代码序列为1001001111,码多项式为T(x)。译码：如收到的代码为1001001111，则用其除以生成多项式对应的代码1101，得余数为0(读者自己验证)。说明信息在传输过程中没错，将最后的r位校验位码“111”去掉，就得到信息码。*网络基础译码并纠错：若收到的T’(x)代码为1001001101，按原过程计算，将其除以生成多项式对应的代码1101，得余数为10(如下页)。这就说明传输有差错，差错e(x)=x，其代码为10。将其纠正1001001101+10=1001001111*网络基础100100110111011101

10001101

10101101

11111101

10101101

11111101

0101111011运算演示：*网络基础

纠错依据：更换不同值的M(x)可以证明,出错模式只与码制和选用的G(x)有关,与M(x)代码值无关。据此可作为该种码制的纠错依据。a1a2a3a4a5a6a7

余数

出错位

正确1100010000

无

出错1100011110000011001101101010111001010000100

1000100010101000111101111017654321(7,4)制CRC码的出错模式表(G(x)=1011)*网络基础

CRC码的特点CRC码是面向数据帧编码检错；理论证明，循环冗余检验码能够检验出：全部奇数个错、全部偶数位错和全部小于、等于冗余位数的突发性错误；理论证明,余数代码与出错位序号之间有唯一的对应关系，据此，CRC有纠错功能；一旦G(x)选定，CRC码对帧内有(r+1)bit出错时无法纠错；使用CRC技术只能做到无差错接受(不包括丢失帧),可靠传输需加上确认重传机制。*网络基础由以上分析可知，只要选择足够的冗余位，就可以使得漏检率减少到任意小的程度。广泛使用的生成码多项式主要有以下四种：CRC12＝x12+x11+x3+x2+x

+1CRC16＝x16+x15+x2+１(IBM公司)CRC16＝x16+x12+x5+１(ITU-T)CRC32＝X32+x26+x23+x22+x16++x11+x10+x8+x7+x5+x4+x2+x+13.线性分组码线性分组码的定义和特点线性分组码，是指信息码元与监督码元之间的关系可以用一组线性方程来表示的分组码，即在（n，d）分组码中，每一个监督码元都是码组中某些信息码元按模2和而得到的，线性分组码是一类重要的纠错码，应用很广。汉明码汉明码是一类常见的线性分组码，是一种能够纠正单个错误的完备码。要纠正码组中的单个错误，则要求与单个错误图样对应的伴随式各不相同，且不能为全零。若码长为n，监督码元的个数为r，则要求2r-1≥n。码组为汉明码时取等号。即用来纠正单个错误时，汉明码所用的监督码元个数最少，效率最高。循环码循环码是另一类重要的线性分组码，它除了具有线性码的一般性质外，还具有循环性，即循环码组中任一码组循环移位所得的码组仍为该循环码中的一许用码组。CRC码的原理如果有r个校验码元，其中每一个校验码元是该码元组中某些信息码元的模2和，由此组成的一组长为n=k+r的码，称为线性码，假定我们构成(n=7,k=3)这样的线性码，若已知三个信息码元为C6、C5和C4，而校验码元C3、C2、C1和C0是未知的。校验码元与信息码元间的关系是根据以下四个线性关系式确立的。

CRC码的原理CRC码的原理按上页编出的线性码息码元码组C6C5C4C6C5C4C3C2C1C000000000000010011101010010011101101110101001001110101101001111011010011111110100CRC码的原理当我们从表中任意挑选出两个码组时，将对应比特按模2相加，所得到的新码组仍然是上页表中的某一码组。这说明由8个码字组成的线性码具有封闭性。封闭性是线性码的一个重要特性。CRC码的原理假设待传送的数据M

（kbit）。我们在M的后面再添加供差错检测用的rbit冗余码一起发送。用二进制的模

2

运算进行2r乘M的运算，这相当于在M后面添加r个0。得到的(k+r)bit的数除以事先选定好的长度为(r+1)bit的数G，得出商是Q而余数是R，余数R比除数G至少要少1个比特。例子设

M=1010001101，r=5,G=110101，模2运算的结果是：商Q=1101010110，余数R=01110。将余数R作为冗余码添加在数据M的后面发送出去，即发送的数据是101000110101110，或2rM+R。例子

1101010110

←

Q

商

除数

P→

110101101000110100000

←

2nM被除数

110101

111011