2009-应用信息论基础-张林-Chap-4-57170296

第四章信道编码第四章信道编码ChannelCoding2009年11月23日2009年11月30日2009年11月30日©THU2009–Allrightsreserved本章要回答的核心问题本章要回答的核问题„在什么条件下，信息可以无差错的传输?„信道容量…一个信道单位时间可以传输的昀大信息量个信道单位时间可以传输的昀大信息量…但是并未保证信息传输的无差错性„例如：例如：…混乱打字机信道容量log13bit…在等概的时候达到容量…但是此时信道是有差错的：AA0.5AB0.5©THU2009–Allrightsreserved混乱的打字机本章学习的脉络本章学习的脉络©THU2009–Allrightsreserved4.1信道编码信道编码定义4.1:对于信道{X,q(y|x),Y}的信道编码包含以下要素…输入符号集合{1,2,…,M}…编码函数Xn：{12M}→Xn该函数为每一个输入符号产生了…编码函数X：{1,2,…,M}→X，该函数为每个输入符号产生了相应的信道编码码字Xn(1),Xn(2),…,Xn(m)，这些码字构成的集合称为“码本”称为“码本”…解码函数g：Yn→{1,2,…,M}，该函数为一个确定性判决函数，它将每一个可能的接收向量映射到一个输入符号。称这样的信道编码为(M,n)码称这样的信道编码为(,n)码©THU2009–Allrightsreserved信道编码的错误概率信道编码的错误概率„定义4.2:输入为符号i时的条件错误概率为Pr{()|()}(|())(())nnninnngYiXxiqyxiIgyiλ=≠==≠∑其中I(‚)为指示函数。(|())(())nyqyxiIgyi≠∑显然„定义4.3:(M,n)码的昀大错误概率为显然：若输入等概，则算术平均错误概„定义4.4:(M,n)码的算术平均错误概率为率等于译码错误概率；算术平均错误概算术平均错误概率小于等于昀大错误概率©THU2009–Allrightsreserved信道编码的码率信道编码的码率„定义4.5:(M,n)码的码率R定义为log/MRn=比特传输信道码的每个码信道码的每个码字母所能携带的昀大信息量„例4.1：…重复码，输入字母数M=2:{0,1}，重复n次，码率为1/n…二进制奇偶校验码，输入字母数M=2n-1:{x1x2x3…xn-1}，信道编码方案为：其中用于辨识码字中1的个数为奇数还是偶数c=x1x2…xnxparity，其中xparity用于辨识码字中1的个数为奇数还是偶数其码率为(n-1)/n©THU2009–Allrightsreserved信道编码的可达性信道编码的可达性„定义4.6:称一个码率R是可达的，若存在一个信道编码，其昀大差错概率在n→∞时趋近0。记号：今后我们为简化起见将使用(2nR)来代替今后，我们为简化起见，将使用(2nR,n)来代替©THU2009–Allrightsreserved信道的容量的另外一种定义信道的容量的另外种定义„定义4.7：一个信道的容量是该信道上所有可达码率的上确界，即supCR=关于本定义的评注：由可达码率R的定义，小于信道容量的码率可以获得任意小的差错概率本定义蕴涵着渐进无差错和码的存在性它对于通信的工程本定义蕴涵着渐进无差错和码的存在性，它对于通信的工程实践具有强大的作用回忆上一章我们讨论的信道容量定义C=maxI(X;Y)，它相对回忆上章我们讨论的信道容量定义(;)，它相对容易求解，但无法保证信道无差错传输香农第二定理：上述两种定义等价，本章的核心问题就是说明这个问题©THU2009–Allrightsreserved说明这个问题4.2经验主义式的设计验义式的设计„信道传输中如何减少差错？P„香农公式（提高抗干扰能力）：)1log()(0WNPWTCST+=βP)1log(0WNPWTS+C）：（提高提高抗干扰能力的方法o2.1C烈）加大带宽（信号变化剧）增加功率（提高信噪比）：（提高To)};({max.3.2YXIC延长时间（降低速率）烈）加大带宽（信号变化剧=W)};({max),(YXICxp功率约束=©THU2009–Allrightsreserved最简单的信道编码——重复码最简单的信道编码复码„昀直观的纠错方法就是：重复，增加冗余„例4.2:NATO规范WesternUnion规范AAlphaBBravoCCharlieDDeltaNNovemberOOscarPPapaQQebecAAdamsBBostonCChicagoDDenerNNewYorkOOceanPPeterQQeenDDeltaEEchoFFoxtrotGGolfQQuebecRRomeoSSierraTTangoDDenverEEasyFFrankGGeorgeQQueenRRogerSSugarTThomasGGolfHHotelIIndiaJJulietTTangoUUniformVVictorWWhiskeyGGeorgeHHenryIIdaJJohnTThomasUUnionVVictorWWilliamJJulietKKiloLLimaMMikeWWhiskeyXX-rayYYankeeZZuluJJohnKKingLLincolnMMaryWWilliamXX-rayYYoungZZero©THU2009–Allrightsreservedy例4.3：二进制信道的纠错编码的方法进制信道的纠错编码的方法„编码1：将每个输入元重复三次…纠正任位上的错误信息数据编码1编码2…纠正任一位上的错误…设码字记为as(c8,c7,c6,c5,c4,c3,c2,c1,c0)信息数据编码1编码2000000000000000000000001000000111001001001(876543210)…由编码方法知，信道无误时010000111000010010010011000111111011011011678ccc==…解码时若c=c≠c则判定c100111000000100100100101111000111101101101110111111000110110110012345cccccc====…解码时，若c8=c6≠c7，则判定c7位出错，即在同一组中，采用简单多数法进行判定110111111000110110110111111111111111111111…“择多译码”规则的依据：连续出现两个错误的概率远远小于出现一个错误的概率。©THU2009–Allrightsreserved于出现个错误的概率。例4.3：二进制信道的纠错编码的方法（续）„编码2：将每个输入字重复三次…纠正任位上的错误进制信道的纠错编码的方法（续）信息数据编码1编码2…纠正任一位上的错误…设码字记为as(c8,c7,c6,c5,c4,c3,c2,c1,c0)信息数据编码1编码2000000000000000000000001000000111001001001(876543210)…由编码方法知，信道无误时010000111000010010010011000111111011011011258ccc==…例发送码字010010010100111000000100100100101111000111101101101110111111000110110110036147cccccc====…例：发送码字010010010接收码字0111000101101111110001101101101111111111111111111118250,1ccc===825714036,1,00,1cccccc======位上有错，可以纠正。由大数判决规则知645,,ccc©THU2009–AllrightsreservedCaseStudy：二进制对称信道条件下重复码之性能y进制对称信道条件下复码之性能1次重复码将收到的符号判定为输入符号0p−10•将收到的符号判定为输入符号•误码率pe=ppp3次重复码•将发送的符号重复三次，简单多数原则判定输符11p−1pp平均错误概率：1入符号•发生错误Ù三次传输发生了两次错误•22322333(1)32epCppCpppp=−+=−pp平均错误概率：22n+1次重复码•重复2n+1次，出现至少n+1次错误的概率为误码率，n→∞时，pe→0•但是，码率R=1/(2n+1)也趋近于0©THU2009–Allrightsreserved()码率R－误码率Pe关系码率误码率e关系信道编码器信道信道解码器消息U消息的估计V码字Xn输出Yn信道编码器信道q(y|x)信道解码器„例4.4:二进制信源在二进制对称信道上的信道编码之R-Pe关系为：1()Hp1()1()eHpRHP−≤−其中p为二进制对称信道的差错概率。证明见板书证明见板书©THU2009–Allrightsreserved二进制信源＋二进制对称信道之“可达区域”进制信源进制对称信道之可域epe可达区域)3.0(1)(1)3.0,(:HpHRR−−≤′′可达数对•])(1[)](1[epHpHR−−=5.0•可达区域•4.03.0•不可达区域•••••2.0)(1pHR−=不可达区域R•••••••1.054321)(1pHR−=])3.0(1[)](1[HpHR−−=•©THU2009–AllrightsreservedR54321对于R-Pe关系的思考对于e关系的思考„上面的例子：)(1)(1)(1PHCPHpHR−=−−≤„变形，得到)(1)(1eePHPH−−11eCPHR−⎛⎞≥−⎜⎟⎝⎠„若RC，Pe严格大于零，R⎝⎠代表不可能进行无差错传输，即不可能进行可靠通信„若RC或R=C，Pe可以等于0所谓好码，就是相同误码率Pe条件下，具有大码率R的码P＝0时R可以无限增加吗？(ShannonTheoremII)©THU2009–AllrightsreservedPe＝0时，R可以无限增加吗？(—ShannonTheoremII)4.3信道编码定理（ShannonTheoremII）信道编码定（）„若信道的信息传输率R不大于信道容量C，总能找到一种适当的编码方式使得在信道上能无差错的以任意接近于适当的编码方式，使得在信道上能无差错的以任意接近于C的速率传输信息；如果信道的信息传输率R大于C，无差错传输信息是不可能的错传输信息是不可能的。„证明的思路（三明治证明）…任何信道都可以看成混乱打字机信道…任何信道都可以看成混乱打字机信道…对于典型输入序列xn，存在大约2nH(Y|X)个可能的输出，且它们等概所有能的典型输序有大…所有可能的典型输出序列有大约2nH(Y)个，这些序列被分为若干个不相交的子集…子集个数为2n(H(Y)-H(Y|X))=2nI(X;Y)，表示信道可以无误传递的昀大字母序列个数©THU2009–Allrightsreserved序列个数联合典型序列联合典序列„定义4.8：设(xn,yn)是长为n的随机序列对，其概率分布满足若满足以下条件则称其为联合典型序列若(xn,yn)满足以下条件，则称其为联合典型序列联合典型序列构成的集合记为联合典型序列构成的集合记为。©THU2009–Allrightsreserved联合渐进等同分割定理（JointAEP)联合渐进等同分割定（)„定理4.1:设(Xn,Yn)是长度为n的随机序列对，其分布满足则以下性质成立：则以下性质成立：ƒ当时，ƒƒ设，即、统计独立((,))()n((,))(1)22nHXYnHXYA−ε+εε−ε≤≤设，即、统计独立且具有与一致的边缘分布，则证明证明若n足够大，则见板书见板书©THU2009–Allrightsreserved联合典型序列概念的注脚联合典序列概念的注脚„联合分布中，大约有2nH(X)个典型X序列和2nH(Y)个典型Y序列其组合共有2nH(X)2nH(Y)2nH(X)+nH(Y)个但是其中联合典型的只有2nH(XY)„其组合共有2nH(X)‚2nH(Y)=2nH(X)+nH(Y)个，但是其中联合典型的只有2nH(