信道编码定理.ppt
1,第5章 信道编码定理,2,信道编码和译码Fano不等式和信道编码逆定理联合典型序列和信道编码定理错误概率限等能量正交编码,3,信道编码和译码,(n0,k0)卷积码(Convolutional codes)：m个分组相关，约束长度为(m+1)k0,编码速率,(N,K)分组码(Block codes)：分组之间独立,编码速率,4,信道编码和译码,译码准则,信息序列个数：,可能的N 长二元序列个数：,编码：信息序列到N 长二元序列空间的映射,K长二元序列空间,N长二元序列空间,5,信道编码和译码,接收矢量：,码字：,译码错误概率（误组率）,接收y的译码错误概率,误比特率Bit error rate,第k位出错的概率,6,信道编码和译码,最小错误概率准则,使,最小,最大后验概率准则,最大后验概率准则,计算后验概率是困难的，针对具体信道（转移概率已知），采用最大似然准则,7,信道编码和译码,离散序列,消息序列先验概率相等,最大似然准则,8,信道编码和译码,译码是由YN到UL的映射，将YN划分为M个不相交的子集,是Ym的补集,最大后验概率译码,最大似然译码,所有消息等概,q元对称信道,最小汉明距离译码,9,信道编码和译码,例5.1.1 两个消息等概，x1=0000，x2=1111，通过二元对称信道，转移概率p,10,信道编码和译码,连续序列,消息序列先验概率相等,最大似然准则,11,信道编码和译码,高斯白噪声信道：均值为0，双边功率谱密度N0/2,最小平方欧氏距离译码,12,信道编码和译码,最大相关译码,若,都相同，即等能量,13,信道编码和译码,判决区域,14,信道编码和译码,判决区域,15,信道编码和译码,错误概率,16,信道编码和译码,错误概率,17,Fano不等式和信道编码逆定理,18,Fano不等式和信道编码逆定理,研究Pb，HL(U),I(UL;VL)之间的关系,先考虑L=1,f(H)是非减函数,19,Fano不等式和信道编码逆定理,设空间U和V各有M各个元素a1，a2，aM。,定理5.2.1(Fano不等式)U 和V 空间中的事件满足下不等式,20,Fano不等式和信道编码逆定理,21,Fano不等式和信道编码逆定理,22,Fano不等式和信道编码逆定理,L1时,信道编码逆定理,23,联合典型序列和信道编码定理,24,联合典型序列和信道编码定理,定义5.3.1 x和y是联合典型序列,(1)x是典型序列，即对任意小的正数e，存在N使,(2)xy是典型序列，即对任意小的正数e，存在N使,(2)y是典型序列，即对任意小的正数e，存在N使,25,联合典型序列和信道编码定理,TX(N,e)表示XN中典型序列的集合TY(N,e)表示YN中的典型序列集TXY(N,e)表示XN YN 中的典型序列集,26,联合典型序列和信道编码定理,引理1,上图中每列最多的点数,上图中每行最多的点数,27,联合典型序列和信道编码定理,引理2,左上角中联合典型序列点的密度,引理3,28,联合典型序列和信道编码定理,DMCP(y|x),令编码速率为R，则各码字的标号集为1,2NR。编码函数,译码函数,29,联合典型序列和信道编码定理,发送消息,平均误组率,发送m的误组率,对给定离散无记忆信道和任意e 0，若有一种编码速率为R 的码，在N足够大时，能使pee，就称R 是可达的。,30,联合典型序列和信道编码定理,定理5.3.1(Shannon信道编码定理)，给定容量为C的离散无记忆信道X，p(x|y)，Y，若编码速率RC，则R是可达的。,从XN中独立随机地选择2NR个序列作为码字，每个码字出现的概率为,X中任一元素独立、等概地出现。这种编码方法称作随机编码。,译码规则：对给定的接收序列y，若存在唯一,使,就将y译为m,31,联合典型序列和信道编码定理,两个以上m和y联合典型,译码错误,定义,的概率，当N 足够大，趋于0,32,联合典型序列和信道编码定理,使之极大化，用C 取代,所以必存在有一种码当N足够大时，其译码错误概率为0,33,错误概率上限,34,错误概率上限,并集限,发送特定码字xm时译码错误概率,平均译码错误概率,35,错误概率上限,并集限,36,错误概率上限,并集限,37,错误概率上限,巴塔恰亚（Bhattacharyya）限,示性函数,38,错误概率上限,巴塔恰亚限,巴塔恰亚距离,39,错误概率上限,例5.4.1 令M=2，且信道为BSC,40,错误概率上限,加拉格（Gallager）限,若,41,错误概率上限,加拉格（Gallager）限,定义,42,错误概率上限,43,错误概率上限,取,针对具体的码计算非常困难，我们转向估计所有可能的速率为R的、N长码集合的平均译码错误概率，使用随机编码的方法得到平均限，,44,错误概率上限,随机码集合平均错误概率上限,定理5.4.1 令信道转移概率为pN(y|x),N1。令QN(x)是XN上的任意概率分布。以概率QN(x)随机的选择长为N的码，对M2个消息进行编码。于是当传送任意消息m，1mM，并按最大似然译码法译码时，此消息的平均译码错误概率上限为：,45,错误概率上限,随机码集合平均错误概率上限,证明：N长输入序列集XN,若从中随机地选择任一序列作为待传送的M2NR个可能消息中某一消息的码字，则码集合,集合中元素个数KN,编码方法种数,随机码集合,码C出现的概率,46,错误概率上限,随机码集合平均错误概率上限,随机选择码字,随机码集合平均错误概率,47,错误概率上限,随机码集合平均错误概率上限,随机选择码字,随机码集合平均错误概率,48,错误概率上限,凸上,49,错误概率上限,以M替代M-1即可得到结论,50,错误概率上限,DMC信道,51,错误概率上限,要对和所有输入分布Q求指数项的最大值。令,可靠性函数,52,错误概率上限,在0RC范围内有界，恒正，单调减凸下函数,计算截止速率或临界速率,线性函数,非线性函数单调减凸下函数,53,错误概率上限,强噪信道,54,等能量正交编码,55,等能量正交编码,56,等能量正交编码,代入Gallager限,57,等能量正交编码,单位时间的信道容量为,58,等能量正交编码,59,等能量正交编码,-1.6dB,Shannon极限,60,等能量正交编码,
