第1讲绪论2014

信息论基础葛建华2014年4月1日ClaudeShannon(1916-2001)主讲教师简介葛建华：1982年毕业于西北电讯工程学院一系获信息论专业学士学位。1989年毕业于西安电子科技大学获通信与电子系统学科博士学位。现为西安电子科技大学通信工程学院教授、博士生指导教师,通院副院长,国家重点实验室副主任。研究方向：移动通信(4G/5G),数字电视传输,空地数据链包含：多天线传输理论与技术、高效调制解调技术（MIMO-OFDM,SC_FDE),高效编码调制技术，多节点协同传输理论与技术。office:科技实验楼A605室E-mail:[e-mail]电话：[phone]课程大纲课程内容：第一章绪论（2学时）第二章信息量和熵（10学时）第三章离散信源无失真编码（10学时）第四章信道容量（10学时）第五章离散信道编码定理（2学时）第六章线性分组码（6学时）第九章无记忆信源的有失真编码（6学时）本课程是通信专业的基础理论课课程特点以及学习要求•信息论主要是应用概率论、数理统计以及随机过程等方法来研究信息传输、存储和处理，因而它对数学要求较高，公式推导较复杂，所以课堂上一定要认真听讲。另一方面，要求大家多做练习，深入理解基本概念以及基本定理。•关于考试形式，采用闭卷120分钟，最终课程成绩由2部分构成：试卷90％，平时10％。其它事项•听课按时、请假、课堂秩序•作业按时、独立完成•答疑课前、网络、集中教材与参考书教材：王育民、李晖、梁传甲编著，信息论与编码理论，高等教育出版社，2005.12参考书：1．傅祖芸编，信息论—基础理论与应用，电子工业出版社，2005.122．ThomasM.Cover，ElementsofInfomationTheory.JohnWiley&Sons,INC.,2006.1（信息论基础，机械工业出版社，2007.7）信息论的基本概念shannon信息论的中心问题信息论的研究内容信息论发展简史第一讲引论什么是信息论?1948年,ClaudeShannon在他的经典论文“AMathematicalTheoryofCommunication”（通信的数学理论）的引言部分写道：“通信的基本问题就是在某一点精确或近似地再生另一点选择的信息。”为解决这一问题，他在该论文中提出了应用数学的一个全新分支，现在称之信息理论或信息编码理论，宣告了一门崭新的学科──信息论的诞生。信息论是研究信息的传输、存储和处理的科学。信息论研究的基本任务是为设计有效而可靠的通信系统提供理论依据。Shannon信息论的核心思想考虑一对特殊的数学模型：二进制对称信源和二进制对称信道二进制对称信源：输出符号0和1，等概分布，速率为单位时间内R个符号，称之比特bits(binarydigits)。二进制对称信道（BSC）：一个在单位时间内可以传输1比特数据的实体，但该信道并不是完全可靠，存在一个固定的概率p，满足0≤p≤1/2，使输出比特与输入比特不相同。现在设想有二个人，一个是发送者，另一个是接收者。发送者必须使接收者尽可能精确再生信源的输出，而他们之间的唯一通信链路就是BSC。注：在启动信源之前，容许发送者和接收者在一起了解彼此将采用的数据处理策略，不对计算能力和存储资源限制。编码问题:对于给定的一个信源速率R、发送者和接收者之间通过BSC的通信可以达到多高的可靠度？shannon信息论给出此问题的精确结论。•假设R=1/3,即信道传输速率是信源产生数据速率的3倍。在传输之前，可以对信源输出的每一比特重复3次（重复编码方法）。码字：000,111例如：信源输出10100，编码后111000111000000对每一信源输出比特，接收者收到3比特，但这3比特可能不完全相同（为什么？）。如信道干扰了传输的第2、5、6、12和13比特，接收者收到101，011，111，001，100。译码最佳策略是什么？对接收到的3比特多数判决(最佳）?101，011，111，001，100,译码结果：11100。一般地，用pb表示误比特率:2233b233(1)32p1/2,pp.bppppppppQ个信道错误个信道错误2111RRpRpb如果R1,即信源产生数据速率是信道传输速率的R倍。问题：如何信源数据压缩（信源编码方法）？方法1：仅传送信源比特的1/R，并且接收者以抛硬币的方式猜测其余的部分。误比特率pb为:方法2：如R=3，信道仅传送信源比特的1/3，因此发送者将信源输出分成3比特一组，并且只传输这3比特中占多数的比特。例如：信源输出101,110,101,000,101信道传输11101最佳译码策略：接收者只需将收到的每个比特重复3次.24143)1(41ppppb3313/)21(21pppb误比特率pb为:注意到：R=3,方法1的误比特率pb为：问题：更有效的编码方法吗？答案是肯定的。回到问题:对于给定的一个信源速率R、发送者和接收者之间通过BSC的通信可以达到多高的可靠度？给定信道，如存在一种编码，码速率R≤x，误码率Pe≤y，则称点（x，y）是可达的。特别地，Pe任意小，可达码速率R的上界该上界称为信道容量。什么是信息?信息的定义很难给出，象物质和能量一样，难以给出明确的定义。在日常生活中，信息经常被误认为就是“情报”、“消息”等。情报：人们对于某个特定对象所见、所闻、所理解而产生的知识。消息：用文字、符号、数据、语言、音符、图片、图像等能够被人们的感觉器官所能感知的形式，把客观物质运动和主观思维活动的状态表达出来就成为消息。消息中包含信息，它是信息的载体。什么是信息?香农在1948年发表了一篇著名的论文，“通信的数学理论”。他从研究通信系统传输的实质出发，对信息作了科学的定义，并给出了定性和定量的描述。Shannon信息定义香农将各种通信系统概括成如图示框图。信源信道信宿噪声或干扰简单通信系统框图输入消息码字输出消息先验概率消息后验概率收到0收到01收到011x1x2x3x4x5x6x7x80000010100111001011101111/81/81/81/81/81/81/81/81/41/41/41/40000001/21/2000000010000Shannon信息定义特点:通过消息的传递，收信者消除或部分消除消息内容不知、不确定。不确定性的消除或部分消除就获得了信息。原先的不确定性消除得越多，获得的信息就越多。香农信息的定义：信息是事物运动状态或存在方式的不确定性的描述。信息是具有不确定性的消息中所包含的表示事物特性的内容。信息、消息和信号•信息–事物运动状态或存在方式不确定性的描述。•消息–指包含有信息的语言、文字和图像等。•信号–消息的物理体现。【例】摸球试验甲袋共100个球，红球白球各50个；乙袋共100个球，红、白、蓝、黑球各25个；现随意从甲袋或乙袋中取出一球，并猜测取出球的颜色？事物出现某状态不确定性的大小，与该状态出现的概率大小有关不确定性度量概率空间•样本空间–信源所有可能发送的消息符号•先验概率p(xi)–选择符号xi作为发送消息的概率)()()(2121nnxpxpxpxxxPX(())ifpx不确定性大小(())fpx不确定性大小信息定义应该满足以下3个条件(1)0f(())fpx是单调减函数独立可加性(()())(())(())fpxpyfpxfpy1.2.3.•自信息其中：a1•条件自信息)(1log)(iaixPxI1()log()ijaijIxypxy信息定义先验概率p(xi)－选择符号xi作为发送消息的概率后验概率p(xi|yj)－接收端收到消息yj后而发送端发的是xi的概率香农定义的信息的优缺点•优点–有明确的数学模型和定量计算公式–与日常用语中的信息含意一致–排除了对信息一词某些主观上的含意•局限性–没有考虑收信者的主观特性和主观意义–定义的出发点假定事物状态可以用一个概率模型来描述信息论的基本概念shannon信息论的中心问题信息论的研究内容信息论发展简史第一讲引论通信系统模型•我们将各种通信系统中具有共同特性的部分抽取出来概括成一个统一的理论模型，通常称它为通信系统模型。通信系统模型这个模型主要分成五个部分：信源、编码器、信道、译码器和信宿。信源•信源是信息的来源，信源的输出称为消息。•信源输出的消息是随机的、不确定的，但又有一定的规律性。•依据信源输出的消息分类：数字信源/模拟信源；离散信源/连续信源；独立信源/相关信源；无记忆信源/有记忆信源；•信源研究的主要问题:消息的统计特性和信源产生信息的速率。编码器•编码器是把信源发出的消息变换成适合信道传输的信号的设备。信号携带着消息，它是消息的载荷者。•编码器可分为二种，即信源编码器和信道编码器。•信源编码是在一定准则下，对信源输出的消息进行适当的变换和处理，目的是为了提高信息传输的效率，为了提高信息传输的有效性。•信道编码是为了提高信息传输的可靠性而对消息进行的变换和处理。•对于各种实际的通信系统，信道编码器还应包括调制等各种变换处理。信道•信道是指通信系统把载荷消息的信号从甲地传输到乙地的媒介（信息传递的媒介），它包含收发设备在内的物理设施。•狭义的通信系统中实际信道：有线信道：明线，电缆，光纤，波导。无线信道：短波，高频，微波，光波。•广义的通信系统信道：信道除了传送信号以外，还有存储信号的作用。信道•在信道中存在噪声和干扰。为了分析方便起见，把在系统其他部分产生的干扰和噪声都等效地折合成信道干扰。•由于干扰或噪声往往具有随机性，所以信道的特性也可以用概率空间来描述。•噪声源的统计特性是划分信道的依据。恒参信道：信道特性不随时间变化，如有线，微波。变参信道：信道特性随时间变化，如短波。离散信道：输入输出离散连续信道：输入输出连续•信道的中心问题：信道的统计特性和信道容量译码器和信宿•译码就是把信道输出的编码信号(已迭加了干扰)进行反变换。•一般认为这种变换是可逆的，但可能近似的。•译码器也可分成信源译码器和信道译码器。•中心问题：研究各种可实现的解调和译码方法。信宿是消息传送的对象，即接收消息的人或机器。信息传输系统模型信道信源信源编码加密信道编码干扰源信宿信源译码解密信道译码加密密钥解密密钥信源信源编码信道信道编码信息传输系统模型Shannon信息论的中心问题•中心问题：找到信息传输过程的共同规律，以提高信息传输的可靠性、有效性、保密性和认证性，使达到信息传输系统最优化。•所谓可靠性高，就是要使信源发出的消息经过信道传输以后，尽可能准确地再现在接收端。•所谓有效性高，就是用尽可能短的时间、尽可能少的功率和频谱、及尽可能少的设备来传送一定数量的信息。•提高可靠性和提高有效性常常会发生矛盾，这就需要统筹兼顾。•保密性：隐蔽和保护通信系统中的传输内容，授权接收者。•认证性：验证消息的完整性。信息论的研究内容•狭义信息论（香农基本理论）–主要研究信息的测度、信道容量以及信源和信道编码理论等问题。•一般信息论–除香农信息论，还包括噪声理论、信号滤波和预测、统计检测和估计等。•广义信息论–不仅包括上述两方面内容，而且包括所有与信息有关的自然和社会领域，如模式识别、心理学等信息论的基本概念shannon信息论的中心问题信息论的研究内容信息论发展简史第一讲引论1924年奈奎斯特“影响电报速率的一些因素”－信息速率与信道带宽成正比1928年哈特莱“信息的传输”－给出了信息度量方法1936年阿姆斯特朗－增大带宽可以提高抗干扰能力1948年Shannon“通信的数学理论”－用概率论的方法研究通信系统，是现代信息论开创性的权威论文信息论的形成1832年莫尔斯电报系统中高效率编码方法1939年达德利发明了声码器。1885年凯尔文研究了一条电缆的极限传信率问题–1959年，Shannon提出率失真函数和率失真信源编码定理–1971年，伯格尔(T．Berger)给出更一般信源的率失真编码定理–率