有噪信道编码定理

第6章有噪信道编码定理6.1错误概率和译码规则6.2错误概率和编码方法6.3有噪信道编码定理信源编码之后的码字序列抗干扰能力很脆弱，在信道噪声的影响下容易产生差错，为了提高通信系统的有效性和可靠性，要在信源编码器和信道之间加上一个信道编码器。有噪声信道编码的主要目的是提高传输可靠性，增加抗干扰能力，因此也称为纠错编码或抗干扰编码。6.1错误概率和译码规则我们已经知道错误概率与信道统计特性有关。信道的统计特性可由信道的传递矩阵来描述。当确定了输入和输出对应关系后，也就确定了信道矩阵中哪些是正确传递概率，哪些是错误传递概率。例如在二元对称信道中，单个符号的错误传递概率是p，正确传递的概率是1pp但通信过程一般并不是在信道输出端就结束了，还要经过译码过程（或判决过程）才到达消息的终端（收信者）。因此译码过程和译码规则对系统的错误概率影响很大。例：影响通信系统可靠性的一个重要问题是译码方式，可以通过一个例子看一下，设一个二元对称信道，其传输特性如图所示（2）采用收0判1，收1判0；则系统正确的译码概率为0.9，错误译码概率为0.1，通信的可靠性提高了。（1）采用收0判0，收1判1；当信源先验概率的等概时p(0)=p(1)=1/2；这时收到Y判X的后验概率等于信道转移概率，系统正确的译码概率为0.1，错误译码概率为0.9。设信道输入符号集X={xi,i=1,2,…,r},输符号集为Y={yj,j=1,2,…,s},F(yj)=xi(i=1,2,…r;j=1,2,…s)对于有r个输入，s个输出的信道来说，可以有rs个不同的译码准则。若对每一个输出符号yj都有一个确定的函数F(yj)，使yj对应于惟一的一个输入符号xi，则这样的函数为译码规则。【例6.1】有一离散单符号信道，信道矩阵为4.03.03.02.03.02.02.03.05.0P根据这样一个信道矩阵，设计一个译码规则，即A332211)()()(:abFabFabFA设计另外一个译码规则，如，即B233211)()()(:abFabFabFB译码规则的选择应该使平均错误概率为最小。为了选择译码规则，首先必须计算平均错误概率。1、错误概率译码准则确定之后，当接收端收到一个bj后，则按译码准则译成F(bj)=ai，这时如果发送的为ai则为正确译码，如果发送的不是ai则为错误译码。所以接收到bj后正确译码的概率就是接收端收到bj后，推测发送端发出ai的正确译码概率：)|(|)(jjjjbaPbbFP错误译码的概率为：jjjijbbFPbaPbeP|)(1)|(1)|(平均错误译码概率为：sjjjjEbePbPbePEP1)|()()|(它表示经过译码后平均接收到一个符号所产生的错误大小，也称平均错误概率。ijabF)()|(jbeP只要设计译码规则，使条件错误译码概率为最小。就应选择为最大。即选择译码函数：BbAaabFjj,**,)(并使之满足条件*),|()|*(aaAabaPbaPiijij这就是说，如果采用这样一种译码函数，它对于每一个输出符号均译成具有最大后验概率的那个输入符号，则先信道错误概率就能最小。这种译码规则称为“最大后验概率译码准则”或“最小错误概率译码准则”。)|(ijabP)(iaP已知信道的传递概率与输入符号的先验概率，根据贝叶斯定律BbaaAaaPabPbPaPabPjiiiijjj*),()|()(*)(*)|(选择译码函数BbAaabFjj**)(并满足*),()|(*)(*)|(aaAaaPabPaPabPiiiijj这样定义的译码规则称为最大似然译码准则。,()(|){1[()]()}1[()]()[()]EjjjjjjjYYYijjjXYYPPbPebPFbbPbPFbbPabPFbb,,()()()ijjijXYYYXaPabPabPab平均正确概率为YYjjjEEbaPbbFPPP)()(1也可以写成aXYijiEabPaPP,)|()(如果先验概率是等概率的raPi/1)()(iaPaXYijEabPrP,)|(1【例6.2】已知信道矩阵4.03.03.05.03.02.02.03.05.0P根据最大似然译码准则可选择码函数为B233211)()()(:abFabFabFB567.0)4.03.0()3.02.0()2.03.0(3131567.0)4.02.0()3.03.0()3.02.0(31)|(31)(,XieaXYEPabPP5.0)|(11abP)3,2,1(3.0)|(2iabPi第一列中，第三列中5.0)|(23abP第二列中若选用前述译码函数A得平均错误概率aXYEabPP,600.0)5.02.0()3.03.0()3.02.0(31)|(31EEPP若输入不是等概率分布，其概率分布为1()1/4Pa2()1/4Pa3()1/2Pa根据最大似然译码准则仍可选择译码函数为B计算其平均错误概率。()()(0.30.2)/4(0.20.3)/4(0.30.4)/20.6iEieXPPaP采用最小错误概率译码准则：2.015.015.0125.0075.005.005.0075.0125.0)(jibaP联合概率矩阵译码函数为333231)()()(:abFabFabFC()()(|)(0.1250.05)(0.0750.075)(0.050.125)0.50()1/411/411/200.50EijiYXaiieXPPaPbaPaPEEPP输入不是等概率分布时最大似然译码准则的平均错误概率不是最小。错误概率与信道疑义度满足以下关系这个不等式称为费诺不等式。6.2错误概率与编码方法1、简单重复编码一个BSC信道，输入为X={0，1}，且为等概分布，信道模型为：按最大似然译码准则为：EP)|(YXH)1log()()|(rPPHYXHEE)1()1()0()0(2211abFabF21001.0EP（输入等概率）将0编为000，1编为111。这时的可用码字为8；分别为：X1=000X2=001X3=010X4=100X5=011X6=110X7=101X8=111而许用码字为000和111，相当于信道输入为X1=000，X2=111，而信道输出端为：Y1=000；Y2=001；Y3=010；Y4=100Y5=011；Y6=110；Y7=101；Y8=111这时的信道转移矩阵为：这时如果按最大似然法则译码，将为：F(Y1)=F(Y2)=F(Y3)=F(Y4)=X1=000F(Y5)=F(Y6)=F(Y7)=F(Y8)=X2=111错误译码概率为：Pe≈3×10-4显然，若重复更多次一定可以进一步降低错误概率。可计算得,7,5n10875105111091047105EEEEPnPnPnPn但这里带来了一个新问题，当很大时，信息传输率就会降低很多。我们把编码后信道的信息传输率（也称码率）表示为nlog/RMn（比特/码符号）若传输每个码符号平均需要秒钟，则编码后每秒钟传输的信息量tlog/()tRMnt（比特/秒）2、消息符号数在一个二元信道的n次无记忆扩展信道中，输入端共有2n个符号序列可能作为消息符号，现仅选其中M个做为消息符号传递。当M选大些，pE也跟着大，R也大；M选取小些，pE就降低，而R也要降低些。例：若信源3次扩展后有8个消息符号数，如果选择其中M个做为输入消息符号传递，则信道输出端将会收到8个输出符号，然后要从这8个输出符号中译出M个消息符号8223n从个符号序列中取个作为消息可以有70种选取方法。选取的方法(编码的方法)不同，错误概率是不同的，现在我们来比较下面两种取法：当n=3，M=2有PE≈3×10-4R=1/3当n=3，M=8有PE≈3×10-2R=1当n=3，M=4有PE≈3×10-2R=2/3第1种选法第2种选法0111011100000010101000002102EP21028.2EP用最大似然译码规则计算3、(5.2)线性码设取M=4,n=5，这时信息传输率R=2/5bit/码符号而输入符号的4个（M=4）个码字采用下述编码方法：设输入序列，其中为序列中第个分量，若中各分量满足方程}1,0{)(54321kiiiiiiiaaaaaa21512134iiiiiiiaaaaaaaakiaiki正确译码概率错误译码概率4、汉明距离设为两个n长的二元码字，则码字和之间的汉明距离定义为其中，表模二和运算。在一个码组（码字集合）中，任意两个等长码字之间，如果有d个相对应的码元不同，则称d为这两个码字的汉明距离。性质：1、非负性D(X,Y)≥02、对称性D(X,Y)=D(Y,X)3、三角不等式D(X,Z)+D(Y,Z)≥D(X,Y)}1,0{)(21kniiiiiaaaa}1,0{)(21knjjjjibbbbijnkjijikkbaD1),(在二元码C中，任意两个码字的汉明距离的最小值，称为码C的最小码距，即5、用汉明距离来表示极大似然译码规则极大似然译码准则码字码字CCCCCCCDdjijiji,)},(min{minnjjYCaaF,**)(CaPaPiiijj*,)|(*)|(}1,0{)(21kniiiiiaaaa}1,0{)(21knjjjjibbbb)()|()|()|()|(2211DijnDijijijijijppabPabPabPPnn当信道是无记忆时，则编码后信道的传递概率为*,),()*,(aCDaDiijij*,),()*,(minaCDaDiijij上式又称为最小距离译码准则。在二元对称信道中最小距离译码准则等于最大似然译码准则。在任意信道中也可采用最小距离译码准则，但它不一定等于最大似然译码准则。6、平均译码错误概率也可用汉明距离来表示若设输入码字数为M(并设输入等概率分布)，平均译码错误概率*,)(1)|(1aCYjiDijnDijijEnppMPMPnYjjDnjDijEppMPMP)(11)|(11或6.3有噪信道编码定理定理6.1有噪信道编码定理：设离散无记忆信道为信道传递概率，其信道容量为。当信息传输率时，只要码长足够长，总可以在输入符号集中找到M2n(C+ε)个码字组成的一组码和相应的译码规则，使译码的平均错误概率任意小（）。)|(,),|(,xyPYxyPXCCRnnX0EP定理6.2有噪信道编码逆定理（定理6.1的逆定）：设离散无记忆信道，其信道容量为。当信息传输率则无论码长n多长，总也找不到一种编码，使译码的错误概率任意小。证明略。YxyPX),|(,CCR),2(nMnR1）若M≤2n(C-ε)，则存在这样的码及相应的译码规则，当n足够大时，使信道输出的错误概率PE任意小；2）若M=2n(C+ε)则无论n多大，也找不到一种编码，使译码错误概率PE任意小。某离散无记忆信道有r个输入，s个输出，信道容量为C，在输入rn个符号中选出M个码字组成一种码，设ε是任意小的正数，