1、2022-12-17通通 信信 原原 理理第第1111章章 差错控制编码差错控制编码2022-12-1711.1 概述概述 数字信号在传输过程中受到干扰，使信号码元数字信号在传输过程中受到干扰，使信号码元波形变形，所以传输到接收端可能发生错误判决。波形变形，所以传输到接收端可能发生错误判决。信号信号 乘性干扰乘性干扰 加性干扰加性干扰均衡的方法解决均衡的方法解决 合理选择调制、解调；合理选择调制、解调；发送功率；发送功率；差错控制差错控制纠错码的目的：纠错码的目的：克服随机差错，牺牲一部分带宽，换取克服随机差错，牺牲一部分带宽，换取 信噪比的提高，获得误码率的降低。信噪比的提高，获得误码率的降
2、低。对语音信号：对纠错要求不高；对语音信号：对纠错要求不高；对数据信号：对纠错要求特别高；对数据信号：对纠错要求特别高；2022-12-171、信道分类：、信道分类：随机信道：随机信道：错码的出现是随机的错码的出现是随机的按加性干扰引起按加性干扰引起错误分布规律不同错误分布规律不同分分信道分类信道分类突发信道：突发信道：错码是成串集中出现的错码是成串集中出现的混合信道：混合信道：既存在随机错码又存在突发错码既存在随机错码又存在突发错码2、差错类型：、差错类型：随机错码：随机错码：比较平缓，比较均匀比较平缓，比较均匀 突发错码：突发错码：突发性、大面积的差错（受外界突发性的影响）突发性、大面积的
3、差错（受外界突发性的影响）2022-12-173、差错图型、差错图型/图样（图样（Error Pattern）发的码组：发的码组：S收的码组：收的码组：R差错码组：差错码组：E例如：例如：S：0 0 1 0 0R：1 1 0 0 0E：1 1 1 0 0E的位为的位为“1”，则该位有错；，则该位有错；E的位为的位为“0”，则该位无错；，则该位无错；2022-12-174、差错控制技术的种类、差错控制技术的种类前向纠错法（前向纠错法（FEC）检错重发法（检错重发法（ARQ）反馈校验法（反馈校验法（HEC）检错删除检错删除（1）前向纠错法（）前向纠错法（FEC）Forward Error Corr
4、ection 接收端不仅能在收到信码中发现错误（检错），还能接收端不仅能在收到信码中发现错误（检错），还能纠正错码（纠错），对码要求有纠错功能，即用纠错码，纠正错码（纠错），对码要求有纠错功能，即用纠错码，对码要求高。对码要求高。不需要反向信道，适用于实时传输；不需要反向信道，适用于实时传输；纠错设备比检错设备复杂。纠错设备比检错设备复杂。2022-12-17（2）检错重发法（）检错重发法（ARQ）Automatic Repeat Quest（自动重发请求）（自动重发请求）接收端在收到的信码中检测出错码时，即通知接收端在收到的信码中检测出错码时，即通知发送端重发送端重发发，直到正确接收到为止。
5、，直到正确接收到为止。需要需要双向信道双向信道，不能传实时信号（不适合音频、视频，不能传实时信号（不适合音频、视频，只适合传数据）只适合传数据）；对性能要求高的数据传输用此类方法。；对性能要求高的数据传输用此类方法。框图：框图：信信源源 编码器和编码器和 缓冲存储器缓冲存储器 重发控制重发控制 双双向向信信道道 解码器解码器 指令产生器指令产生器 输出输出缓冲缓冲存储器存储器 信信宿宿 2022-12-17 信信源源 编码器和编码器和 缓冲存储器缓冲存储器 重发控制重发控制 双双向向信信道道 解码器解码器 指令产生器指令产生器 输出输出缓冲缓冲存储器存储器 信信宿宿 n 在发送端，输入的信息码
6、元在编码器中被分组编码在发送端，输入的信息码元在编码器中被分组编码（加入监督码元）后，除了立即发送外，还暂存于缓冲（加入监督码元）后，除了立即发送外，还暂存于缓冲存储器中。存储器中。n 若接收端解码器检出若接收端解码器检出错码错码，则由解码器控制产生一个，则由解码器控制产生一个重发指令重发指令。n 此指令经过反向信道送到发送端。由发送端重发控制此指令经过反向信道送到发送端。由发送端重发控制器控制器控制缓冲存储器缓冲存储器重发一次。重发一次。2022-12-17n 接收端仅当解码器认为接收信息码元接收端仅当解码器认为接收信息码元正确正确时，才将时，才将信息码元送给收信者，否则在输出缓冲存储器中删
7、除信息码元送给收信者，否则在输出缓冲存储器中删除接收码元。接收码元。n 当解码器未发现错码时，经过反向信道发出不需重当解码器未发现错码时，经过反向信道发出不需重发指令。发送端收到此指令后，即继续发送后一码组，发指令。发送端收到此指令后，即继续发送后一码组，发送端的缓冲存储器中的内容也随之更新。发送端的缓冲存储器中的内容也随之更新。信信源源 编码器和编码器和 缓冲存储器缓冲存储器 重发控制重发控制 双双向向信信道道 解码器解码器 指令产生器指令产生器 输出输出缓冲缓冲存储器存储器 信信宿宿 正确时输出正确时输出错误时删除错误时删除2022-12-171）3种种ARQ系统系统 停止等待停止等待AR
8、Q系统系统接收码组接收码组ACKACKNAKACKACKNAKACKt 1233455发送码组发送码组12334556t有错码组有错码组有错码组有错码组n 每发送一组数据后发送端等待接收端的确认每发送一组数据后发送端等待接收端的确认(ACK)答复，答复，然后再发送下一组数据。然后再发送下一组数据。n 当接收数据有误，接收端发回一个否认当接收数据有误，接收端发回一个否认(NAK)答复，这时，答复，这时，发送端将重发该组数据。发送端将重发该组数据。系统是工作在系统是工作在半双工状态半双工状态，时间没有得到充分利用，时间没有得到充分利用，传输效率较低。传输效率较低。2022-12-17 拉后拉后AR
9、Q系统系统n 发送端连续发送数据组，接收端对于每个接收到的数据发送端连续发送数据组，接收端对于每个接收到的数据组都发回组都发回确认确认(ACK)或或否认否认(NAK)答复。答复。n 例如，图中第例如，图中第5组接收数据有误，则在发送端收到第组接收数据有误，则在发送端收到第5组组接收的否认答复后，接收的否认答复后，从第从第5组开始重发数据组。组开始重发数据组。在这种系统中需要对发送的数据组和答复进行编号，在这种系统中需要对发送的数据组和答复进行编号，以便识别。显然，这种系统需要以便识别。显然，这种系统需要双工信道双工信道。接收数据接收数据有错码组有错码组有错码组有错码组910 1110 1112
10、2143657981110576ACK1NAK5NAK9ACK5发送数据发送数据576952143679810 1110 11 12重发码组重发码组重发码组重发码组ACK92022-12-17 选择重发选择重发ARQ系统系统接收数据有错码组有错码组有错码组有错码组9214365759810 11131412发送数据995852143671011131412重发码组重发码组重发码组重发码组NAK9ACK1NAK5ACK5ACK9它只重发出错的数据组，因此进一步提高了传输效率。它只重发出错的数据组，因此进一步提高了传输效率。2）ARQ的主要优点：的主要优点：和前向纠错方法相比和前向纠错方法相比 监
11、督码元较少即能使误码率降到很低，即码率较高；监督码元较少即能使误码率降到很低，即码率较高；检错的计算复杂度较低，成本降低；检错的计算复杂度较低，成本降低；检错用的编码方法和加性干扰的统计特性基本无关，能检错用的编码方法和加性干扰的统计特性基本无关，能适应不同特性的信道。适应不同特性的信道。2022-12-173）ARQ的主要缺点：的主要缺点：需要双向信道来重发，不能用于单向信道，也不能需要双向信道来重发，不能用于单向信道，也不能用于一点到多点的通信系统。用于一点到多点的通信系统。因为重发而使因为重发而使ARQ系统的传输效率降低。系统的传输效率降低。在信道干扰严重时，可能发生因不断反复重发而造在
12、信道干扰严重时，可能发生因不断反复重发而造成事实上的通信中断。成事实上的通信中断。不适合要求实时通信的场合，例如电话通信。不适合要求实时通信的场合，例如电话通信。（3）反馈校验法（）反馈校验法（HEC）接收端将收到的信码原封不动地转发给发送端，并与接收端将收到的信码原封不动地转发给发送端，并与原发送信码相比较，如果有错，发送端重发。原发送信码相比较，如果有错，发送端重发。需要双向信道。需要双向信道。因为每一组信码都传输因为每一组信码都传输2次，所以传输效率很低。次，所以传输效率很低。2022-12-17（1）前向纠错法（）前向纠错法（FEC）（2）检错重发法（）检错重发法（ARQ）（3）反馈校
13、验法（）反馈校验法（HEC）差错控制技术的种类差错控制技术的种类 其中，（其中，（1）,（2）两种方法均在接收端识别有无错码，）两种方法均在接收端识别有无错码，这是由发送端的信道编码器在信息码元序列中增加一些这是由发送端的信道编码器在信息码元序列中增加一些监监督码元督码元来实现的。来实现的。（1）差错控制编码）差错控制编码在信息码元序列中加入监督码元。在信息码元序列中加入监督码元。5、差错控制编码：常称为纠错编码、差错控制编码：常称为纠错编码（2）监督码元：）监督码元：为了在接收端识别有无错码，通常在发送端需要在信息为了在接收端识别有无错码，通常在发送端需要在信息码元序列中增加一些差错控制码元
14、，它们称为监督码元。码元序列中增加一些差错控制码元，它们称为监督码元。2022-12-17 例如，若编码序列中平均每两个信息码元就添加例如，若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的多余度为一个监督码元，则这种编码的多余度为1/3。（4）编码效率（简称码率）编码效率（简称码率）：信息码元数量（信息码元数量（k）和总码元数量（）和总码元数量（n）之比：）之比：k/n （3）多余度：）多余度：监督码元数监督码元数(n-k)和总码元数和总码元数 n 之比：之比：理论上，差错控制以理论上，差错控制以降低信息传输速率为代价降低信息传输速率为代价换取提高换取提高传输可靠性。传输可靠性。
15、一般地，增加的监督码元越多（多余度越大），一般地，增加的监督码元越多（多余度越大），检（纠）错能力就越强。检（纠）错能力就越强。2022-12-1711.2 纠错编码的基本原理纠错编码的基本原理 设有一种由设有一种由3位二进制数字构成的码组，它共有位二进制数字构成的码组，它共有8种不同的可能组合。若将其全部用来表示天气，则可种不同的可能组合。若将其全部用来表示天气，则可以表示以表示8种不同天气：种不同天气：引例：引例：000晴，晴，001云云 010阴，阴，011雨雨100雪，雪，101霜霜110雾，雾，111雹雹 其中任一码组在传输中若发生一个或多个错码，则将其中任一码组在传输中若发生一个或
16、多个错码，则将变成另一个信息码组。这时，接收端将无法发现错误。变成另一个信息码组。这时，接收端将无法发现错误。2022-12-17若在上述若在上述8种码组中只准许使用种码组中只准许使用4种来传送天气，例如：种来传送天气，例如：000晴，晴，011云云 101阴，阴，110雨雨许用码组许用码组（合法码组）（合法码组）则剩余的码组：则剩余的码组：001，010，100，111禁用码组禁用码组（非法码组）（非法码组）虽然虽然4个许用码组只能传送个许用码组只能传送4种不同的天气，但是接种不同的天气，但是接收端却有可能发现码组中的一个错码（检错）。收端却有可能发现码组中的一个错码（检错）。1、许用码组和
17、禁用码组、许用码组和禁用码组 出现禁用码组，即可判断出错。出现禁用码组，即可判断出错。2022-12-17000（晴）（晴）例如：若例如：若“000”（晴）中错了一位，即：（晴）中错了一位，即：001010100禁用码组禁用码组 接收端在收到禁用码组时，就认为发现了错码。接收端在收到禁用码组时，就认为发现了错码。当发生当发生3个错码时，个错码时，“000”变成了变成了“111”，它也是禁用，它也是禁用码组，故这种编码也能检测码组，故这种编码也能检测3个错码。个错码。但是这种码但是这种码不能发现一个码组中的两个错码不能发现一个码组中的两个错码，因为发，因为发生两个错码后产生的是许用码组。生两个错
18、码后产生的是许用码组。000（晴）（晴）011云云101阴阴110雨雨许用码组许用码组2022-12-172、检错和纠错、检错和纠错 上面这种编码只能检测错码，不能纠正错码。上面这种编码只能检测错码，不能纠正错码。例如，当接收码组为禁用码组例如，当接收码组为禁用码组“100”时，接收端将时，接收端将无法判断是哪一位码发生了错误，因为晴、阴、雨三者无法判断是哪一位码发生了错误，因为晴、阴、雨三者错了一位都可以变成错了一位都可以变成“100”。000晴，晴，011云云 101阴，阴，110雨雨000晴晴101阴阴110雨雨传错一位传错一位1002022-12-17若规定：若规定：要能够纠正错误，还
19、要增加要能够纠正错误，还要增加多余度多余度。000晴，晴，111雨雨（许用码组）（许用码组）001，010，011，100，101，110（禁用码组）（禁用码组）则能够检测两个以下错码，或能够纠正一个错码。则能够检测两个以下错码，或能够纠正一个错码。分析：分析：纠正为纠正为“000”（晴）（晴）当收到禁用码组当收到禁用码组“100”时，时，若假定仅有一个错码。若假定仅有一个错码。当收到禁用码组当收到禁用码组“100”时，时，若假定错码数不超过两个。若假定错码数不超过两个。只能检测出存在错码只能检测出存在错码而无法纠正错码而无法纠正错码2022-12-173、分组码、分组码 将信息码分组，为每组
20、信息码附加若干监督码将信息码分组，为每组信息码附加若干监督码的编码。即：的编码。即：分组码信息码监督码分组码信息码监督码注意：监督码仅仅监督本码组中的信息码元。注意：监督码仅仅监督本码组中的信息码元。信息位信息位监督位监督位晴晴000云云011阴阴101雨雨110例如：例如：000晴晴011云云101阴阴110雨雨2022-12-17（1）分组码的一般结构）分组码的一般结构分组码的符号：分组码的符号：(n,k)n 码组的总位数，又称为码组的长度（码长）码组的总位数，又称为码组的长度（码长）k 码组中信息码元的数目码组中信息码元的数目nk=r 码组中的监督码元数目，或称监督位数目码组中的监督码元
21、数目，或称监督位数目2022-12-17（2）分组码的码重）分组码的码重W 分组码中分组码中“1”的个数目称为码组的重量，简称码重。的个数目称为码组的重量，简称码重。（3）分组码的码距）分组码的码距d 把两个码组中对应位上数字不同的位数称为码组的距把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距又称离，简称码距。码距又称汉明距离汉明距离。例如：例如：000晴晴011云云101阴阴110雨雨码距均为码距均为21）最小码距最小码距(d0)：把某种编码中各个码组之间距离的最把某种编码中各个码组之间距离的最小值。例如，上面的编码的最小码距小值。例如，上面的编码的最小码距d0=2。202
22、2-12-17 设一个码组设一个码组A位于位于O点。若码组点。若码组A中发生一个错码，中发生一个错码，则我们可以认为则我们可以认为A的位置将移动至以的位置将移动至以O点为圆心，以点为圆心，以1为半为半径的圆上某点，但其位置不会超出此圆。径的圆上某点，但其位置不会超出此圆。2）码距和检纠错能力的关系码距和检纠错能力的关系 一种编码的最小码距一种编码的最小码距d0的大小直接关系着这种的大小直接关系着这种编码的检错和纠错能力。编码的检错和纠错能力。为检测为检测e个错码，要求最小码距个错码，要求最小码距 d0 e+1【证】0123BA汉明距离汉明距离ed0 若码组若码组A中发生两中发生两位错码，则其位
23、置不会位错码，则其位置不会超出以超出以O点为圆心，以点为圆心，以2为半径的圆。为半径的圆。2022-12-170123BA汉明距离汉明距离ed0 同理，若一种编码的同理，若一种编码的最小码距为最小码距为d0，则将能检，则将能检测测(d0-1)个错码。个错码。反之，若要求检测反之，若要求检测e个错码，则最小码距个错码，则最小码距d0应满足：应满足：d0 e+1 因此，只要最小码距不小于因此，只要最小码距不小于3，码组，码组A发生两位发生两位以下错码时，不可能变成另一个许用码组以下错码时，不可能变成另一个许用码组B，因而能，因而能检测错码的位数等于检测错码的位数等于2。2022-12-17 为了纠
24、正为了纠正t个错码，要求最小码距个错码，要求最小码距d0 2t+1BtA汉明距离汉明距离012345td0 图中画出码组图中画出码组A和和B的距离为的距离为5。码组。码组A或或B若发生若发生不多于两位错码，则其位置均不会超出半径为不多于两位错码，则其位置均不会超出半径为2以原位以原位置为圆心的圆。这两个圆是不重叠的。置为圆心的圆。这两个圆是不重叠的。判决规则为：判决规则为：若接收码组落于以若接收码组落于以A为圆心的圆上为圆心的圆上就判决收到的是码组就判决收到的是码组A，若落于以，若落于以B为圆心的圆上就判为圆心的圆上就判决为码组决为码组B。若错码达到若错码达到3个，个，就将落入另一圆上，就将落
25、入另一圆上，从而发生错判。从而发生错判。这样，就能够纠正两位错码。这样，就能够纠正两位错码。2022-12-17 为纠正为纠正t个错码，同时检测个错码，同时检测e个错码，要求最小码距个错码，要求最小码距BtA汉明距离汉明距离012345td0下图所示的例子，图中码组下图所示的例子，图中码组A和和B之间距离为之间距离为5。按照检错能力公式，最多能检测按照检错能力公式，最多能检测 个错码，即：个错码，即：e=d0 1=5 1=44按照纠错能力公式纠错时，能纠正按照纠错能力公式纠错时，能纠正 个错码个错码2d0 2t+12022-12-17BtA汉明距离汉明距离012345td0 但是，不能同时做到
26、即检测但是，不能同时做到即检测4个错码，又纠正个错码，又纠正2个错码。个错码。例如，码组例如，码组A若错了若错了3位，就会被误认为码组位，就会被误认为码组B错错了了2位造成的结果，从而被错位造成的结果，从而被错“纠纠”为为B。这就是说，检错和纠错公式不能同时成立或同时这就是说，检错和纠错公式不能同时成立或同时运用。运用。2022-12-17 为了在可以纠正为了在可以纠正t个错码的同时，能够检测个错码的同时，能够检测e个错个错码，就需要像下图所示那样，使某一码组（譬如码组码，就需要像下图所示那样，使某一码组（譬如码组A）发生）发生e个错误之后所处的位置，与其他码组（譬如个错误之后所处的位置，与其
27、他码组（譬如码组码组B）的）的纠错圆圈纠错圆圈至少距离等于至少距离等于1，不然将落在该纠，不然将落在该纠错圆上从而发生错误地错圆上从而发生错误地“纠正纠正”。因此，由此图可以直观看出，要求最小码距：因此，由此图可以直观看出，要求最小码距：这种纠错和检错结合的工作方式简称这种纠错和检错结合的工作方式简称纠检结合。纠检结合。ABe1tt汉明距离汉明距离e2022-12-17为检测为检测e个错码，要求最小码距个错码，要求最小码距 d0 e+1 为了纠正为了纠正t个错码，要求最小码距个错码，要求最小码距d0 2t+1 为纠正为纠正t个错码，同时检测个错码，同时检测e个错码，要求最小码距：个错码，要求最
28、小码距：例如：例如：若最小码距若最小码距d0=5，则：，则：按照检错能力公式，最多能检测按照检错能力公式，最多能检测 个错码；个错码；4按照纠错能力公式，最多能纠正按照纠错能力公式，最多能纠正 个错码；个错码；2按照纠检错结合方式工作时，若计算纠错能力为按照纠检错结合方式工作时，若计算纠错能力为1，则最，则最多能检测多能检测 个错码；个错码；32022-12-1711.4 简单的实用编码简单的实用编码11.4.1 奇偶监督码奇偶监督码 奇偶监督码分为奇偶监督码分为奇数监督码奇数监督码和和偶数监督码偶数监督码两种，两种，两者的原理相同。两者的原理相同。设码组：设码组：（an-1 an-2 an-
29、2 a1 a0）an-1 先出现先出现a0最后出现最后出现n位位n-1位：信息位位：信息位奇偶校验位奇偶校验位1、编码效率（码率）：、编码效率（码率）：2022-12-172、校验方法、校验方法（1）偶校验）偶校验监督位使整个码组中监督位使整个码组中“1”的数目为偶数，即满足：的数目为偶数，即满足：（即各码元模即各码元模2相加相加）若结果若结果01认为无错认为无错 认为有错认为有错 （2）奇校验）奇校验监督位使整个码组中监督位使整个码组中“1”的数目为奇数，即满足：的数目为奇数，即满足：（即各码元模即各码元模2相加相加）若结果若结果10认为无错认为无错 认为有错认为有错 2022-12-17若
30、若n=6，信息位为：，信息位为：10110采用采用偶校验偶校验，则发方码组为，则发方码组为：若接收码组为：若接收码组为：（101101）判为合法（实为正确）判为合法（实为正确）（111100）判为合法（实为错码）判为合法（实为错码）（111101）判为非法（一定有误码）判为非法（一定有误码）注意：注意：奇偶校验码组只能检测奇位错（奇偶校验码组只能检测奇位错（1位）。位）。偶校验码组属于线性分组码；偶校验码组属于线性分组码；奇校验码组不属于线性分组码，而属于非线性分组码。奇校验码组不属于线性分组码，而属于非线性分组码。（101101）2022-12-1711.4.2 二维奇偶监督码（方阵码）二维
31、奇偶监督码（方阵码）非线性非线性 它是先把上述奇偶监督码的若干码组排成矩阵，它是先把上述奇偶监督码的若干码组排成矩阵，每一码组写成一行，然后再按列的方向增加第二维每一码组写成一行，然后再按列的方向增加第二维监督位，如下图所示：监督位，如下图所示：012101212021222110111211ccccaaaaaaaaaaaannmmmnmnnnnn信息信息 位位监督位监督位第一个码组第一个码组 第二个码组第二个码组 第第m个码组个码组 按列进行第二次编码按列进行第二次编码所增加的监督位所增加的监督位2022-12-17二维奇偶监督码的性能二维奇偶监督码的性能（1）这种编码有可能检测偶数个错码。
32、）这种编码有可能检测偶数个错码。因为每行的监督位虽然不能用于检测本行中的偶数个因为每行的监督位虽然不能用于检测本行中的偶数个错码，但按列的方向有可能由错码，但按列的方向有可能由cn-1 cn-2 c1 c0等监督位检测等监督位检测出来。出来。有一些偶数错码不可能检测出来。有一些偶数错码不可能检测出来。222121mmnnaaaa 例如，构成矩形的例如，构成矩形的4个错码，个错码，譬如图中：譬如图中：2022-12-17（2）这种二维奇偶监督码适于检测突发错码。）这种二维奇偶监督码适于检测突发错码。（3）由于方阵码只对构成矩形四角的错码无法检测，故其）由于方阵码只对构成矩形四角的错码无法检测，故
33、其检错能力较强。检错能力较强。（4）二维奇偶监督码不仅可用来检错，还可以用来纠正）二维奇偶监督码不仅可用来检错，还可以用来纠正一些错码。一些错码。例如，仅在一行中有奇数个错码时，则能够确定错例如，仅在一行中有奇数个错码时，则能够确定错码位置，从而纠正它。码位置，从而纠正它。2022-12-17例：例：信息位信息位（1110110111011010111100100）1110110111011010111100100组成组成55的方阵。构造的方阵。构造二维奇偶监督码二维奇偶监督码0 0 1 0 1 01 1 0 0 0 2022-12-1711.4.3 恒比码恒比码 在恒比码中，在恒比码中，每个
34、码组均含有相同数目的每个码组均含有相同数目的“1”（和（和“0”）。由于。由于“1”的数目与的数目与“0”的数目之比保的数目之比保持恒定，故得此名。持恒定，故得此名。这种码在检测时，只要计算接收码组中这种码在检测时，只要计算接收码组中“1”的数目的数目是否对，就知道有无错码。是否对，就知道有无错码。恒比码的主要优点是简单和适于用来传输电传机或其恒比码的主要优点是简单和适于用来传输电传机或其他键盘设备产生的字母和符号。对于信源来的二进制随机他键盘设备产生的字母和符号。对于信源来的二进制随机数字序列，这种码就不适合使用了。数字序列，这种码就不适合使用了。2022-12-1711.4.4 正反码正反
35、码 是一种简单的能够纠正错码的编码。其中的是一种简单的能够纠正错码的编码。其中的监督位数目与信息位数目相同监督位数目与信息位数目相同。1、编码原则：、编码原则：监督码元与信息码元相同（重复）监督码元与信息码元相同（重复）当信息位中含当信息位中含有有奇数个奇数个“1”；监督码元与信息码元相反（反码）监督码元与信息码元相反（反码）当信息位中含当信息位中含有有偶数个偶数个“1”；例如：例如：若信息位为若信息位为11001，若信息位为若信息位为10001，则码组为则码组为1100111001；则码组为则码组为1000101110。2022-12-172、正反码的解码、正反码的解码（1）先将接收码组中）
36、先将接收码组中信息位和监督位按模信息位和监督位按模 2 相加相加，得到一个得到一个5位的位的合成码组合成码组。若若接收码组的接收码组的信息位信息位中有中有奇数个奇数个“1”，则，则合成码组合成码组就就是校验码组；是校验码组；若若接收码组的接收码组的信息位信息位中有中有偶数个偶数个“1”，则取，则取合成码组合成码组的反码的反码作为校验码组。作为校验码组。（3）最后，观察）最后，观察校验码组中校验码组中“1”的个数的个数，按下表进行，按下表进行判决及纠正可能发现的错码。判决及纠正可能发现的错码。（2）由合成码组产生一个）由合成码组产生一个校验码组校验码组。2022-12-17校验码组的组成校验码组
37、的组成错码情况错码情况1 1全为全为“0”0”无错码无错码2 2有有(n-1)(n-1)个个“1”1”和和1 1个个“0”0”信息码中有信息码中有1 1位错码，位错码，其位置对应校验码组中其位置对应校验码组中“0”0”的位置的位置3 3有有(n-1)(n-1)个个“0”0”和和1 1个个“1”1”监督码中有监督码中有1 1位错码，位错码，其位置对应校验码组中其位置对应校验码组中“1”1”的位置的位置4 4其他组成其他组成错码多于错码多于1 1个个校验码组和错码的关系校验码组和错码的关系例如，例如，若发送码组为：若发送码组为：1100111001，若若接收码组接收码组为：为：1100111001
38、 则则合成码组合成码组为：为：11001 11001=00000。由于接收码组信息位中有奇数个由于接收码组信息位中有奇数个“1”，所以，所以 校验码组校验码组为：为：00000所以无错码。所以无错码。2022-12-17例如，例如，若发送码组为：若发送码组为：1100111001，若若接收码组接收码组为：为：1000111001 则则合成码组合成码组为：为：10001 11001=01000。由于接收码组信息位中有偶数个由于接收码组信息位中有偶数个“1”，所以，所以 校验码组校验码组为：为：10111（反码）（反码）所以有错码，且在信息位中第二位为错码。所以有错码，且在信息位中第二位为错码。例
39、如，例如，若发送码组为：若发送码组为：1100111001，若若接收码组接收码组为：为：1100110001 则则合成码组合成码组为：为：11001 10001=01000。由于接收码组信息位中有奇数个由于接收码组信息位中有奇数个“1”，所以，所以 校验码组校验码组为：为：01000所以有错码，且在信息位中第二位为错码。所以有错码，且在信息位中第二位为错码。2022-12-17例如，例如，若发送码组为：若发送码组为：1100111001，若若接收码组接收码组为：为：1001111001 则则合成码组合成码组为：为：10011 11001=01010。由于接收码组信息位中有奇数个由于接收码组信息
40、位中有奇数个“1”，所以，所以 校验码组校验码组为：为：01010所以有错码，且多余一个。所以有错码，且多余一个。上述长度为上述长度为10的正反码具有纠正的正反码具有纠正1位错码的能力，并能位错码的能力，并能检测全部检测全部2位以下的错码和大部分位以下的错码和大部分2位以上的错码。位以上的错码。补充：补充：重复码重复码 0（00000）1（11111）效率很低，但抗干扰能力很强。效率很低，但抗干扰能力很强。解码：择大判决。解码：择大判决。（11001）12022-12-1711.5 线性分组码线性分组码1、基本概念、基本概念（1）码）码码型，最高的概念；码型，最高的概念；Code 有各种各样的
41、码，可自行设计，要求效率高，纠错能有各种各样的码，可自行设计，要求效率高，纠错能力强，电路简单。力强，电路简单。（2）码组）码组Code Words （设共（设共n位）位）码由码组组成，是一个集合：码由码组组成，是一个集合：码组码组。合法码组：合法码组：属于码（集合）的码组：属于码（集合）的码组：非法码组：非法码组：不属于码（集合）的码组：不属于码（集合）的码组：（an-1 an-2 ar ar-1a1 a0）k位：信息位位：信息位r位：监督位位：监督位2k个个2n-2k个个2022-12-17（3）码长）码长n=k+r （4）码元）码元Code bitsRC=k/n （5）编码效率（简称码率
42、）编码效率（简称码率）：(n-k)/k=r/k（7）冗余度）冗余度：（8）汉明重量（）汉明重量（Hamming Weight）：码组中码组中“1”的个数的个数 例如：例如：u（1101110）W=5 （码的）最小汉明重量：（码的）最小汉明重量：W0或或Wmin 码是很多码组的集合，每个码组都有各自的重量，码是很多码组的集合，每个码组都有各自的重量，其中最小的重量即为码的其中最小的重量即为码的“最小汉明重量最小汉明重量”。(n-k)/n=r/n（6）多余度）多余度：2022-12-17（8）汉明距离（码组）汉明距离（码组）：两个码组所含不同位的个数，称为两个码组所含不同位的个数，称为“码组的汉明
43、距离码组的汉明距离”。例如：例如：u（1101110）d(u,v)=3 （码的）最小汉明距离：（码的）最小汉明距离：d0或或dmin 码是很多码组的集合，每对码组都有各自的汉明距码是很多码组的集合，每对码组都有各自的汉明距离，其中最小的距离即为码的离，其中最小的距离即为码的“最小汉明距离最小汉明距离”。v（1001011）最小汉明距离直接决定了码的就错能力：最小汉明距离直接决定了码的就错能力：d0纠错能力纠错能力d0 2t+1d0 e+12022-12-172、线性分组码的定义、线性分组码的定义 线性分组码：线性分组码：按照一组线性方程构成的分组码。按照一组线性方程构成的分组码。设设C为码，为
44、码，Ci为码组，若：为码组，若：C=Ci，其中，其中CiC，CjC，且有：，且有：Ci Cj C则则C为为线性分组码线性分组码。线性分组码中必含有全零码。线性分组码中必含有全零码。对于线性分组码有：对于线性分组码有：W0=d0 推论：推论：2022-12-173、线性分组码的监督阵和生成阵、线性分组码的监督阵和生成阵监督阵监督阵H：rn生成阵生成阵G：kn知道了知道了H，即可得到，即可得到G：知道了：知道了G，即可得到，即可得到H。（1）监督阵和生成阵）监督阵和生成阵1）监督方程：）监督方程：其中：其中：H监督阵，监督阵，rnA码组，码组，1n0矩阵，矩阵，1r2022-12-17例如，对于著
45、名的（例如，对于著名的（7，4）汉明码：（）汉明码：（n=7,k=4）111010011010101011001H6543210Aaaaaaaa00002022-12-17G矩阵的性质：矩阵的性质：G矩阵的各行是线性无关的。矩阵的各行是线性无关的。G的各行本身就是一个码的各行本身就是一个码 因此，如果已有因此，如果已有k个线性无关的码组，则可以用其个线性无关的码组，则可以用其作为生成矩阵作为生成矩阵G，并由它生成其余码组。，并由它生成其余码组。2）生成方程：）生成方程：其中：其中：G生成阵，生成阵，knA码组，码组，1nX信息矢量，信息矢量，1k6543210Aaaaaaaa6543Xaaaa
46、2022-12-17（2）典型的监督阵和生成阵）典型的监督阵和生成阵1）典型）典型H (rn)()rHPInkrrP：rkIr：rr单位阵单位阵2）典型）典型G (kn)()kGIQnkrkQ：krIk：kk单位阵单位阵2022-12-173）典型阵的关系：）典型阵的关系：【证明【证明】监督方程：监督方程：110nrrraaPIaarkrrk1r11100nrraaPaa110rnn kaaPaa 因为模因为模2运算，运算，无需考虑正负。无需考虑正负。2022-12-17110rnn kaaPaa101Trnn kaaaaP 1101Tnn krnn kkaaaaaaIPTkAX IP又因为又
47、因为TkGIP()kGIQ又因为又因为TTQPPQ2022-12-174）生成阵）生成阵G和监督阵和监督阵H的行变换的行变换 G的每一行都是一个合法的码组，它们构成码的每一行都是一个合法的码组，它们构成码的一个基。的一个基。对典型对典型G阵进行阵进行“行变换行变换”后仍然为该码的生成阵，后仍然为该码的生成阵，仍有：仍有：但但G已为非典型。已为非典型。对典型对典型H阵进行阵进行“行变换行变换”后仍然为该码的监督阵，后仍然为该码的监督阵，仍有：仍有：但但H已为非典型。已为非典型。注意：列变化将改变码型。注意：列变化将改变码型。2022-12-175）G的行矢量的行矢量H的行矢量（内积为零）的行矢量
48、（内积为零）【证明【证明】gG的行的行hH的行的行即证明：即证明：则有：则有：ghT=0AX G0TAH0TXGH0TTH A 由于由于X为任意的信息矢量，则有：为任意的信息矢量，则有：0TGH即：即：2022-12-17【例【例】n=5，k=2合法码组：合法码组：2k4已知其中两个合法码组为：已知其中两个合法码组为：C101100C211011试求生成阵试求生成阵G及其典型阵；求监督阵及其典型阵；求监督阵H。【解【解】设其中另一个为全零码组：设其中另一个为全零码组：00000由线性码可知：由线性码可知：C3 C1 C2 10111（1）生成阵）生成阵G：kn0110011011G2022-1
49、2-170110011011GG转换成典型阵转换成典型阵1101101100G1011101100G行变换行变换（2）监督阵）监督阵H由典型由典型G可直接推得典型可直接推得典型H()rHPI()kGIQ且：且：1011101100G1 1 1 0 01 0 0 1 01 0 0 0 1H2022-12-174、利用监督阵、利用监督阵H检错（不纠错）检错（不纠错）如果发送为码组如果发送为码组A如果接收为码组如果接收为码组B将将B代入监督方程：代入监督方程：0TH B若若 真的无错码真的无错码有错码，但超出了检错能力有错码，但超出了检错能力0TH B若若出现错码出现错码 2022-12-175、利
50、用校正子、利用校正子S纠检错纠检错（1）校正子）校正子S的定义：的定义：其中：其中：E差错矢量差错矢量/差错图样（差错图样（1n）H监督阵（监督阵（rn）S（1r）若若E=0，则判无差错，则，则判无差错，则S=0。(mod2)EAB若发方为若发方为A码组，收方码组，收方为为B码组。码组。2022-12-17（2）利用校正子）利用校正子S纠检错纠检错收发收到收发收到B矢量：矢量：使用使用H对接收信号进行校验：对接收信号进行校验：监督方程：监督方程：0TAH()0TTTTTBHAE HAHEHEHS0，无错码或漏检，无错码或漏检0，有错码，有错码2022-12-17例如例如：（：（7，4）汉明码）
