通信原理第11章-差错控制编码要点课件

通信原理第11章差错控制编码12/6/202311.1概述数字信号在传输过程中受到干扰，使信号码元波形变形，所以传输到接收端可能发生错误判决。信号乘性干扰

加性干扰——均衡的方法解决——合理选择调制、解调；发送功率；差错控制纠错码的目的：克服随机差错，牺牲一部分带宽，换取信噪比的提高，获得误码率的降低。对语音信号：对纠错要求不高；对数据信号：对纠错要求特别高；12/6/20231、信道分类：随机信道：错码的出现是随机的按加性干扰引起错误分布规律不同分信道分类突发信道：错码是成串集中出现的混合信道：既存在随机错码又存在突发错码2、差错类型：随机错码：比较平缓，比较均匀突发错码：突发性、大面积的差错（受外界突发性的影响）12/6/20233、差错图型/图样（ErrorPattern）发的码组：S收的码组：R差错码组：E例如：

S：00100R：11000E：11100E的位为“1”，则该位有错；E的位为“0”，则该位无错；12/6/20234、差错控制技术的种类前向纠错法（FEC）检错重发法（ARQ）反馈校验法（HEC）检错删除（1）前向纠错法（FEC）——ForwardErrorCorrection接收端不仅能在收到信码中发现错误（检错），还能纠正错码（纠错），对码要求有纠错功能，即用纠错码，对码要求高。不需要反向信道，适用于实时传输；纠错设备比检错设备复杂。12/6/2023（2）检错重发法（ARQ）——AutomaticRepeatQuest（自动重发请求）接收端在收到的信码中检测出错码时，即通知发送端重发，直到正确接收到为止。需要双向信道，不能传实时信号（不适合音频、视频，只适合传数据）；对性能要求高的数据传输用此类方法。框图：12/6/2023在发送端，输入的信息码元在编码器中被分组编码（加入监督码元）后，除了立即发送外，还暂存于缓冲存储器中。若接收端解码器检出错码，则由解码器控制产生一个重发指令。此指令经过反向信道送到发送端。由发送端重发控制器控制缓冲存储器重发一次。12/6/2023接收端仅当解码器认为接收信息码元正确时，才将信息码元送给收信者，否则在输出缓冲存储器中删除接收码元。当解码器未发现错码时，经过反向信道发出不需重发指令。发送端收到此指令后，即继续发送后一码组，发送端的缓冲存储器中的内容也随之更新。正确时输出错误时删除12/6/20231）3种ARQ系统①停止等待ARQ系统接收码组ACKACKNAKACKACKNAKACKt1233455发送码组12334556t有错码组有错码组每发送一组数据后发送端等待接收端的确认(ACK)答复，然后再发送下一组数据。当接收数据有误，接收端发回一个否认(NAK)答复，这时，发送端将重发该组数据。系统是工作在半双工状态，时间没有得到充分利用，传输效率较低。12/6/2023②拉后ARQ系统发送端连续发送数据组，接收端对于每个接收到的数据组都发回确认(ACK)或否认(NAK)答复。例如，图中第5组接收数据有误，则在发送端收到第5组接收的否认答复后，从第5组开始重发数据组。在这种系统中需要对发送的数据组和答复进行编号，以便识别。显然，这种系统需要双工信道。接收数据有错码组有错码组910111011122143657981110576ACK1NAK5NAK9ACK5发送数据57695214367981011101112重发码组重发码组ACK912/6/2023③选择重发ARQ系统接收数据有错码组有错码组921436575981011131412发送数据995852143671011131412重发码组重发码组NAK9ACK1NAK5ACK5ACK9它只重发出错的数据组，因此进一步提高了传输效率。2）ARQ的主要优点：——和前向纠错方法相比①监督码元较少即能使误码率降到很低，即码率较高；②检错的计算复杂度较低，成本降低；③检错用的编码方法和加性干扰的统计特性基本无关，能适应不同特性的信道。12/6/20233）ARQ的主要缺点：①需要双向信道来重发，不能用于单向信道，也不能用于一点到多点的通信系统。②因为重发而使ARQ系统的传输效率降低。③在信道干扰严重时，可能发生因不断反复重发而造成事实上的通信中断。④不适合要求实时通信的场合，例如电话通信。（3）反馈校验法（HEC）接收端将收到的信码原封不动地转发给发送端，并与原发送信码相比较，如果有错，发送端重发。需要双向信道。因为每一组信码都传输2次，所以传输效率很低。12/6/2023（1）前向纠错法（FEC）（2）检错重发法（ARQ）（3）反馈校验法（HEC）差错控制技术的种类其中，（1）,（2）两种方法均在接收端识别有无错码，这是由发送端的信道编码器在信息码元序列中增加一些监督码元来实现的。（1）差错控制编码——在信息码元序列中加入监督码元。5、差错控制编码：常称为纠错编码（2）监督码元：为了在接收端识别有无错码，通常在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元。12/6/2023例如，若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的多余度为1/3。（4）编码效率（简称码率）：信息码元数量（k）和总码元数量（n）之比：k/n（3）多余度：监督码元数(n-k)和总码元数n之比：理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。一般地，增加的监督码元越多（多余度越大），检（纠）错能力就越强。12/6/202311.2纠错编码的基本原理设有一种由3位二进制数字构成的码组，它共有8种不同的可能组合。若将其全部用来表示天气，则可以表示8种不同天气：引例：000——晴，001——云010——阴，011——雨100——雪，101——霜110——雾，111——雹其中任一码组在传输中若发生一个或多个错码，则将变成另一个信息码组。这时，接收端将无法发现错误。12/6/2023若在上述8种码组中只准许使用4种来传送天气，例如：000——晴，011——云101——阴，110——雨许用码组（合法码组）则剩余的码组：001，010，100，111禁用码组（非法码组）虽然4个许用码组只能传送4种不同的天气，但是接收端却有可能发现码组中的一个错码（检错）。1、许用码组和禁用码组

出现禁用码组，即可判断出错。12/6/2023000（晴）例如：若“000”（晴）中错了一位，即：001010100禁用码组接收端在收到禁用码组时，就认为发现了错码。当发生3个错码时，“000”变成了“111”，它也是禁用码组，故这种编码也能检测3个错码。但是这种码不能发现一个码组中的两个错码，因为发生两个错码后产生的是许用码组。000（晴）011——云101——阴110——雨许用码组12/6/20232、检错和纠错上面这种编码只能检测错码，不能纠正错码。例如，当接收码组为禁用码组“100”时，接收端将无法判断是哪一位码发生了错误，因为晴、阴、雨三者错了一位都可以变成“100”。000——晴，011——云101——阴，110——雨000——晴101——阴110——雨传错一位10012/6/2023若规定：要能够纠正错误，还要增加多余度。000——晴，111——雨（许用码组）001，010，011，100，101，110（禁用码组）则能够检测两个以下错码，或能够纠正一个错码。分析：纠正为“000”（晴）当收到禁用码组“100”时，若假定仅有一个错码。当收到禁用码组“100”时，若假定错码数不超过两个。只能检测出存在错码而无法纠正错码12/6/20233、分组码将信息码分组，为每组信息码附加若干监督码的编码。即：分组码＝信息码＋监督码注意：监督码仅仅监督本码组中的信息码元。信息位监督位晴000云011阴101雨110例如：

000——晴011——云101——阴110——雨12/6/2023（1）分组码的一般结构分组码的符号：(n,k)n——码组的总位数，又称为码组的长度（码长）k——码组中信息码元的数目n－k=r——码组中的监督码元数目，或称监督位数目12/6/2023（2）分组码的码重W分组码中“1”的个数目称为码组的重量，简称码重。（3）分组码的码距d把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距又称汉明距离。例如：000——晴011——云101——阴110——雨码距均为21）最小码距(d0)：把某种编码中各个码组之间距离的最小值。例如，上面的编码的最小码距d0=2。12/6/2023设一个码组A位于O点。若码组A中发生一个错码，则我们可以认为A的位置将移动至以O点为圆心，以1为半径的圆上某点，但其位置不会超出此圆。2）码距和检纠错能力的关系一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力。①为检测e个错码，要求最小码距d0

e+1【证】0123BA汉明距离ed0若码组A中发生两位错码，则其位置不会超出以O点为圆心，以2为半径的圆。12/6/20230123BA汉明距离ed0同理，若一种编码的最小码距为d0，则将能检测(d0-1)个错码。

反之，若要求检测e个错码，则最小码距d0应满足：d0

e+1因此，只要最小码距不小于3，码组A发生两位以下错码时，不可能变成另一个许用码组B，因而能检测错码的位数等于2。12/6/2023②为了纠正t个错码，要求最小码距d0

2t+1BtA汉明距离012345td0图中画出码组A和B的距离为5。码组A或B若发生不多于两位错码，则其位置均不会超出半径为2以原位置为圆心的圆。这两个圆是不重叠的。判决规则为：若接收码组落于以A为圆心的圆上就判决收到的是码组A，若落于以B为圆心的圆上就判决为码组B。若错码达到3个，就将落入另一圆上，从而发生错判。这样，就能够纠正两位错码。12/6/2023③为纠正t个错码，同时检测e个错码，要求最小码距BtA汉明距离012345td0下图所示的例子，图中码组A和B之间距离为5。按照检错能力公式，最多能检测

个错码，即：e=d0–1=5–1=44按照纠错能力公式纠错时，能纠正

个错码2d0

2t+112/6/2023BtA汉明距离012345td0但是，不能同时做到即检测4个错码，又纠正2个错码。例如，码组A若错了3位，就会被误认为码组B错了2位造成的结果，从而被错“纠”为B。这就是说，检错和纠错公式不能同时成立或同时运用。12/6/2023为了在可以纠正t个错码的同时，能够检测e个错码，就需要像下图所示那样，使某一码组（譬如码组A）发生e个错误之后所处的位置，与其他码组（譬如码组B）的纠错圆圈至少距离等于1，不然将落在该纠错圆上从而发生错误地“纠正”。因此，由此图可以直观看出，要求最小码距：这种纠错和检错结合的工作方式简称纠检结合。ABe1tt汉明距离e12/6/2023①为检测e个错码，要求最小码距d0

e+1②为了纠正t个错码，要求最小码距d0

2t+1③为纠正t个错码，同时检测e个错码，要求最小码距：例如：若最小码距d0=5，则：按照检错能力公式，最多能检测

个错码；4按照纠错能力公式，最多能纠正

个错码；2按照纠检错结合方式工作时，若计算纠错能力为1，则最多能检测

个错码；312/6/202311.4简单的实用编码11.4.1奇偶监督码奇偶监督码分为奇数监督码和偶数监督码两种，两者的原理相同。设码组：（an-1an-2an-2……a1a0）an-1先出现a0最后出现n位n-1位：信息位奇偶校验位1、编码效率（码率）：12/6/20232、校验方法（1）偶校验监督位使整个码组中“1”的数目为偶数，即满足：（即各码元模2相加）若结果＝0＝1认为无错认为有错（2）奇校验监督位使整个码组中“1”的数目为奇数，即满足：（即各码元模2相加）若结果＝1＝0认为无错认为有错12/6/2023若n=6，信息位为：10110采用偶校验，则发方码组为：若接收码组为：（101101）——判为合法（实为正确）（111100）——判为合法（实为错码）（111101）——判为非法（一定有误码）注意：①奇偶校验码组只能检测奇位错（1位）。②偶校验码组属于线性分组码；③奇校验码组不属于线性分组码，而属于非线性分组码。（101101）12/6/202311.4.2二维奇偶监督码（方阵码）——非线性它是先把上述奇偶监督码的若干码组排成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位，如下图所示：信息位监督位第一个码组第二个码组第m个码组按列进行第二次编码所增加的监督位12/6/2023二维奇偶监督码的性能（1）这种编码有可能检测偶数个错码。因为每行的监督位虽然不能用于检测本行中的偶数个错码，但按列的方向有可能由cn-1cn-2

c1c0等监督位检测出来。有一些偶数错码不可能检测出来。例如，构成矩形的4个错码，譬如图中：12/6/2023（2）这种二维奇偶监督码适于检测突发错码。（3）由于方阵码只对构成矩形四角的错码无法检测，故其检错能力较强。（4）二维奇偶监督码不仅可用来检错，还可以用来纠正一些错码。例如，仅在一行中有奇数个错码时，则能够确定错码位置，从而纠正它。12/6/2023例：信息位（1110110111011010111100100）组成5×5的方阵。构造二维奇偶监督码0010101100012/6/202311.4.3恒比码在恒比码中，每个码组均含有相同数目的“1”（和“0”）。由于“1”的数目与“0”的数目之比保持恒定，故得此名。这种码在检测时，只要计算接收码组中“1”的数目是否对，就知道有无错码。恒比码的主要优点是简单和适于用来传输电传机或其他键盘设备产生的字母和符号。对于信源来的二进制随机数字序列，这种码就不适合使用了。12/6/202311.4.4正反码是一种简单的能够纠正错码的编码。其中的监督位数目与信息位数目相同。1、编码原则：监督码元与信息码元相同（重复）当信息位中含有奇数个“1”；监督码元与信息码元相反（反码）当信息位中含有偶数个“1”；例如：若信息位为11001，若信息位为10001，则码组为1100111001；则码组为1000101110。12/6/20232、正反码的解码（1）先将接收码组中信息位和监督位按模2相加，得到一个5位的合成码组。若接收码组的信息位中有奇数个“1”，则合成码组就是校验码组；若接收码组的信息位中有偶数个“1”，则取合成码组的反码作为校验码组。（3）最后，观察校验码组中“1”的个数，按下表进行判决及纠正可能发现的错码。（2）由合成码组产生一个校验码组。12/6/2023校验码组的组成错码情况1全为“0”无错码2有(n-1)个“1”和1个“0”信息码中有1位错码，其位置对应校验码组中“0”的位置3有(n-1)个“0”和1个“1”监督码中有1位错码，其位置对应校验码组中“1”的位置4其他组成错码多于1个校验码组和错码的关系例如，若发送码组为：1100111001，若接收码组为：1100111001则合成码组为：11001

11001=00000。由于接收码组信息位中有奇数个“1”，所以

校验码组为：00000所以无错码。12/6/2023例如，若发送码组为：1100111001，若接收码组为：1000111001则合成码组为：10001

11001=01000。由于接收码组信息位中有偶数个“1”，所以

校验码组为：10111（反码）所以有错码，且在信息位中第二位为错码。例如，若发送码组为：1100111001，若接收码组为：1100110001则合成码组为：11001

10001=01000。由于接收码组信息位中有奇数个“1”，所以

校验码组为：01000所以有错码，且在信息位中第二位为错码。12/6/2023例如，若发送码组为：1100111001，若接收码组为：1001111001则合成码组为：10011

11001=01010。由于接收码组信息位中有奇数个“1”，所以

校验码组为：01010所以有错码，且多余一个。上述长度为10的正反码具有纠正1位错码的能力，并能检测全部2位以下的错码和大部分2位以上的错码。补充：重复码0（00000）1（11111）效率很低，但抗干扰能力很强。解码：择大判决。（11001）112/6/202311.5线性分组码1、基本概念（1）码——码型，最高的概念；Code有各种各样的码，可自行设计，要求效率高，纠错能力强，电路简单。（2）码组——CodeWords（设共n位）码由码组组成，是一个集合：{码组}。合法码组：属于码（集合）的码组：非法码组：不属于码（集合）的码组：（an-1an-2…arar-1……a1a0）k位：信息位r位：监督位2k个2n-2k个12/6/2023（3）码长——n=k+r

（4）码元——CodebitsRC=k/n

（5）编码效率（简称码率）：(n-k)/k=r/k（7）冗余度：（8）汉明重量（HammingWeight）：码组中“1”的个数例如：u＝（1101110）W=5（码的）最小汉明重量：W0或Wmin码是很多码组的集合，每个码组都有各自的重量，其中最小的重量即为码的“最小汉明重量”。(n-k)/n=r/n（6）多余度：12/6/2023（8）汉明距离（码组）：两个码组所含不同位的个数，称为“码组的汉明距离”。例如：u＝（1101110）d(u,v)=3（码的）最小汉明距离：d0或dmin码是很多码组的集合，每对码组都有各自的汉明距离，其中最小的距离即为码的“最小汉明距离”。v＝（1001011）最小汉明距离直接决定了码的就错能力：d0纠错能力d0

2t+1d0

e+112/6/20232、线性分组码的定义线性分组码：按照一组线性方程构成的分组码。设C为码，Ci为码组，若：C={Ci}，其中Ci∈C，Cj∈C，且有：Ci＋Cj∈C则C为线性分组码。线性分组码中必含有全零码。对于线性分组码有：W0=d0

推论：12/6/20233、线性分组码的监督阵和生成阵监督阵H：r×n生成阵G：k×n知道了H，即可得到G：知道了G，即可得到H。（1）监督阵和生成阵1）监督方程：

其中：H——监督阵，r×nA——码组，1×n0——矩阵，1×r12/6/2023例如，对于著名的（7，4）汉明码：（n=7,k=4）12/6/2023G矩阵的性质：

①G矩阵的各行是线性无关的。②G的各行本身就是一个码因此，如果已有k个线性无关的码组，则可以用其作为生成矩阵G，并由它生成其余码组。2）生成方程：其中：G——生成阵，k×nA——码组，1×nX——信息矢量，1×k12/6/2023（2）典型的监督阵和生成阵1）典型H(r×n)nkrrP：r×kIr：r×r——单位阵2）典型G(k×n)nkrkQ：k×rIk：k×k——单位阵12/6/20233）典型阵的关系：【证明】监督方程：r×kr×rk×1r×1因为模2运算，无需考虑正负。12/6/2023又因为又因为12/6/20234）生成阵G和监督阵H的行变换

G的每一行都是一个合法的码组，它们构成码的一个基。对典型G阵进行“行变换”后仍然为该码的生成阵，仍有：但G已为非典型。对典型H阵进行“行变换”后仍然为该码的监督阵，仍有：但H已为非典型。注意：列变化将改变码型。12/6/20235）G的行矢量⊥H的行矢量（内积为零）【证明】g∈G的行h∈H的行即证明：则有：g·hT=0由于X为任意的信息矢量，则有：即：12/6/2023【例】n=5，k=2合法码组：2k＝4已知其中两个合法码组为：C1＝01100C2＝11011试求生成阵G及其典型阵；求监督阵H。【解】设其中另一个为全零码组：00000由线性码可知：C3＝C1＋C2＝10111（1）生成阵G：k×n12/6/2023G转换成典型阵——行变换（2）监督阵H——由典型G可直接推得典型H且：12/6/20234、利用监督阵H检错（不纠错）如果发送为码组A如果接收为码组B将B代入监督方程：若真的无错码有错码，但超出了检错能力若——出现错码12/6/20235、利用校正子S纠检错（1）校正子S的定义：其中：E——差错矢量/差错图样（1×n）H——监督阵（r×n）S——（1×r）若E=0，则判无差错，则S=0。若发方为A码组，收方为B码组。12/6/2023（2）利用校正子S纠检错收发收到B矢量：使用H对接收信号进行校验：监督方程：＝0，无错码或漏检≠0，有错码12/6/2023例如：（7，4）汉明码生成阵为：校正子：12/6/2023校正子：ES错码情况0000000000无错0000001001错1位并纠错0000010010000010010000010000110010000101010000011010000001110000011011只能检错……纠错：根据校验得到的校正子在监督矩阵中所处的位置纠错。12/6/2023例如：

发方码组A：0100110收方码组B：0100010错码通过校正子纠错：监督阵H：（7，4）汉明码：=（100）即对应的a2位出错，纠错即可。12/6/2023或者，查表得到差错图样，同样可以纠错：=（100）ES错码情况0000000000无错0000001001错1位并纠错0000010010000010010000010000110010000101010000011010000001110000011011只能检错……纠错：12/6/2023【例】（5，2）线性分组码，已知：（1）监督矩阵H；（2）最小汉明距离d0；（3）若接收到码组为B=（10001），求校正子S；（4）已知B中只有一位错，试纠正。求：【解】（1）监督矩阵H：12/6/2023（2）最小汉明距离d0：——穷举法C1=10101C2=01011必然包含全零码：C4=00000由线性码可知：C3=C1+C2=11110最小汉明距离d0=3能检

个错；能纠

个错；21d0

e+1d0

2t+112/6/2023（3）若接收到码组为B=（10001），求校正子S；=（100）（4）已知B中只有一位错，试纠正。12/6/2023补充：汉明码能够纠正1位错码且编码效率较高的一种线性分组码。（1）线性码（n，k）码长——n；信息位——k；监督位——r=n-k；（2）r个监督位：即为r位校正子r位校正子（监督位）的可能取值：2r其中，用“0