1、第6章信道编码理论 第第6 6章信道编码理论章信道编码理论6.1概述概述6.2分组编码分组编码6.3卷积码卷积码6.4级联码级联码6.5Turbo码码6.6网格编码调制网格编码调制(TCM)习题习题第6章信道编码理论 6.1概述概述6.1.1信道编码的基本概念信道编码的基本概念数字信号在传输过程中,不可避免地要受到热噪声和脉冲噪声等的污染。在这两种噪声的影响下,被传送的信息数据将引起两种不同类型的差错,即随机分散出现的随机差错和成串出现的突发差错,从而出现在通信接收端收到的数据与发送端实际发出的数据不一致的现象。第6章信道编码理论 为了保证通信系统的差错在许可的范围内,必须对通信可靠性要求高的
2、系统加入差错控制编码措施。信道编码就是用来减小甚至消除信道噪声产生差错的一种主要措施。差错控制编码的原理是:发送方对被传输的信息数据进行分组,然后按某种编码规则算法附加上一定的冗余位,构成一个码字后再向信道发送。接收方收到编码数据(可能有差错)后进行校验,即检查信息位和附加的冗余位之间的关系,以检查传输过程中是否有差错发生。实现这种编码的设备叫信道编码器。第6章信道编码理论 当每个k位信息组按照编码规则加上足够的r个校验位而组成k+r位的码组后,这样的码组(也叫码字)就不仅能发现传输中出现的差错,甚至具有纠正这类差错的能力。受到污染的信息数据在到达接收端后,由相应的信道译码器对受到污染的信息数
3、据进行反变换,即译码。通常,经过译码的数据是原始发送信息数据的精确复制品,或者是带有可以被接受的差错的复制品。第6章信道编码理论 衡量编码性能好坏的一个重要参数是编码效率R,kkRnkr其中,n表示码字的位数,k表示数据信息的位数,r表示冗余位(监督位)的位数。上述编码就是常见的分组编码。长度为n的“码字”共有2n个,但其中只有2k个许用码字(组),其余2n2k个是禁用码字。第6章信道编码理论 6.1.2差错控制工作方式差错控制工作方式常用的差错控制工作方式主要有三种:前向纠错(简称FEC)、检错重发(简称ARQ)和混合纠错(简称HEC)。它们的系统构成如图6.1所示。第6章信道编码理论 图
4、6.1差错控制工作方式第6章信道编码理论 前向纠错方式的信道编码器的发送端发出可以纠正错误的码,接收端可以发现并纠正传输中的某些错误。其特点是单向传输,实时性好,但译码设备较复杂。在检错重发方式中,发射机中的信道编码器发出能够发现错误的编码信号。接收端译码后如果未发现差错,则通过反向信道向发送端反馈一个“确认”(ACK)回执信号,接收端译码后如果发现有传输错误,则通过反向信道向发送端反馈一个“否认”(NAK)回执信号,发送端再把前面发送的信息重新发送一次,直至接收端能正确接收为止。第6章信道编码理论 有三种检错重发方式,即停发等候重发(SW-ARQ)、退N步重发(go-back-N-ARQ)和
5、选择重发(S-ARQ)。SW-ARQ(stop-and-wait ARQ)也称停等法。在此系统中,发送端每发送一帧后就要停下等待接收方的确认返回,仅当接收方确认正确接收后再继续发送下一帧。如果接收端检测出错误,则反馈一个否认信号(NAK),发送端接到NAK信号后重发前一个码组,并再次等候ACK或NAK信号,如图6.2所示。这种方式由于在两个码组之间有停顿时间,所以传输效率低,常在数据通信中应用。第6章信道编码理论 图 6.2SW-ARQ工作原理示意图第6章信道编码理论 SW-ARQ法的实现过程如下:发送方每次仅将当前信息帧作为待确认的帧保留在缓冲存储器中。当发送方开始发送信息帧时,随即启动计时
6、器。当接收方检测到一个出错(E)的信息帧时,便舍弃(D)该帧。当接收方收到无差错的信息帧后,即向发送方返回一个确认帧。若发送方在规定的时间内未能收到确认帧(即计时器超时),则应重发存于缓冲器中待确认的信息帧;若发送方在规定的时间内收到确认帧,即将计时器清零，继而开始下一帧的发送。第6章信道编码理论 此方案最主要的优点就是所需的缓冲存储空间最小,因此在链路端使用简单终端的场合中被广泛采用。go-back-N-ARQ是当接收方检测出失序的信息帧后,要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧,或者当发送方发送了N帧后,若发送该N帧的前一帧在计时器超时后仍未返回其确认信息,则该帧被判
7、定为出错或丢失。第6章信道编码理论 对接收方来说,因为这一帧出错,就不能以正确的序号向它的终端递交数据,对其后发送来的N帧也可能都不能接收而丢弃。因此,发送方发现这种情况后,就不得不重新发送该出错帧及其后的N帧,这就是go-back-N(退回N)法名称的由来。go-back-N-ARQ法的工作过程如图6.3所示。图中假定发送完8号帧后,发现2号帧的确认返回在计时器超时后还未收到,则发送方只能退回从2号帧开始重发。第6章信道编码理论 图 6.3go-back-N-ARQ工作原理示意图第6章信道编码理论 S-ARQ系统的发送端也是不停顿地发送信号。当接收方发现某帧出错后,其后继续送来的正确的帧虽然
8、不能立即递交给接收端的终端,但接收端仍可收下来,并存放在一个缓冲区中,同时要求发送端重新传送出错的那一帧。一旦收到重新传来的正确帧后,就可与原已存于缓冲区中的其余帧一并按正确的顺序递交给终端。与退N步重发不同的是,它的发送端收到接收端返回的NAK信号后只重发有错误的那个码组。其工作原理示意图如图6.4所示。显然,选择重发系统的传输效率高,当然其设备也复杂一些。第6章信道编码理论 图 6.4S-ARQ工作原理示意图第6章信道编码理论 检错重发方式的特点是译码设备简单,但需要双工链路,实时性差。信道编码器输出码的检错能力,一般大于其纠错能力。在混合纠错方式中,接收端若检测到能够纠正的错误,则进行纠
9、错处理;若检测到无法纠正的错误,则向发送端返回否认信号,接收端收到此信号后重新发送传输中出错的码组。此方式的实时性和复杂性介于前向纠错与检错重发方式之间。第6章信道编码理论 6.1.3差错控制编码的分类差错控制编码的分类按照实现的功能,可将差错控制码分为检错码和纠错码。当然,纠错码必须具有检错功能,而具有检错能力的码不一定具有纠错功能。按照信息码元与监督码元之间的函数关系,可将差错控制码分为线性码和非线性码。如果函数关系是线性的,即满足一组线性方程式,则称为线性码,反之称为非线性码。实际应用的一般都是线性码。第6章信道编码理论 按照监督码元是否仅与本码组内的信息码元有关系,可将差错控制码分为分
10、组码和卷积码。在分组码中,每个码组内的监督码元或许仅与该码组内的信息码元有关;在卷积码中,每个码组内的监督码不仅与本码组内的信息码元有关,而且还与前面若干码组内的信息码元有关。按照编码后的信息码元组是否与编码前的相同,可将差错控制码分为系统码和非系统码。在系统码中,编码后的信息码元组保持不变;在非系统码中,编码后的信息码元被校验位分隔。常用的线性分组码一般为系统码。第6章信道编码理论 另外,按照码字的结构是否具有循环性,可以分为循环码和非循环码;按照纠错的类别,可以分为纠随机错误的码和纠突发错误的码。6.1.4差错控制编码的基本原理差错控制编码的基本原理差错编码的基本思想是在被传输信息中增加一
11、些冗余码,利用附加码元和信息码元之间的约束关系加以校验,以检测和纠正错误。增加冗余码的个数可增加纠错和检错能力。第6章信道编码理论 1.码长、码长、码重和码距码重和码距编码码组的码元总位数称为码组的长度,简称码长。如“1011”码长为4,“110011”码长为6。码组中,“1”码元的数目称为码组的重量,简称码重。如“10110”码重为3。两个等长码组之间对应位上不同码元的个数称为这两个码组的距离,简称码距。如“11000”与“11011”有两个对应位不同,故码距为2,常称此为汉明距离。第6章信道编码理论 码组集中任意两个码字之间距离的最小值称为最小码距,用dmin表示。最小码距是码的一个重要参
12、数,它是衡量编码检错和纠错能力的重要依据。2.检错和纠错能力检错和纠错能力最小码距与检错、纠错能力的关系:为了能够检测e个错误,要求dmine+1;为了能够纠正t个错误,要求dmin2t+1;为了能够纠正t个错误,同时检测e个错误(et),要求dmint+e+1。第6章信道编码理论 上述检错及纠错能力与最小码距的关系,可以用图6.5所示的几何图形加以说明。图6.5(a)中,C表示某一码组,当误码不超过e个时,该码组的位置移动范围将不超出以它为圆心、以e为半径的圆。只要其他任何许用码组不落入此圆内,则码组C就不会与其他码组混淆,这就意味着只要码组C与其他任何许用码组之间的最小码距不小于e+1,就
13、可以检测出码组C发生了e个错误。第6章信道编码理论 图6.5(b)中,C1、C2分别表示两个许用码组,当各自的误码不超过t时,若最小码距不小于2t+1,则可根据码组落在哪个圆内正确判断为C1或C2,即可以纠正错误。图6.5(c)中表示许用码组C1发生e个错误,而许用码组C2发生t个误码(et)。当最小码距不小于t+e+1时,若C1及C2的误码不超过t个,则可根据码组落在哪个圆内正确判断为C1或C2;若C1发生了e个错误,则该码组的位置移动范围仍没与码组C2的位置移动范围相混淆,仍可检测出码组C1发生了e个错误。第6章信道编码理论 图 6.5码距与纠错、检错能力的关系第6章信道编码理论 例如,若
14、将晴天编为“1”,雨天编为“0”,则dmin=1,无法检测错误和纠正错误。若将天气情况编为(2,1)码,两个许用码组是11与00,dmin=2,收端译码,当出现01、10禁用码组时,这种错误可以检测出来,但无法纠正。如果将天气情况编为(3,1)码,两个许用码组是111与000,dmin=3,可以检测出一个或两个错误码元,纠正一个错误码元。当收端出现两个或三个1时,判为1,否则判为0。此时,可以纠正单个错误,或者该码可以检出两个错误。显然采用这种译码方法所得到的误判(即误码)概率是最小的,这称为最大似然译码准则。第6章信道编码理论 6.1.5最大似然译码准则最大似然译码准则设发送码字为C=(cn
15、1,cn2,c0),它有2k个许用码组,当接收码字为R=(cn1,cn2,c0)时,计算2k个条件概率P(R|Ci)(i=1,2,2k)。若条件概率P(R|CL)为最大,则认为发送的码字为CL。这就是最大似然准则。P(R|CL)可用下式计算:10()()iniLiLcP R CPc(6.1)第6章信道编码理论 式中,ci为接收码字的第i个码元,cLi为许用码字CL的第i个码元。设信道为二进制对称信道,错误转移概率为Pe,接收码字R与许用码字CL的码距为d,则上式可写成P(R|CL)=(1Pe)ndPde (6.2)由于Pe0.5,故P(R|CL)随d增大而单调减小。所以,当所有码字的发送概率相
16、同时,按最大似然概率译码等效于按最小码距译码,即接收码字与哪一个许用码字的码距最小,就认为传送的是哪个码字。第6章信道编码理论 6.2分分 组组 编编 码码信息论指出,在固定信噪比下,可通过增加波形的复杂度使消息错误概率趋近于零。只要总信息传送速率低于信道容量,上述结论就有效。因此,迫切寻找一种特殊的技术,在不增加传送功率的条件下降低消息误码率,或实现同样消息误码率的条件下降低传送功率。同时构造传送波形,能够缓解信道的失真,并在合理的复杂度下接收机能正常接收。第6章信道编码理论 假设信源已经通过理想信源编码,它的输出就是一个独立等概的二进制数字序列。信源输出序列在编码器中加上一些为在接收端能够
17、纠正传输错误所必需的结构。在很多情形下,编码器输入和输出字符为二进制,为了使信源序列加上一些必要的结构组成传送信号,二进制输入/输出编码器的输出符号速率应比它的输入比特速率高。第6章信道编码理论 假设信道为转移概率为Pr(y|x)的二进制对称信道,其中的y、x0,1。当信道的输入和输出字符集相同时,信道被称为硬判决信道,与其相关的解码器被称为硬判决解码器。在讨论卷积码时,信道将允许输出符号的符号集大于输入符号集。大的输出符号集使信道可以给译码器提供判决可靠性信息。当可靠性信息从信道输出时,信道被称为软判决信道,其相关的译码器被称为软判决译码器。第6章信道编码理论 6.2.1基本概念基本概念分组
18、编码技术就是那些以信息分组为单位进行处理的编码技术。二进制输入/输出分组编码器把k位二进制信息符号作为一个分组,然后把它映射为n位二进制为一分组的输出符号。分组码的编码速率定义为R=k/n,它等于每次使用信道的信息传送速率,即编码器的每一个输出符号被传送的时候,就有R比特的信息被传送。第6章信道编码理论 一个由n个信道使用组成的分组传送nR=n(k/n)=k比特的信息。如要通过编码来提高信号的可靠性,信息传送速率必须低于信道容量。对于二进制输入信道,它的信道容量最大为每次使用信道传送1比特信息,所以RCN1.0,同样得出kn。第6章信道编码理论 1.分组编码的定义分组编码的定义k位信息比特的分
19、组用一k维矢量Wm=wm(k1)wm2wm1wm0来表示,其中每个wmi取值为0或1,脚标m表示正考虑的特定的消息。对应2k种可能的编码器输入消息有2k个二进制k维矢量Wm,信源输出消息m的概率表示为QM(m),对于假设的二进制对称信道,所有输出的消息是等概的,所以对所有的m有QM(m)=2k。编码器映射为二进制n维矢量Xm=xm0 xm1xm2 xm(n1)。第6章信道编码理论 这种映射是一对一的映射,意味着不会出现两个消息对应同一X的情形,即对于mm,有XmXm。分组码(n,k)是消息m所对应的Xm的集合,每个Xm是编码的一个码字,共有2n种可能的码字和2k种可能的消息。因为kn,消息数2
20、k小于可能的码字数2n,所以并不是所有的n维矢量都用作码字。一般来说,所用码字占总可用码字的比值为2kn=2k(11/R),因为R1.0,很显然这个比值随k的增加而降低。码字的纠错能力表明并不是所有可能的n维矢量都能用作码字。第6章信道编码理论 正因为这样,才有可能通过挑选码字来生成编码,使得在接收端的一个码字与另一个码字混淆前必然发生传输错误。2.汉明距离和汉明码汉明距离和汉明码表6.1给出了一组典型的分组编码。这组分组编码的信息比特是4位(k=4),把它们映射成了长度为7的码字(n=7),码率为R=4/7。第6章信道编码理论 第6章信道编码理论 因为n=7,有27=128种可能的码字,现只
21、选择其中的16种来编码。检查一下表6.1中的码字,就会发现任意两个码字间至少有3处不同,这意味若一个或两个传输错误不可能使其中一个码字转变为另一个码字。在这种情况下,译码器虽然不能够纠正这些错误,但可以告知用户传输错误已经发生;有3个错误发生时,就能够把传输的码字变成另一可用码字,这样解码器就不会检测出或不会纠正这些错误。例如,如果对应消息数2的码字被传输,且在第1,2和4(从右数)的位置上发生错误,接收到的码字正好是对应消息数3的码字。第6章信道编码理论 如发生的错误超过3个时,只有在接收到的码字矢量不是可用码字时才能够检测出错误。成对码字Xm和Xm 间相应位置不同的数目是一种很重要的特性,
22、被称为码字间的汉明距离,记为dH或dH(Xm,Xm)。码字集合中任意两个码字间的最小汉明距离被称为码的最小距离,记为dmin。表6.1中的码是一个汉明码,汉明码的最小码距是3,后面将会证明它能够纠正任意传输码字分组中的单一错误。第6章信道编码理论 成对码字间的汉明距离等于两码字模2矢量中1的个数。两码字的模2矢量就是矢量的各分量(无进位)逐项模2求和,任意码字矢量中1的个数称为这个码字的汉明重量(即码重),记为wH或wH(Xm)。第6章信道编码理论 3.错误矢量错误矢量码字Xm在二进制对称信道上传输,为了方便起见,用一个n维错误矢量建立错误模型来表征在传输中哪些位置发生了错误。错误矢量在每一位
23、没有发生错误的位置为0,每一位发生错误的位置为1。这样,二进制对称信道的输出矢量就是传送的码字矢量Xm和错误矢量e的模2和。例如,一个7比特的码字在1,2和4位置发生错误时,7维的错误矢量为e=0001011,如对应于表6.1的码中消息2(m=2)的码字被传送,并按上述错误矢量发生失真,则接收到的7维矢量将是:第6章信道编码理论 2011010011010001011100 xey(6.3)接收到的n维矢量标记为y=yn1y2y1y0。假设信道是无记忆的,意味着任意特定符号发生错误的概率独立于发生在所有其他符号的事件。进一步假设二进制对称信道的转移概率Pr(yi|xi)对所有的传送都是常数,因
24、而第6章信道编码理论 1 0|(|)nrrnnnP y xP yx(6.4)对于二进制对称信道有Pr(1|0)=Pr(0|1)=p,所以Pr(0|0)=Pr(1|1)=1p,则二进制对称信道引发错误使e=0001011的概率为Pre=0001011=pp(1p)(1p)(1p)(6.5)一般来说,二进制对称信道在长度为n的分组码字的特定位置引发e个错误序列的概率为第6章信道编码理论(6.6)Pr在码字的特定位置发生e个错误(1)en epp这一结论被用来计算Pr(y|xm),即在给定xm被传输的前提下接收到y的概率,这个概率可由下式给出:Pr(y|xm)=pdH(1p)ndH (6.7)其中d
25、H是xm和y之间的汉明距离。长度为n且包含e个错误的特定序列的数目可由下面的二项式系数给出:第6章信道编码理论!()!nnenee(6.8)因而,二进制对称信道引发的在长度为n的分组中包含e个错误序列的概率为 Pr在长度为n的分组中发生e个错误(1)en enppe(6.9)=第6章信道编码理论 4.最佳译码准则最佳译码准则译码器的输入是接收到的矢量y,预先已知全部码字xm(m=0,1,2k1)的集合。信源输出消息的概率QM(m)和信道转移概率Pr(y|xm)。利用上述信息,设计译码器对传送的码字做出“最佳可能”的估计。“最佳可能”估计是指估计的结果提供给信息用户的平均比特错误的数值最小。比特
26、错误概率记作Pb。第6章信道编码理论 首先考虑比较简单的情况。我们按以下方法选择译码规则:在不考虑某个特定码字发生错误所引起的信息比特错误数量的情况下,选择译码准则使得对传送码字做出不正确估计的概率最小。分组译码的错误概率记为PB，译码器对传送的码字的估值记为，已知接收到的矢量为y和 xm，如xm确实是被传送的码字时则译码器的估值就是正确的。x x 第6章信道编码理论)()()|()|(APBPBAPABP,P(A)0 (6.10)因为y有2n种可能，而码字只需要2k个，在这种准则下就会有多个y映射到同一xm的情形。所有对应于最佳译码器的估值 =xm的y的集合称为xm的判决区域，有2n种取值可
27、能的y的整个空间被划分为2k个互不重叠的判决区域，对每一可能的消息都存在一判决区域。为计算后验概率Pr(xm|y),利用贝叶斯准则x 第6章信道编码理论 由概率理论有|rmrrmrmP xy P yP y xP x(6.11)因而|rmrmrmrP y xP xP xyP y(6.12)等式右端的分母为210|krMrmmp yQm P y x(6.13)第6章信道编码理论 它是正数且独立于消息m。因此,解码准则又可以变为:选择使得式(6.14)最大的xm作为译码器的估值,这个等式在已知式(6.4)的信道转移概率和消息的先验概率时可求解。|rmrmrmMP y xP xP y xQm(6.14
28、)x 第6章信道编码理论 当所有消息的概率相等时,译码准则可进一步简化为选择使得Pry|xm最大的xm作为译码器的估值。对于二进制对称信道,Pry|xm由式(6.7)给出。因为对数对于递增变量是单调递增函数,所以,Pry|xm的对数也可以在不改变任何译码器判决的情况下应用到最大似然译码准则中。取式(6.7)的对数,对于二进制对称信道(BSC)的译码准则可表示为:选择使得式(6.15)最大的xm作为译码器的估值。x x 第6章信道编码理论 HHlg|lg()()lg(1)rmP y xdpndpHlg()lg(1)1pdnpp(6.15)在等式中,dH是接收到的n维矢量与所考虑的n维码字间的汉明
29、距离。因为对于p0.5,有lgp/(1p),所以使式(6.15)最大即等效为使dH最小,因而译码准则就是最小距离译码准则。对于pM个信道错误发生时就会有分组译码错误且信息比特错误的最大数是mink,i+M。很明显,不会发生超过全部信息比特数量的错误,并且如果全部错误发生在码字的信息比特部分且i+M位正确的比特被译码器更改,就会有M位信息比特发生错误。故比特错误概率的上界为第6章信道编码理论 1b11min,(1)nini MnPk iMppik (6.52)其中,1/k是指每一分组被译码时有k位信息比特输出,二项式系数 是n个符号的分组中发生i个错误的组合数。in第6章信道编码理论 6.2.3
30、循环码循环码(n,k)分组编码就是简单地把k位信息比特巧妙地映射为n位符号的码字。对于编码来说,码字和映射关系必须认真选取,因为它对提高通信系统的性能是非常有用的。对编码的结构则没有进一步的限制,一个(n,k)分组编码的编码是通过查表的方法实现的。一般地,它的译码也可用查表的方法利用最小距离译码准则来完成。对于很大的n和k,因为需要很大的表,查表的方法就无法采用。第6章信道编码理论 在前面,仅考虑线性分组编码,所需的线性特性可大大简化编码和译码过程。线性分组码的编码可由k维信息矢量与生成矩阵G的矩阵乘积完成,它的译码可以很简单地利用校正子的概念和标准阵列实现。在本小节,对线性分组码提出了附加的
31、结构条件,可使它的编码和译码功能进一步简化。这一附加结构使得编码器可以采用简单的前馈移位寄存器的形式。同样地,译码器可以采用反馈移位寄存器,再附加一些用来计算错误矢量的逻辑组成。本小节的主题是循环码,它是所有线性编码的子集。第6章信道编码理论 1.循环码的定义循环码的定义循环码是一线性编码,具有线性编码的所有特性,并且码字的任意位循环移位仍是另一有效码字。因此,如x=xn1xn2 x2x1x0是循环码的一码字,则x=xn2 x2x1x0 xn1是循环码的一码字;重复利用这一特性,码字经过q次移位后,记作x(q),仍是循环码的一码字。这时x(q)=xnq1x1x0 xnq+1xnq。循环码可用生
32、成矩阵G或奇偶校验矩阵H表示,但通常它们是用生成多项式的概念来表述的。在定义生成多项式前,我们先复习一下多项式的乘法和除法运算。第6章信道编码理论 2.多项式运算多项式运算w(D)=wk1Dk1+w2D2+w1D+w0是D的多项式,每一wj的取值取自集合0,1。这一多项式的次数等于系数为非零值的D的最高幂次,如多项式w(D)=D4+D+1的次数为4。为了方便,系数为零的项不再写出,同时与1的乘积中的1也略去,即w(D)=(1 D4)+(0 D3)+(0 D2)+(1 D1)+(1 D0)写作w(D)=D4+D+1第6章信道编码理论 这一多项式也代表k位信息矢量w=wk1 w2w1w0。设多项式
33、g(D)=gk1Dk1+g2D2+g1D+g0是另一多项式,同样定义多项式y(D)、x(D)和e(D),则两个多项式x(D)和e(D)的模2和为y(D)=ytDt+y2D2+y1D+y0该多项式的系数是x(D)和e(D)中相应具有相同幂次的D的系数的模2和,即yj=xj+ej两个多项式的乘积为x(D)=xn1Dn1+x2D2+x1D+x0第6章信道编码理论 它的系数由下式给出:g(D)w(D)=(gnk wk1)Dn1 +(gnk wk2+gnk1 wk1)Dn2 +(gnk wk3+gnk1 wk2+gnk2 wk1)Dn3 +(g0,w0)D0 =xn1Dn1+xn2Dn2+x0D0jii
34、jijgwx0(6.53)第6章信道编码理论 其中所有的运算是模2运算,超出多项式有效范围的系数假设等于零。多项式x(D)是编码矢量x=xn1 x2x1x0的另一种表示方式。由等式(6.53)可知,利用一个简单的电路就可实现多项式的乘积。图6.7给出了计算x(D)=w(D)g(D)的电路框图。第6章信道编码理论 图中,先输入和输出的都是高阶系数。首先初始化图6.7 中的移位寄存器的值全为零,作为输入的w(D)的系数从wk1开始一次只输入一个。图的右边输出的第一个值为xn1=wk1 gnk。现移位寄存器的时钟工作一次,wk1就被移存到寄存器1,这时输出为xn2=(wk2 gnk)+(wk1 gn
35、k1),移位寄存器的时钟工作n1次就输出了x(D)的n个系数。输入k个系数之后,零就输入到移位寄存器中。这种电路使循环码的编码变得非常容易。第6章信道编码理论 图 6.7多项式积w(D)g(D)=x(D)的实现电路第6章信道编码理论 接下来讨论两个多项式的商w(D)g(D)。这一除法遵循多项式除法的一般规则,只是这里的所有运算是模2运算。如果x(D)不能够被g(D)整除,余式为(D),商记为q(D),则有:x(D)=q(D)g(D)+(D)(6.54)余式(D)在研究循环码时非常重要。多项式的模2除法很容易通过例子解释清楚。现考虑多项式x(D)=D5+D4+D3+D2+D+1被多项式g(D)=
36、D3+D+1除的情况,这个长除式为第6章信道编码理论 第6章信道编码理论 在几乎所有的循环编码情形中,人们感兴趣的结果是它的余式,这一余式记为:Rg(D)x(D)=(D),可采用一个简单的电路来完成多项式的除法。图6.8给出多项式x(D)被多项式g(D)除的示意框图。图6.9示出了上述完成多项式的长除运算的移位寄存器的操作。第6章信道编码理论 图 6.8x(D)除以g(D)的实现电路第6章信道编码理论 图 6.9x(D)=D5+D4+D2+D+1除以g(D)=D3+D+1的实现第6章信道编码理论 3.循环码的性质循环码的性质对于任意(n,k)循环码,所有的码字矢量(码多项式)可由次数为rnk的
37、生成多项式g(D)和次数为k1的消息多项式w(D)的乘积表示。乘积x(D)=w(D)g(D)的次数正好是所希望的(k1)+(nk)n1。有2k个不同的多项式w(D)=wk1Dk1+w2D2+w1D+w0 与系数所有可能的二进制选择相对应,因而有2k个码多项式。二进制循环编码的码字可以很容易用图6.7所示的电路生成。生成多项式的特性如下:第6章信道编码理论(1)任一循环码的生成多项式都是多项式Dn+1的因式。因此,多项式Dn+1被g(D)除时,余式为0。更进一步,任何次数为nk,同时是多项式Dn+1的因式的多项式就是一(n,k)循环码的生成多项式。(2)g(D)的次数总为nk。(3)一个码字的q
38、次移位就是多项式Dqx(D)除以Dn+1的余式。(4)给定一循环码的生成多项式g(D)=gnkDnk+g2D2+g1D+g0,它的kn阶生成矩阵G和奇偶校验矩阵H分别如下：第6章信道编码理论 01101101101100000000000000000ggggggggggggggggGknknknknknknknkn(6.55)第6章信道编码理论(6.56)kkkkkkkkhhhhhhhhhhhhhhhhH11011011011000000000000000000其中,多项式h(D)=hkDk+h2D2+h1D+h0是多项式Dn+1除以g(D)的结果,没有余式,多项式h(D)称做奇偶校验多项式。
39、第6章信道编码理论 4.循环码的编码循环码的编码只要完成了生成多项式与消息多项式的乘积,就可产生所有的有效码多项式。但是这些多项式不是系统码的形式,可以采用图6.8所示的多项式除法电路或通过手工多项式长除法得到具有系统码形式的码多项式。其步骤如下:(1)消息多项式w(D)乘以Dnk。(2)多项式Dnkw(D)除以生成多项式g(D),得到余式(D)。(3)得到的码多项式就是x(D)=(D)+Dnkw(D)。第6章信道编码理论 5.循环码的译码循环码的译码与非循环的信息码相比,循环码的结构使译码过程有很大的简化。假设传送的是码多项式x(D),在信道上传送时叠加了一些错误,错误用多项式e(D)=en
40、1Dn1+e2D2+e1D+e0表示,其中ej=1表明在第j个位置上发生了错误。接收矢量用多项式y(D)yn1Dn1+y1D+y0=x(D)+e(D)表示。第6章信道编码理论 正如前面用标准阵列译码时一样,循环码的译码首先计算校正子多项式s(D),校正子多项式仅决定于错误多项式,即xm(D)+e(D)的校正子对所有的消息m都是相同的。校正子多项式就是接收多项式y(D)除以g(D)的余式,即s(D)=Rg(D)y(D)。用图6.8所示的电路计算校正子多项式,当且仅当接收多项式与某一码多项式相同时校正子多项式才为零,出现这种情形或者是没有错误发生,或者是错误多项式正好与某一码多项式相同。第6章信道
41、编码理论 译码过程的下一步就是把校正子与最可能的错误多项式关联起来,这一过程依赖于所考虑的特定编码。假设存在校正子与错误图样间关联的表,则可采用查表的方法。从校正子确定错误多项式后,译码器可通过把估计的错误多项式与接收多项式相加得到估计的码多项式而完成译码。在这个过程中,编码的循环结构带来了很多优势,循环结构可以使错误e0,e1,，en1的估计从en1开始一个时钟周期一位。第6章信道编码理论 译码器首先从初始化的校正子得到第一个估值en1,接着译码器电路的时钟工作一个周期生成另一校正子,从而估计出en2,依此类推,直到估计出e0。译码器的简化完全得益于用来依次估计en1,en2,e0的电路是相
42、同的。当译码器检测到错误时,就在接收多项式中把它纠正过来,同时从校正子计算电路中去除已经纠正错误的影响。第6章信道编码理论 图6.10是一个循环码的译码器方框图。其中,接收多项式r(D)从左端移位进入校正子寄存器。接收多项式输入到(首先是高阶项)一个缓冲寄存器(顶部)和一个长除电路。当接收序列在往译码器读的过程中,图6.10中的门a、h和d关闭,门c和e打开。接收序列输入完成后,门a、b和d打开,门c和e关闭。长除完成接收多项式除以生成多项式g(D)的除法并得到余式(D),它就是第一个校正子多项式s(D)。校正子输入到“错误图样检测电路”,这个电路取决于特定的编码,而且非常简单。第6章信道编码
43、理论 图 6.10循环码的译码器方框图第6章信道编码理论 如果检测到接收多项式的最高阶rn1位发生了错误en1=1,错误检测电路输出一位1,缓冲寄存器和除法寄存器时钟同时工作一个周期,输出第一位译码的符号,这一符号已由图中右上角的异或电路进行过纠错(如需要)。误码估值同时输入到除法电路,以消除它对余下校正子的影响。重复这一过程,直到所有的n个接收符号都经过纠错处理。循环码译码器的复杂度正比于码字的长度n。和任意分组编码采用查表方法或采用标准阵列译码器的复杂度相比,采用查表法时必须有2n项(每一可能的接受矢量对应一项),而标准阵列译码也必须有对应每一可纠正错误图样的条目的表。第6章信道编码理论
44、6.2.4汉明码汉明码1.汉明码的定义汉明码的定义汉明码是1950年由R.W.汉明发现的一组编码。所有汉明码的最小距离为3,在长度为n的一分组中只能纠正一位错误(t1)及检测所有的两个错误。汉明码是一个线性循环系统码,对于任何整数j3,存在n=2j1和k=nj。这些编码的编码率为R=k/n=(2j1j)/(2j1),且随j的增大R趋近于1。第6章信道编码理论 表6.4给出了一个(n,k)码的短表,且列出了前8个汉明码的编码率R。第6章信道编码理论 汉明码总是用它的奇偶校验矩阵来定义,它的奇偶校验矩阵有nk=j行、n列,它的列由所有可能的非零j维矢量组成。例如,在前面例子中多次讨论过的(7,4)
45、汉明码的奇偶校验矩阵为100101101011100010111H第6章信道编码理论 可以看出,所有非零的3维矢量作为矩阵的列。汉明码的生成矩阵可通过针对线性系统码的关系式(6.30)和式(6.31)得到。这一编码的生成多项式在前面的例子中已给出。可以证明,这一定义表示生成多项式g(D)是一类特别的称为本原多项式的成员。表6.5是本原多项式的一截短列表,它们可以被用来做分组长度最大达到n=2241的汉明码的生成多项式。第6章信道编码理论 第6章信道编码理论 2.汉明码的编码汉明码的编码汉明码编码的编码器可采用各种形式。如果编码器的速度要求不是很苛刻,编码器可以通过软件直接计算生成矩阵乘积来完成
46、编码;如果编码器的速度要求苛刻,通常就会采用其他方法。图6.11就给出了可由高速逻辑组建的直接实现汉明编码的方框图。图6.11中顶部的k1位移位寄存器从数据源接收信息比特,输入寄存器存满后,模2加法器的输出就是正确的码字符号,每一符号是由生成矩阵定义的确定的信息比特的模2和,生成矩阵可从生成多项式得到。其表示式为第6章信道编码理论 0110110110110000000000000000ggggggggggggggggGknknknknknknknkn(6.57)第6章信道编码理论 码字符号通过闭合模2加法器下面的开关写入底部的移位寄存器(图中用xn1,x1,x0表示),码字在时钟触发下移出编
47、码器到调制器用于传送。顶部移位寄存器和底部移位寄存器的工作时钟速率不同,底部寄存器的时钟速率是顶部寄存器(图中用wk1,w1,w0表示)的1/R倍。码字从底部寄存器中读出的同时新的信息比特读进顶部寄存器。图6.11 所示的编码器可用于生成矩阵系数，以选择合适的循环码。可看出,编码器的复杂度正比于n(nk),对于很大的分组长度来说它可能就无法实现了。第6章信道编码理论 图 6.11汉明码编码器第6章信道编码理论 既然汉明码是循环码,就会由一些更简单的编码器来实现。回顾一下,具有系统码结构的循环码的码字可由以下步骤实现:(1)消息多项式w(D)乘以Dnk。(2)多项式Dnkw(D)除以生成多项式g
48、(D)得余式(D),即(D)=Rg(D)Dnkw(D)。(3)得到的码多项式就是x(D)=(D)+w(D)Dnk。第6章信道编码理论 图6.12给出的编码器电路就精确地完成了上述计算。输入已经往右移了(nk)位,实现了w(D)乘以Dnk。编码器开始工作时,那些开关的状态如图中所述。k位消息比特输入到除法器的同时也直接输出到用户,最后一位消息比特输入后,移位寄存器内就是长除的余式,两处的开关状态改变,上面的开关打开,输出的开关将改变输出寄存器的内容。移位寄存器的时钟必须触发足够多次来输出所有的奇偶比特,以完成编码过程。这一编码器的复杂度正比于(nk)。显然,对于n很大的编码应该选择这样的编码器。
49、第6章信道编码理论 图 6.12利用反馈移位寄存器实现的汉明编码器第6章信道编码理论 3.汉明码的译码汉明码的译码汉明码的译码可用前面提到的许多技术来实现,包括查表法、标准阵列法和图6.10所示的一般循环码译码器,这里只讨论图6.10给出的译码器。很明显,对于只纠正单个错误的汉明码来说,图6.10中的错误图样检测电路采用了一个特别简单的有(nk)个输入的与门的形式。第6章信道编码理论 汉明码的译码电路由图6.13示出。只有当移位寄存器中包含的校正子为s(D)=(1 Dnk1)+(0 Dnk2)+(0 D1)+(0 D0)时才检测到(和纠正)一位错误。电路的工作过程与前面描述的图6.10所示电路
50、的工作过程完全一样。这种译码器之所以如此简单,完全得益于编码的代数结构。第6章信道编码理论 图 6.13循环汉明码的译码器第6章信道编码理论 4.汉明码的性能汉明码的性能只能纠正一位错误的编码的分组错误概率PB就是在传送过程中发生两个或更多个错误的概率。这个概率等于1减去0个或1个错误发生的概率,由式(6.35)得nlnnpppP11B)1()1(0.1(6.58)第6章信道编码理论 只有一个“错误图样”没有错误,它发生的概率为(1p)n;有n=2j1个发生了单个错误的错误图样,每一错误图样发生的概率为p(1p)n1。图6.14给出了表6.6给出的一些汉明码的PB曲线,PB是二进制对称信道(B
