第15讲――信道编码定理2014

信道编码定理第十七讲对于给定的，通过增加N就能使为任意小；反之，若，就会趋于1。CRbpCRShannon信道编码定理bp信息传输速率R,信道容量C，传输误码率Pb以及编码长度N之间的关系？离散信道编码逆定理信道编码信道信道译码),,,(21Luuu),,,(21Nxxx),,,(21Nyyy),,,(21LvvvLULVNXNY由信息不增原理);();(LNNNVXIYXI而);();(LLLNVUIVXI所以);();(NNLLYXIVUINC1log(1)()()LLeepMHpHUVL);()(1LLLVUIUHL);(1)(NNLYXILUH);();(NNLLYXIVUICLNUHL)(NCYXINN);(又)()(UHUHL（平均符号熵随L增加非递增）)(XHNlog(1)()()(/)eepMHpHUNLC则离散信道编码逆定理()(/)0HUNLC()/LHUNC,即时pe0若信息传输速率大于信道容量C,则不管采何种编码和译码方法都不能使平均错误概率为0。)(UHNL离散信道编码逆定理设离散平稳源的字母表有M个字母，且熵为每秒产生一个字母。令离散无记忆信道的容量为C，每秒传送一个符号。若长为L的信息序列被编成长为的码字，则误码率pb满足)(lim)(UHUHLLscsLN/CUHpHMpcsbb)/()()()1log(当CUHNLUHsc)()()/(时，pb为非零值。若信息传输速率大于信道容量,则不管采何种编码和译码方法都不能使平均错误概率为0。上述定理可推广到一般离散有记忆信道。)(UHNLC联合ε典型序列令X、Y是两个概率空间，NNXxxx),,,(21xNNYyyy),,,(21y若序列x和y满足(1)x是ε典型序列，即对任意小的正数ε，存在N使)()(log1XHpNx(2)y是ε典型序列，即对任意小的正数ε，存在N使)()(log1YHpNy(3)xy是ε典型序列，即对任意小的正数ε，存在N使)()(log1XYHpNxy就称序列对(x,y)是联合ε典型序列。联合ε典型序列【引理1】对于任意0，当N足够大时有1),(NTpXYr])([])([2),(2)1(XYHNXYXYHNNT【引理2】若),(NTXYxy,则])([])([2)(2XYHLXYHLpxy【引理3】对于NXxNYy,若x与y相互独立，则当]3);([]3);([2),(),(2)1(YXINXYrYXINNTyxpN足够大时，有【引理3】对于,若x与y相互独立，则当N足够大时，有NXxNYy]3);([]3);([2),(),(2)1(YXINXYrYXINNTyxp证明：由定义及引理1[()][()][()][()][()][()]2()22()2(1)2|(,)|2NHXNHXNHYNHYNHXYNHXYXYppTNxy将上述三个不等式相应项相乘，并用I(X；Y)=H(XY)–H(X)–H(Y)就可得到引理3不等式。联合典型编码与译码在编码时，从XN中独立随机的选择M个典型序列作为码字，在接收端YN中，对接收序列y寻找与它构成联合典型序列的那个码字。若只对应唯一一个码字，则判定该码字为所发送的码字。因为发送的码字与接收序列y构成联合典型序列的概率很高，它们之间是高概率密切相关的。总之，若令x,y分别表示信道的输入和输出，则联合典型序列(x,y)表示那些信道的输入和输出之间密切关联、经常出现的序列对。信道编码正定理给定容量为C的离散无记忆信道，若编码速率，则R是可达的。YxypX),(,CR可达：对给定离散无记忆信道和任意的0一种编码速率为R的码，在N足够大时，能使，就称R是可达的。，若存在ep设DMC的输入为),,,(21Nxxxx,输出为),,,(21Nyyyy转移概率为Nnnnxypp1)()(xy令编码速率为R，编码NNRXE]2,1[:]2,1[:NRNYD译码NLR则各码字的标号集为[1，2NR]。编码规则：从XN中独立随机地选择2NR个序列作为码字，这样得到的码字必然是典型序列，这种编码称作随机编码。每个码字出现的概率为译码规则：对给定的接收序列y，若存在唯一的]2,1['NRm使),(),('NTXYmyx就将y译为m’，即')(mDy。若mm'或者有两个以上的m’和y联合典型时就认为出现译码错误。信道编码正定理证明NnnxQQ1)()(x令事件),(),(NTEXYmmyx]2,1[NRm则发送标号为1的消息时，译码错误概率为111mcmreeEEppp1)()(1mmcEpEp由引理1知，当N足够大时有。由引理3知，序列xm和序列y是联合ε典型序列，其概率的上限为0)(1cEp]3);([2)(YXINmEp因而有]3);([122)(YXINNRmmEp]3);([2YXIRN因为随机码集合的平均错误概率就是任意特定消息被译错的概率。不失一般性，可假定发送的是第一个消息。要使上式趋于0，。3);(YXIRN0ep若,则，。3CR信道传递信息时，我们总希望R尽可能大。因此可以选择输入分布为最佳，即以C代替I(X;Y)，于是重述上述结论。当RC时，可以通过编码方法使得译码错误概率趋于零，而且pe是随码长N的增加按指数规律下降的。它是一个存在性定理，非构造性，并没有构造出实际上可实现的、具有上述性能的码的方法。纠错编码就是为解决这一问题而产生的学科，它的目的是寻找一种在实际上易于实现且能达到有效而可靠的通信的编译码方法。信道编码正定理联合信源信道编码定理信道编码定理：RC，才能可靠地传输数据。信源编码定理：无失真编码，RH(U)。联合这二个定理，会提出这样的问题：若信源通过信道传输，要做到有效和可靠地传输，是否HC是充分和必要的条件？信源-信道编码定理：若是有限符号集上的随机序列并满足AEP，又信源S的极限熵，则存在信源和信道编码，其HCnS=12n（s,s,,s)HC0ep反之，对于任意平稳随机序列，若极限熵，则错误概率远离0，即不可能在信道中以任意小的错误概率传输随机序列。信源通过信源编码后再信道编码两步证明。信源编码和信道编码可独立进行，大大简化了通信系统的设计。本节小结（本节内容见课本146-153页）Fano不等式信道编码定理)()()1log(VUHpHMpbb对于给定的，通过增加N就能使为任意小；反之，若，就会趋于1。CRbpCRShannon第二编码定理第四章习题