第1讲绪论2014

1、Claude Shannon (1916-2001)主讲教师简介主讲教师简介葛建华：葛建华： 1982年毕业于西北电讯工程学院一系获信息论专业学士学位。年毕业于西北电讯工程学院一系获信息论专业学士学位。 1989年毕业于西安电子科技大学获通信与电子系统学科博士学位。年毕业于西安电子科技大学获通信与电子系统学科博士学位。 现为西安电子科技大学通信工程学院教授、博士生指导教师现为西安电子科技大学通信工程学院教授、博士生指导教师,通院副通院副院长院长,国家重点实验室副主任。国家重点实验室副主任。 研究方向：移动通信研究方向：移动通信(4G/5G),数字电视传输数字电视传输,空地数据链空地数据链 包含

2、：多天线传输理论与技术、高效调制解调技术（包含：多天线传输理论与技术、高效调制解调技术（MIMO-OFDM,SC_FDE),高效编码调制技术，多节点协同传输理论与技术。高效编码调制技术，多节点协同传输理论与技术。 office:科技实验楼科技实验楼A605室室 E-mail: 电话：电话13909189716 课程大纲课程内容：课程内容：第一章第一章 绪论（绪论（2学时）学时）第二章第二章 信息量和熵（信息量和熵（10学时）学时）第三章第三章 离散信源无失真编码（离散信源无失真编码（10学时）学时）第四章第四章 信道容量（信道容量（10学时）学时）第五章第五章 离散

3、信道编码定理（离散信道编码定理（2学时）学时）第六章第六章 线性分组码（线性分组码（6学时）学时）第九章第九章 无记忆信源的有失真编码（无记忆信源的有失真编码（6学时）学时）本课程是通信专业的基础理论课本课程是通信专业的基础理论课课程特点以及学习要求课程特点以及学习要求 信息论主要是应用概率论、数理统计以及随机过程等方法来研究信息传输、存储和处理，因而它对数学要求较高，公式推导较复杂，所以课堂上一定要认真听讲。另一方面，要求大家多做练习，深入理解基本概念以及基本定理。 关于考试形式，采用闭卷120分钟，最终课程成绩由2部分构成：试卷90，平时10。其它事项 听课 按时、请假、课堂秩序 作业 按

4、时、独立完成 答疑 课前、网络、集中教材与参考书教材与参考书教材：教材： 王育民、李晖、梁传甲编著，信息论与编码理论，高等教育出版社，2005.12参考书：参考书：1傅祖芸编，信息论基础理论与应用， 电子工业出版社，2005.12 2Thomas M.Cover，Elements of Infomation Theory. John Wiley & Sons,INC.,2006.1 （信息论基础，机械工业出版社，2007.7）什么是信息论什么是信息论 ?1948年,Claude Shannon在他的经典论文“ A Mathematical Theory of Communication

5、”（通信的数学理论）的引言部分写道： “通信的基本问题就是在某一点精确或近似地再生另一点选择的信息。”为解决这一问题，他在该论文中提出了应用数学的一个全新分支，现在称之信息理论或信息编码理论，宣告了一门崭新的学科信息论的诞生。信息论是研究信息的传输、存储和处理的科学。信息论是研究信息的传输、存储和处理的科学。信息论研究的基本任务是为设计有效而可靠的通信系统提供理论依信息论研究的基本任务是为设计有效而可靠的通信系统提供理论依据。据。Shannon信息论的核心思想信息论的核心思想 考虑一对特殊的数学模型：考虑一对特殊的数学模型： 二进制对称信源和二进制对称信道二进制对称信源和二进制对称信道 二进制

6、对称信源：二进制对称信源： 输出符号0和1，等概分布，速率为单位时间内R个符号，称之比特bits ( binary digits)。 二进制对称信道（二进制对称信道（BSC）：）： 一个在单位时间内可以传输1比特数据的实体，但该信道并不是完全可靠，存在一个固定的概率p，满足0p1/2，使输出比特与输入比特不相同。 现在设想有二个人，一个是发送者，另一个是接收者。发送者必须使接收者尽可能精确再生信源的输出，而他们之间的唯一通信链路就是BSC。 注：在启动信源之前，容许发送者和接收者在一起了解彼 此将采用的数据处理策略，不对计算能力和存储资源限制。编码编码问题问题:对于给定的一个信源速率对于给定的

7、一个信源速率R、发送者和接收者之发送者和接收者之 间通过间通过BSC的通信可以达到多高的可靠度？的通信可以达到多高的可靠度？ shannonshannon信息论给出此问题的精确结论。信息论给出此问题的精确结论。 假设假设R=1/3,即即信道传输速率是信源产生数据速率的信道传输速率是信源产生数据速率的3倍倍。 在传输之前，可以对信源输出的每一比特重复3次 （重复编码方法）。码字：000, 111 例如：信源输出10100，编码后111 000 111 000 000 对每一信源输出比特，接收者收到3比特，但这3比特可能不完全相同（为什么？）。 如信道干扰了传输的第2、5、6、12和13比特，接收

8、者收到101，011，111，001，100。译码最佳策略是什么？译码最佳策略是什么？ 对接收到的3比特多数判决(最佳）? 101，011，111，001，100, 译码结果：11100。 一般地，用pb表示误比特率: 2233b233(1)32 p1/2, p 1,即信源产生数据速率是信道传输速率的R倍。 问题： 如何信源数据压缩（信源编码方法）？ 方法1：仅传送信源比特的1/R，并且接收者以抛硬币的方式猜测 其余的部分。 误比特率pb为: 方法2：如R=3，信道仅传送信源比特的1/3，因此发送者将信源输 出分成3比特一组，并且只传输这3比特中占多数的比特。 例如：信源输出 101,110,

9、101,000,101 信道传输 11101 最佳译码策略最佳译码策略： 接收者只需将收到的每个比特重复3次. 24143)1 (41ppppb3313/)21(21pppb 误比特率 pb 为: 注意到：R=3, 方法1的误比特率pb为：问题： 更有效的编码方法吗？答案是肯定的。回到问题回到问题: : 对于给定的一个信源速率对于给定的一个信源速率R R、发送者和接收者发送者和接收者之间通过之间通过BSCBSC的通信可以达到多高的可靠度？的通信可以达到多高的可靠度？给定信道，如存在一种编码，码速率给定信道，如存在一种编码，码速率Rx，误码率，误码率Pey，则称点（则称点（x，y）是可达的。）是

10、可达的。特别地，特别地，Pe任意小，可达码速率任意小，可达码速率R的上界的上界该上界称为信道容量。该上界称为信道容量。什么是信息什么是信息 ?信息的定义很难给出，象物质和能量一样，难以给出明确的定义。在日常生活中，信息信息经常被误认为就是 “情报情报” 、“消息消息” 等。情报情报：人们对于某个特定对象所见、所闻、所理解而产生的知识。消息消息：用文字、符号、数据、语言、音符、图片、图像等能够被人们的感觉器官所能感知的形式，把客观物质运动和主观思维活动的状态表达出来就成为消息。消息中包含信息，它是信息的载体。消息中包含信息，它是信息的载体。什么是信息什么是信息 ?香农在1948年发表了一篇著名的

11、论文，“通信的数学理论”。他从研究通信系统传输的实质出发，对信息作了科学的定义，并给出了定性和定量的描述。Shannon信息定义信息定义香农将各种通信系统概括成如图示框图。信源信源信道信道信宿信宿噪声或干扰噪声或干扰简单通信系统框图简单通信系统框图输 入输 入消 息消 息码 字码 字输 出输 出消 息 先消 息 先验 概 率验 概 率消息后验概率消息后验概率收到收到0 收到收到01收到收到011x1x2x3x4x5x6x7x80000010100111001011101111/81/81/81/81/81/81/81/81/41/41/41/40000001/21/2000000010000S

12、hannon信息定义信息定义特点特点: 通过消息的传递，收信者消除或部分消除消息内容 不知、不确定。不确定性的消除或部分消除就获得了信息。原先的不确定性消除得越多，获得的信息就越多。香农信息的定义：香农信息的定义：信息是事物运动状态或存在方式的不确定性的描述。信息是具有不确定性的消息中所包含的表示事物特性的内容。信息是具有不确定性的消息中所包含的表示事物特性的内容。信息、消息和信号信息、消息和信号 信息信息 事物运动状态或存在方式事物运动状态或存在方式不确定性不确定性的描述。的描述。 消息消息 指包含有信息的语言、文字和图像等指包含有信息的语言、文字和图像等 。 信号信号 消息的物理体现。消息

13、的物理体现。 【例】摸球试验【例】摸球试验 甲袋共甲袋共100个球，红球白球各个球，红球白球各50个；乙袋共个；乙袋共100个个球，红、白、蓝、黑球各球，红、白、蓝、黑球各25个；现随意从甲袋或个；现随意从甲袋或乙袋中取出一球，并猜测取出球的颜色？乙袋中取出一球，并猜测取出球的颜色？事物出现某状态事物出现某状态不确定性不确定性的大小，与该状态出现的大小，与该状态出现的的概率概率大小有关大小有关不确定性度量不确定性度量概率空间概率空间 样本空间样本空间 信源所有可能发送的消息符号信源所有可能发送的消息符号 先验概率先验概率p(xi) 选择符号选择符号xi作为发送消息的概率作为发送消息的概率)()

14、()(2121nnxpxpxpxxxPX( ( )if p x不确定性大小不确定性大小( ( )f p x不确定性大小不确定性大小信息定义信息定义应该满足以下应该满足以下3个条件个条件(1)0f( ( )f p x是单调减函数是单调减函数独立可加性独立可加性( ( ) ( )( ( )( ( )f p x p yf p xf p y1. 2. 3. 自信息自信息 其中：其中：a 1 条件自信息条件自信息 )(1log)(iaixPxI1()log()ijaijI x yp x y信息定义信息定义先验概率先验概率p(xi) 选择符号选择符号xi作为发送消息的概率作为发送消息的概率后验概率后验概率

15、p(xi | yj) 接收端收到消息接收端收到消息yj后而发送端后而发送端 发的是发的是xi 的概率的概率香农定义的信息的优缺点香农定义的信息的优缺点 优优 点点 有明确的数学模型和定量计算公式有明确的数学模型和定量计算公式 与日常用语中的信息含意一致与日常用语中的信息含意一致 排除了对信息一词某些主观上的含意排除了对信息一词某些主观上的含意 局限性局限性 没有考虑收信者的主观特性和主观意义没有考虑收信者的主观特性和主观意义 定义的出发点假定事物状态可以用一个概率模型来定义的出发点假定事物状态可以用一个概率模型来描述描述通信系统模型通信系统模型 我们将各种通信系统中具有共同特性的部分抽取出来概

16、括成一个统一的理论模型，通常称它为通信系统模型。 通信系统模型通信系统模型这个模型主要分成五个部分：信源这个模型主要分成五个部分：信源、编码器编码器、信道信道、译码器和信宿。译码器和信宿。 信源信源 信源是信息的来源，信源的输出称为消息。 信源输出的消息是随机的、不确定的，但又有一定的规律性。 依据信源输出的消息分类： 数字信源/模拟信源； 离散信源/连续信源； 独立信源/相关信源； 无记忆信源/有记忆信源； 信源研究的主要问题:消息的统计特性和信源产生信息的速率。编码器编码器 编码器是把信源发出的消息变换成适合信道传输的信号的设备。信号携带着消息，它是消息的载荷者。 编码器可分为二种，即信源

17、编码器和信道编码器。 信源编码是在一定准则下，对信源输出的消息进行适当的变换和处理，目的是为了提高信息传输的效率，为了提高信息传输的有效性。 信道编码是为了提高信息传输的可靠性而对消息进行的变换和处理。 对于各种实际的通信系统，信道编码器还应包括调制等各种变换处理。 信道信道 信道是指通信系统把载荷消息的信号从甲地传信道是指通信系统把载荷消息的信号从甲地传输到乙地的媒介（信息传递的媒介），它包含输到乙地的媒介（信息传递的媒介），它包含收发设备在内的物理设施。收发设备在内的物理设施。 狭义的通信系统中实际信道：狭义的通信系统中实际信道： 有线信道：明线，电缆，光纤，波导。有线信道：明线，电缆，光

18、纤，波导。 无线信道：短波，高频，微波，光波。无线信道：短波，高频，微波，光波。 广义的通信系统信道：信道除了传送信号以外，广义的通信系统信道：信道除了传送信号以外，还有存储信号的作用。还有存储信号的作用。信道信道 在信道中存在噪声和干扰。为了分析方便起见，把在系统其他部分产生的干扰和噪声都等效地折合成信道干扰。 由于干扰或噪声往往具有随机性，所以信道的特性也可以用概率空间来描述。 噪声源的统计特性是划分信道的依据。 恒参信道：信道特性不随时间变化，如有线，微波。 变参信道：信道特性随时间变化，如短波。 离散信道：输入输出离散 连续信道：输入输出连续 信道的中心问题：信道的统计特性和信道容量译

19、码器和信宿译码器和信宿 译码就是把信道输出的编码信号(已迭加了干扰)进行反变换。 一般认为这种变换是可逆的，但可能近似的。 译码器也可分成信源译码器和信道译码器。 中心问题：研究各种可实现的解调和译码方法。信宿信宿是消息传送的对象，即接收消息的人或机器。是消息传送的对象，即接收消息的人或机器。信息传输系统模型信息传输系统模型信道信道信源信源信源编码信源编码加密加密信道编码信道编码干 扰 源干 扰 源信宿信宿信源译码信源译码解密解密信道译码信道译码加密加密密钥密钥解密解密密钥密钥信源信源信源编码信源编码信道信道信道编码信道编码信息传输系统模型信息传输系统模型Shannon 信息论的中心问题信息论

20、的中心问题 中心问题：找到信息传输过程的共同规律，以提高信中心问题：找到信息传输过程的共同规律，以提高信息传输的可靠性、有效性、保密性和认证性，使达到息传输的可靠性、有效性、保密性和认证性，使达到信息传输系统最优化。信息传输系统最优化。 所谓所谓可靠性可靠性高，就是要使信源发出的消息经过信道传高，就是要使信源发出的消息经过信道传输以后，尽可能准确地再现在接收端。输以后，尽可能准确地再现在接收端。 所谓所谓有效性有效性高，就是用尽可能短的时间、尽可能少的高，就是用尽可能短的时间、尽可能少的功率和频谱、及尽可能少的设备来传送一定数量的信功率和频谱、及尽可能少的设备来传送一定数量的信息。息。 提高可

21、靠性和提高有效性常常会发生矛盾，这就需要提高可靠性和提高有效性常常会发生矛盾，这就需要统筹兼顾。统筹兼顾。保密性：隐蔽和保护通信系统中的传输内容，授权接收者。保密性：隐蔽和保护通信系统中的传输内容，授权接收者。认证性：验证消息的完整性。认证性：验证消息的完整性。信息论的研究内容信息论的研究内容 狭义信息论（香农基本理论）狭义信息论（香农基本理论） 主要研究信息的测度、信道容量以及信源和信道编主要研究信息的测度、信道容量以及信源和信道编码理论等问题。码理论等问题。 一般信息论一般信息论 除香农信息论，还包括噪声理论、信号滤波和预测、除香农信息论，还包括噪声理论、信号滤波和预测、统计检测和估计等。

22、统计检测和估计等。 广义信息论广义信息论 不仅包括上述两方面内容，而且包括所有与信息有不仅包括上述两方面内容，而且包括所有与信息有关的自然和社会领域，如模式识别、心理学等关的自然和社会领域，如模式识别、心理学等1924年年 奈奎斯特奈奎斯特 “影响电报速率的一些因素影响电报速率的一些因素” 信息速率与信道带宽成正比信息速率与信道带宽成正比 1928年年 哈特莱哈特莱 “信息的传输信息的传输” 给出了信息度量方法给出了信息度量方法 1936年年 阿姆斯特朗增大带宽可以提高抗干扰能力阿姆斯特朗增大带宽可以提高抗干扰能力 1948年年 Shannon “通信的数学理论通信的数学理论”用概率论的方法研

23、究通信系统，是现代信息用概率论的方法研究通信系统，是现代信息论开创性的权威论文论开创性的权威论文 信息论的形成信息论的形成18321832年莫尔斯电报系统中高效率编码方法年莫尔斯电报系统中高效率编码方法1939年达德利发明了声码器。年达德利发明了声码器。18851885年凯尔文研究了一条电缆的极限传信率问题年凯尔文研究了一条电缆的极限传信率问题 1959年，年，Shannon提出率失真函数和率失真提出率失真函数和率失真信源编码定理信源编码定理 1971年，伯格尔年，伯格尔(TBerger)给出更一般信源给出更一般信源的率失真编码定理的率失真编码定理 率失真信源编码理论是信源编码的核心问题，率失

24、真信源编码理论是信源编码的核心问题，是频带压缩、数据压缩的理论基础是频带压缩、数据压缩的理论基础 目前，已提出多种限失真编码方案如音频、目前，已提出多种限失真编码方案如音频、视频视频: JPEG2000,MPEG-1,MPEG-2, MPEG-4,H.263,H.264 等等率失真信源编码发展率失真信源编码发展 1950年汉明码年汉明码 1955年埃利斯提出了卷积码年埃利斯提出了卷积码; 1959年年BCH码码/1960年年RS码码; 1960年卷积码的概率译码，年卷积码的概率译码，Viterbi译码译码 1966年级联码（年级联码（Forney) 1982年年Ungerboeck编码调制技术

25、编码调制技术（TCM，BCM） 接近接近Shannon限的码：限的码：Turbo(1993，Berrou）,LDPC(1963,Gallager;1995)等等.信道编码发展信道编码发展 香农在香农在1949年发表的年发表的“保密通信的信息理论保密通信的信息理论”论论文中，首先用信息论的观点对信息保密问题作文中，首先用信息论的观点对信息保密问题作了全面的论述。了全面的论述。 1976年迪弗年迪弗(Diffe)和海尔曼和海尔曼(Hellman)发表了发表了“密码学的新方向密码学的新方向”一文，提出了公开密钥密码一文，提出了公开密钥密码体制，保密通信问题才得到广泛研究。体制，保密通信问题才得到广泛

26、研究。 人们把初等数论、矩阵、近世代数等引入保密人们把初等数论、矩阵、近世代数等引入保密问题的研究，已形成了独树一帜的分支问题的研究，已形成了独树一帜的分支密密码学理论。码学理论。 密码学发展密码学发展多用户信息论多用户信息论/网络信息论网络信息论 香农香农1961年发表的年发表的“双路通信信道双路通信信道”开拓了网开拓了网络信息论的研究。络信息论的研究。 1971年年R.Ahlswede和和1972年年H.Liao给出了多元给出了多元接入信道的容量。接入信道的容量。 1972年年T.M.Cover提出了广播信道的研究提出了广播信道的研究网络信息论取得丰富成果，是当前研究热点。网络信息论取得丰

27、富成果，是当前研究热点。 1948年香农提出了无失真信源定理，给出了简年香农提出了无失真信源定理，给出了简单的编码方法单的编码方法(香农编码香农编码) 1952年年Fano码，码，Huffman码码 1968年埃利斯年埃利斯(PElias)提出了算术编码的初提出了算术编码的初步思路步思路; 1976 Rissanen给出和发展了算术编码给出和发展了算术编码 1982年他和兰登年他和兰登(GGLangdon)一起将算术一起将算术编码系统实现化编码系统实现化 1977,1978年年Ziv和和Lempel的的LZ通用信源编算法通用信源编算法无失真信源编码发展无失真信源编码发展Claude Shann

28、on (1916-2001) 1916年生于美国密歇根州的加洛德镇，年生于美国密歇根州的加洛德镇， 2001年在马萨诸塞州辞世，享年年在马萨诸塞州辞世，享年85岁。岁。 阿尔茨海默症（退化性老年痴呆症）阿尔茨海默症（退化性老年痴呆症） 父亲是加洛德镇的法官，母亲是镇父亲是加洛德镇的法官，母亲是镇里中学校长，他生长在一个有良好教育里中学校长，他生长在一个有良好教育的环境，不过父母给他的科学影响好像的环境，不过父母给他的科学影响好像还不如祖父的影响大。还不如祖父的影响大。 香农的祖父是一位农场主兼发明家，香农的祖父是一位农场主兼发明家，发明过洗衣机和许多农业机械。发明过洗衣机和许多农业机械。 香农

29、心目中的英雄是爱迪生，后来香农心目中的英雄是爱迪生，后来才知道他与爱迪生还有远亲关系。才知道他与爱迪生还有远亲关系。Claude Shannon (1916-2001) 1936年在密歇根大学获数学与电气工程学士年在密歇根大学获数学与电气工程学士学位。学位。1938年在年在MIT获得电气工程硕士学位获得电气工程硕士学位硕士论文题目是硕士论文题目是A Symbolic Analysis of Relay and Switching Circuits(继电器与开继电器与开关电路的符号分析关电路的符号分析)。他把布尔代数的真与。他把布尔代数的真与假和电路系统的开与关对应起来假和电路系统的开与关对应起

30、来,用布尔代用布尔代数分析并优化开关电路，奠定了数字电路的数分析并优化开关电路，奠定了数字电路的理论基础。哈佛大学的理论基础。哈佛大学的Gardner教授说教授说“这这可能是本世纪最重要、最著名的一篇硕士论可能是本世纪最重要、最著名的一篇硕士论文文”。1940年在年在MIT获数学博士学位，获数学博士学位，博士博士论文关于人类遗传学的，题目是论文关于人类遗传学的，题目是An Algebra for Theoretical Genetics(理论遗理论遗传学的代数学传学的代数学)。Claude Shannon (1916-2001) 就职于贝尔电话研究所，就职于贝尔电话研究所，他受着前辈的工他受着

31、前辈的工作的启示作的启示, 在信息论的领域中钻研了在信息论的领域中钻研了8年之年之久，久，1948年在贝尔系统技术杂志上发年在贝尔系统技术杂志上发表了表了244页的长篇论著通信的数学理页的长篇论著通信的数学理论论,次年次年,他又在同一杂志上发表了另一他又在同一杂志上发表了另一篇名著噪声下的通信，这两篇文章成篇名著噪声下的通信，这两篇文章成了信息论的奠基著作。了信息论的奠基著作。在这两篇论文中，在这两篇论文中，香农解决了过去许多悬而未决的问题：阐香农解决了过去许多悬而未决的问题：阐明了通信的基本问题，给出了通信系统的明了通信的基本问题，给出了通信系统的模型，提出了信息量的数学表达式，并解模型，提

32、出了信息量的数学表达式，并解决了信道容量、信源统计特性、信源编码、决了信道容量、信源统计特性、信源编码、信道编码等一系列基本技术问题。两篇论信道编码等一系列基本技术问题。两篇论文成为了信息论的基础性理论著作。那时，文成为了信息论的基础性理论著作。那时，他才不过刚刚三十出头。他才不过刚刚三十出头。 Claude Shannon (1916-2001) Shannon所给出的编码定理的证明是非构造性所给出的编码定理的证明是非构造性的，所给出的证明也不够严格，但的，所给出的证明也不够严格，但“他的数学他的数学直观出奇地正确直观出奇地正确” (A. N. Kolmogrov，1963)，他是，他是“最

33、近几十年最伟大的工程师之一，同最近几十年最伟大的工程师之一，同时是最伟大的数学家之一。时是最伟大的数学家之一。”经过无数科技工作者经过无数科技工作者50年来的努力奋斗，人年来的努力奋斗，人们不仅在数学上已严格地证明了们不仅在数学上已严格地证明了Shannon编码编码定理，而且发现了各种具体可构造的有效编定理，而且发现了各种具体可构造的有效编码理论和方法，可以实现码理论和方法，可以实现Shannon指出的极限。指出的极限。文章曾遭受到数学家的抨击，责难文章曾遭受到数学家的抨击，责难Shannon的一些结果未经证明，在数学上不严格，靠的一些结果未经证明，在数学上不严格，靠不大住。不大住。Shannon对此评论说，对此评论说，“我不喜欢我不喜欢他的评论，他并未仔细看这篇文章。我确信他的评论，他并未仔细看这篇文章。我确信我是正确的，我清楚地知道我所做的。我是正确的，我清楚地知道我所做的。” Cl