《通信原理第11章-差错控制编码要点课件.ppt》由会员分享，可在线阅读，更多相关《通信原理第11章-差错控制编码要点课件.ppt（73页珍藏版）》请在三一办公上搜索。
1、2023/4/2,通 信 原 理,第11章 差错控制编码,2023/4/2,11.1 概述,数字信号在传输过程中受到干扰，使信号码元波形变形，所以传输到接收端可能发生错误判决。,信号,乘性干扰,加性干扰,均衡的方法解决,合理选择调制、解调；发送功率；差错控制,纠错码的目的：克服随机差错，牺牲一部分带宽，换取 信噪比的提高，获得误码率的降低。,对语音信号：对纠错要求不高；,对数据信号：对纠错要求特别高；,2023/4/2,1、信道分类：,随机信道：错码的出现是随机的,按加性干扰引起错误分布规律不同分,信道分类,突发信道：错码是成串集中出现的,混合信道：既存在随机错码又存在突发错码,2、差错类型：
2、,随机错码：比较平缓，比较均匀,突发错码：突发性、大面积的差错（受外界突发性的影响）,2023/4/2,3、差错图型/图样（Error Pattern）,发的码组：S,收的码组：R,差错码组：E,例如：,S：0 0 1 0 0,R：1 1 0 0 0,E：1 1 1 0 0,E的位为“1”，则该位有错；,E的位为“0”，则该位无错；,2023/4/2,4、差错控制技术的种类,前向纠错法（FEC）检错重发法（ARQ）反馈校验法（HEC）检错删除,（1）前向纠错法（FEC）,Forward Error Correction,接收端不仅能在收到信码中发现错误（检错），还能纠正错码（纠错），对码要求有
3、纠错功能，即用纠错码，对码要求高。,不需要反向信道，适用于实时传输；,纠错设备比检错设备复杂。,2023/4/2,（2）检错重发法（ARQ）,Automatic Repeat Quest（自动重发请求）,接收端在收到的信码中检测出错码时，即通知发送端重发，直到正确接收到为止。,需要双向信道，不能传实时信号（不适合音频、视频，只适合传数据）；对性能要求高的数据传输用此类方法。,框图：,2023/4/2,在发送端，输入的信息码元在编码器中被分组编码（加入监督码元）后，除了立即发送外，还暂存于缓冲存储器中。若接收端解码器检出错码，则由解码器控制产生一个重发指令。此指令经过反向信道送到发送端。由发送端
4、重发控制器控制缓冲存储器重发一次。,2023/4/2,接收端仅当解码器认为接收信息码元正确时，才将信息码元送给收信者，否则在输出缓冲存储器中删除接收码元。当解码器未发现错码时，经过反向信道发出不需重发指令。发送端收到此指令后，即继续发送后一码组，发送端的缓冲存储器中的内容也随之更新。,正确时输出,错误时删除,2023/4/2,1）3种ARQ系统,停止等待ARQ系统,每发送一组数据后发送端等待接收端的确认(ACK)答复，然后再发送下一组数据。,当接收数据有误，接收端发回一个否认(NAK)答复，这时，发送端将重发该组数据。,系统是工作在半双工状态，时间没有得到充分利用，传输效率较低。,2023/4
5、/2,拉后ARQ系统,发送端连续发送数据组，接收端对于每个接收到的数据组都发回确认(ACK)或否认(NAK)答复。例如，图中第5组接收数据有误，则在发送端收到第5组接收的否认答复后，从第5组开始重发数据组。,在这种系统中需要对发送的数据组和答复进行编号，以便识别。显然，这种系统需要双工信道。,2023/4/2,选择重发ARQ系统,它只重发出错的数据组，因此进一步提高了传输效率。,2）ARQ的主要优点：和前向纠错方法相比,监督码元较少即能使误码率降到很低，即码率较高；检错的计算复杂度较低，成本降低；检错用的编码方法和加性干扰的统计特性基本无关，能适应不同特性的信道。,2023/4/2,3）ARQ
6、的主要缺点：,需要双向信道来重发，不能用于单向信道，也不能用于一点到多点的通信系统。因为重发而使ARQ系统的传输效率降低。在信道干扰严重时，可能发生因不断反复重发而造成事实上的通信中断。不适合要求实时通信的场合，例如电话通信。,（3）反馈校验法（HEC）,接收端将收到的信码原封不动地转发给发送端，并与原发送信码相比较，如果有错，发送端重发。,需要双向信道。,因为每一组信码都传输2次，所以传输效率很低。,2023/4/2,（1）前向纠错法（FEC）（2）检错重发法（ARQ）（3）反馈校验法（HEC）,差错控制技术的种类,其中，（1）,（2）两种方法均在接收端识别有无错码，这是由发送端的信道编码器
7、在信息码元序列中增加一些监督码元来实现的。,（1）差错控制编码在信息码元序列中加入监督码元。,5、差错控制编码：常称为纠错编码,（2）监督码元：为了在接收端识别有无错码，通常在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元。,2023/4/2,例如，若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的多余度为1/3。,（4）编码效率（简称码率）：信息码元数量（k）和总码元数量（n）之比：k/n,（3）多余度：监督码元数(n-k)和总码元数 n 之比：,理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。,一般地，增加的监督码元越多（多余度越大），检（纠）错能
8、力就越强。,2023/4/2,11.2 纠错编码的基本原理,设有一种由3位二进制数字构成的码组，它共有8种不同的可能组合。若将其全部用来表示天气，则可以表示8种不同天气：,引例：,000晴，001云 010阴，011雨100雪，101霜110雾，111雹,其中任一码组在传输中若发生一个或多个错码，则将变成另一个信息码组。这时，接收端将无法发现错误。,2023/4/2,若在上述8种码组中只准许使用4种来传送天气，例如：,000晴，011云 101阴，110雨,许用码组（合法码组）,则剩余的码组：,001，010，100，111,禁用码组（非法码组）,虽然4个许用码组只能传送4种不同的天气，但是接
9、收端却有可能发现码组中的一个错码（检错）。,1、许用码组和禁用码组,出现禁用码组，即可判断出错。,2023/4/2,000（晴）,例如：若“000”（晴）中错了一位，即：,001,010,100,禁用码组,接收端在收到禁用码组时，就认为发现了错码。当发生3个错码时，“000”变成了“111”，它也是禁用码组，故这种编码也能检测3个错码。,但是这种码不能发现一个码组中的两个错码，因为发生两个错码后产生的是许用码组。,000（晴）,011云,101阴,110雨,许用码组,2023/4/2,2、检错和纠错,上面这种编码只能检测错码，不能纠正错码。例如，当接收码组为禁用码组“100”时，接收端将无法判
10、断是哪一位码发生了错误，因为晴、阴、雨三者错了一位都可以变成“100”。,000晴，011云 101阴，110雨,000晴101阴110雨,传错一位,100,2023/4/2,若规定：,要能够纠正错误，还要增加多余度。,000晴，111雨,（许用码组）,001，010，011，100，101，110,（禁用码组）,则能够检测两个以下错码，或能够纠正一个错码。,分析：,纠正为“000”（晴）,当收到禁用码组“100”时，若假定仅有一个错码。,当收到禁用码组“100”时，若假定错码数不超过两个。,只能检测出存在错码而无法纠正错码,2023/4/2,3、分组码,将信息码分组，为每组信息码附加若干监督
11、码的编码。即：,分组码信息码监督码,注意：监督码仅仅监督本码组中的信息码元。,例如：,000晴011云101阴110雨,2023/4/2,（1）分组码的一般结构,分组码的符号：(n,k),n 码组的总位数，又称为码组的长度（码长）,k 码组中信息码元的数目,nk=r 码组中的监督码元数目，或称监督位数目,2023/4/2,（2）分组码的码重W,分组码中“1”的个数目称为码组的重量，简称码重。,（3）分组码的码距d,把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距又称汉明距离。,例如：,000晴011云101阴110雨,码距均为2,1）最小码距(d0)：把某种编码中各个码组之间距
12、离的最小值。例如，上面的编码的最小码距d0=2。,2023/4/2,设一个码组A位于O点。若码组A中发生一个错码，则我们可以认为A的位置将移动至以O点为圆心，以1为半径的圆上某点，但其位置不会超出此圆。,2）码距和检纠错能力的关系,一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力。,为检测e个错码，要求最小码距 d0 e+1,【证】,若码组A中发生两位错码，则其位置不会超出以O点为圆心，以2为半径的圆。,2023/4/2,同理，若一种编码的最小码距为d0，则将能检测(d0-1)个错码。,反之，若要求检测e个错码，则最小码距d0应满足：,d0 e+1,因此，只要最小码距不小于3，码
13、组A发生两位以下错码时，不可能变成另一个许用码组B，因而能检测错码的位数等于2。,2023/4/2,为了纠正t个错码，要求最小码距d0 2t+1,图中画出码组A和B的距离为5。码组A或B若发生不多于两位错码，则其位置均不会超出半径为2以原位置为圆心的圆。这两个圆是不重叠的。判决规则为：若接收码组落于以A为圆心的圆上就判决收到的是码组A，若落于以B为圆心的圆上就判决为码组B。,若错码达到3个，就将落入另一圆上，从而发生错判。,这样，就能够纠正两位错码。,2023/4/2,为纠正t个错码，同时检测e个错码，要求最小码距,下图所示的例子，图中码组A和B之间距离为5。,按照检错能力公式，最多能检测 个
14、错码，即：e=d0 1=5 1=4,4,按照纠错能力公式纠错时，能纠正 个错码,2,d0 2t+1,2023/4/2,但是，不能同时做到即检测4个错码，又纠正2个错码。,例如，码组A若错了3位，就会被误认为码组B错了2位造成的结果，从而被错“纠”为B。这就是说，检错和纠错公式不能同时成立或同时运用。,2023/4/2,为了在可以纠正t个错码的同时，能够检测e个错码，就需要像下图所示那样，使某一码组（譬如码组A）发生e个错误之后所处的位置，与其他码组（譬如码组B）的纠错圆圈至少距离等于1，不然将落在该纠错圆上从而发生错误地“纠正”。,因此，由此图可以直观看出，要求最小码距：,这种纠错和检错结合的
15、工作方式简称纠检结合。,2023/4/2,为检测e个错码，要求最小码距 d0 e+1,为了纠正t个错码，要求最小码距d0 2t+1,为纠正t个错码，同时检测e个错码，要求最小码距：,例如：若最小码距d0=5，则：,按照检错能力公式，最多能检测 个错码；,4,按照纠错能力公式，最多能纠正 个错码；,2,按照纠检错结合方式工作时，若计算纠错能力为1，则最多能检测 个错码；,3,2023/4/2,11.4 简单的实用编码,11.4.1 奇偶监督码,奇偶监督码分为奇数监督码和偶数监督码两种，两者的原理相同。,设码组：,（an-1 an-2 an-2 a1 a0）,an-1 先出现a0最后出现,n位,n
16、-1位：信息位,奇偶校验位,1、编码效率（码率）：,2023/4/2,2、校验方法,（1）偶校验,监督位使整个码组中“1”的数目为偶数，即满足：,（即各码元模2相加）,若结果,0,1,认为无错,认为有错,（2）奇校验,监督位使整个码组中“1”的数目为奇数，即满足：,（即各码元模2相加）,若结果,1,0,认为无错,认为有错,2023/4/2,若n=6，信息位为：10110,采用偶校验，则发方码组为：,若接收码组为：,（101101）,判为合法（实为正确）,（111100）,判为合法（实为错码）,（111101）,判为非法（一定有误码）,注意：奇偶校验码组只能检测奇位错（1位）。偶校验码组属于线性
17、分组码；奇校验码组不属于线性分组码，而属于非线性分组码。,（101101）,2023/4/2,11.4.2 二维奇偶监督码（方阵码）非线性,它是先把上述奇偶监督码的若干码组排成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位，如下图所示：,信息 位,监督位,第一个码组,第二个码组,第m个码组,按列进行第二次编码所增加的监督位,2023/4/2,二维奇偶监督码的性能,（1）这种编码有可能检测偶数个错码。,因为每行的监督位虽然不能用于检测本行中的偶数个错码，但按列的方向有可能由cn-1 cn-2 c1 c0等监督位检测出来。有一些偶数错码不可能检测出来。,例如，构成矩形的4个错码，譬如图中
18、：,2023/4/2,（2）这种二维奇偶监督码适于检测突发错码。,（3）由于方阵码只对构成矩形四角的错码无法检测，故其检错能力较强。,（4）二维奇偶监督码不仅可用来检错，还可以用来纠正一些错码。例如，仅在一行中有奇数个错码时，则能够确定错码位置，从而纠正它。,2023/4/2,例：信息位（1110110111011010111100100）,组成55的方阵。构造二维奇偶监督码,0,0,1,0,1,0,1,1,0,0,0,2023/4/2,11.4.3 恒比码,在恒比码中，每个码组均含有相同数目的“1”（和“0”）。由于“1”的数目与“0”的数目之比保持恒定，故得此名。,这种码在检测时，只要计算
19、接收码组中“1”的数目是否对，就知道有无错码。,恒比码的主要优点是简单和适于用来传输电传机或其他键盘设备产生的字母和符号。对于信源来的二进制随机数字序列，这种码就不适合使用了。,2023/4/2,11.4.4 正反码,是一种简单的能够纠正错码的编码。其中的监督位数目与信息位数目相同。,1、编码原则：,监督码元与信息码元相同（重复）,当信息位中含有奇数个“1”；,监督码元与信息码元相反（反码）,当信息位中含有偶数个“1”；,例如：若信息位为11001，若信息位为10001，,则码组为1100111001；,则码组为1000101110。,2023/4/2,2、正反码的解码,（1）先将接收码组中信
20、息位和监督位按模 2 相加，得到一个5位的合成码组。,若接收码组的信息位中有奇数个“1”，则合成码组就是校验码组；若接收码组的信息位中有偶数个“1”，则取合成码组的反码作为校验码组。,（3）最后，观察校验码组中“1”的个数，按下表进行判决及纠正可能发现的错码。,（2）由合成码组产生一个校验码组。,2023/4/2,校验码组和错码的关系,例如，若发送码组为：1100111001，若接收码组为：1100111001 则合成码组为：1100111001=00000。由于接收码组信息位中有奇数个“1”，所以 校验码组为：00000所以无错码。,2023/4/2,例如，若发送码组为：1100111001
21、，若接收码组为：1000111001 则合成码组为：1000111001=01000。由于接收码组信息位中有偶数个“1”，所以 校验码组为：10111（反码）所以有错码，且在信息位中第二位为错码。,例如，若发送码组为：1100111001，若接收码组为：1100110001 则合成码组为：1100110001=01000。由于接收码组信息位中有奇数个“1”，所以 校验码组为：01000所以有错码，且在信息位中第二位为错码。,2023/4/2,例如，若发送码组为：1100111001，若接收码组为：1001111001 则合成码组为：1001111001=01010。由于接收码组信息位中有奇数个
22、“1”，所以 校验码组为：01010所以有错码，且多余一个。,上述长度为10的正反码具有纠正1位错码的能力，并能检测全部2位以下的错码和大部分2位以上的错码。,补充：重复码,0,（00000）,1,（11111）,效率很低，但抗干扰能力很强。,解码：择大判决。,（11001）,1,2023/4/2,11.5 线性分组码,1、基本概念,（1）码码型，最高的概念；Code,有各种各样的码，可自行设计，要求效率高，纠错能力强，电路简单。,（2）码组Code Words（设共n位）,码由码组组成，是一个集合：码组。,合法码组：属于码（集合）的码组：,非法码组：不属于码（集合）的码组：,（an-1 an
23、-2 ar ar-1a1 a0）,k位：信息位,r位：监督位,2k个,2n-2k个,2023/4/2,（3）码长n=k+r,（4）码元Code bits,RC=k/n,（5）编码效率（简称码率）：,(n-k)/k=r/k,（7）冗余度：,（8）汉明重量（Hamming Weight）：,码组中“1”的个数,例如：u（1101110）,W=5,（码的）最小汉明重量：W0或Wmin,码是很多码组的集合，每个码组都有各自的重量，其中最小的重量即为码的“最小汉明重量”。,(n-k)/n=r/n,（6）多余度：,2023/4/2,（8）汉明距离（码组）：,两个码组所含不同位的个数，称为“码组的汉明距离”
24、。,例如：u（1101110）,d(u,v)=3,（码的）最小汉明距离：d0或dmin,码是很多码组的集合，每对码组都有各自的汉明距离，其中最小的距离即为码的“最小汉明距离”。,v（1001011）,最小汉明距离直接决定了码的就错能力：,d0,纠错能力,d0 2t+1,d0 e+1,2023/4/2,2、线性分组码的定义,线性分组码：按照一组线性方程构成的分组码。,设C为码，Ci为码组，若：,C=Ci，其中CiC，CjC，且有：,Ci Cj C,则C为线性分组码。,线性分组码中必含有全零码。对于线性分组码有：W0=d0,推论：,2023/4/2,3、线性分组码的监督阵和生成阵,监督阵H：rn,
25、生成阵G：kn,知道了H，即可得到G：知道了G，即可得到H。,（1）监督阵和生成阵,1）监督方程：,其中：,H监督阵，rn,A码组，1n,0矩阵，1r,2023/4/2,例如，对于著名的（7，4）汉明码：（n=7,k=4）,2023/4/2,G矩阵的性质：,G矩阵的各行是线性无关的。G的各行本身就是一个码,因此，如果已有k个线性无关的码组，则可以用其作为生成矩阵G，并由它生成其余码组。,2）生成方程：,其中：,G生成阵，kn,A码组，1n,X信息矢量，1k,2023/4/2,（2）典型的监督阵和生成阵,1）典型H(rn),P：rk,Ir：rr,单位阵,2）典型G(kn),Q：kr,Ik：kk,
26、单位阵,2023/4/2,3）典型阵的关系：,【证明】,监督方程：,rk,rr,k1,r1,因为模2运算，无需考虑正负。,2023/4/2,又因为,又因为,2023/4/2,4）生成阵G和监督阵H的行变换,G的每一行都是一个合法的码组，它们构成码的一个基。,对典型G阵进行“行变换”后仍然为该码的生成阵，仍有：,但G已为非典型。,对典型H阵进行“行变换”后仍然为该码的监督阵，仍有：,但H已为非典型。,注意：列变化将改变码型。,2023/4/2,5）G的行矢量H的行矢量（内积为零）,【证明】,gG的行,hH的行,即证明：,则有：ghT=0,由于X为任意的信息矢量，则有：,即：,2023/4/2,【
27、例】,n=5，k=2,合法码组：,2k4,已知其中两个合法码组为：,C101100,C211011,试求生成阵G及其典型阵；求监督阵H。,【解】,设其中另一个为全零码组：00000,由线性码可知：,C3 C1 C2 10111,（1）生成阵G：kn,2023/4/2,G转换成典型阵,行变换,（2）监督阵H,由典型G可直接推得典型H,且：,2023/4/2,4、利用监督阵H检错（不纠错）,如果发送为码组A,如果接收为码组B,将B代入监督方程：,若,真的无错码,有错码，但超出了检错能力,若,出现错码,2023/4/2,5、利用校正子S纠检错,（1）校正子S的定义：,其中：,E差错矢量/差错图样（1
28、n）,H监督阵（rn）,S（1r）,若E=0，则判无差错，则S=0。,若发方为A码组，收方为B码组。,2023/4/2,（2）利用校正子S纠检错,收发收到B矢量：,使用H对接收信号进行校验：,监督方程：,0，无错码或漏检,0，有错码,2023/4/2,例如：（7，4）汉明码,生成阵为：,校正子：,2023/4/2,校正子：,纠错：根据校验得到的校正子在监督矩阵中所处的位置纠错。,2023/4/2,例如：,发方码组A：0100110 收方码组B：0100010,错码,通过校正子纠错：,监督阵H：（7，4）汉明码：,=（100）,即对应的a2位出错，纠错即可。,2023/4/2,或者，查表得到差错
29、图样，同样可以纠错：,=（100）,纠错：,2023/4/2,【例】,（5，2）线性分组码，已知：,（1）监督矩阵H；,（2）最小汉明距离d0；,（3）若接收到码组为B=（10001），求校正子S；,（4）已知B中只有一位错，试纠正。,求：,【解】,（1）监督矩阵H：,2023/4/2,（2）最小汉明距离d0：,穷举法,C1=10101,C2=01011,必然包含全零码：,C4=00000,由线性码可知：,C3=C1+C2=11110,最小汉明距离d0=3,能检 个错；,能纠 个错；,2,1,d0 e+1,d0 2t+1,2023/4/2,（3）若接收到码组为B=（10001），求校正子S；,
30、=（100）,（4）已知B中只有一位错，试纠正。,2023/4/2,补充：汉明码,能够纠正1位错码且编码效率较高的一种线性分组码。,（1）线性码（n，k）,码长n；,信息位k；,监督位r=n-k；,（2）r个监督位：即为r位校正子,r位校正子（监督位）的可能取值：,2r,其中，用“000”表示无错；,剩余的(2r-1)则可能指出(2r-1)种一位错码的位置。,2023/4/2,一般来说，对于n位码组，如果希望用r个监督位构造出r个监督关系式来指示1位错码，则要求：,例：设分组码(n,k)中k=4，且能纠正1位错码。,由,监督位数 r 3,若取 r=3，则n=k+r=7,分组码(7,4),202
31、3/4/2,7位码组：,3位校正子：,则S1、S2和S3的值与错码位置的对应关系可以规定如下表所列：,2023/4/2,由表中规定可见，仅当一位错码的位置在a2、a4、a5或a6时，校正子S1为1；否则S1为零。这就意味着a2、a4、a5和a6四个码元构成偶数监督关系:,同理，a1、a3、a5和a6构成偶数监督关系：,以及a0、a3、a4 和a6构成偶数监督关系：,2023/4/2,在发送端编码时，信息位a6、a5、a4和a3的值决定于输入信号，因此它们是随机的。监督位a2、a1和a0应根据信息位的取值按监督关系来确定，即监督位应使上3式中S1、S2和S3的值为0（表示编成的码组中应无错码）：,上式经过移项运算，解出监督位：,2023/4/2,给定信息位后，可以直接按上式算出监督位，结果见下表：,2023/4/2,接收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。例如，若接收码组为0000011，按上述公式计算可得：S1=0，S2=1，S3=1。由于S1 S2 S3 等于011，故查表可知在a3位有1错码。,按照上述方法构造的码称为汉明码。表中所列的(7,4)汉明码的最小码距d0=3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n=(n-r)/n=1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。,
