版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
第7章纠错编码7.1差错控制方式7.2纠错编码的基本原理7.3常用的简单编码7.4线差错控制方式
图7.1差错控制方式的系统构成(a)检错重发；(b)前向纠错；(c)混合纠错7.1.1检错重发在检错重发方式中，发送端经编码后发出能够发现错误的码，接收端收到后经检验如果发现传输中有错误，则通过反向信道把这一判断结果反馈给发送端，然后，发送端把前面发出的信息重新传送一次，直到接收端认为已正确地收到信息为止。常用的检错重发系统有三种，即停发等候重发、返回重发和选择重发。图7.2中画出了这三种系统的工作原理图。
图7.2ARQ差错控制系统工作原理(a)停发等候重发；(b)返回重发；(c)选择重发
图7.2（a）表示停发等候重发系统的发送端、接收端的信号传递过程。发送端在TW时间内送出一个码组给接收端，接收端收到后经检测若未发现错误，则发回一个认可信号（ACK）给发送端，发送端收到ACK信号后再发出下一个码组。返回重发系统如图7.2（b）所示。7.1.2前向纠错在前向纠错系统中，发送端经编码发出能够纠正错误的码，接收端收到这些码组后，通过译码能自动发现并纠正传输中的错误。前向纠错方式不需要反馈信道，特别适合于只能提供单向信道的场合。由于该系统能自动纠错，不要求检错重发，因而具有延时小，实时性好等特点。7.1.3混合纠错混合纠错方式是前向纠错方式和检错重发方式的结合。在这种系统中，发送端不但有纠正错误的能力，而且对超出纠错能力的错误有检测能力。遇到后一种情况时，通过反馈信道要求发送端重发一遍。混合纠错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷。7.2纠错编码的基本原理
现在我们来讨论纠错编码的基本原理。为了便于理解，先通过一个例子来说明。一个由三位二进制数字构成的码组，共有八种不同的可能组合。若将其全部利用来表示天气，则可以表示八种不同的天气，譬如：000（晴），001（云），010（雨），011（阴），100（雪），101（霜），110（雾），111（雹）。其中，任意码组在传输中若发生1个或多个错码，则该码组将变成另一信息码组。这时接收端将无法发现错误。若在上述八种码组中只准许使用四种来传送信息，譬如：
分组码一般用符号（n，k）表示，其中k是每组二进制信息码元的数目，n是编码组的总位数，又称为码组长度（码长），n-k=r为每个码组中的监督码元数目或称监督位数目。通常，将分组码规定为具有如图7.3所示的结构。图中前面k位（an-1
…a0）。在式（7.1）的分组码中，n=3，k=2，r=1。表7.1图7.3分组码的结构
在分组码中，我们把“1”的数目称为码组的重量，而把两个码组对应位上数字不同的位数称为码组的距离，简称码距，又称汉明（Hamming）距离。式（7.1）中四个码组之间任何两个的距离均为2。我们把某种编码中各个码组间距离的最小值称为最小码距（d0），例如，按式（7.1）编码的最小码距d0=2。图7.4码距的几何意义
一种编码的最小码距d0的大小直接关系到这种编码的检错和纠错能力。下面我们将具体对此加以说明。
位差错的能力。因为当编码之间最小码距为d0,比错码位数大于1时,只要编码中出现的错码位数不超过e,则都不可能变成另一个允许使用的编码,因此接收端能发现这样的差错(2)若编码组中编码之间最小码距满足:
位码后形成的编码之间还有至少1位的码距,则这两个编码就不会被混淆,就可纠正为原来的正确编码;否则就可能被错误地纠正为另一个允许使用的编码,而使差错更大。(3）为纠正t个错码，同时检测e个错码，要求最小码距为
位差错的能力。需要注意的是:若接收到的编码与某一允许使用的编码之间的距离在纠错范围t
位内,则对其进行纠错;若接收到的编码与某一允许的编码之间的距离超过t,则只能对其进行检错,检错能力范围为e
。当某一允许使用的编码出现e位差错后与另一个允许使用的编码间距离至少为t-1,否则会进入另一个允许使用的编码的纠错范围而被错纠为另一编码。
假设在随机信道中发送“0”时的错误概率和发送“1”时的相等，都等于p，且p1,容易证明，在码长为n的码组中恰好发生r个错码的概率为
（7.5）可见,采用差错控制编码,即使仅能纠正(或检测)这种码组中1~2个错误,也可以使误码率下降几个数量级。这就表明,即使是较简单的差错控制编码也具有较大的使用价值。7.3常用的简单编码7.3.1奇偶监督码奇偶监督码是一种最简单的检错码，又称奇偶校验码，在计算机数据传输中得到了广泛的应用。在ISO和CCITT提出的七单位国际5层字母表、美国信息交换码ASCII字母表及我国的七单位字符编码标准中都采用7比特码组表示128种字符，如字符A的编码表示为1000001（在第8章将较详细地介绍）。
一般情况下奇偶监督码的编码规则是：首先将要传输的信息分成组，然后将各位二元信息及附加监督位用模2和相加，选择正确的监督位，保证模2和的结果为0（偶校验）或1（奇校验）。这种监督关系可以用公式表示。设码组长度为n，表示为（an-1an-2
…a0），其中前n-1位为信息，第n位为校验位，则偶校验时有监督码元a0即为(7.6a)（7.6b）奇校验时有（7.6c）（7.6d）监督码元a0为7.3.2水平奇偶监督码针对上述奇偶监督码检错能力不高，特别是不能检测突发错误的缺点，可以将经过奇偶监督编码的码元序列按行排列成方阵，每行为一组奇偶监督码（如表7.2所示），但发送时则按列的顺序传输：…1001011，接收端仍然将码元排成发送时的方阵形式，然后按行进行奇偶校验。由于按横行进行奇偶校验，因此称其为水平奇偶监督码或行奇偶监督码。表7.2水平奇偶监督码7.3.4群计数码在群计数码中，信息码元分组后计算其“1”的个数，然后将这个数目的二进制表示作为监督码元附加在信息码元之后送往信道。例如一组信息码元为11100101，其中有5个“1”，用二进制数字表示为“101”，传输的码组即为。这种码的检错能力很强，除了发生1变0和0变1成对的错误之外，它能检测出所有形式的错误。7.4线线性分组码的概念前面介绍的奇偶监督码其编码原理利用了代数关系式，我们把这类建立在代数基础上的编码称为代数码。在代数码中，常见的是线性码。线性码中的信息位和监督位是由一些线性代数方程联系着的，或者说，线性码是按一组线性方程构成的。这里将以汉明码为例引入线性分组码的一般原理。
按式（7.6a）条件构成的偶数监督码由于使用了1位监督位a0，因此它就能和信息位an-1
…a1一起构成一个代数式，如式（7.6a）所示。在接收端解码时，实际上就是计算（7.7）
一般说来，若码长为n，信息位数为k，则监督位数r=n-k。如果希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求
由表中规定可见，仅当1个错码位置在a2、a4、a5或a6时，校正子S1为1；否则S1为0。这就意味着a2、a4、a5和a6
（7.11）在发端编码时，信息位a6、a5、a4和a3的值决定于输入信号，因此它们是随机的。监督位a2、a1和a0应根据信息位的取值按监督关系来确定，监督位应使上式中S1、S2和S3的值为零（表示编成的码组中应无错码），即a6⊕a5⊕a4⊕a2=0a6⊕a5⊕a3⊕a1=0a6⊕a4⊕a3⊕a0=0(7.12)由上式经移项运算，解出监督位为
接收端收到每个码组后，先按式（7.9）~式（7.11）计算出S1、S2和S3，再按表7.3判断错误情况。例如，若接收码组为0000011，则按式（7.9）～式（7.11）计算可得S1=0，S2=1
，S3=1。由于S1S2S3等于011，故根据表7.3可知在a3位有一错码。7.4.2线性分组码的矩阵描述现在我们再来讨论线性分组码的一般原理。上面已经提到，线性码是指信息位和监督位满足一组线）就是这样一组线性方程的例子。现在将它改写成1·a6＋1·a5＋1·a4＋0·a3＋1·a2＋0·a1＋0·a0=01·a6＋1·a5＋0·a4＋1·a3＋0·a2＋1·a1＋0·a0=01·a6＋0·a5＋1·a4＋1·a3＋0·a2＋0·a1＋1·a0=0(7.14)
上式中将“⊕”简写为“+”。在本章后面，除非另加说明，这类式中的“+”都指模2加。式（7.14）又可以表示成(模2)（7.15）上式还可以简记为
类似于式（7.12）改变成式（7.15）中矩阵形式那样，式（7.13）也可以改写成以下形式：（7.18）或者（7.19）
式中，G称为生成矩阵，因为由它可以产生整个码组，即有［a6a5a4a3a2a1a0］=［a6a5a4a3］·G
（7.23）与H矩阵相似,我们也要求G矩阵的各行是线)可以看出,任意码组A都是G的各行的线性组合。G
个线性无关的码组,则可以用其作为生成矩阵G,并由它生成其余的码组。7.4.3线性分组码的纠错和检错一般来说，式（7.23）中A为一n列的行矩阵。此矩阵的n个元素就是码组中的n个码元，所以发送的码组就是A。此码组在传输中可能由于干扰而引入差错，故接收码组与A不一定相同。若设接收码组为一n列的行矩阵
=0，则表示该位接收码元无错；若en=1，则表示该位接收码元有错。式（7.25）
B代入式（7.16）不一定成立。在错码较多，已超过这种编码的检错能力时，
B变为另一许用码组，则式（7.28）仍能成立。这样的错码是不可检测的。在未超过检错能力时，式(7.28)不成立，即其右端不等于零。假设这时式（7.28）的右端为S，即
卷积码编码器的一般形式如图7.5所示，它包括：一个由N段组成的输入移位寄存器，每段有k级，共nN位寄存器；一组n个模2和相加器；一个由n级组成的输出移位寄存器。图7.5卷积码编码器的一般形式
描述卷积码的方法有两类：图解表示和解析表示。这里我们以图7.6所示的（2，1，3）卷积码为例介绍图解法。图7.6(2，1，3)卷积码编码器7.5.2卷积码的图解表示由图7.6可得
现若按（2，1，3）卷积码编码器进行编码，当M=［11010］时，由式（7.31）可知：
X={0}1.树状图如图7.6所示，在（2,1,3）卷积码编码器中，输出移位寄存器用转换开关代替，每输入一个信息比特，经编码产生2个输出比特。假设移位寄存器的起始状态为全0，则当第一个输入比特为0时，输出比特为00；当第一个输入比特为1时，输出比特为11。随着第二个比特的输入，第一个比特右移1位，此时输出比特同时受当前输入比特和前一个输入比特的影响。第三个比特输入时，第一、二个比特分别右移1位，同时输出两个由这3位移位寄存器存储内容所共同决定的比特。图7.7（2,1,3）卷积码的树状图表示
X=［0］卷积码编码器输出的码对应码树中的每个分支的上支，用图7.7中上支所示的虚线］
终点a卷积码编码结果X就是把路径按先后次序写出，即得X=［100］2.网格图按照码树中观察到的重复性，得到一种更为紧凑的图形表示，即网格图，如图7.9所示。
在网格图中，把码树中具有相同状态的节点合并在一起。码树中的上支路（对应于输入比特0）用实线表示，下支路(对应于输入比特1)用虚线表示。网格图中支路上标注的码元为输出比特，自上而下四行节点分别表示a、b、c、d四种状态。一般情况下应有2N-1
种状态，从第N节（从左向右计数）开始，网格图的图形开始重复。3.状态图取出已达到稳定状态的一节网格，便得到图7.9（a）所示的状态图。再把目前状态与下行状态重叠起来，即可得到图7.9（b）所示的反映状态转移图。图中两个自闭合圆环分别表示a-a和d-d状态转移。当给定输入信息序列和起始状态时，可以用上述三种图解表示法的任何一种，找到输出序列和状态变化路径。图7.9（2,1,3）卷积码的状态图
设M=［1］，试分别用码树图、理论公式直接计算和码状态图三种方法进行卷积编码，再对结果进行比较。
图7.7所示的卷积码编码器若起始状态为a，输入序列为0，求输出序列和状态变化路径。
由卷积码的网格图表示，找出编码时网格图中的路径，如图7.11所示，由此可得到输出序列和状态变化路径，示于同一图中。图7.11(2,1,3)卷积码的编码过程及路径7.5.3卷积码的维特比译码方法
卷积码的译码方式有三种：维特比译码、序列译码和门限译码。其中维特比译码和序列译码都是以最大似然译码的原理为基础的，由于篇幅的限制，这里只初步介绍一下维特比译码的原理和方法。1.最大似然译码原理在一个卷积码编/译码系统中，输入信息序列M被编码为序列X，此X序列可以用树状或网格图中某一特定的路径来表示，假设X序列经过有噪声的无记忆信道传送给译码器，如图7.12所示。图7.11编、译码系统模型
对二进制对称信道来说，若P(1/0)=P(0/1)=P，假设发送序列X的长度为L个符号，并在传输过程中发生了e个符号错误，即X与Y有e个位置上的符号不同，它们的汉明距为e，则对数似然函数为(7.34)2.维特比译码前面我们已经谈到，卷积码网格图中共有2k(N-1)
种状态，每个节点（即每个状态）有2k条支路引入,也有2k条支路引出。为简便起见，我们讨论k=1的情形，从全0状态起始点开始讨论。由网格图的前N-1条连续支路构成的路径互不相交，即最初的2N-1
条路径各不相同，当接收到第N条支路时，每条路径都有两条支路延伸到第N级上，而第N级上的每两条支路又都汇聚在一个节点上。3.维特比解码法根据前面的原理叙述，维特比解码法的基本思路是：在接收端码字序列中先取前面组数等于编码约束度N的接收码字序列，与码网格图中N级的节点a，b，c，d的可能路径进行比较，然后按码距较小原则，每个节点选一条路径。以后逐次升高级别，逐次筛选路径，最后保留下来一条路径，则该路径的值就是编码输出。
为了更具体地阐明维特比译码法的过程，这里仍以图7.7所示的（2，1，3）编码器所编的卷积码为例。当发送数据为M=［11010］时，为使全部数据通过编码器，在后面再加三个“0”，此时数据变为
M=［11010000］，编码的码字X为［0］若通过信道传输后有差错，则收端的码字Y序列要变，假若变为［0
维特比解码法的解码过程如下：第一步，确定至三级节点a，b，c，d的路径。由于该卷积码的编码约束度为3，因此先选接收码字序列的前3组，即010101，并用下标表示节点的级别，如a3表示第3级节点a，依次类推。起点至第3级节点的路径有8条，可算出8条可能路径的码距（写在括号内）为a0→a3：
每个节点保留一条码距较小者的路径，若至同一节点的两条路径码距相等，则任选一条。经过第一步筛选，保留的路径分别为
第二步，将级别由第3级增至第4级，每个节点有两条路径，又有8条路径，接收码用作比较的部分增加一组，变为01010110，则8条路径的码距为a0→a3→a4：
第三步，把级数增加至第5级，路径还有4条主干，8条分支，如图7.13所示。用于比较的接收码字序列再增加一组，相应的码距为a0→a4→a5：
因为已知发送数据为5位，加3位0，共8位，所以到第8级汇聚于a状态。但第7级只有a7、c7可达a8，所以，只挑选两条路径：
最后确定的路径为a0→a8，如图7.13所示。这条路径的解码输出为［0］译出的信息码M′为［11010000］该结果M′与发端数据M完全相符。在本例中，接收的16个码元有4个出错，但在维特比解码过程中被查出并予以纠正，说明卷积码有很强的抗干扰能力。图7.13维特比解码法筛选出来的路径习题与思考题7.1在通信系统中，采用差错控制的目的是什么？
7.4一种编码的最小码距与其检、纠错能力有何关系？7.5已知8个码组为（000000）、（001110）、（010101）、（011011）、（100011）、（101101）、（110110）、（111000），求该码组的最小码距。码组若用于检错，能检出几位错码？若用于纠错，能纠正几位错码？若同时用于检错与纠错，则纠错、检错的性能如何？
7.6一码长n=15的汉明码，监督位r应为多少？编码速率为多少？试写出监督码元与信息码元之间的关系。7.7已知某线性码监督矩阵为试列出所有许用码。7.8设有8个码组为（10110010)、（00010101）、（01010011）、（10101100）、（10010101）、（11100101）、（01101010）、（10100111），试写出其矩阵码校验单元。
7.9已知系统分组码的码元为C=［1101c5c6c7］，试写出校验单元c5、c6、c7。
试确定卷积码的码树、状态图及网格图。7.12若发送数据为M=［10111］，并使全部数据通过（2,1,2）卷积码编码器。（1）写出编码器的码字输出。（2）若接收端将该码流显示为［0］，试用维特比解码法加以纠正，并列出解码过程。
2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
2024-2025学年机械设备制造修理人员模考模拟试题含完整答案详解（考点梳理）
湖南省邵阳市新宁县十校22024-2025学年九年级上学期10月期中考试道德与法治试卷（含答案）
2025-2026学年人教版（2024）初中生物八年级上册教学计划及进度表
2025广西公需科目培训考试答案(90分)一区两地一园一通道建设人工智能时代的机遇与挑战
