第7章 有噪信道编码

第7章有噪信道编码信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：如何正确接收载有信息的信号－－线路编码如何避免少量差错信号对信息内容的影响－－纠错编码主要介绍：有扰离散信道的编码定理；纠错编译码的基本原理与分析方法；几个重要的编码算法(线性分组码;卷积码)7.1错误概率和译码规则有噪信道的错误和信道统计特性、译码过程有关例：在BSC信道中，p=p(0/0)=1/3规则1：接收到0—0，接收到1—1平均错误PE=P(0)*2/3+P(1)*2/3=2/3规则2：接收到0—1，接收到1—0平均错误PE=P(0)*1/3+P(1)*1/3=1/3译码规则：设计一个函数F(bj),对于每一个输出bj可以唯一确定一个输入符号ai。错误概率和译码规则确定F(bj)=ai后，如果发送端发送的就是ai，则正确译码，否则错误译码。收到bj的译码正确概率为P(F(bj)/bj))=P(ai/bj)令P(e/bj)为条件错误概率，平均错误概率：(最大后验概率准则)为使PE最小，就要使P(F(bj)/bj))最大。即选择译码函数F(bj)=a*，满足:jjjjjjjEbbFPbPbePbPP)))/((1)(()/()(*),/()/*(aabapbapijij错误概率和译码规则(最大似然译码准则)选择译码函数F(bj)=a*，满足:当输入符号等概时，上述两个准则等价例：输入分布P(a3)=P(a2)=0.25,P(a1)=0.5,*),/(*)/(aaabpabpiijj2/16/13/13/12/16/16/13/12/1P信道编码的基本思想添加冗余，重复发送消息。(以BSC信道为例,取p=0.01):发送方:0—000;1—111,接收方8种可能，利用最大似然的方式选择译码规则。问题：信息传输率降低。定义编码后的消息传输率：R=logM/n；M是输入消息的个数，n是码字的长度。有噪信道编码定理：能否找一种编码，使得PE相当低，而R保持一定的水准？错误概率和译码规则如果输入端有2n个符号序列可以作为消息，如果选出其中的M个作为消息传递，当M较大时，PE也跟着会大，而R也大。M小时，PE和R也会降低。M一定时，选择怎样的序列作为消息发送？例：n=3，M=4,R=logM/3=2/3;PE1PE2法1:(000,011,101,110)法2:(000,001,010,100)例：n=5，M=4，(00000,01101,10111,11010)得：PE=7.8*10-4有噪信道编码定理正定理：只要传信率R小于信道容量C，总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。逆定理：信道容量C是可靠通信系统传信率R的上边界，如果RC，就不可能有任何一种编码能使差错概率任意小。信道编码的途径增大信道容量C减少信息传输率R增加码长n7.2联合信源信道编码定理例题7.27.3线性分组码信息码元、校验元、编码效率检错码、纠错码线性码、非线性码信道的检错和纠错能力汉明距离：长度为n的两个符号序列ai和bj，对应位置上不同码元的个数。用D(ai,bj)表示.码的最小距离dmin：任两个码字汉明距离的最小值。dmin越大，PE越小。最小距离越大，受干扰后，越不容易把一个码字错成为另外的一个码字，因而错误概率小。最大似然译码准则(最小距离译码准则):*),,()*,(aabaDbaDijij定理1：线性分组码中，如果要检测e个随机错误，则要求码字的最小距离dmin至少为e+1;而如果要纠正e个随机错误，则要求码字的最小距离dmin至少为2e+1如果dmin=3，纠错能力是1，检错能力是2信道的检错和纠错能力5.6.1生成矩阵和校验矩阵c＝m*G1×n1×kk×n码字消息生成矩阵G＝[gk-1…g1g0]T，有k个(1×n)行矢量，如何选择呢？c=mk-1gk-1+…+m1g1+m0g0码字都可以写成k个基底的线性组合由于k个基底即G的k个行矢量线性无关，矩阵G的秩一定等于k。当信息元确定后，码字仅由G矩阵决定，因此我们称这k×n矩阵G为该(n,k)线性分组码的生成矩阵。系统形式的生成矩阵(n,k)码的任何生成矩阵都可以通过行运算（以及列置换）简化成“系统形式”。G=[IkP]=Ik是k×k单位矩阵，P是k×(n-k)矩阵。(1)(1)(1)1(1)01(1)11100(1)01001000100001knkkknknkppppppppp生成的码字C前k位由单位矩阵Ik决定，等于把信息组m原封不动搬到码字的前k位；其余的n-k位叫冗余位或一致校验位，是前k个信息位的线性组合。这样生成的(n,k)码叫做系统码。若生成矩阵G不具备系统形式，则生成的码叫做非系统码。系统化不改变码集，只是改变了映射规则。空间构成n维n重空间有相互正交的n个基底选择k个基底构成码空间C选择另外的(n-k)个基底构成空间HC和H是对偶的CHT＝0,GHT=0n维n重空间Vk维k重k维n重n-k维信息组码空间n重H空间mC校验矩阵将H空间的n-k个基底排列起来可构成一个(n-k)×n矩阵，称为校验矩阵H。用来校验接收到的码字是否是正确的；G是(n,k)码的生成矩阵，H是它的校验矩阵；如果(n,k)码是系统码，由GHT=0，得H＝[－PTIn-k]，二进制时，负号可省略。P98页的例题5.6.2伴随式与标准阵列译码mC=(cn-1,…,c1,c0)R=(rn-1,…,r1,r0)(n,k)信道定义差错图案EE＝(en－1,…,e1,e0)＝R－C＝(rn-1－cn-1,…,r1－c1,r0－c0)二进制码中模2加与模2减是等同的，因此有E=R＋C及R=C＋E伴随式S的定义因为CHT=0所以RHT＝(C＋E)HT＝CHT＋EHT=EHT如果收码无误：必有RHT=0。如果收码有误：即E0，则RHT=EHT0。在HT固定的前提下，RHT仅仅与差错图案E有关，而与发送码C无关。定义伴随式SS=(sn-k-1,…,s1,s0)=RHT=EHT从物理意义上看，伴随式S并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。差错图案E是n重矢量，共有2n个可能的组合，而伴随式S是(n-k)重矢量，只有2n-k个可能的组合，因此不同的差错图案可能有相同伴随式接收端收到R后，因为已知HT，可求出S＝RHT；如果能知道对应的E，则通过C=R＋E而求得C。S=(sn-k-1,…,s1,s0)=EHT,有n个未知数en－1,…e1,e0,却只有n-k个方程，可知方程组有多解。概率译码：把所有2k个解的重量(差错图案E中1的个数)作比较，选择其中最轻者作为E的估值。该方法概念上很简单但计算效率不高。伴随式S的意义汉明码(HammingCode)汉明码不是指一个码，而是代表一类码。汉明码的纠错能力t=1，既有二进制的，也有非二进制的。二进制时，汉明码码长n和信息位k服从以下规律：(n,k)=(2m-1,2m-1-m)，其中m=n-k。当m＝3、4、5、6、7、8…时，有汉明码(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247)…。汉明码是完备码，因为它满足上述等式。1011(21)22mmnkinni汉明码校验矩阵的构成汉明码的校验矩阵H具有特殊的性质，能使构造方法简化。一个(n,k)码的校验矩阵有n－k行和n列，二进制时n-k个码元所能组成的列矢量总数是2n-k-1,恰好和校验矩阵的列数n=2m-1相等。只要排列所有列，通过列置换将矩阵H转换成系统形式，就可以进一步得到相应的生成矩阵G。例6.4构造一个m=3的二元(7，4)汉明码。解：先利用汉明码的特性构造一个(7，4)汉明码的校验矩阵H，再通过列置换将它变为系统形式：0001111列置换1110100H=01100110111010=[PTI3]10101011101001再得生成矩阵G为1000101G=[I4P]=010011100101100001011