信息论基础 (2010 年度畅销榜NO.56299 )

信息论是20世纪40年代后期从长期通讯实践中总结出来的一门学科，是专门研究信息的有效处理和可靠传输的一般规律的学科。本书共分7章，内容包括：随机变量的信息度量；随机过程的信息度量；数据压缩和信源编码；数据可靠传输和信道编码；限失真数据压缩和率失真理论；网络信息理论；信息论应用等。既包括了信息论的基本理论，也涉及了一些信息处理的算法及信息论在其他领域的应用。\r\n\r\n 本书可作为数学类信息与计算科学专业的教材，也可为其他相关专业同类课程所选用。\r\n
\r\n

前 言 \r\n\r\n 第一章 随机变量的信息度量 \r\n\r\n 1. 1 自信息 \r\n\r\n 1. 2 熵. 联合熵. 条件熵 \r\n\r\n 1. 3 相对熵和互信息 \r\n\r\n 1. 4 信息量的一些基本性质 \r\n\r\n 1. 5 广义熵 \r\n\r\n 习题一 \r\n\r\n 第二章 随机过程的信息度量和渐近等分性 \r\n\r\n 2. 1 信源和随机过程的基本概念 \r\n\r\n 2. 2 随机过程的信息度量 \r\n\r\n 2. 3 渐近等分性质 \r\n\r\n 2. 4 渐近等分性在数据压缩中的应用——信源编码定理 \r\n\r\n 2. 5 Shannon-McMillan-Breiman定理 \r\n\r\n 习题二 \r\n\r\n 第三章 数据压缩和信源编码 \r\n\r\n 3. 1 等长码 \r\n\r\n 3. 2 变长编码 \r\n\r\n 3. 3 哈夫曼(Huffman)码 \r\n\r\n 3. 4 算术码 \r\n\r\n 3. 4. 1 申农—法诺码 \r\n\r\n 3. 4. 2 自适应算术码 \r\n\r\n 3. 5 通用信源编码 \r\n\r\n 3. 5. 1 LZ算法 \r\n\r\n 3. 5. 2 LZW(Lempel-Ziv-Welch)算法 \r\n\r\n 3. 5. 3 Kieffer-Yang算法(基于语法的普适信源压缩算法) \r\n\r\n 习题三 \r\n\r\n 第四章 数据可靠传输和信道编码 \r\n\r\n 4. 1 离散无记忆信道和信道容量 \r\n\r\n 4. 2 信道容量的计算 \r\n\r\n 4. 2. 1 拉格朗日乘子法 \r\n\r\n 4. 2. 2 信道容量的迭代算法 \r\n\r\n 4. 3 信道编码理论 \r\n\r\n 4. 3. 1 一些定义和概念 \r\n\r\n 4. 3. 2 联合典型序列 \r\n\r\n 4. 3. 3 信道编码定理 \r\n\r\n 4. 4 带反馈的信道模型 \r\n\r\n 4. 5 联合信源—信道编码定理 \r\n\r\n 4. 6 线性分组码 \r\n\r\n 习题四 \r\n\r\n 第五章 限失真信源编码和率失真函数 \r\n\r\n 5. 1 限失真信源编码模型和率失真函数 \r\n\r\n 5. 1. 1 限失真信源编码模型和率失真函数定义 \r\n\r\n 5. 1. 2 率失真函数的性质 \r\n\r\n 5. 1. 3 平稳信源的率失真函数 \r\n\r\n 5. 2 率失真函数的计算 \r\n\r\n 5. 2. 1 一个简单的例子 \r\n\r\n 5. 2. 2 拉格朗日乘子法 \r\n\r\n 5. 2. 3 迭代算法 \r\n\r\n 5. 3 限失真信源编码定理 \r\n\r\n 习题五 \r\n\r\n 第六章 连续信源和信道编码理论 \r\n\r\n 6. 1 可微熵 \r\n\r\n 6. 2 相对熵和互信息 \r\n\r\n 6. 3 连续信源的率失真函数 \r\n\r\n 6. 3. 1 率失真函数和失真率函数 \r\n\r\n 6. 3. 2 高斯信源的率失真函数 \r\n\r\n 6. 3. 3 一般连续信源的率失真函数 \r\n\r\n 6. 4 高斯信道 \r\n\r\n 6. 4. 1 有加性噪声的信道模型和信道容量 \r\n\r\n 6. 4. 2 复合高斯信道和平稳高斯信道 \r\n\r\n 习题六 \r\n\r\n 第七章 网络信息理论 \r\n\r\n 7. 1 网络通信模型 \r\n\r\n 7. 2 多变量联合典型序列 \r\n\r\n 7. 3 多址信道 \r\n\r\n 7. 3. 1 址信道模型和编码定理 \r\n\r\n 7. 3. 2 多址信道容量区域的计算 \r\n\r\n 7. 3. 3 高斯多址信道 \r\n\r\n 7. 4 相关信源编码 \r\n\r\n 7. 4. 1 Slepian-Wolf模型 \r\n\r\n 7. 5 相关信源和多址信道复合编码问题 \r\n\r\n 习题七 \r\n\r\n 参考文献 \r\n
\r\n

(1)信息论简史

信息论是20世纪40年代后期从长期通讯实践中总结出来的一门学科, 是专门研究信息的有效处理和可靠传输的一般规律的科学. 信息是系统传输和处理的对象, 它载荷于语言. 文字. 数据. 图像. 影视. 信号等之中, 要研究信息处理和传输的规律, 首先要对信息进行定量的描述, 即信息的度量, 这是信息论研究的出发点. 但要对通常含义下的信息(如知识. 情报. 消息等)给出一个统一的度量是困难的, 因为它涉及客观和主观两个标准, 而迄今为止最成功. 应用最广泛的是建立在概率模型基础上的信息度量, 进而建立在此种信息量基础上的信息论成功地解决了信息处理和可靠传输中的一系列理论问题.

切略(E. C. Cherry)曾写过一篇早期信息理论史, 他从石刻象形文字起, 经过中世纪启蒙性语言学, 直到16世纪吉尔伯特(E. N. Gilbert)等人在电报学方面的工作.

现代信息论实际是从20世纪20年代奈奎斯特(H. Nyquist)和哈特莱(L. V.R. Hartley)的工作开始的, 他们最早研究了通信系统传输信息的能力, 并试图度量系统的信道容量.

克劳德·申农(ClaudeShannon)于1948年发表的具有里程碑性质的论文“通信的数学理论”是世界上首次将通讯过程建立了数学模型的论文, 这篇论文和1949年发表的另一篇论文一起奠定了现代信息论的基础. 申农开创性地定义了“信息”, 他所定义的信息与语义无关, 而是反映了将“信息”编码成由简单的0和1表示的语言的能力, 由此整个通讯过程可表示成以下的过程, 从一个信源发出的消息, 经过编码后通过一个信道传输给接收者, 接收者通过译码器将收到的信号复原成信源发出的原消息.

申农证明了任何的信息源——文本. 图像. 影视. 数据——都伴随着一个可定量化的信息内涵, 它表示了可以如何有效地表达这类信息的能力, 此即信息压缩的基础, 比如, 申农证明了任何人再聪明也不可能把英文文本压缩到1. 5比特／字母. 申农还揭示了人们通过一个有噪音的信道传输信息的有效性的极限, 称之谓信道容量.

申农以上的工作奠定了现在称之谓“信息论”的理论基础, 他关于信息处理和可靠通讯的工作是当今无所不在的数据压缩. 调制解调器. 广播. 电视. 卫星通信. 计算机存储乃至因特网通讯的理论基础. 此外申农在第二次世界大战期间在密码方面的工作形成了现代信息安全系统的理论框架.

申农的工作也是因特网以及其他应用广泛的从音乐. 影视到电子邮件等高新技术的核心, 他的工作在计算机科学. 人工智能. 基因工程. 神经解剖学乃至金融投资学等众多领域也有广泛应用, 因此有人称申农1948年的论文是信息时代的“基本法”. 在过去的20世纪中只有少数几个科学家能称得上世纪科学巨人, 申农就是其中之一.

自申农1948年的奠基性文章发表后, 前苏联和美国的科学家采取了不同的研究途径进一步发展了信息论. 在前苏联以辛钦(Shiqin). 柯尔莫哥洛夫(Kolmogorov). 宾斯基(Pinsker)和达布鲁新(Dabrushin)为首的一批著名数学家致力于信息论的公理化体系和更一般更抽象的数学模型, 对信息论的基本定理给出了更为普遍的结果, 为信息论发展成数学的一个分支作出了贡献. 而在美国则是由一批数学修养很高的工程技术人员致力于信息有效处理和可靠传输的可实现性, 为信息论转化为信息技术作出了贡献.

我国数学家和信息科学专家在20世纪50年代将信息论引进中国, 经过50多年的不懈努力, 特别是20世纪80年代中叶以来, 一批华裔信息论专家在国际学术界崛起, 为信息论的发展作出了自己的贡献.

(2)关于申农

克劳德·申农, 1916年4月30日生于美国密西根州的贝多斯克(Petoskey), 2001年2月24日在长期患老年痴呆症后在美国马萨诸塞州的蒙得福特(Med-ford)去世, 享年85岁, 申农有2个儿子和1个女儿.

1936年申农20岁时在密西根大学获数学和电机工程学学士学位, 此后进入著名的麻省理工学院(MIT), 1938年获硕士学位, 他的硕士学位论文“延迟电路和开关电路的符号分析”后来获美国电机工程师协会优秀论文奖(1940), 1940年申农以题为“理论遗传学的代数学”的论文获MIT数学博士, 但那以后他再也没写过遗传学方面的论文.

在MIT, 申农跟随V·布什(VannevarBush)研究当时称为微分分析器的模拟计算机, 1940年夏天, 他曾在AT&T的贝尔电话实验室工作. 之后, 他在林斯顿大学的高等研究院跟随著名数学家H·外尔(HermannWeyl)工作了一年. 在普林斯顿, 他开始思考如何建立通信系统的恰当的数学基础.

1941年, 他回到贝尔实验室, 在那里一直工作了15年. 在第二次世界大战期间, 他参与了数字密码系统的研究, 包括曾用于邱吉尔和罗斯福的跨洋会议系统. 1945年他完成了“密码学的数学理论”的报告, 该文直到1949年才在Bell System Technical Journal(BSTJ)上发表, 正是他对密码学的思考促进了他对通信理论的研究. 1948年, 申农发表了“通信的数学理论”这篇划时代的杰作, 奠定了信息论的基础.

1956年, 申农离开了贝尔实验室回到母校MIT, 担任通信科学方面的教授, 1958年起担任Donner讲座教授直到1978年退休.

国际电子和电机工程师协会(IEEE)在1950年初期成立了信息论学会, 并于1973年设立申农讲座(现已更名申农奖), 用以表彰对信息论发展作出卓越贡献的科学家, 是国际信息论界的最高荣誉, 而申农本人则是申农讲座的第一个得主.

申农后来的兴趣跃出了, 通信工程范围, 曾致力于密码学, 用概率论研究如何投资股票市场, 试图在DNA复制和荷尔蒙信号研究中应用信息论方法, 他还研究过早期的机器人, 设计能在轮盘赌中取胜的计算机软件. 智力游戏机. 申农本人能一边骑自行车一边玩杂耍, 他设计了一个类似骑自行车玩杂耍的机械.

申农一生发表了一百多篇论文, 1993年出版的申农论文集收集了他1938—1982年期间发表的127篇论文. 申农一生获得过无数的荣誉与奖励. 他是IEEE的会士. 美国科学院院士. 美国艺术与科学院院士. 他获得的奖励中包括IEEE成就奖(1966). 美国国家科学奖. 以色列哈维(Harvey)奖(1972)和日本Kyoto奖(1985).

(3)信息论简介

由于现代通信技术的飞速发展及和其它学科的交叉渗透, 信息论的研究已经从申农当年仅限于通信系统的数学理论的狭义范围扩展开来, 而成为现在称之为信息科学的一个庞大体系. 但是作为大学本科生课程的信息论基础, 我们仍限于申农意义下的狭义信息论. 一章简单介绍信息论在其它领域的应用, 以供读者进一步学习的参考.

(a)通信系统

作为通信系统的数学理论, 申农在1948年的奠基性文章中提出了通信系统的一般模型(如下图所示)

信息的产生和发送者称之为信源, 信源要将输出的消息通过某种通讯渠道传输给称为信宿的接收者. 我们称信源发出的信息为消息, 这里并不考虑其内含的语义信息, 而只考虑它的统计特性, 通信的主要目标之一是使接收端能尽可能准确地复制信源发送的消息. 为研究方便起见, 先将信源与信道分开来介绍.

(b)信源编码

通常信源发出的消息是有冗余的, 比如普通语言与文字是有高冗余度的, 为了有效地进行通信, 往往对有冗余的消息先进行无冗余或少冗余编码, 或称压缩编码, 这就是信源编码器的任务. 接收端的信源译码器对收到的压缩后的信息进行编码的逆运算, 或称译码, 将信源发送的原消息复现, 此即信源译码器的任务. 根据消息的不同特征及信宿对复制消息的不同要求, 复制时可以无失真, 如对文本消息, 也可以允许有一定失真, 如对语音. 图像. 影视信息. 由此发展起来了无失真信源编码和允许失真的率失真理论, 以寻求信息压缩的最优理论极限, 同时也寻求压缩率尽可能接近这个理论极限的实用压缩编码技术, 这两部分构成了信源编码理论的主体.

(c)信道编码

信源发出的消息经过压缩后要通过某种渠道传输给接收者, 这种渠道称之为信道, 实际信道包括电缆. 光纤. 微波. 无线通讯等. 信道中通常会有噪声干扰, 使传输的消息产生失真, 如语音通信系统产生的噪音. 电视系统中的“雪花”干扰等. 由于噪声的存在, 使信道能可靠传输信息的能力受到限制, 信道的最大理论信息传输速率称之为信道容量. 信道只能用低于信道容量的速率来可靠地传输信息, 如传输速率超过了信道容量, 就会出现错误.

研究各种特定信道的容量是信息论的另一基本问题. 为了增加传输信息的抗干扰能力, 就需增加信息的冗余度, 这就是信道编码器的任务. 经信道编码增加了冗余度的消息通过信道后, 即便受噪声干扰可能会出现一些错误, 但信道译码可利用增加的冗余信息进行纠错, 尽可能正确地复制出信道编码前的消息. 信道编码技术的研究已形成了现在称之为纠错码的一个完整体系.

信道容量和纠错码就构成了信道编码理论的主体.

(d)复合信源—信道编码

对信源与信道分隔开讨论后再回到(a)中所示的通信系统, 我们就可以发现, 只要信源编码的压缩率不超过信道容量, 就可以达到既有效又可靠地传输信息的目的, 也把看似矛盾的信源编码(要减少冗余)和信道编码(要增加冗余)统一在一起. 同时为提高效率, 可以把信源与信道编码器合二而一为一个编码器, 同理也可把信道与信源译码器合二而一为一个译码器.

(e)网络通信

以上介绍的通信系统是点对点. 一对一的通信模型. 在20世纪70年代以世纪80年代开始, 长期从事信息理论与信息处理的科研与教学工作, 积累了一定的经验, 考虑到“信息与计算科学”专业对本课程的需求, 编写了这本教材. 本教材对信息论涉及的内容进行了精选, 并将信息论研究的传统方法(如随机码方法)与现代数学方法(如典型序列法)相结合并贯穿始终, 同时注意理论与应用的结合, 在讨论信息论基本编码定理的基础上也介绍了一些实用算法, 使之尽可能地适用于一般院校该专业本科生所用.

本书共分七章, 第一章随机变量的信息度量, 介绍了基本的信息量和它们的主要性质, 第二章随机过程的信息度量和渐近等分性, 将第一章的信息度量推广到随机过程, 基于大数定理的渐近等分性是第一个信源编码定理的基础, 第三章数据压缩和信源编码, 讨论信源编码基本定理及数据压缩的实现技术, 特别介绍了几种有很强实用价值的信源编码方法, 第四章数据可靠传输和信道编码, 主要讨论信道容量及基于它的信道编码定理, 并简单介绍了线性分组纠错码, 但没有进一步讨论卷积码和代数码, 第五章限失真数据压缩和率失真理论, 讨论了允许一定失真的信源编码的率失真理论, 着重介绍了率失真函数的计算.

以上各章讨论的均是离散模型, 第六章连续信源和信道编码理论, 首先将信息度量推广到连续情形, 然后着重讨论了高斯信道与高斯信源, 第七章网络信息理论, 在简述了各种多用户信源和信道通信模型后, 只简单介绍了其中已得到完全解决的几个简单模型.

本教材主要对象是大学数学类数学与应用数学专业. 信息与计算科学专业的本科生, 也可作为其它相关专业(如通信工程. 电子工程等)同类课程的教材.

本教材适用于54学时的课程, 当然在增删部分内容后也可用于36学时的短课程或72学时的扩展课程.

(5)致谢

本教材的编写得到了上海交通大学九五重点教材基金的资助, 其出版则得到了高等教育出版社的大力支持.

美国南加州大学的张箴教授详细阅读了本书前四章的初稿, 南开大学沈世镒教授阅读了全书, 他们都提出了许多宝贵的修改意见, 加拿大滑铁卢大学的杨恩辉教授提供了克佛—杨(Kieffer-Yang)通用信源编码方法的通俗描述, 周煦. 王俊. 姚奕帮助用CCTEX打印了本书. 德国康斯坦茨(Konstanz)大学数学与统计学系西格佛瑞特·海勒(Siegfried Heiler)教授盛情邀请作者访问该校, 本书的部分章节与习题就是2002年暑假在美丽的博登湖畔完成的.

对他们的帮助. 支持和关心表示衷心感谢.

作者由衷地感谢攻读硕士和博士阶段的导师南开大学胡国定教授. 沈世镒教授和美国康奈尔(Cornell)大学托比·贝尔格(Toby Berger)教授, 是他们将作者引入信息论以至信息科学这个博大精深, 使作者从中得到无穷乐趣并值得为之奋斗终身的科学领域.

作者特别感谢妻子毛经义和女儿叶蕾对本人的关爱. 理解和支持, 没有良好的写作环境, 本书的成书几无可能.

叶中行

2002年10月于沪

无封面