差错控制编码

差错控制编码第1页/共131页2023/4/24:01211.1概述

1.误码的主要形式

（1）随机错误：误码的位置随机（误码间无关联），随机误码主要由白噪声引起。（2）突发错误：误码成串出现，主要由强脉冲及雷电等突发的强干扰引起。（3）混合错误：以上两种误码及产生原因的组合。11.1差错控制编码的基本概念差错控制的主要方式第2页/共131页2023/4/24:013

（1）前向纠错（FEC）；

（2）检错重发（ARQ）:停发等候重发，返回重发，选择重发；

（3）反馈校验（IRQ）；

（4）混合纠错（HEC）；

（5）检错删除。

能够发现错误的码反馈信号发收检错重发（ARQ）可以纠正错误的码发收前向纠错（FEC）数据信息发收信息反馈数据信息可以纠正和发现错误的码发收混合纠错检错（HEC）反馈信号发送端将信息序列编码成能够纠正错误的码，接收端根据编码规则进行检查，如果有错自动纠正；不需要反馈信道，特别适合只能提供单向信道场合；自动纠错，不要求检错重发，延时小，实时性好；纠错码必须与信道的错误特性密切配合；若纠错较多，则编、译码设备复杂，传输效率低；收端把收到的数据序列全部经反向信道送回发端，发端比较发出和送回的数据序列，从而发现有否错误，并把有错误的数据序列再次传送，直到发端没有发现错误；不需要纠错、检错的编、译码器，设备简单；需要和正向信道相同的反向信道，实时性差；发端需要一定容量的存储器以存储发送码组；仅适应于传输速率较低，信道差错率较低，具有双向传输线路及控制简单的系统。FEC与ARQ的结合；发端发出同时具有检错和纠错能力的码，收端收到后，检查错误情况：如果错误在纠错能力之内，则自动纠正；若超出纠错能力，但在检错能力之内，则经反向信道要求重发；在实时性和译码复杂性方面是FEC和ARQ的折衷。11.1差错控制编码的基本概念2.差错控制的主要方式

几个概念第3页/共131页2023/4/24:014监督码元：在接收端识别有无错码，所以在发送端需要在信息码元序列中增加一些除了信息码元之外的差错控制码元，它们称为监督码元。编码效率(简称码率)

：设编码序列中信息码元数量为k，总码元数量为n，则比值k/n就是码率。例如，若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的码率为1/3。冗余度：监督码元数(n-k)和信息码元数k之比。不同的编码方法，有不同的检错或纠错能力。理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。纠错编码又称为差错控制编码差错控制编码的分类第4页/共131页2023/4/24:015

3.差错控制编码的分类（1）线性码：信息码与监督码之间的关系为线性关系（信息位与监督位之间是由一些线性方程联系的）；

非线性码：信息码与监督码之间的关系为非线性关系。（2）分组码：信息码与监督码以组为单位建立关系（将信息码分组，为每组信码附加若干监督码的编码）；

卷积码：监督码与本组和前面码组中的信息码有关。（3）系统码：编码后码组中信息码保持原图样顺序(形式)不变;

非系统码：编码后码组中原信息码原图样发生变化。（4）数学方法：

代数码:建立在代数学基础上的编码

几何码；算术码。分组码结构11.2差错控制编码的基本原理第5页/共131页2023/4/24:016分组码的结构将信息码分组，为每组信息码附加若干监督码的编码称为分组码。分组码中，监督码元仅监督本码组中的信息码元。分组码的一般结构分组码的符号：(n,k)N－码组的总位数，又称为码组的长度（码长），k－码组中信息码元的数目，n–k＝r,码组中的监督码元数目，或称监督位数目。纠错编码基本原理第6页/共131页2023/4/24:01711.2纠错编码的基本原理

1.纠错编码的基本原理理论依据：Shannon信道编码定理。定理指出：对于一给定的有扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值。2.纠错编码的基本思想：发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系……以牺牲通信的有效性（信息传输速率）来提高可靠性码的检错和纠错能力是用信息量的冗余来换取的。一般说来，添加的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。检错与纠错第7页/共131页2023/4/24:0183.检错与纠错的基本概念11.2差错控制编码的基本原理例1，用1位二进制码的2种编码组合，分别表示“月有阴晴圆缺”中“月”的四种状态。0-圆，1-缺。

a.若任一位或一位以上的错误都会变成另一码组，所以无法检错和纠错。例如，发送“0”，错误收到“1”

b.若用2位二进制（有4个码组），表示“圆、缺”两种信息。00-圆，11-缺用到的：00，11称为“许用码组”：其余不用的，称为“禁用码组”：10，01

因任一位误码，都会变成禁用码组，所以可检出1位误码。

续第8页/共131页2023/4/24:019可见纠错编码之所以具有检错和纠错能力，是因为在信息码元外添加了冗余码元（监督码元）；直观地，冗余度越大，许（准）用码组间的区别越大，检错和纠错能力越强。几个术语

c.若用3位二进制（有8个码组），表示“圆、缺”两种信息。000-圆，111-缺。其余为禁用码。则可发现两位及以下的误码，并纠正1位误码。11.2差错控制编码的基本原理第9页/共131页2023/4/24:0110a.

码重W：码组中非零码元的数目。如“011”码字的码重为2；b.码距d：两码组中对应码元位置上取值不同的个数。如码字“011”与“110”间码距为2；c.最小码距d0（Hamming距）：准用码组中任两码组间的最小码距。

几个术语

分组码码距和纠检错能力之间的关系11.2差错控制编码的基本原理第10页/共131页2023/4/24:0111【证】设一种编码的最小码距为3。任一个码组A位于O点，码组A发生两位以下错码时，不可能变成另一个准用码组，因而能检测错码的位数等于2。0123BA汉明距离ed0即，若一种编码的最小码距为d0，则将能检测(d0-1)个错码。反之，若要求检测e个错码，则最小码距d0至少应不小于(e+1)。分组码的码距和检纠错能力的关系1）一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力为检测e个错码，要求最小码距d0e+1续第11页/共131页2023/4/24:0112【证】图中画出码组A和B的距离为5。码组A或B若发生不多于两位错码，则其位置均不会超出半径为2以原位置为圆心的圆。这两个圆是不重叠的。判决规则为：若接收码组落于以A为圆心的圆上就判决收到的是码组A，若落于以B为圆心的圆上就判决为码组B。从而，就能够纠正两位错码。BtA汉明距离012345td02）为了纠正t个错码，要求最小码距d0

2t+1续第12页/共131页2023/4/24:0113图中码组A和B之间距离为5。按照检错能力公式，最多能检测4个错码，即e=d0–1=5–1=4，按照纠错能力公式纠错时，能纠正2个错码。但是，不能同时做到两者，因为当错码位数超过纠错能力时，该码组立即进入另一码组的圆内而被错误地“纠正”了。例如，码组A若错了3位(超过2位)，就会被误认为码组B错了2位造成的结果，从而被错“纠”为B。这就是说，检错和纠错公式不能同时成立或同时运用。BtA汉明距离012345td03）为纠正t个错码，同时检测e个错码，要求最小码距续第13页/共131页2023/4/24:0114

这种纠错和检错结合的工作方式简称纠检结合。ABe1tt汉明距离所以，为了在可以纠正t个错码的同时，能够检测e个错码，就需要像下图所示那样，使某一码组（譬如码组A）发生e个错误之后所处的位置，与其他码组（譬如码组B）的纠错圆圈至少距离等于1，不然将落在该纠错圆上从而发生错误地“纠正”。因此，由此图可以直观看出，要求最小码距续第14页/共131页2023/4/24:0115这种工作方式是自动在纠错和检错之间转换的。当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；当错码数量多时，系统按反馈重发方式纠错，以降低系统的总误码率。所以，它适用于大多数时间中错码数量很少，少数时间中错码数量多的情况。纠检结合纠错编码性能第15页/共131页2023/4/24:0116由上节所述的纠错编码原理可知，为了减少接收错误码元数量，需要在发送信息码元序列中加入监督码元。这样作的结果使发送序列增长，冗余度增大。若仍须保持发送信息码元速率不变，则传输速率必须增大，因而增大了系统带宽。系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。信噪比的下降反而又使系统接收码元序列中的错码增多。一般说来，采用纠错编码后，误码率总是能够得到很大改善的。改善的程度和所用的编码有关。11.3纠错编码的性能系统带宽和信噪比的矛盾：传输速率和信噪比关系第16页/共131页2023/4/24:0117若希望提高传输速率，可看出势必导致信噪比下降，误码率增大。假设系统原来工作在图中C点，提高速率后由C点升到E点。但加用纠错编码后，仍可将误码率降到D点。这时付出的代价仍是带宽增大。10-610-510-410-310-210-1编码后PeCDEAB信噪比(dB)传输速率和Eb/n0的关系对于给定的传输系统式中，RB为码元速率。几种简单的常用编码第17页/共131页2023/4/24:011811.4.1奇偶效验码

在信息码组an-1,an-2,…,a1中加入监督位a0，使编码后码组中“1”的个数为奇数（奇效验）或偶数（偶效验）。偶效验：取校验码（监督码元）a0，使下式成立

an-1an-2…a1a0＝0

即，a0=an-1an-2…a1奇效验：取校验码（监督码元）

a0，使下式成立an-1an-2…a1a0＝1即，

a0=an-1an-2…a11奇偶效验码码组间最小距离d0＝2，至少可检出一位误码。实际，可检测所有奇数个误码。(用于计算机通信）水平奇偶校验码11.4几种简单的常用编码第18页/共131页2023/4/24:0119a1n-1a1n-2……a11

a10a2n-1a2n-2……a21a20

……………amn-1amn-2……am1am0

m个码组分别以各自码组为单位作奇效验或偶效验，然后以各码组的最高位、次高位，…依次发送：11.4.2水平奇偶效验码水平奇偶校验码特点分组进行奇偶校验发送次序当突发的错误数小于m个时，每个码组中的误码个数最多为1个，通过奇偶效验可以检出。第19页/共131页2023/4/24:0120水平奇偶效验码特点：在上面的分析中，整个方阵作为一个“码组”，长度为原来的m倍；可检出不大于m个的突发错误；在未增加监督位的条件下，检错能力为原来的m倍，这是香农信道编码定理应用的一个例子。

该编解码所付的代价：缓存空间和延时增大。水平垂直奇偶校验码第20页/共131页2023/4/24:012111.4.3水平垂直二维奇偶效验码（方阵码）8.1差错控制编码的基本概念a1n-1a1n-2……a11

a10a2n-1a2n-2……a21a20

……………ann-1ann-2……an1an0

在水平奇偶监督码的基础上增加列的奇偶效验可检出任一行和任一列的所有奇数个错误，及长度不大于行数（按列发）或不大于列数（按行发）的突发错误。其他校验码第21页/共131页2023/4/24:012211.4.4恒比码每个码组中含“1”和“0”的个数的比例恒定，又称等重码能检测出所有奇数个错误，并能部分检测出偶数个错误（成对交换错则检测不出）简单，适应于对字母或符号进行编码11.4.5群计数码码组中的监督码元是信息序列中“1”码个数的二进制表示；假设待编码信息序列为1011101，则编码后码组为1011101101；较强的检错能力，能检测出几乎所有形式的差错（除同时发生“0”变“1”和“1”变“0”的成对错误外）正反码第22页/共131页2023/4/24:0123例如，码长n=10，信息位k=5，监督位r=5。其编码规则为：若信息位为11001，则码组为1100111001；若信息位为10001，则码组为1000101110。11.4.6正反码正反码的编码：它是一种简单的能够纠正错码的编码。其中的监督位数目与信息位数目相同，监督码元与信息码元相同或者相反则由信息码中“1”的个数而定:信息位中有奇数个“1”时，监督位是信息位的重复；当信息位有偶数个“1”时，监督位是信息位的反码。正反码解码第23页/共131页2023/4/24:0124先将接收码组中信息位和监督位按模2相加，得到一个合成码组。然后，由此合成码组产生一个校验码组：若接收码组的信息位中有奇数个“1”，则合成码组就是校验码组；若接收码组的信息位中有偶数个“1”，则取合成码组的反码作为校验码组。最后，观察校验码组中“1”的个数，按下表进行判决及纠正可能发现的错码。

正反码的解码：校验码组的组成错码情况1全为“0”无错码2有4个“1”和1个“0”信息码中有1位错码，其位置对应校验码组中“0”的位置3有4个“0”和1个“1”监督码中有1位错码，其位置对应校验码组中“1”的位置4其他组成错码多于1个例第24页/共131页2023/4/24:0125例，发送1100111001，无错接收，则合成码组应为1100111001=00000。由于接收码组信息位中有奇数个“1”，所以校验码组就是00000。按上表判决，结论是无错码。若传输中产生了差错：接收码组错成1000111001，则合成码组1000111001＝01000。由于接收码组中信息位有偶数个“1”，所以校验码组应取合成码组的反码，即10111。按上表判断信息位中左边第2位为错码。若接收码组错成1100101001，则合成码组1100101001＝10000。由于接收码组中信息位有奇数个“1”，故校验码组就是10000，按上表判断，监督位中第1位为错码。若接收码组为1001111001，则合成码组1001111001＝01010，校验码组与其相同，按上表判断，这时错码多于1个。上述长度为10的正反码具有纠正1位错码的能力，并能检测全部2位以下的错码和大部分2位以上的错码。线性分组码第25页/共131页2023/4/24:012611.5线性分组码

11.5.1.基本概念线性分组码的特点：

(1)两许用码组之和（逐位模2和）仍为一许用码组（封闭性）；

(2)码组间的最小距离等于非零码的最小码重。

如何编码？校正子线性分组码：码组中的信息位和监督位之间的关系由线性方程确定。

表示方法：（n，k）,其中n—码组总位数；k—信息位数

第26页/共131页2023/4/24:0127在偶数监督码中，由于使用了一位监督位a0，它和信息位an-1…a1一起构成一个代数式：在接收端解码时，实际上就是在计算若S=0，就认为无错码；若S=1，就认为有错码。现将上式称为监督关系式，S称为校正子。由于校正子S只有两种取值，故它只能代表有错和无错这两种信息，而不能指出错码的位置。

11.5.2校正子校正子续第27页/共131页2023/4/24:0128例：具有纠正一位误码的分组码（7，4）

a6a5a4a3a2a1a0

n=7,k=4,

信息位监督位r=n－k＝311.5线性分组码定义一组确定误码位置的参量：S1S2S3(校正子)

由上表可得：如何确定a2a1a0?监督位确定当出现一位误码时，校正子能够确定误码的位置。S1S2

S3错码位置S1S2

S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码11.5.2校正子（续）第28页/共131页2023/4/24:0129由此,编码时监督位的产生：给出一组信息码a6a5a4a3，可计算出监督位a2a1a0。例11.5线性分组码11.5.3监督方程当无误码时，应有上述方程亦称为监督方程。第29页/共131页2023/4/24:0130例：

设信息码组a6a5a4a3＝0101

则监督位为：若接收时有一位(a5)码出错：

a6a5a4a3a2a1a0＝0001101则有：S1＝a6a5a4a2＝0001=1

S2＝a6a5a3a1＝0010=1

S3＝a6a4a3a0＝0011=0根据校正子S1S2S3＝110，可判断误码发生在a5，并恢复。则发送码组：

a6a5a4a3a2a1a0＝0101101

11.5线性分组码监督矩阵第30页/共131页2023/4/24:0131

11.5.4监督矩阵11.5线性分组码监督矩阵该监督方程可用矩阵形式表示可用表示为前述的监督方程第31页/共131页2023/4/24:0132前述的监督方程可用矩阵形式表示11.5线性分组码矩阵H称为监督矩阵。监督矩阵一般式及性质

这里

11.5.4监督矩阵第32页/共131页2023/4/24:0133一般地，对于任意的监督方程都可用矩阵形式表示11.5线性分组码矩阵H称为监督矩阵。监督矩阵的性质：（1）H由码元间的监督关系[S]唯一确定；（2）H的行向量相互独立，当采用系统码结构时，具有形式H=[PIr]其中Ir是r×r单位阵。并称之为典型监督矩阵。（3）若发[A]，收到[B]，H[B]T≠[0]则有误码。

11.5.4监督矩阵生成矩阵第33页/共131页2023/4/24:013411.5.5生成矩阵在上例中，根据监督方程，监督位的产生可表示为可用矩阵表示为一般式即其中，11.5线性分组码第34页/共131页2023/4/24:0135其转置形式：式中例定义为生成矩阵。

其中Ik是k×k的单位阵，k为信息位数。发送码组可按下式产生：直接得到整个码组，而不是只有监督位！11.5线性分组码第35页/共131页2023/4/24:0136如，在上例中可得生成矩阵发送码组可按下式产生：11.5线性分组码三个关系第36页/共131页2023/4/24:013711.5.6

校正[S]与[H]及误码码组[E]的关系

11.5线性分组码设发送码组为[A]，接收码组为[B]误码码组为：[E]=[B]-[A]=[en-1en-2……e1e0]在接收端计算校正子为矩阵E常称为错误样图。（实际中只知道B而并不知道A和E）[S]=[B]HT={[A]+[E]}HT

＝[A]HT+[E]HT

=0+[E]HT=[E]HT可见，[S]仅与[E]和HT有关，[S]与[E]之间存在确定关系，所以只需计算[S]，就可得到[E]，从而实现检错纠错。H与G关系第37页/共131页2023/4/24:0138可见，监督矩阵和生成矩阵存在对应关系，线性码既可以由G确定，也可以直接由H生成。使用场合11.5.7H和G矩阵对应关系第38页/共131页2023/4/24:0139通常，编码时使用生成矩阵，译码时使用监督矩阵。[S]=[B]HT=[E]HT例E、S、监督方程、P、H、G六者之间是相互关联，一一对应的。一个改变必然导致其它5者的相应变化。第39页/共131页2023/4/24:0140【例1】给定一个（7，4）线性分组码的生成矩阵若信息码为d=1101，求该信息码的线性分组编码。解：

采用生成矩阵进行编码11.5.8应用举例第40页/共131页2023/4/24:0141例2所以，该信息码的线性分组编码为：1101000第41页/共131页2023/4/24:0142【例2】已知线性（6，3）码的生成矩阵为求线性分组码、各码组的码重、最小码距和该码的差错控制能力。解：

因为k=3，所以信息码码组组成的矩阵为（3×8阶）矩阵D：第42页/共131页2023/4/24:0143续

则由第43页/共131页2023/4/24:0144可得出分组码码组矩阵为码重第44页/共131页2023/4/24:0145可见非零码组的最小码重为3，则分组码的最小码距dmin=3；因此，该分组码能够检2位错；或同时纠1位错，检1位错。例三第45页/共131页2023/4/24:0146

【例3】已知一线性(7，4)码的生成矩阵为求当接收端收到码组R=［1010110］时，所对应的信息码组D。分析：首先，需要由G推导出[H]；然后，通过[H]计算S；再，判断纠错。解第46页/共131页2023/4/24:0147解：根据前面H与G的关系可得将接收码组R=［1010110］代入，可得S第47页/共131页2023/4/24:0148第7位出错。所以，接收端收到码组R=1010110］时，所对应的信息码组D=0010。汉明码？E、S、监督方程、P、H、G六者之间是相互关联，一一对应的。一个改变必然导致其它5者相应变化。本题S=111对应的是a4出错。所以信息码应为1000。请大家验证一下！第48页/共131页2023/4/24:0149S1S2

S3错码位置S1S2

S3错码位置001a0111a4010a1011a5100a2110a6101a3000无错码监督矩阵错误图样监督方程本题S=111对应的是a4出错。所以信息码应为1000。第49页/共131页2023/4/24:015011.5.9汉明码11.5线性分组码第四讲具有下列特点的线性分组码称之为汉明码：码长：n＝2r－1，信息位k＝2r-r-1，监督位：r＝n-k记为：（n，k）＝（2r－1，2r－1－r）最小码距

dmin＝3，纠错能力t＝1汉明码的编码效率：监督矩阵第50页/共131页2023/4/24:0151汉明码的监督矩阵有n列r行，它的n列是除全零以外的r位码组构成，且每一码组只在某列中出现一次。以r=3为例，可构造如下监督矩阵其编译码可直接根据H、G使用数字电路实现。其中，译码方法采用计算校正子，然后确定错误图样并加以纠正。编码器第51页/共131页2023/4/24:0152编码器译码器编码器方法1：方法2：第52页/共131页2023/4/24:0153[S]=[B]HT=[E]HT译码器扩展汉明码译码器方法1：方法2：第53页/共131页2023/4/24:0154*11.5.10扩展汉明码11.5线性分组码

在汉明码中增加一位校验码（n，k）（n＋1，k），对所有的位作偶监督。例：设原汉明码（7，4）：

a7a6a5a4a3a2a1a7a6a5a4a3a2a1a0

信息位监督位信息位原监督位偶校验位

监督矩阵：HHe特点第54页/共131页2023/4/24:0155扩展汉明码特点：

11.5线性分组码校正子[S’]的确定方法与原汉明码校正子[S]的确定方法基本相同。只是新增了一个校正子最小码距：

在纠正1位误码的同时可以检测两为误码。在某些情况下也可以将，汉明码的码长和信息位缩短，得到缩短汉明码。如（5，2）交织码第55页/共131页2023/4/24:0156*11.5.11交织码

目的：减小信道中错误的相关性，将长突发错误离散成短突发错误或随机错误。措施：将m个（n,k）分组码码组按行排列成一个m×n的码阵，从而得到一个（mn，mk）交织码，并规定以列的顺序自左至右传送。性能：如果（n,k）可纠正t个误码，则（mn,mk）可纠正不大于mt的单个突发错误，或纠正t个长度不大于m的突发错误。循环码第56页/共131页2023/4/24:015711.6.1循环码的基本概念（1）定义

对线性分组码T，如对任意Ti

T，Ti

循环左移或循环右移任意位后得到的码组Ti’仍然有Ti’T，则称T为循环码。（2）码多项式

为用代数理论研究循环码，可将码组用多项式表示，该多项式称为码多项式。

一般地，长为n的码组an-1an-2…a1a0，对应码多项式T(x)11.6循环码式中，xi的系数对应码字中ai的取值。例：（7,3）的一个码字：1001110对应x6＋x3＋x2＋x码多项式的按模运算第57页/共131页2023/4/24:0158所有，在模运算下，一整数m按模n运算等于其被n除所得之数余数。（3）码多项式的按模运算在整数除法中，可进行按n运算，若（Q为整数，p<n）（模n）码多项式的除法第58页/共131页2023/4/24:0159类似地，可以定义关于多项式N(x)的除法运算，若式中Q(x)为整式，余式R(x)的幂<N(x)的幂。上式可写成：记为：此时，码多项式系数仍按模2运算，即只取0和1值。例：有例2第59页/共131页2023/4/24:0160再如由于在模2运算中，用加法代替了减法，故余项定理1第60页/共131页2023/4/24:0161

证明：设，(1)i＝1时，有

定理1

若T(x)是长度为n的循环码中的一个码多项式，则xiT(x)按模xn＋1运算的余式T’(x)必为循环码中的另一码多项式。P343

可见余式是由码组an-1an-2…a1a0左循环一位之后的得到的码组：an-2…a1a0an-1第61页/共131页2023/4/24:0162（接定理1证明），若i＝2显然，余式为对应码组an-1an-2…a1a0左循环两位之后的得到的码组。

一般地，对任意i有：余式an-i-1an-i-2…a1a0an-1an-2…an-i+1an-i对应an-1an-2…a1a0左循环i位之后的得到的码组。

证毕循环码生成多项式第62页/共131页2023/4/24:016311.6.2循环码的生成多项式g(x)及生成矩阵

定理2循环码中，n－k次码多项式g(x)有且只有一个。g(x)称为循环码码生成多项式。

P343证明：（1）在含K个信息位的循环码中，除全0码外，其它码组最多只有k-1个连0。否则，经循环移位后前面k个信息码元全为0，而监督码元不全为0的码组，这在线性分组码中是不可能的。（2）n－k次的码多项式g(x)的常数项不能为0，否则该多项式右移一位就会出现k个连0的情况。(因该码组前k-1位为0)（3）n－k次的码多项式g(x)只可能有一个，若有两个，两多项式相加后由线性分组码的封闭性仍为码多项式，但由于n－k次项和常数项相消，会产生k＋1连0的情况，由（1）分析，这是不可能的。综上（1）、（2）和（3），证毕。循环码生成矩阵第63页/共131页2023/4/24:0164循环码生成矩阵G(x)例任一码多项式都可由其信息码元和生成矩阵G[x]确定：第64页/共131页2023/4/24:0165例如表11-5的(7,3)循环码，n=7,k=3,r=4,唯一的一个(n–k)=4次码多项式代表的码组是第二码组0010111，与它相对应的码多项式，即生成多项式定理3其生成矩阵分别为第65页/共131页2023/4/24:016611.6.2

循环码的生成多项式g(x)及生成矩阵(续)

g(x)为码多项式A(x)的一个因式，所以T(x)可被g(x)整除。证毕循环码生成多项式（续）定理4推论：次数不大于k－1次的任何多项式与g(x)的乘积都是码多项式。定理3在循环码中，所有的码多项式T(x)都能够被g(x)整除。

P344式11.6-18

证明：因为任一码多项式都可由其信息码元和生成矩阵G[x]确定：第66页/共131页2023/4/24:016711.6.2循环码的生成多项式g(x)及生成矩阵(续)

定理4循环码（n，k）的生成多项式g(x)是xn＋1的一个因式。其中R(x)的幂小于n。由定理1，R(x)是码多项式，又由定理3，有R(x)=h(x)g(x)，即有移项整理得：即g(x)是xn＋1的一个因式。证毕总结证明：因为g(x)幂为n－k，因而可得∵定理1若T(x)是长度为n的循环码中的一个码多项式，则xiT(x)按模xn＋1运算的余式T(i)(x)必为循环码中的另一码多项式。∵定理3在循环码中，所有的码多项式T(x)都能够被g(x)整除。第67页/共131页2023/4/24:016811.6.2循环码的生成多项式g(x)及生成矩阵(续)

总结：监督多项式定理1

若T(x)是长度为n的循环码的一个码多项式，则xiT(x)按模xn＋1运算的余式T(i)(x)必为循环码中的另一码多项式。定理2循环码中，n－k次码多项式g(x)有且只有一个。g(x)称为循环码码生成多项式。定理3在循环码中，所有的码多项式T(x)都能够被g(x)整除。推论：不大于k－1次的任何多项式与g(x)的乘积都是码多项式。定理4循环码（n，k）的生成多项式g(x)是xn＋1的一个因式。生成多项式g(x)的三个性质（充要条件）：

（1）g(x)是n－k次多项式；

（2）g(x)的常数项不等于0；

（3）是xn＋1的一个因式。第68页/共131页2023/4/24:0169

则，对任一码多项式，T(x)＝I(x)g(x)，有

h(x)T(x)=h(x)[I(x)g(x)]=[h(x)g(x)]I(x)=(xn+1)I(x)

即若T(x)是许用码组对应的多项式，其与h(x)的乘积h(x)T(x)一定可被xn＋1整除。称h(x)为循环码的一致校验多项式，即监督多项式。h(x)是常数项为1的k次多项式由定理4”循环码（n,k）的生成多项式g(x)是xn＋1的一个因式“可知*11.6.3监督多项式监督矩阵编译码第69页/共131页2023/4/24:0170根据监督多项式，可得监督矩阵H

其中h*(x)是h(x)的逆多项式。

例*11.6.3监督多项式及监督矩阵第70页/共131页2023/4/24:0171例如(7，3)循环码，g(x)=x4+x3+x2+1，则循环码的编译码第71页/共131页2023/4/24:017211.6.4循环码的编码和译码1.采用循环码生成矩阵：例：若生成多项式g(x)＝x4+x3+x2+1，k=3，则其生成矩阵为：实际的编码方法对应的矩阵G一般不符合[Ik,Q]的形式。编码输出结果相当于m(x)g(x)为非系统码结构。信息码和监督码不容易区分。设数据101,则输出为第72页/共131页2023/4/24:0173

2.系统结构循环码的编码方法11.6.4

循环码的编码和译码（续）（1）以xn-k乘信息多项式m(x)，得到xn-km(x)；（幂<n）

（2）用g(x)除xn-km(x)得余式r(x)(幂<n-k)即

xn-km(x)＝Q(x)g(x)+r(x)（3）编码输出的码多项式

T(x)=xn-km(x)+r(x)（*）

上述编码方式的合理性：

T(x)=xn-km(x)+r(x)＝[Q(x)g(x)+r(x)]+r(x)=Q(x)g(x)

因为Q(x)的幂次数小于k，所以Q(x)g(x)一定是循环码的码多项式，显然（*）定义的T(x)为一种系统码结构的循环码。编译码器第73页/共131页2023/4/24:0174*3.循环码编码器的电路实现

8.3.4循环码的编码和译码（续）除法运算的实现过程：先将移位寄存器清“0”；进行n次移位，将被除数全部送入除法器后，在寄存器内，即可得到相应的余式。例：除数为g(x)＝x6＋x5＋x4＋x3＋1除法电路，(即r=6)

如下图，反馈的接入由g(x)确定x6x5x4＋＋＋DDDDD＋Dx31例（a）多项式除法多项式除法可用带反馈的移位寄存器实现。第74页/共131页2023/4/24:0175（接上例）计算m(x)/g(x)，设m(x)=x13+x11+x10+x7+x4+x3+x+1,即k=14010110010011011000000100000010000101000110100011010001101000001100111110100111010111101111001011011001010余数000000111001110x6x5x4＋＋＋DDDDD＋Dx3100000001000001001000000101000101101001001101000001101010000011110011101110100001110101011110111111001010110111100101010除法运算在移位进行了r-1位后才开始，运算完成后，要将余式移出，还要做r-1次移位。速度较慢。实际电路第75页/共131页2023/4/24:0176（b）实际应用的循环码编码电路

特点：采用“预先乘xn-k方案”（信号直接到达最后一级），边移位边做除法运算，当k个信息码输入后，同时也完成了除法运算。（1）当信息位输入时，开关K1、K2合向下，k个信息位经K2逐位输出，同时直接送到最高位做除法运算：（2）当信息位全部输入后，相应除法运算完成，开关K1、K2合向上，将余数顺序输出。DD＋D＋D＋x4x31x2K1K2输入输出除法原理例第76页/共131页2023/4/24:0177例：设m(x)=x2＋x＋1111，xn-k＝x7－3＝x4，xn-km(x)＝1110000，上述运算也可看作下列分别运算的结果：商为：110⊕11⊕1100余数：1110⊕0111⊕11010100商为：100，余数为：0100译码过程第77页/共131页2023/4/24:01784.循环码的译码过程

用生成多项式g(x)除接收码多项式R(x)，得到余式r(x);通过余式r(x)，计算校正子多项式S(x)；由S(x)确定误码的错误图样E(x)；将E(x)与R(x)相加，纠正错误（若在纠错范围内）。

纠错译码原理第78页/共131页2023/4/24:0179（1）纠错译码原理

a.计算S(x)＝R(x)/g(x)b.确定错误图样S(x)E(x)c.根据E(x)纠错。123n-k......校正子计算电路:S(x)错误图样识别：E(x)缓冲移位寄存器＋R(x)C(x)例：纠正单个错误的电路完成除法运算第79页/共131页2023/4/24:0180*（2）纠正单个错误的译码电路根据上节讨论，当用于纠正单个错误时，只需要记住一个错误图样。E(x)识别电路可用简单的逻辑电路来实现。例：g(x)＝x4＋x2＋x＋1ab＋c＋dx4x31x2输入输出＋与门DDDDDDD＋设接收码组为:1000101余数dcba:0100一码组输入完成后，输入k个“0”，进行信码输出和纠错。本例，当输入第1个0时，输出第一位信码，并使dcba=1000，进而使与门输出1，输入第二个0时，完成错误纠正，输出1100101。循环码检错能力E(x)识别电路第80页/共131页2023/4/24:018111.6.5循环码的检错能力能检出全部的奇数个错码；能检测所有与准用码距小于dmin的错误；能检出所有长度L<n-k+1的突发错误在突发长度L大于(n-k)的错误中，若L=n-k+1，则(n，k)循环码不能检测的概率为2-(n-k-1)；若L>n-k+1，则不能检测的概率为2-(n-k）。BCH码第81页/共131页2023/4/24:0182截短目的：在设计纠错编码方案时，常常信息位数k、码长n和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的循环码存在。这时，可以采用将码长截短的方法，得出满足要求的编码。截短方法：设给定一个(n,k)循环码，它共有2k种码组，现使其前i(0<i<k)个信息位全为“0”，变成仅有2k-i种码组。然后删去这i位全“0”的信息位，得到一个(n–i,k–i)的线性码。将这种码称为截短循环码。截短循环码性能：循环码截短前后至少具有相同的纠错能力，并且编解码方法仍和截短前的方法一样。

例：要求构造一个能够纠正1位错码的(13,9)码。这时可以由(15,11)循环码的11种码组中选出前两信息位均为“0”的码组，构成一个新的码组集合。于是发送码组成为(13,9)截短循环码。

11.6.6截短循环码第82页/共131页2023/4/24:018311.6.7BCH码发现者：Hocguenghem，Bose和Chaudhuri特点：能纠正多个随机错误，并有严密的数学结构循环码中一类重要子码：g(x)与dmin关系密切BCH码的码长n与监督位r、纠错能力t间关系：

对于任一正整数m和t(t<m/2)，必定存在一个码长n=2m-1，监督位r=n-k≤mt，能纠正所有不大于t个随机错误的BCH码分两类：本原BCH码：g(x)中含有最高次数为m的本原多项式，且码长n=2m-1非本原BCH码：

g(x)中不含上述本原多项式，且码长n是2m-1的一个因子BCH码及对应的生成多项式见P348，表11-6本原多项式第83页/共131页2023/4/24:0184例如m=3时，本原多项式（次数为m)：（1）是既约的；（2）可以整除（3）不能整除则称该多项式为最高次数为m的本原多项式。此时最高次数为3的本原多项式有两个：(x3+x2+1)和(x3+x+1)，它们都能除得尽x7-+1，但除不尽x6+1和x5+1。

BCH码的构造见书p348RS码第84页/共131页2023/4/24:018511.6.8RS码多进制BCH码(m=2q进制)；具有很强的纠错能力，特别适合于纠正突发错误；纠t个符号错误的(n,k)RS码：码长：n=m-1=2q-1个符号bit信息码元数:k个符号监督码元数：n-k=2t个符号最小码距：d0=2t+1个符号卷积码若将每个m进制码元表示成相应的q位二进制码元，则得到的二进制码的参数为：码长：n=q(2q–1)（二进制码元）监督码：r=2qt（二进制码元）第85页/共131页2023/4/24:018611.7卷积码几点说明：又名连环码，是一种非分组码与分组码相比，在同等码率和相似的纠错能力下，卷积码的实现往往更简单卷积码主要应用于FEC数据通信系统中11.7.1基本原理：在任何一段规定时间里编码器产生的n个码元，不仅取决于这段时间中的k个信息码元,而且还取决于前（N-1）段规定时间内的信息码元，编码过程中相互关联的码元为Nn个。N称为编码约束度，N段时间内的码元数目Nn称为卷积码的编码约束长度。记作(n，k，N)，编码效率R=k/n。例第86页/共131页2023/4/24:01871.一种简单的（2,1,2）卷积码编码器编码器：译码编码过程：输入一位信息，电子开关倒换2次，即前半拍（半个输入码元宽）接通b端，后半拍接通c端(监督位)。监督位ci除与本组信息码元bi有关外，还跟上一组信息码元bi-1有关。并且此监督位紧跟此信息位之后发送出去。D+bcbici输出信息码输入bi简单(2,1,2)卷积码编码器bi-1监督位编码公式：ci=bi+bi-1

tb1b2b3b4b1c1b2c2b3c3b4c4输入t输出第87页/共131页2023/4/24:0188解码器工作过程解码器输入端的电子开关按节拍把信息码元与监督码元分接到b'端与c'端；2个移位寄存器的节拍比码序列节拍低一倍，其中移位寄存器D1，D2在信息码元到达时移位，监督码元到达期间保持原状；而移位寄存器D3在监督码元到达时移位，信息码元到达期间保持原状；移位寄存器D1、D2和模2加法器1构成与发端一样的编码器，它从接收到的信息序列中计算出对应的监督序列来；模2加法器2把计算出的监督序列与接收到的监督序列进行比较：两者相同，输出“0”；两者不同，输出“1”，显然此时，必定出现了差错。如果有差错，则通过大数逻辑判决门确定差错位置并纠错。判决准则2.简单(2,1,2)卷积码的译码简单(2,1,2)卷积码译码器1D2信息码输出卷积码输入D3Sib'3c'2D1大数判决“1”的个数>1？Si-1第88页/共131页2023/4/24:0189具体判决如下：根据译码图，校正子S的方程（即解码方程）如下：可见每个信息码元出现在两个S方程中，即bi'与Si-1和Si有关，在判决bi'是否有错时，应根据Si-1和Si的值。决定Si-1和Si值的共有5个码元，但其中只有bi'与Si-1、Si两值都有关，而其他码元只与一个值有关。判决准则第89页/共131页2023/4/24:0190在差错不多于1个时，根据正交性得判决规则如下：①当Si-1、Si都为“0”时，解码方程与编码方程一致，判决无错；②当Si-1、Si都为“1”时，必定是bi'有错，给予纠正；③当Si-1、Si中只有一个“1”时，必定是bi'以外四个码元：bi-1'、bi+1'、ci'及ci+1'中的一个出错，判决bi'无错；完成上述判决规则的电路是译码器中的移位寄存器D3，与门及模2加法器3：从该例可以看到：该码可以纠正连续3个码组中的一位差错。卷积码的几何描述第90页/共131页2023/4/24:019111.7.2卷积码的几何描述

编码过程diciei

(3,1,3)卷积码编码器bi-2bi输入bibi-1编码输出M2M3M1设输入信息比特序列是bi-2

bi-1

bibi+1，则当输入bi时，此编码器输出3比特cidiei，输入和输出的关系为：第91页/共131页2023/4/24:0192起始状态，各级移位寄存器清零，即M1M2M3为000。M1等于当前输入数据(bi)，而移位寄存器状态M2M3存储以前的数据(bi-1bi-2)，输出码字由下式确定(3,1,3)编码器的工作过程(状态)变化如下表状态图原状态(M3M2)a(00)b(01)c(10)d(11)输入(M1)01010101监督位输出(diei)0011011011001001新状态(M3M2)a(00)b(01)c(10)d(11)a(00)b(01)c(10)d(11)dicieibi-2bi输入bibi-1编码输出M2M3M1第92页/共131页2023/4/24:01931.状态图

(3,1,3)码的状态图上表也可以用状态转移图表示，如下图(a)所示。如果把相同的当前状态和其下一状态重叠起来，就可以得到如图(b)所示的状态图。cbad110010011111100001000101(b)其中实线代表输入”0”，虚线代表输入“1”。树图当前状态下一状态abcdabcd00011101110001110010101(a)输出第93页/共131页2023/4/24:0194100110001cdc100011abd101010cd001110a111000abb110001cdc100011ab011上半部下半部2.树图a111000abb000a111ba000111d101010cd010c101db001110a(00)111000输入信息码起点01寄存器状态a=M3M2＝00b=M3M2＝01c=M3M2＝10d=M3M2＝11输入1101时，编码输出为：111110010100输出diei网格图第94页/共131页2023/4/24:0195由节点和支路组成：节点表示4种状态；支路代表状态间的转移关系(实线代表输入”0”，虚线代表输入“1”)；支路上的数字代表当前输出的监督位。3.网格图

利用树状图中的重复性，将其中具有相同状态的节点合并到一起，即可得到另一种表示方式：网格图。起点利用本图也可以方便得到任意输入序列的输出序列和状态转移路径。例：输入110111在网格图中每一条路径就意味着可能发送的某一个序列组合。概率译码输出：111110010100110101a000aaaaaabbbccccbbcbddddd000000000000000100100100100110110110010010010010101101101101111111111111111111001001001001110110001011011011011第95页/共131页2023/4/24:019611.7.3卷积码的概率译码（维特比解码）

有两种译码方法：一是大数逻辑译码，又称门限译码。即，从线性码的伴随式出发，找到一组特殊的能够检查信息位置是否发生错误的方程组，从而实现纠错译码。如11.7.1之2。二是概率译码。建立在最大似然准则基础上，其基本思想是：比较接收序列与所有可能的发送序列，从中选择与接收序列汉明距最小的发送序列作为译码输出。又分为：维持比特译码和序列译码两种。

门限译码是以分组码理论为基础的，其译码设备简单，速度快，但其误码性能比概率译码差。概率译码例第96页/共131页2023/4/24:0197cbad1010111100010001设编码输入序列为：1101000则编码器输出为：111110010100001011000设接收序列为：

111010010110001011000下面讨论其译码方法和过程：例实线代表输入”0”，虚线代表输入“1”。第97页/共131页2023/4/24:0198由于该卷积码的约束长度=N*n=3*3=9，因此一般先取接收序列的前9位序列（111010010），同时到达第三时刻(节点)的所有可能的8个序列进行比较，并保留到达各节点路径中，与接收序列码距最小的路径，共4条。以此类推可以得到第4、5、6、7时刻的幸存路径。到最后第7时刻幸存的路径即为译码输出。1234567a00起点aaaaaabbbccccbbcbddddd000000000000000000011010101010101001010101111111111111010101011010abc01111111111100111010第一步00d01第98页/共131页2023/4/24:0199a00起点aaacbbcbdd000000011010100111111101123a:000000000

111001011b:000000111

111001100c:000111001

111110010d:000111110

11111010111d053647164设接收序列：111010010110001011000保留到达各节点路径中，与接收序列码距最小的路径，共4条：即111010010第99页/共131页2023/4/24:01100a起点aaacbbcbdd00011010011112311设接收序列：111010010110001011000保留到达各节点路径中，与接收序列码距最小的路径，共4条。考查第4时刻1-3d0a1110010113b1110011004c1111100101d1111101014第100页/共131页2023/4/24:01101a起点aaacbbcbdd000110100111123411设接收序列：111010010110001011000保留到达各节点路径中，与接收序列码距最小的路径，共4条：即abcd00001010011101111-34d0a11100101100051111100100113b11100101111141111100101002c11100110000171111101010105d11100110011041111101011016第101页/共131页2023/4/24:01102a起点aaacbbcbdd0001101001111234设接收序列：111010010110001011000保留到达各节点路径中，与接收序列码距最小的路径，共4条。以此类推abcd001010111-34d0a1111100100113b1111100101002c1111101010105d1110011001104第102页/共131页2023/4/24:01103按照上述算法继续解码。这样得到的幸存路径网格图示于下图中。译码输出序列：1101000幸存路径d0a1111100101000010110000b1111100101000010111113c1111100100110001110016d111110010011000111110710111001abcdabcd0011000011111234567110110第103页/共131页2023/4/24:01104 在上例中卷积码的约束度N=3，需要存储和计算8条路径的参量。由此可见