（计算机应用技术专业论文）受限编码信道容量的研究.pdf

r e s e a r c ho nt h ec h a n n e lc a p a c i t yo fc o n s t r a i n e dc o d e b y g o n gh u i y e b e ( l a n z h o uu n i v e r s i t yo ft e c h n o l o g y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro f e n g i n e e r i n g 1 n c o m p u t e ra p p l i c a t i o nt e c h n o l o g y i nt h e g r a d u a t es c h o o l o f l a n z h o uu n i v e r s i t yo f t e c h n o l o g y s u p e r v i s o r p r o f e s s o rz h a n gy u a n p i n g m a y , 2 0 1 1 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 玳慧矽十 日期：如“年6 月 ie t 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同 时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据 库，并通过网络向社会公众提供信息服务。 日期：知f 阵6 月f 日 日期：如f 年厶月6e l 硕十学何论文 目录 摘要i a b s t r a c t i i 插图索引i i i 第1 章绪论1 1 1 课题研究的背景及意义1 1 2 受限编码信道容量的研究现状1 1 3 本文的研究内容和组织结构3 第2 章信道容量5 2 1 信道定义及分类5 2 2 信道编码5 2 2 1 信道编码的基本原理一5 2 2 2 信道编码的实质6 2 2 3 信道编码的作用7 2 2 4r l l ( d ，k ) 序列：一7 2 3 信道容量8 2 4 离散信道的统计特性及其分类8 2 4 1 按照信道的统计特性即条件概率p ( y x ) 的不同分类2 刀8 2 4 2 离散信道按照输入以及输出进行分类9 2 5 本章小结一l0 第3 章信道容量的计算“ 3 1 容量的计算方法1 l 3 1 1 方法一概率计算法：1 l 3 1 2 方法- n 用信道容量的公式1 2 3 1 3 方法三利用转移矩阵的方法1 3 3 2 特定的受限编码信道容量1 4 3 2 ，1 一维受限系统的信道容量一1 4 3 2 2 二维r l l ( 1 ，0 0 ) 受限系统础1 5 3 2 3 求解受限系统缸2 信道容量上下界所采用的方法一1 6 3 2 4 求解2 系统信道容量所遇到的困难1 7 3 2 5 读写独立记忆系统( r w i m ) 1 7 3 3 本章小结1 8 第4 章信道容量的证明19 4 1 已有的结果2 0 受限编码信道容量的研究 4 2 信道容量的证明2 l 4 2 1 信道容量为正2 1 4 2 2 信道容量为零2 2 4 2 3 主要结果一2 4 4 2 4 结果分析2 7 4 3 本章小结一2 7 结论和展望2 8 参考文献一3 0 致谢3 3 附录a 攻读学位期间发表的论文3 4 硕+ 学何论文 摘要 二维受限编码无处不在，在磁存储、光存储以及数字记录中都要用到受限编码。二 元序列受限编码中最为常见的是所谓e l l ( , ，k 1 序列，即相邻两个1 之间间隔至少有d 个0 最多有k 个0 。在信息论中信道容量是衡量信道性能的重要参数，反映了信道所能传输的 最大信息量。但是对于固定的信道，总存在一种信源，使信道平均传输一个符号在接收 端获得的信息量最大，即接近信道容量。这样如何有效的进行编码以达到或最大的接近 信道的最大传输速率是我们研究的重要方面。所以对二维受限编码信道容量的判断也尤 为重要，若二维受限编码在信道传输中所达到的最大信息量为零，即受限编码所包含的 信息量为0 ，则这一编码是毫无意义的。因此在编码过程中必须判断受限编码的信道容 量是否在正的区域。 文中介绍了受限编码信道容量的概念及特性，总结了计算信道容量的三种方法，并 对其方法进行了分析。在这些理论的基础上利用了扫描方法对二维非对称受限编码的信 道容量是否为正进行判断。若满足限制( d l ，k l ，么，乞) 矩阵中的每个位置都可以通过已知 的标志来决定并且被扫描，则限制( 盔，岛，攻，红) 的信道容量为0 。通过对特定二维受限编 码信道容量的证明，验证了扫描方法比依据信道容量定义的组合方法更为有效。同时采 用证明信道容量大于零常用的方法，找到满足( 西，毛，以，乞) 受限的两个m x ，l 矩阵，若两 1 矩阵在各种变形下都满足( d l ，墨，d 2 ，如) 限制，则信道容量q 幽矗岛上。这一方法对信 m 刀 道容量为正的区域进行扩展。 关键词：二维受限编码；非对称限制；信道容量；扫描方法；正的容量区域 a b s t r a c t c o n s t r a i n e db i n a r ys t r i n g so rw o r d sa r eu b i q u i t o u si nc o d e sf o r m a g n e t i ca n do p t i c a l r e c o r d i n g t h em o s tc o m m o nc o n s t r a i n e dc o d e si ss o c a l l e d r l l ( d ，k ) c o d e sw h i c ha r et h e c o d e so v e rb i a n r ya l p h a b e t ( 0 ，1 ) w h e r ed ( k ) i st h em i n i m u m ( m a x i m u m ) p e r m i t t e dn 啪b e r o f0 s s e p a r a t i n gc o n s e c u t i v e1 s i ni n f o r m a t i o nt h e o r yc h a n n e lc a p a c i t yi st h ei m p o n a i l t p a r 锄e t e r st om e a s b r ec h a n n e lp r o p e r t i e s ，r e f l e c t i n gt h ec h a n n e lc a nt r a n s f e rt h eb i g g e s t i n f o r m a t i o n b u tf o rf i x e dc h a n n e l ，t h e r ei s a l w a y sas o u r c et h a tg a i n st r a n s m i s s i o nb i g g e s t i n f o r m a t i o nd o s i n gt oc h a n n e lc a p a c i t y s oh o we f f e c t i v ec o d i n gt oa c h i e v eo fd o s et o t h e c n 锄e lc a p a c i t yi sa ni m p o r t a n ta s p e c to f0 1 1 1 s t u d y s or e s e a r c ho n t h ec h a n n e lc a p a c i t yo f t w o 。d i m e n s i o n a lc o n s t r a i n e dc o d e i s v e r yi m p o r t a n t i ft r a n s m i s s i o ni n 硒咖a t i o n o f t w o - d i m e n s i o n a li nc h a n n e li sz e r o ，t h e nt h ec o d i n gi s p o i n t l e s s t h e r e f o r e ，i nt h ec o d i n g p r o c e s sm u s td e t e r m i n ew h e t h e rt h ec h a n n e lc a p a c i t yo ft w o d i m e n s i o n a lc o n s t r a i n e dc o d ei s p o s i t i v eo ri sz e r o t h ec o n c e p ta n df e a t u r e so ft h ec h a n n e lc a p a c i t yo fc o n s t r a i n e dc o d ea r ei n t r o d u c e di l l t h i sp a p e r ，a n dt h r e em e t h o d so fc a l c u l a t i o nc h a n n e lc a p a c i t ya r e 跚m m a d z e d t bd e t e r m i l l e w h e t h e rt h ec h a n n e lc a p a c i t yo ft w o - d i m e n s i o n a la s y m m e t r i cc o n s t r a i n e dc o d e i sp o s i t i v eo f i s z e r o ，s c a n n m gm e t h o di sp r o p o s e do nt h eb a s i so ft h e s et h e o r i e s i fe a c h1 0 c a t i o ni i l ( 吐，向，d 2 ，如) 。c o n s t r a i n e dm a t r i xc a nb ed e t e r m i n e db yk n o w ns i g n sa n di sa b l et ob es c a 肌e d t h e nc h a n n e lc a p a c i t yi s0 s o m es p e c i f i cc o n s t r a i n t sa r eu s e dt o v e r i f ys c a n n i n gm e t h o di s m o r ev a l i d a t e dt h a nc o m b i n a t o r i a lm e t h o d t h ec o m m o nt e c h n o l o g y f o rp r o o f i n gc h a l l l l e l c a p a c i t yp o s i t i v e i s u s e dt of i n dt w o d i s t i n c tmxn m a t r i c e s s a t i s f y i n g ( 吐，盔，吐，如) c o n s t r a i n t s i ft h e s et w om a t r i c e ss a t i s f y ( d ik l ，d 2 ，七2 ) c o n s t r a i n t su n d e re a c h t r a n s f b 肋a t i o n ，t h e nt h ec h 锄e lc 印a c i t v c a , , k , , d 2s , 2 历1 i 啦sm e t h o di su s e dt oe x p a i l d p o s i t i v ec a p a c i t yr e g i o n k e yw o r d s ：t w o d i m e n s i o n a lc o n s t r a i n e d s c a n n i n gm e t h o d ；p o s i t i v ec a p a c i t yr e g i o n c o d e ；a s y m m e t r i cc o n s t r a i n t s ；c h a n n e lc a p a c i t y ； i l 硕十学何论文 插图索引 图2 1 数字通信系统模型6 图2 2 数字通信系统的简化模型6 图2 3 数字通信中的数字传输8 图2 4 离散信道的模型9 图3 1r l l ( d ，k ) 序列的f s t d 描述1 4 图4 1 满足( d ，d + 1 ) 限制的阵列的扫描2 3 图4 2a 、b 为两个满足受限条件( 4 d + 3 ) ( 2 d + 2 ) 的o 1 矩阵2 4 图4 3a 、b 为两个满足受限条件的7 行4 列矩阵2 5 图4 4a 、b 为满足限制的6 行5 列矩阵一2 5 图4 5 满足( d ，2 d ，d ，d + 1 ) 限制的阵列的扫描2 6 硕十2 伶论文 第1 章绪论 受到噪声干扰的信道是比较常见的，它使得传输的信息发生差错，如高斯信道。但 还有一类常见的信道，称之为受限信道，这类信道对于许可的输入序列有一定的限制。 为了在数据序列中获得信号的同步，必须对信道中所传输的数据序列加以限制，从而传 输可靠有效的数据。随着光存储技术的不断发展，许多先进的光存储和数字记录信道被 相继提出，多维光存储已成为提高信息记录密度和读写速度的重要途径，为了满足特定 的多维光存储信道的需要，研究人员提出了相应的二维受限编码。受限编码无处不在， 磁存储与光存储以及数字记录中都有使用到受限编码【l 】，因此对受限编码信道容量的研 究是十分必要的。本章节简要的介绍了受限编码信道容量研究背景及意义，国内外研究 现状，最后介绍了研究内容以及章节安排。 1 1 课题研究的背景及意义 二维受限编码信道容量的研究涉及到矩阵分析、图谱、信息论、组合以及数值计算。 二维受限编码无处不在，在磁存储、光存储以及数字记录中都要用到受限编码。为了提 高信息存储密度以及读写速度，提出了二维游程受限编码。所谓二维游程受限编码是指 在编码序列中连续相同码元的长度是受到限制的。二元序列受限编码中最为常见的是所 谓r l l ( d ，k ) 序列，即相邻两个l 之间间隔至少有d 个0 最多有k 个0 。在信息论中信道 容量是衡量信道性能的重要参数，反映了信道所能传输的最大信息量，其大小与信源无 关。但是对于固定的信道，总存在一种信源，使信道平均传输一个符号在接收端获得的 信息量最大，即接近信道容量。所以如何有效的进行编码以达到或最大的接近信道的最 大传输速率是我们研究的目标之一。最早在文献 2 】证明了二维游程受限编码信道的存 在，并做出了相应的计算。同样对二维受限编码信道容量的判断也尤为重要，若二维受 限编码在信道传输中所达到的最大信息量为零，即受限编码所包含的信息为0 ，则这一 编码是毫无意义的。因此在编码过程中必须判断受限编码的信道容量是否在正的区域。 1 2 受限编码信道容量的研究现状 在1 9 8 1 年n o r r i s 和b l o o m b e r g t 3 1 已经定义出了一维r l l ( d ，k ) 受限码的容量，其中醴： 是两个1 之间间隔至少有d 个0 的一维受限系统， c ：印( 霹：) = l o g ：a( 1 1 ) 同时利用代数证明九l 是下列多项式的根。 l , k ( x ) = ；篡五：1 k 0 0 ( 1 2 ) 受限编码信道界量的形f 究 接着，在1 9 8 7 年a s h l e y 和s i e g e l 4 】证明了当d l ，有 c 印( 岛岛) = c 印( 研州) ( 1 3 ) 同样在文献 4 】中所用到的方法是组合和代数，并很容易得出下列结果 唧( 霹翟) c a p ( s ；1 ) ( 1 4 ) 在文献【5 】中得出一维( o ，1 ) 受限编码的信道容量是 c v 0 0 0 1 ) ：1 0 9 2 ( 半) = 0 6 9 4 2 4 2 ( 1 5 ) 同时在文献 6 】中给出了二维( o ，1 ) 受限编码信道容量精确的估计值 0 5 8 7 8 9 11 6 1 7 7 5 c ：7 0 5 8 7 8 9 11 6 1 8 6 8 ( 1 6 ) 而在1 9 9 6 年a s h l e y 和m a r c u s t i l l - 算出了一维r l l ( 1 ，2 ) 受限码的信道容量为 c a p ( s 8 ) = 0 4 0 5 7 ( 1 7 ) 近年来有关二维受限编码信道容量的研究也越来越多。s h a n n o n 定义其容量为 1 c a p ( s ) = l i m 二l 0 9 2n ( m ，咒，s )( 1 8 ) i ? 1 1 , i - - - i 啪m 以 其中m ? l 为s 的线性排列个数，n ( m ，n ，s ) 表示满足限制的0 1 矩阵的个数。在二维受限 编码中二维r l l ( 1 ，o o ) 这种受限系统被广泛的应用。在统计学中，这个受限系统被称为 h a r d - s q u a r e 系统或者h a r d c o r el a t t i c eg a s 系统【8 1 1 1 ，该系统要求水平与竖直方向上都不能 有连续的1 存在。1 9 8 8 年w e b e r 首先考虑到这一系统的容量问题，在文献 1 2 1 中利用求 解转移矩阵最大特征值的方法，给出系统的容量满足 1 4 5 2 却1 5 5 4 ( 1 9 ) c a p ( s 知, ) 其中表示h a r d s q u a r e 系统的信道容量。e n g e l 1 3 1 利用同样的方法将上下界缩为 1 5 0 3 0 4 8 0 8s2 卸( 1 1 3 1 6 0 7 6 7 ( 1 1 0 ) 1 9 9 8 年c a l k i n 和w i l l t 4 】进一步推进了容量的上下界 0 5 8 7 8 9 1 2 铆( & s0 5 8 8 3 3 9 ( 1 11 1 ) 在2 0 0 1 年n a g y l l 5 】将系统容量的上下界精确到小数点后9 位 o 5 8 7 8 9 11 6 1 7 7 5 2 c 印( 矗s0 5 8 7 8 9 11 6 1 8 6 8 ( 1 1 2 ) 同时给出了三维的r l l ( 0 ，1 ) 的信道容量为 0 5 2 2 5 1 7 4 1 8 3 8sc ( s ) 0 5 2 6 8 8 0 8 0 4 7 8 2 5 ( 1 1 3 ) e n g e l ，c a l k i n 和w i l f 等所用到的方法是转移矩阵技术【1 6 1 。二维受限编码中有关读写独 立记忆系统( r w i m ) 也有许多研究，该系统由f r e i m a n 和w y n d l 7 】在1 9 6 4 年首先提出。 k a u t z 1 8 】给出了此记忆系统的容量为 l o g ；= 0 6 9 4( 1 1 4 ) 比特秒其中妒是斐波那契序列的最大特征值。在文献 1 9 1 5 b 有关于重写方面的研究。在 1 9 9 5 年，c o h n 2 0 】给出了读写独立记忆系统的容量为 0 5 0 9 c 0 5 6 1 ( 1 1 5 ) 2 硕十何论文 2 0 0 4 年由g o l i n 等得出最紧凑的读写独立记忆的受限编码的信道容量上下别2 1 】 0 5 3 5 0 0 c o 5 5 2 0 9 ( 1 1 6 ) w e e k s 和b l a h u t 6 】首先提出棋盘限制的编码，该编码是二维的( o ，1 ) 排列，要求每个“l 周围都有特定形式的“0 ”。最近i t o 【2 2 1 给出了当n 2 时，n 维受限系统。s d 。n 。) 的情况 ( 1 ) 对于d 0 ，k d ，当且仅当k = d + l 时卸( 剐) = o 。 ( 2 ) 对于d 0 ，k d ，当且仅当k 2 d 时l i m c 印( 碰翟) = o 。 在文献 2 3 q an a g y 和z e g e r 对二维棋盘限制编码的信道容量的特性进行了研究。 信道容量的计算从图论的角度实际上是对于任意给定的正整数k ，计算特定图中长 度为k 的路径数目，以及分析它的渐近性。受限编码的信道容量研究可以转化为一些特 定的图谱问题研究【2 4 1 。而通过计算图的邻接矩阵的最大特征值可以得出受限系统的信道 容量。受限编码的信道容量研究可以转化为一些特定图的问题研究。编码的目的就是传 输或者存储可靠的数据保证正常通信，所以判断受限编码信道容量是否在正的区域非常 重要。 最后有关二维受限编码信道容量证明也是常见的。k a t o 和z e g e r 证明了二维对称受 限编码信道容量的存在，并采用代数与组合的方法证明了d l ，当且仅当k = d + 1 时， q 。i = 0 。而c e n s o r 和e t z i o n l 2 5 通过采用扫描方法对c 加l = o 进行了证明，并对一些特 定的模型如三角形，六边形，正方形等受限编码的信道容量进行了证明。k a t o 等人在文 献【2 6 】中给出了有关非对称二维受限编码信道容量的一些特征，判断出在满足一些特定 受限条件下的信道容量是否在正的区域。 1 3 本文的研究内容和组织结构 本课题通过对信道容量的定义以及特征的描述，以及对具体的一维、二维受限编码 信道容量的分析，总结出求解二维受限编码信道容量的方法，并分析了其优劣，提出了 判断受限编码信道容量是否在正的区域的方法。通过对具体的受限编码进行分析，根据 信道容量的定义，利用扫描方法以及代数与组合方法来证明信道容量为零，同时利用证 明信道容量大于零常用的技术，对满足特定受限条件下的信道容量进行证明，判断其信 道容量是否为正，从而对信道容量为正的区域进行扩展。 本文共分四章，各章主要内容组织如下： 第l 章绪论简要的介绍了受限编码信道容量研究背景及意义，国内外研究现状，最 后介绍了研究内容以及章节安排。 第2 章主要介绍了信道、信道容量的概念及特性、信道编码以及离散信道的简单模 型。 第3 章根据信道容量的概念及特性，总结了计算信道容量的三种方法，并描述了具 体二维受限编码信道容量的求解，并对其方法进行了分析。 3 受限编码信道容帚的研究 第4 章利用扫描方法以及代数与组合方法来证明信道容量为零，同时利用证明信道 容量大于零常用的方法，对满足特定受限条件下的信道容量进行证明，判断其信道容量 是否为正，对信道容量为正的区域进行扩展。 硕十学位论文 2 1 信道定义及分类 第2 章信道容量 定义2 1 【2 7 】信道：( 1 ) 传递消息的通道，广义上是指从信源到信宿间传递物理信号的 媒质和设施。( 2 ) 信道的种类很多，如电信中常用的架空明线、同轴电缆、波导、光纤、 传输电磁波的空间等都是信道。信道的任务是以信号方式传输信息和存储信息。 定义2 2 【2 8 】受限信道：对于许可的输入序列有一定的限制的信道。 信道的分类： 1 、根据载荷消息的媒体不同分为：邮递信道、电信道、光信道、声信道 2 、根据信道的用户的多少：两端( 单用户) 信道、多端( 多用户) 信道 3 、根据信道输入端和输出端的关联：无反馈信道、反馈信道 4 、根据信道的参数与时间的关系：固定参数信道、时变参数信道 5 、根据输入和输出信号的特点：离散信道、连续信道、半离散半连续信道、波形 信 6 、根据信道的统计特性是否随时间变化分为： ( 1 ) 恒参信道( 平稳信道) ：信道的统计特性不随时间变化。卫星通信信道在某种意 义下可以近似为恒参信道。 ( 2 ) 随参信道( 非平稳信道) ：信道的统计特性随时间变化。如短波通信中，其信道 可看成随参信道。 2 2 信道编码 2 2 1 信道编码的基本原理 一般来说信道编码又称为纠错编码或差错控制编码。信息在传输过程中主要是考虑 可靠性问题。而不同的用户对可靠性的要求是不同的。可靠性与信道的特性及其传输中 所受到的干扰有关，因此要提高可靠性。但是信道的改善程度有限，所以主要是采用合 理的信道编码，降低误码率，从而提高系统的可靠性。一般数字通信系统的模型如图 2 1 所示： 受限编码信道容最的研究 信源编信道编 心 波 一警 4 码器码器 形 信 信源编 i 一 信道编 + 叫蛆卜一 道 码器码器 裔 图2 1 数字通信系统模型 在通信过程中，信源的定义：( 1 ) 消息的源，通常指向通信系统提供消息的人、设备 或事物。( 2 ) 信源输出的是以符号形式出现的具体消息，它载荷信息。( 3 ) 信源输出的消 息有多种形式：a 例如，从消息在时间上和幅度上的分布情况这一角度，可分为离散信 源( d i s c r e t es o u l c c ) 和连续信源( c o n t i n u o u ss o u r c e ) 。b 前者指信源发出的消息在时 间和幅度上都是离散分布的，如字母、文字、数字等符号组成的符号序列或单个符号c 后 者指在时间和幅度上都是连续分布的，如话音、图像等。信源编码器输出为携带信息的 二进制序列。调制器是将包含信息的二进制序列转换成适合信道传输的各类信号。由于 我们关心的是差错控制系统中使用的信道编码器和信道译码器，为了研究方便，可将上 述模型进一步简化成下图2 2 所示的简化模型。在此模型中将信源编码器归入到信源部 分，且假定它的输出是一个码元见彼此无关且出现概率相等的二进制序列，称为信息序 列m ；信道是包括调制器、实际信道( 即传输媒质) 和解调器在内的广义的信道，又称 编码信道，它的输入是信道编码器输出的码字序列c ，在没有特别说明的情况下，其输 出r 通常也是二进制序列；信道译码器输出的是信息估值序列m ；最后一部分信宿 则包括信源译码器和用户，它可以是计算机或人。 图2 2 数字通信系统的简化模型 2 2 2 信道编码的实质 信道编码的实质：是在信息码中增加一定数量的多余码元( 称为监督码元) ，使它们 满足一定的约束关系，这样，由信息码元和监督码元共同组成一个由信道传输的码字。 6 硕十学何论文 一旦传输过程中发生错误，则信息码元和监督码元间的约束关系被破坏。在接收端按照 既定的规则校验这种约束关系，从而达到发现和纠正错误的目的。信息通过信道传输， 由于物理介质的干扰和无法避免噪声，信道的输入和输出之间仅具有统计意义上的关 系，在做出唯一判决的情况下将无法避免差错，其差错概率完全取决于信道特性。因此， 一个完整、实用的通信系统通常包括信道编译码模块。视频信号在传输前都会经过高度 压缩以降低码率，传输错误会对最后的图像恢复产生极大的影响，因此信道编码尤为重 要。 2 2 3 信道编码的作用 一是使码流的频谱特性适应通道的频谱特性，从而使传输过程中能量损失最小，提 高信号能量与噪声能量的比例，减小发生差错的可能性； 二是增加纠错能力，使得即便出现差错也能得到纠正。 定理2 3 【2 9 1 ( 香农第二定理) ：若有一离散无记忆平稳信道，其容量为c ，输入序 列长度为，只要待传输的信息率r c ，总可以找到一种编码，当足够长时，译码 错误概率 c 时，任何编码的必大于零， 当专o o 时，专l 。 与无失真信源编码定理( 香农第一定理) 类似，香农第二定理只是一个存在定理， 它指出信道容量是一个临界值，只要信息传输率不超过这个临界值，信道就可几乎无失 真地把信息传送过去，否则就会产生失真。即在保证信息传输率低于( 直至无限接近) 信道容量的前提下，错误概率趋于“o ”的编码是存在的。虽然定理没有具体说明如何 构造这种码，但它对信道编码技术与实践仍然具有根本性的指导意义。编码技术研究人 员在该理论指导下致力于研究实际信道中各种易于实现的具体编码方法。二十世纪六十 年代以来，这方面的研究非常活跃，出现了代数编码、循环码、卷积码、级联码、格型 码等，为提高信息传输的可靠性做出了重要贡献。 2 2 4r l l ( d ，k ) 序列： 文中主要研究的是游程受限编码，所谓“游程”，即指编码序列中连续相同码元的长 度。游程长度限制是光存储信道的一种典型限制，即在存储信息时，连续出现的相同码 元的长度不能太短，也不能太长。 受限序列对于输入符号序列有一定的限制，表现在禁止具有某些类型数据序列的输 入。所以，要求一种数据转换编码( d t c ) ，它的主要任务是使得信源输出的任意序列转 换成为一种满足特定受限的编码序列，从而使得某些序列不允许出现，进而可以在受限 信道上传输。而数据转换编码也可以被认为是一种受限系统。而一个受限系统可以通过 有向标号或称有限状态转移图来表示。下图2 3 表示数字通信中的数据转换编码。 为了在数据序列中获得信号的同步，必须对信道中所传输的数据序列加以限制，从 而传输可靠有效的数据，这就有了受限编码。受信道限制的二元序列中最常见的是所谓 受限编码信道容帚的研究 r l l ( d ，k ) 序列。二元r l l ( d ，k ) 序列是一个l h ( o ，1 ) 组成的序列，其中d 表示相邻的两个l 之间o 的最小个数。k 表示相邻的两个1 之间0 的最大个数。k 用于在记录波形时提供 足够的信号交换，保证时钟同步，以防止时钟漂移。d 用于防止码间干扰。 图2 3 数字通信中的数字传输 2 3 信道容量 定义2 4 【2 7 】信道容量：信道容量是信道的一个参数，反映了信道所能传输的最大信 息量，其大小与信源无关。对不同的输入概率分布，互信息量一定存在最大值，则这个 最大值称为信道容量。一旦转移概率矩阵确定后，信道容量也完全确定了。尽管信道容 量的定义涉及到输入概率分布，但信道容量的数值与输入概率分布无关。将不同的输入 概率分布称为试验信源，对不同的试验信源，互信息也不同。其中必有一个试验信源使 互信息量达到最大，这个最大值就是信道容量。对于固定的信道，总存在一种信源( 某 种输入概率分布) ，使信道平均传输一个符号在接收端获得的信息量最大，也就是说对 于每一个固定信道都有一个最大的信息传输速率，这个最大传输率即为信道容量c 。信 道容量有时也表示为单位时间内可传输的二进制位的位数( 称信道的数据传输速率，位 速率) ，以位秒( b s ) 形式予以表示，简记为b p s 。 信道容量的物理意义： l 、信道容量c 只是信道传递概率函数，只与信道的统计特性有关，而与输入信源 的概率分布无关。即对于一个特定的信道，其信道容量c 是确定的，是不随输入信源的 概率分布变化而改变的。 2 、信道容量c 取值的大小，直接反映了信道质量的高低。 3 、信道容量是完全描述信道特性的参量，是信道能够传输的最大信息量。 4 、信道实际传输的信息量必然不大于信道容量。 2 4 离散信道的统计特性及其分类 2 4 1 按照信道的统计特性即条件概率p ( y x ) 的不同分类【2 7 】 图2 4 为离散信道模型，条件概率p ( y 功反映了信道的统计特性，描述了输入信 号和输出信号之间统计依赖关系。按照信道的统计特性即条件概率e ( y x ) 的不同。离散 信道又可分成三种情况：( 1 ) 无干扰信道，( 2 ) 有干扰无记忆信道，( 3 ) 有干扰有记忆信道。 硕十。学何论文 这三种情况表示如下： x ! 二卜_ y x 2 ( x i ，x 2 ，x n ) p ( y x ) y 2 ( y l ，y 2 y n ) x ：【a l 确】 p ( y x ) ：l y ：【b l ，b s 】 图2 4 离散信道的模型 ( 1 ) 无干扰( 噪声) 信道 信道中没有随机性的干扰或者干扰很小，输出信号y 与输入信号x 之间有确定的、 一一对应的关系。即： y = f ( x )( 2 1 ) p ( y x ) = 1 y = f ( x ) ( 2 2 ) ( 2 ) 有干扰无记忆信道 a 信道输入和输出之间的条件概率是一般的概率分布。 b 如果任一时刻输出符号只统计依赖于对应时刻的输入符号，则这种信道成为无记 忆信道。 p ( y x ) = p ( y i 儿一执i x l x 2 如) = 兀尸( 乃玉) ( 2 3 ) ( 3 ) 有干扰( 噪声) 有记忆信道 实际信道往往是既有干扰( 噪声) 又有记忆的这种类型。例如在数字通信中，由于信 道滤波使频率特性不理想时造成了码字之间的干扰。在这一类信道中某一瞬间的输出符 号不但与对应时刻的输入符号有关，而且还与此以前其他时刻信道的输入符号及输出符 号有关，这样的信道称为有记忆信道。 2 4 2 离散信道按照输入以及输出进行分类 单符号离散信道：若输入符号为x ，取值于 q ，a ，】。输出符号为】r ，取值于 6 l ，包】则为单符号离散信道。 条件概率： p ( y x ) = p ( y = 屯肛= t l i ) = p ( b ：l a ，) ( 2 4 ) 这一组条件概率称为信道的传递概率或转移概率，可以用来描述信道干扰影响的大小。 由转移概率所得到的矩阵称为转移矩阵。 9 受限编码信道容母的研究 一般简单的单符号离散信道可以用 x ，p ( y x ) ，明三者加以描述。其数学模型可以用 概率空间 x ，p ( y l x ) ，y 】描述。 一般离散单符号信道的传递概率可用矩阵形式表示，即 p = p ( b l l a 。) p ( b j a ，) p ( b , a 。) p ( b , a ：) 尸( 6 2 口：) p ( a , a ：) p ( 6 l q ) p ( b ：a ，) e ( a , l a ，) ( 2 5 ) 矩阵p 完全描述了信道的特性，可用它做为离散单符号信道的另一种数学模型形 式。p 中有些是信道干扰引起的错误概率，有些是信道正确传输的概率。所以该矩阵又 称为信道矩阵( 转移矩阵) 。 2 5 本章小结 本章中主要介绍了信道容量的概念及特性，信道编码以及离散信道的简单模型。从 中可以得出信道容量c 只是信道传递概率函数，只与信道的统计特性有关，而与输入信 源的概率分布无关。即对于一个特定的信道，其信道容量c 是确定的，是不随输入信源 的概率分布变化而改变的。编码的目的是在保证可靠传输的前提下，使编码的信道容量 最大限度的接近信道所能达到的最大传输速率。 l o 硕+ 学何论文 皇曼鼍i i 一 ii ii i 一。一。曼曼曼曼曼量曼鼍曼皇曼皇曼 3 1 容量的计算方法 第3 章信道容量的计算 3 1 1 方法一概率计算法 通信的目的是为了获得信息，为度量信息的多少( 信息量) ，用到了熵这个概念。 而在信道容量中涉及到的两个熵：l 、发射端处信源即发射端信源的不确定度。用h ( x ) 表示，即在接收到输出y 以前，关于输入变量x 的先验不确定性，称为先验熵。2 、接 收端处在接收信号条件下的发射端信源熵一就是在一定程度上获得了发射端信源的信 息，这部分信息的获取是通过信道的传输信号带来的。用h ( x m 表示，即信道接收端 接收到输出符号后，关于输入符号的信息测度。研究信道的目的是要讨论信道中平均每 个符号所能传送的信息量即信息传输率r 。 定义3 1 【3 0 】信息量：i ( x ；y ) 就是接收到符号y 后平均每个符号获得的关于x 的信 息量。互信息量表示先验的不确定性减去尚存的不确定性，就是收信者获得的信息量 所以： j ( 石；y ) = h ( x ) - h ( x y ) ( 比特符号)( 3 1 ) 信道中每秒平均传输的信息量。其中： 日( x ) 2 善p ( a t ) 1 。g 南一p ( z ) l o g p ( x ) ( 3 2 ) 职；y ) 2 手军p ( 训( 栅) 2 莩军p ( 训1 。g 掣 ( 3 3 ) 定义3 2 【3 0 1 信道容量c ：( 利用概率的方法来定义) 由于平均互信息，( x ；】，) 是输