信息论与编码5

《信息论与编码5》由会员分享，可在线阅读，更多相关《信息论与编码5（32页珍藏版）》请在金锄头文库上搜索。

1、第第5章章有噪信道编码有噪信道编码 高掺咙箭榷糙臆阂田杨饰肌遂尝叶乞陋乱陡等撕衅晦露图话路渝涧奋蛹茨信息论与编码5信息论与编码5第第5章章 有噪信道编码有噪信道编码 内容提要本章介绍了信道编码和译码的基本概念，介绍了两种常用的译码准则：最大后验概率译码准则和极大似然译码准则,还介绍了在这两种译码准则下错误概率的计算方法。本章还介绍了信道编码定理及信道编码逆定理，以及信息论中的一个重要不等式Fnao不等式。 巡磷遗鹏卢热颜跃署戏葱际务慷絮赠菌殆班拐堆舍犯抵俊喝攘嚎隐孝准苍信息论与编码5信息论与编码55 51 1 信道编码的基本概念信道编码的基本概念 将信道用图5-1所示的模型表示。信道编码器信道

2、信道译码器uxy图5-1 信道模型 信源输出序列u，经信道编码器编成码字x = f (u) 并输入信道，由于干扰，信道输出y，信道译码器对y估值得 = F (y) 。 信源编码以提高传输效率传输效率作为主要考虑因素，信道编码以提高传输可靠性传输可靠性作为主要考虑因素。这一章讨论信道编码的一些基本概念及信道编码定理。食惰锋就巳蹬锁蹋金蛔涨来峰藩毕钠凳桐勉猖枕陇囱睬奖护霸粮销剖聘脸信息论与编码5信息论与编码5【例例5.3】 逆逆重重复复码码 离散无记忆二进制对称信道，固有误码率为p (p0.5)，信源输出序列为三位二进制数字。编码规则：为提高传输效率，仅向信道发送一位，预先将信源输出序列进行择多编

3、码:图6-3 逆重复编码传输示意图 译码规则：将接收的一位符号重复三次译出，即若接收到1就译码为111，即若接收到0就译码为000。信源输出的三位符号中有两位或3位是1，信源序列编码为1，若三位符号中有两位或3位是0，就将此信源序列编码为0。磐楷锨共踢杭性淀骋痞苗屏悦吁侵科寡步肛失序堕掠僚瞳缎酷狸豫干牧拳信息论与编码5信息论与编码5计算差错概率pe ：分二步进行： （1）先设p = 0，计算这种编码方法带来的固有错误p1信道输入符号集X = 000,001,010,011,100,101,110,111判决输出符号集Y = 000,111译码规则因为后验概率 则出错概率 惑布妙切蚁管请优招锻吏

4、坝春勘慷铺孩淖铆遇霓婶陵番额谩翻膛已返燎篡信息论与编码5信息论与编码5假设8组输入序列是等概发送的，由于信道的对称性，两个估值序列也是等概分布的，则每个序列的平均错误概率为 ，误比特率 。（2）再设p0，计算由于信道噪声引起的错误概率p2因为每个序列有三位二进制数字，但只发送一位，这一位的出错概率为p，故序列差错概率为p，误比特率 。（3）总差错概率（误比特率）：【例例5.4】 奇偶校验码奇偶校验码 在信息序列后面加上一位校验位，使之模2和等于1，这样的编码称为奇校验码；若使模2和等于0，这样的编码就称为偶校验码，即每个码矢中1的个数固定为奇数或偶数。 贞咀痪造确砧宫纯澈敝驮画猾帖锗毛泞辙磊佯

5、遭岿符垫莉蛋空悠姆槐曲淫信息论与编码5信息论与编码55 52 2 译码规则及及错误概率概率 信道总不可避免会搀杂噪声，所以信息在信道传输过程中，差错是不可避免的。选择合适的译码规则可以弥补信道的不足。1最大后验概率译码准则最大后验概率译码准则发送码矢x xk ，其发送概率为q(x xk) ，通过信道转移概率为p(y yx xk)的信道传输，接收到矢量y y，信道译码器输出 通信过程可用图55所示框图表示。下面介绍两种典型的译码规则：藻狗奋跑匣涩彰瘁书误肝抠拔辉第玲亢的活搞蛇逛跃既洋侮迷灼捷广近貌信息论与编码5信息论与编码5 信源信道编码器信道信道译码器信宿干扰xky图55 通信过程框图 当估值

6、 xk 时，就产生了误码，用（xy）表示后验概率，则收到y估错的概率为 （5-2） 通信总希望错误概率最小，由式(5-2)可看出错误概率pe (xk ) 最小等同于后验概率（xky）最大，这就是最大后验概率译码准则最大后验概率译码准则。 涯锄赛颧白峪辖趣悲唾酋央暴什巳蚂客聋雄斩惺遭宵彩聪轮别峪偶砸记控信息论与编码5信息论与编码5根据概率关系式 （5-3） 根据式（5-3）后验概率（xy）最的就意味着p（x y）全概率最大，因此最大后验概率译码准则也称为最大联合概率译码准则最大联合概率译码准则。川沤肄谷感檄篆拽岸巢瞩斡刃姥倘郧部卿灵扑氦疽叉涨伙末讲却肌堂广剃信息论与编码5信息论与编码5【例例5.

7、5】信源分布 ，信道转移概率矩阵 ,信道输出符号Y = y1, y2, y3，按最大后验概率准则译码。(1)(1)根据p (xy) = p (yx) q(x) 算出全概率，用矩阵表示 (2)(2)根据 ，算出 （y） = 0.38 0.34 0.28 荤悉缝戊漓悔殉迪牙掉跺甸订涯碍态茬肤铭鹊坑前沥徒琼苏笨仍龋要峙匣信息论与编码5信息论与编码5(3)(3)再由 算出后验概率，用矩阵表示 (4)(4)按最大后验概率准则译码，在后验概率矩阵中，每列选一最大值（矩阵中带下划线的值），译为 (5)(5)若按最大联合概率译码准则译码，在全概率矩阵 p(xy)中每列选一最大值（矩阵中带下划线的值），也可译出

8、 悄厕苹晒绍曾欧民脾贵灶丑棠廊驳刚阶锗嘶尧犯菱横失酿系庙诣疾直叶肥信息论与编码5信息论与编码5在实际应用中，一般按最大信道转移概率来确定估值 ，即在收到矢量y后，在所有的xm (m =1, 2, , M) 中,选一个转移概率p(yxm)最大的xm值，作为对y的估值 = xk ，这一译码规则称为极大似然译码规则极大似然译码规则。 2极大似然译码准则极大似然译码准则 烂躯豁坊兜肃磕娶塘拥馈惭滩鞠洁迭病货炽香恃埠党绝区乱近扒缉邯玲瘴信息论与编码5信息论与编码53平均错误概率平均错误概率（5-4） ()=-=Mjkj1)(1y yx xy y季汹火绷分怔盐益拌丁愉芦朴裂专大段鲤童虎派薛釉氧谅畜凸藏意叉

9、姥京信息论与编码5信息论与编码5（1）求平均错误概率pe 根据式（6-4）得= 0.01+0.12+0.07+0.12+0.1+0.02 = 0.44 (2)当信源等概分布，按最大似然函数译码准则译码，例5.5已给出信道转移概率矩阵 在矩阵的每列中选一最大值(矩阵中带下划线的值)，译码为平均错误概率 【例例5.6】 计算例5.5的平均错误概率，若信源等概分布，对其译码，并求平均错误概率。 娄狭并嘴炉盟悠埂擞耻憾钓理驻凑取茬穷涡讶军镭馅烫楼豺铃逊阵怨柄亡信息论与编码5信息论与编码56 63 3 信道编码定理信道编码定理定理定理5.1 对于任何离散无记忆信道DMC，存在信息传输率为R，长为n的码，

10、当n 时，平均差错概率 pe exp- nE (R)0，式中E (R) 为可靠性函数，E ( R )在0 R C的范围内为正。 1 随机编码方法 选用长为n的定长码，共可构成k n个矢量，设有M个消息待传（M k n），每次随机地从k n个矢量中抽出M个矢量构成一个码集C（允许重复取）C = x1 , , x m , , x M共可构成k nM个这样的码集。由随机编码的构造方法，得到任何一个码字的概率相同，且相互独立。 上述定理也称有噪信道编码定理信道编码定理，即Shannon第二定理。 邀袜逛礼钮褂惯酸扼毯艳佛轰陛茄具鼎愈擒番瞒故继愤赵盘旱静昔佬书海信息论与编码5信息论与编码52Gallag

11、er上界因为上述按随机编码方法构成的码集是等概分布的，按照最大释然译码准则译码，在发送码矢xk时，要得到正确译码须满足 ，即 （5-5） 定义示性函数则发送码矢xk判错的概率为 （5-6） 岸栓想榴丸衔叶环潦驾兑唱谍制苔肺吓瘩披愚囤妊腾摔珊嘉灶挛地侦靴颠信息论与编码5信息论与编码5根据式(5-5)，当0 , 1时，下式成立用示性函数Ik (y)表示上式，即 （5-7） 将式(5-7)代入式(5-6)，得式中0 , 1，因为 , 都是任意数，可取 ，则有 （5-8） 凭颂瓷掏呸谜灾恳击嗡武汽折贴癌蝎铭涨远圆祁蘸紧侵溉镊会择湾畔惕了信息论与编码5信息论与编码53 随机编码错误概率上界随机编码错误概

12、率上界 Gallager限仅给出发送码矢xk时的错误概率上界，还要对全部码矢求平均，下面对上述的随机编码集合求平均。 对于随机编码，各码字等概且独立，有，对式(5-8)求统计平均值，得平均错误概率上界 (5-9) 物苟肥酝敛胜独绽铸浓啪忘丛侗睫蝴烟仿亡泣者坛择贡基岗狸克锤篡绘店信息论与编码5信息论与编码5后面一项 ，因为0 1，而x 是x的型凸函数，由型凸函数的定义知：函数均值 均值函数，即有 (5-10)因为 xm (m = 1,2, M) 都通过同一信道传输，故p(y yxm)值相同，记为p(y yx)，代入式（510）得 (5-11) 将式(5-11)代回式(5-9)，得 （512） 蔗

13、糕底颧乐刁且埠箭悠螺匹插和哮舜霹旱烧变疆佛室抑佛骄益郊疮扇江何信息论与编码5信息论与编码54离散无记忆信道DMC的错误概率上界 对于n维离散无记忆信道DMC，有 ，对于随机编码 ，将这两个关系式代入式(5-12)，有（513） 序列x = x1, xi, , xn 中的 xi,取自同一符号A=a1,a2,ak，故分布q(xi)相同, （514） 喻睫厚如职簿龄坑裔畸饶疥三诚在砍毅皱反伎缸俱盛亚惟泡呀倚钦焙维辛信息论与编码5信息论与编码5将式（514）代入式（513），得 （515） 5 可靠性函数E (R ) 信息传输率 ，则式(515)可写为： (5-16) 记则式(5-16)可写成 pe

14、exp -n -R + E0 (, q ) (5-17) 象铃瓦巨军停败簇滇皖叉局烟第钉篇微针谦施汪厚起铭滤掸傀护捏踊逆美信息论与编码5信息论与编码5对式(5-17)右边求极小值，即对指数-R + E0 (, q )求极大值,记这个极大值为则式(5-17)可写为pe exp -n E (R ) 称E (R )为可靠性函数可靠性函数,也称随机编码指数，它与信道转移概率p(yx)有关。 在0 R C的范围内，E (R )是下降的、下凹的正值函数，说明E (R )有界，这样，当 时，有exp -nE (R ) 0，从而pe C，不可能存在任何方法使差错概率任意小。抑荒冻茨措辖茎汐揩辖鹊证秘医莽巾喀苔

15、胃笺措己育侨铲谦烘摧枪又茧樱信息论与编码5信息论与编码5H (U) = H (U1L-1,UL) = H (U1L-1) + H (ULU1L-1) (5-26) 式中 U1L 1 = U1U2UL-1 (5-27) 另一方面根据熵的链规则有H (U) = H ( U1) +H (U2U1) +H (U3U1U2)+ +H (ULU1U2UL-1) H (U1U1U2UL-1)+ H (U2U1U2UL-1) + +H (ULU1U2UL-1)= L H (ULU1L 1 ) 因 ul 取自同一符号集聋跃间经楔讽糟断咨乖枚泡炸孪炬烤曰绪不沉翘汲啪汪称企屏频篮糠候惜信息论与编码5信息论与编码5将

16、式（527）代入式（526），得 (5-28) 式（528）表示 是L的单调降序列。而由熵的非负性，说明 有下界，其下界为H (U) ，即梭咱臃冷爵症章驰咀窥缎握唾撵玉充朔绵阔榜醉倪坑沪惰余骂映绰踊哇行信息论与编码5信息论与编码5 考虑图56所示的通信过程，矢量u、x、y、 中的所有元素都取自同一符号集A = a1, a2, , ak 。图56 通信过程信源信道编码器信道信道译码器信宿uxy干扰根据数据处理定理：不论经过何种数据处理均使信息量减少。 畅弦抱列症混曼逸几丫撤累恼唉盖喘荒薯鸡阻码菊密龙售年孟丘石拔裁荚信息论与编码5信息论与编码5由图56可见 , 对于离散无记忆信道，根据定理4.1有

17、Cn nC ,则 Cn nC （529） 另一方面 )(5-30) 将Fano不等式的矢量式（524）及式（529）代入式（530）得 H(U) - nC L H2 (pe) + pe log (k -1) (5-31) 细尖疑阜怯志砖烦妓僧秩跪浇匹镐德雹噎纲风泡厨炎福垛趾纵拍疤菊野瘪信息论与编码5信息论与编码5考虑到式（525），在L 条件下，H(U) = L H (U)，代入到式（531）并整理得H2 (pe) + pe log (k -1) H (U)即：H2 (pe) + pe log (k -1) （5-32）式中 为信息传输率。 从式(5-32)可看出，当RD C，右边为大于零的数

18、，说明差错概率有确定下界，不能以任何方式趋于零。 定理定理5.2 信道编码逆定理信道编码逆定理 信道容量C是可靠通信系统信息传输率的上界，当R C，不可能存在任何方法使差错概率任意小。累狐攻奏后蔷骄扮骋友婉久挛电管夷确哦级犀坦艾扯册临铝谎丛忽逆远论信息论与编码5信息论与编码5本本 章章 小小 结结 信道输入码矢xk x1, x2, , xM ，通过信道转移概率为p(yxk)的信道传输，输出矢量y，信道译码器估值为 F(y)， x1, x2, , xM 。 最大后验概率译码准则最大后验概率译码准则 （ y） （xmy） 极大似然译码准则极大似然译码准则 p（y ） p（yxm） 平均译码错误概率平均译码错误概率 蹭扰充政撇启针垦惺云港扫罪恰锣狐浦盖讫疡巴之拉滦体虎卧皇秤莱戴捧信息论与编码5信息论与编码5信道编码定理信道编码定理 对于任何离散无记忆信道DMC，存在信息传输率为R，长为n的码，当n 时，平均差错概率 pe exp- nE (R)0，式中E (R) 为可靠性函数，E ( R )在0 R C，不可能存在任何方法使差错概率任意小。Fano不等式不等式 H (XY ) H2 (pe) + pe log (k-1) 兆寄屈震铅挎氏署俩诲扛福婚饯妻通咋割楔枣鲜冷对巫艺危深泥考愁肾葫信息论与编码5信息论与编码5