信息论与纠错编码（第2版）.pdf

新编电气与电子信息类本科规划教材 信息论与纠错编码（第 2 版）孙丽华 陈荣伶 编著 Publishing House of Electronics Industry 北京BEIJING 内 容 简 介 本书重点介绍了信息论与纠错编码的基础内容，全文共分 10 章。内容包括信息及信息的度量、离散信源及信源熵、离散信道及信道容量、信源编码定理和信道编码定理、平均失真测度和信息率失真函数、率失真编码定理、纠错编码代数基础、线性分组码、循环码和卷积码。本书文字通顺，深入浅出，概念清晰，对一些较难理解的概念，辅有较多的例题，并配有免费电子课件、习题解答等教辅资料。本书适合作为高等院校理工类本科电子技术、信息工程、通信工程、雷达、计算机、自动化、仪器仪表等相关专业的教材，也可作为信息科学及系统工程等专业教学人员及科研人员的参考书。未经许可，不得以任何方式复制或抄袭本书之部分或全部内容。版权所有，侵权必究。图书在版编目（CIP）数据 信息论与纠错编码/孙丽华，陈荣伶编著2 版北京：电子工业出版社，2009.8 新编电气与电子信息类本科规划教材 ISBN 978-7-121-09369-2.信 .孙陈 .信息论高等学校教材信源编码编码理论高等学校教材信道编码编码理论高等学校教材 .TN911.2 中国版本图书馆 CIP 数据核字（2009）第 133392 号 策划编辑：王羽佳 责任编辑：秦淑灵 印 刷：装 订：出版发行：电子工业出版社 北京市海淀区万寿路 173 信箱 邮编：100036 开 本：7871 092 1/16 印张：14.5 字数：371 千字 印 次：2009 年 8 月第 1 次印刷 印 数：4 000 册 定价：25.00 元 凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系，联系及邮购电话：（010）88254888。质量投诉请发邮件至 ，盗版侵权举报请发邮件至 。服务热线：（010）88258888。前 言 信息论是应用近代概率统计方法研究信息传输、交换、存储和处理的一门学科，也是源于通信实践发展起来的一门新兴应用科学。当前人类已步入信息社会，随着信息概念的不断深化，信息在科学技术上的重要性也早已超越了狭义的通信工程的范畴，受到越来越多的关注。在高等院校中，信息工程类专业是最热门的专业之一，信息技术已经改变了很多传统电子类专业的知识结构。在这种形式下，许多高校都在相关专业开设了信息论课程，作为本科生、研究生的必修或选修课程。一方面，这门课是电子类专业的核心课程，很多学校都把它作为必修课或必选课；但另一方面，这门课程涉及多门工程数学理论，例如概率统计论、线性代数、近世代数等，一直有教师难教、学生难学的说法。本书力求在内容筛选及编排上以读者最易接受的方式介绍信息理论的知识。本书包括“信息论与纠错编码”的基本内容及应用。第 1 章为“信息论基础”，介绍了信息论的基本概念，以及本书的研究对象各种信源和信道。第 26 章为信息论部分，介绍了信息的度量，内容主要围绕香农三大定理展开，研究在不允许失真的情况下信息传输率的极限值，以及给定信源并且允许一定失真的条件下信息速率的极限值，并研究在误码率小于给定值的条件下如何最有效地利用信道的传输能力。第 7 章讲述了纠错编码所必需的数学知识。第 810 章为纠错编码部分，纠错编码是后人沿着香农指明的可行方向，为寻求有效而可靠的编译码方法而发展起来的一门学科，主要研究在有噪信道条件下各种可行的编码方案及实施技术。与现有的各种“信息论与编码”教材相比，本教材特色如下。（1）本书力图在编排上由浅入深，循序渐进，希望读者以易于掌握的方式接受信息论与纠错编码方面的基本理论知识；（2）对于部分具有结论性、指导性的定理，教材省去了冗长烦琐的定理证明，注重物理概念的阐述以及对后人工作的指导意义；（3）增加了纠错编码部分的内容。教材第 8，9 章和第 10 章分别论述纠错码中最基本的线性分组码、循环码和卷积码的编译码理论，并列举了几种常用的码，如汉明码、BCH 码和卷积码，介绍了它们主要的编译码方法。（4）对一些难以理解的概念，本书配有较多的例题，以帮助学生理解抽象定理。各章后面配有较多难易程度不等的思考题和习题，以供选用。（5）在第 1 版的基础上，收集了使用该书师生的反馈意见，对一些较难理解的概念，增加了较多的例题、思考题和习题，并将第 1 版中第 5 章和第 6 章的内容做了一些调整，使之更趋合理。本书全部内容约需 62 学时，不同专业可根据需要进行调整。本书配有教学课件和配套辅助文件，需要者可到华信教育资源网http:/免费注册下载。本书第 1，7，10 章、附录 1 和附录 2 由陈荣伶编写，第 26 章、第 8 章和第 9 章由孙丽华编写，由孙丽华负责全书的策划、修改和统编。本书在编著过程中参阅了一些国内外相关著作，这些著作已在参考文献中一一列出，在此谨向有关作者表示深深的谢意！在此也向第 1 版的合作者谢仲华表示深深的谢意！本书在编写过程中得到电子工业出版社的大力支持，王羽佳和秦淑灵编辑做了大量的工作，使本书得以顺利出版，在此一并表示衷心的感谢！本书涉及知识领域广泛，知识变化日新月异，由于时间和水平的限制，难免有差错和不足之处，敬请读者指正！孙丽华 2009 年 6 月 于南昌 I 目 录 第 1 章 信息论基础1 1.1 信息的概念2 1.2 数字通信系统3 1.3 信源及其数学模型5 1.3.1 离散无记忆信源5 1.3.2 离散有记忆信源6 1.3.3 波形信源8 1.4 信道及其数学模型9 1.4.1 离散无记忆信道9 1.4.2 离散无记忆扩展信道 11 本章小结12 思考题与习题12 第 2 章 信息的度量13 2.1 自信息量和互信息量14 2.1.1 自信息量和条件自信息量15 2.1.2 互信息量和条件互信息量18 2.2 离散集的平均自信息量 22 2.2.1 信息熵 22 2.2.2 熵函数的性质26 2.3 离散集的平均互信息量 31 2.3.1 平均互信息量31 2.3.2 平均互信息量的性质 33 2.3.3 有关平均互信息量的两条定理36 2.4 N 维扩展信源的熵和平均互信息量 40 2.4.1 N 维扩展信源的熵40 2.4.2 N 维扩展信源的平均互信息量 41 2.4.3 有关 N 维平均互信息量的两条定理42 本章小结44 思考题与习题45 第 3 章 离散信源无失真编码48 3.1 概述49 3.1.1 码的分类50 3.1.2 平均码长的计算53 3.1.3 信息传输速率55 3.2 等长码及等长编码定理 56 II 3.3 变长码及变长编码定理 59 3.3.1 变长码 59 3.3.2 克拉夫特不等式60 3.3.3 变长编码定理62 3.4 变长码的编码方法67 3.4.1 香农编码法67 3.4.2 费诺编码法69 3.4.3 霍夫曼编码法70 本章小结75 思考题与习题75 第 4 章 离散信道的信道容量80 4.1 信道容量的定义81 4.2 离散无记忆信道容量的计算81 4.2.1 达到信道容量的充要条件82 4.2.2 几类特殊的信道86 4.3 组合信道的容量93 4.3.1 独立并行信道93 4.3.2 和信道 94 4.3.3 串行信道95 本章小结97 思考题与习题98 第 5 章 有噪信道编码100 5.1 信道编码的基本概念101 5.2 译码规则及错误概率104 5.3 信道编码定理107 5.4 费诺引理及信道编码逆定理111 5.4.1 费诺不等式111 5.4.2 信道编码逆定理112 本章小结114 思考题与习题 114 第 6 章 率失真编码117 6.1 失真测度与平均失真118 6.2 信息率失真函数 R(D)121 6.2.1 率失真函数的定义121 6.2.2 率失真函数的值域、定义域122 6.2.3 率失真函数的性质124 6.3 率失真函数的计算127 6.3.1 两种特殊情况下的求解127 6.3.2 R(D)的参数表示法130 6.4 率失真信源编码定理135 III 本章小结135 思考题与习题 136 第 7 章 纠错编码代数基础139 7.1 基本概念 140 7.1.1 整数140 7.1.2 多项式 140 7.1.3 线性空间141 7.2 群与环142 7.2.1 群的定义142 7.2.2 子群144 7.2.3 环145 7.3 域146 7.3.1 域的定义146 7.3.2 有限域的本原元148 7.3.3 有限域的结构149 本章小结153 思考题与习题 153 第 8 章 线性分组码155 8.1 纠错码的基本概念156 8.1.1 信道纠错编码156 8.1.2 差错类型156 8.1.3 差错控制系统模型及分类157 8.1.4 纠错码的分类158 8.2 线性分组码的编码159 8.2.1 生成矩阵、校验矩阵 159 8.2.2 系统码 163 8.2.3 对偶码 165 8.2.4 编码的实现166 8.3 线性码的纠检错能力168 8.3.1 码的距离和重量168 8.3.2 线性码的纠错、检错能力169 8.4 标准阵列和译码172 8.4.1 标准阵列172 8.4.2 陪集分解173 8.4.3 译码176 8.5 汉明码177 8.5.1 汉明码的构造177 8.5.2 汉明限与完备码179 本章小结180 思考题与习题 180 IV 第 9 章 循环码183 9.1 循环码的一般概念184 9.1.1 循环码的定义184 9.1.2 循环码的多项式描述 184 9.2 循环码的生成多项式和生成矩阵185 9.2.1 生成多项式185 9.2.2 生成矩阵188 9.3 循环码的校验多项式和校验矩阵189 9.4 循环码的编码192 9.4.1 利用 g(x)实现编码192 9.4.2 利用 h(x)实现编码194 9.5 循环码的译码196 9.5.1 伴随式计算196 9.5.2 循环码的纠错译码198 9.5.3 Meggit 译码器 200 9.6 一些重要的循环码202 9.6.1 循环 Hamming 码202 9.6.2 BCH 码203 本章小结206 思考题与习题 206 第 10 章 卷积码208 10.1 卷积码基本概念209 10.2 卷积码的数学描述210 10.2.1 卷积码的矩阵描述 210 10.2.2 卷积码的多项式描述 212 10.3 卷积码的图形表示方法 214 10.3.1 状态图214 10.3.2 树图 214 10.3.3 网格图216 10.4 Viterbi 译码216 10.4.1 Viterbi 译码步骤217 10.4.2 Viterbi 译码217 本章小结218 思考题与习题 219 附录 A GF（2m）中元素的最小多项式和本原多项式（1m8）220 附录 B 熵函数计算用简明对数表221 参考文献222 第 1 章 信息论基础 内容提要 信息论是人们在长期的通信实践中发展起来的一门新兴应用科学，它应用近代概率统计方法来研究信息的传输、交换、存储和处理。自 Claude E.Shannon 发表通信的数学理论开始，随着信息概念的不断深化，信息理论在科学技术上的应用早已超越了狭义的通信工程范畴，受到越来越多的关注。本章首先引出信息、消息的概念，讨论信息论的研究范畴；然后简述数字通信系统的结构和特点，讨论离散信源、波形信源和离散信道的数学模型和特点；最后介绍几种常见的离散无记忆信源和离散无记忆信道。知识要点 信息的定义、信息论的研究范畴、数字通信系统的组成、离散信源和离散信道的数学模型。教学建议 本章是信息论的基本概念，后续信息的度量、信源编码及信道编码都是围绕本章的概念而展开的，建议学时数为 3 学时。2 1.1 信息的概念信息的概念 人们认为，物质、能量和信息是构成客观世界的三大要素。信息是物质和能量在空间和时间上分布的不均匀