信息论与编码.ppt

2019/12/6,电信学院江小平,1/43,信息论与编码,2019/12/6,电信学院江小平,2/43,学时：36教材：信息论与编码,陈运,电子工业出版社参考教材：信息论与编码,沈连丰,科学出版社信息论基础理论与应用,傅祖芸,电子工业出版社纠错码原理与方法,王新梅,西安电子科技大学出版社“DigitalModulationandCoding”,S.Wilson,PrenticeHall（“数字调制与编码”影印版，电子工业出版社）,2019/12/6,电信学院江小平,3/43,课程概况,目的：了解学习信息论与编码理论的作用与意义，对信息论与编码理论的研究方法和成果有广泛的基本认识，学会应用，为进一步研究打下基础特点：以概念和物理意义为主，数学推导尽量放到课外作业：部分课后习题。考核：平时30%，考试70%,2019/12/6,电信学院江小平,4/43,信息论的产生,物质客观世界三大基本要素能量信息信息时代社会的发展离不开物质(材料)、能量（能源）和信息资源。美国学者欧廷格说：“没有物质什麽都不存在，没有能量什麽都不发生，没有信息什麽都没意义。”,2019/12/6,电信学院江小平,5/43,课程基本内容,一.信息论信息论的发展以及通信系统的模型离散信源熵，互信息以及冗余度二.信源编码定长编码，变长编码以及最佳编码离散信源的信息率失真函数R(D)限失真信源编码定理以及常用信源编码方法三.信道编码信道模型和容量线性分组码卷积码网格编码调制与级联码Turbo码及其迭代译码原理,2019/12/6,6,1.信息论研究的中心问题和发展历史,2019/12/6,电信学院江小平,7/43,通信的基本问题,通信的基本问题：在一点精确地或近似地恢复另一点所选择的消息。通信系统三项性能指标：传输的有效性传输的可靠性传输的安全性,2019/12/6,电信学院江小平,8/43,Shannon信息论的基本任务,1948年shannon发表了“通信的数学理论”奠定了信息论理论基础基本任务是设计有效而可靠的通信系统可靠是要使信源发出的消息经过传输后，尽可能准确地、不失真地再现在接收端有效是用尽可能短的时间和尽可能少的设备来传输一定信息量的消息安全性,2019/12/6,电信学院江小平,9/43,信息论的研究内容,狭义信息论（shannon经典信息论）研究信息测度，信道容量以及信源和信道编码理论一般信息论研究信息传输和处理问题，除经典信息论外还包括噪声理论，信号滤波和预测，统计检测和估值理论，调制理论，信息处理理论和保密理论广义信息论除上述内容外，还包括自然和社会领域有关信息的内容，如模式识别，计算机翻译，心理学，遗传学，神经生理学,2019/12/6,电信学院江小平,10/43,信息论发展简史,电磁理论和电子学理论对通信理论技术发展起重要的促进作用18201830年，法拉第发现电磁感应莫尔斯18321835建立电报系统。1876年Bell发明电话1864麦克斯韦预言电磁波存在，1888年赫兹验证该理论1895年马可尼发明了无线电通信微波电子管导致微波通信系统，微波雷达系统激光技术使通信进入光通信时代,2019/12/6,电信学院江小平,11/43,信息论发展简史,1832年莫尔斯电码对shannon编码理论的启发1885年凯尔文研究了一条电缆的极限传信速率1922年卡逊对调幅信号的频谱结构进行研究1924年奈奎斯特证明了信号传输速率和带宽成正比1928年Hartley提出信息量定义为可能消息量的对数1939年Dudley发明声码器1940维纳将随机过程和数理统计引入通信与控制系统,2019/12/6,电信学院江小平,12/43,信息论发展简史,1948年shannon信息论奠基1952年Fano证明了Fano不等式，给出了shannon信源编码逆定理的证明1957，Wolfowitz，1961Fano，1968Gallager给出信源编码定理的简介证明，并描述了码率，码长和错误概率的关系。1956McMillan证明了Kraft不等式。1952年Fano码，Huffman码。1976Rissanen算术编码，1977，78Ziv和Lempel的LZ算法1959年，Shannon提出率失真函数和率失真信源编码定理,2019/12/6,电信学院江小平,13/43,信息论发展简史,1950年汉明码Hamming码、Golay码1954年,Reed-Muller码，CRC码1955年Elias提出卷积码1959年BCH码(Bose,Chaudhuri,Hocquuenghem)1960年RS码(Reed-Solomon)1961年，Shannon的“双路通信信道”开拓了网络信息论的研究，目前是非常活跃的研究领域。1960年卷积码的概率译码-Viterbi译码。1966年Forney级联编码概念联编码概念1974年Bahl发明了卷积码的迭代译码算法（BCRJ）1982年Ungerboeck编码调制技术(TCM)。1993年Turbo编译码技术,2019/12/6,电信学院江小平,14/43,狭义信息论体系结构,Shannon信息论,压缩理论,有失真编码,无失真编码,等长编码定理Shannon1948McMillan1953,变长编码定理Shannon1948McMillan1956,Huffman码(1952)、Fano码算术码(1976,1982)LZ码(1977,1978),率失真理论ShannonGallagerBerger,压缩编码JPEGMPEG,传输理论,信道编码定理,网络信息理论,纠错码编码调制理论,网络最佳码,2019/12/6,电信学院江小平,15/43,AWGN:AdditiveWhiteGaussianNoiseLDPC:Low-densityParity-checkCodes,RecentprogressinFECsforopticalcommunicationsystems.,2019/12/6,电信学院江小平,16/43,2019/12/6,电信学院江小平,17/43,香农对信息的定义,信息：是对事物运动状态和变化方式的表征，它存在于任何事物之中，可以被认识主体（人或机器）获取和利用。香农信息论：考虑事物运动状态及其变化方式的外在形式，实际上研究的是语法信息。,2019/12/6,电信学院江小平,18/43,维纳对信息的定义,香农：创立了信息论，但并没有给出信息的确切定义，他认为“信息就是一种消息”。维纳：信息论的创始人之一，把人与外部环境交换信息的过程看作是一种广义的通信过程。后来才认识到“信息既不是物质又不是能量，信息就是信息”。即信息是独立于物质和能量之外存在于客观世界的第三要素。,2019/12/6,电信学院江小平,19/43,香农和维纳理论的区别,香农理论：香农研究的对象是从信源到信宿之间的全过程，是收、发端联合最优化问题，其重点是放在编码。他指出，只要在传输前后对消息进行适当的编码和译码，就能保证在干扰的存在下，最佳地传送和准确或近似地再现消息。为此发展了信息测度理论、信道容量理论和编码理论。维纳理论：维纳研究的重点是在接收端。研究一个信号如果在传输过程中被某些因素（如噪声、非线性失真等）所干扰时，在接收端怎样把它恢复、再现，从干扰中提取出来。在此基础上，创立了最佳线性过滤理论（维纳滤波器）、统计检测与估计理论、噪声理论。,2019/12/6,电信学院江小平,20/43,信息论研究的对象和目的,研究对象：信息论是一门应用概率论、随机过程、数理统计和代数的方法，来研究广义的信息传输、提取和处理系统中一般规律的工程学科。研究目的：提高信息系统的可靠性、有效性和安全性以便达到系统最优化。,2019/12/6,电信学院江小平,21/43,香农信息论的深化研究方向,香农信息论：网络信息理论和多重相关信源编码理论的发展和应用；通信网的一般信息理论研究；信息率失真理论的发展及在数据压缩和图像处理中的应用；信息论在大规模集成电路中的应用；纠错码理论：在工程方面应用最优编码方法研究。维纳信息论：量子检测和估计理论非参数检测和估计理论，非线性检测与估计理论的研究。信源，信道和安全编码之间的结合联合信源信道编码联合安全信道编码,2019/12/6,22,2.通信系统的模型,2019/12/6,电信学院江小平,23/43,通信系统的通用模型,2019/12/6,电信学院江小平,24/43,通信系统的细化模型,等效离散信道,等效离散信源,等效信宿,信道编码器,信道译码器,2019/12/6,电信学院江小平,25/43,各部件功能,信源：(核心问题）信源的消息中所包含的信息量以及信息如何量度产生消息的源，消息可以是文字，语言，图像。可以离散，可以连续。随机发生。研究的主要问题是消息的统计特性和产生信息的速率编码器：(核心问题）将消息变成适合于信道传输的信号信源编码器：对信源输出进行变换（消去冗余，压缩），提高信息传输的有效性信道编码器：对信源编码输出变换（加入冗余），提高抗干扰能力，提高信息传输的可靠性调制器：将信道编码输出变成适合信道传输的方式,2019/12/6,电信学院江小平,26/43,信源编码器,信源编码器的功能是将信源消息变成符号，目的是提高传输有效性，也就是压缩每个信源符号传输所需代码（通常为二进制代码）的数目（对二进制代码称比特数）。例如，一个信源含4个符号a,b,c,d，概率分别为1/2，1/4，1/8，1/8。如果不采用信源编码，每个信源符号至少需要用2个二进制代码传输。如果采用信源编码，分别将a,b,c,d编码成为：0，10，110，111，那么平均每信源符号只需1.75个二进制代码传输。可见，采用合适的信源编码确实能通过压缩码率提高传输有效性。所以，信源编码也称信源压缩编码。,2019/12/6,电信学院江小平,27/43,信道编码器,信道编码器给信源编码符号增加冗余符号，目的是提高传输可靠性。信源编码输出直接传送，不能保证传输可靠性。利用信道编码对信源编码器的输出符号增加一些冗余符号，并让这些符号满足一定的数学规律，使传输具有纠错或检错能力。因为出现传输错误就会破坏这种数学规律。在接收端就会发现错误。例如，最简单的奇偶纠错，将信源编码输出的每个码组的尾补一个1或0，使得整个码组“1”的个数为奇或偶（或模二加为1或0）。当传输发生奇数差错，打乱了“1”数目的奇偶性，就可以检测出错误。,2019/12/6,电信学院江小平,28/43,信道编码器,增加冗余符号提高传输可靠性（图中，有阴影的点表示码字）,2019/12/6,电信学院江小平,29/43,各部件功能,信道信号从发端传到收端的介质信道的中心问题是研究信道的统计特性和传信能力，即信道容量干扰源系统各部分引入的干扰，包括衰落，多径，码间干扰，非线性失真，加性噪声，主要是统计特性,2019/12/6,电信学院江小平,30/43,各部件功能,译码器编码器的逆变换中心问题是研究各种可实现的解调和译码方法信宿信息的接收者,2019/12/6,电信学院江小平,31/43,信息、消息和信号,信息一个抽象的概念，可以定量的描述。信息、物质和能量是构成一切系统的三大要素消息是信息的载体，相对具体的概念，如语言，文字，数字，图像信号表示消息的物理量，电信号的幅度，频率，相位等等,2019/12/6,32,3.香农信息论的应用,2019/12/6,电信学院江小平,33/43,内容,仙农信息论的内容可用一句话概括为：“一个概念，三个定理”，就是信息熵的概念和三个编码定理。,2019/12/6,电信学院江小平,34/43,熵,1关于信源信息的度量仙农将信源限制为具有某一先验概率的随机过程，对信息进行量度是信息论的首要问题。仙农定义了信息熵作为信源所含信息的量度，是信息论中最重要的概念。信息熵的含义与应用以及不同于仙农定义的信息量度方法是研究的主要内容。,2019/12/6,电信学院江小平,35/43,香农第一定理,2.无失真信源编码定理（香农第一定理）无失真信源编码定理，也称仙农第一定理，是信源压缩编码的理论基础，其内容是:如果信源编码码率（编码后传送信源符号所需比特数）不小于信源的熵，就存在无失真编码，反之，不存在无失真编码。可以简述为：其中，R为信源编码码率，H为信源的熵。,编码,2019/12/6,电信学院江小平,36/43,香农第一定理,例如，英文字母加空共27符号，用代码传送，每个符号需5比特。但通过试验发现，实际的英文字母信源熵大约为1.4比特/符号，所以根据仙农第一定理，存在某种信源编码方式，使得每字母仅用1.4个二进制符号就能无失真传送，这样可以显著提高传输效率。由于定理解决的是信源无损压缩极限的理论问题，并未给出普遍的信源编码的方法，所以寻找接近或达到信源熵的压缩编码技术、分析其性能并有效实现是研究的主要问题。,2019/12/6,电信学院江小平,37/43,香农第二定理,3.关于信道容量与信息的可靠传输有噪信道编码定理（香农第二定理）是信道编码的理论基础，其内容是：如果信息传输速率小于信道容量，则总可找到一种编码方式使得当编码序列足够长时传输差错任意小，反之不存在使差错任意小的编码。可以简述为：其中，R为信息传输速率，也称信道编码码率，C为信道容量。,存在译码差错任意小的编码,2019/12/6,电信学院江小平,38/43,香农第二定理,例如，一个带宽为3kHz的系统，用二进符号传输，如果不进行信道编码，无码间干扰的最大传输速率为6kbps，按照香农AWGN信道容量公式可知，通过合适的信道编码，在信噪比为26dB的条件下，实现可靠传输的最大速率可达到25.6kbps。,2019/12/6,电信学院江小平,39/43,香农第三定理,4信息率失真理论（数据压缩的理论基础）在很多情况下，我们并不需要信息精确的传输，而是容许有一定限度差错的传输。这样在保证获取足够信息的前提下，可以提高传输效率，降低通信成本。仙农指出：“实际上，当我们有一个连续信源时，我们感兴趣的不是精确的传输，而只是在一个给定容限内的传输。问题就是，当我们仅需要一定的以合适方式度量的恢复保真度时，我们能不能给连续信源分配一个确定的速率。”为实现限失真传输的有效性，我们总是希望在满足一定的失真要求条件下，使编码器的码率最小，这是一个最优有损数据压缩编码的理论问题，其理论基础就是信息率失真理论，核心是限失真信源编码定理。,2019/12/6,电信学院江小平,40/43,香农第三定理,限失真信源编码定理（香农第三定理）的是有损压缩编码的理论基础，其内容是：对任何失真测度D0，只要码字足够长，总可找到一种编码，使得当信源编码的码率R（D）时，码的平均失真D；反之，如果信源编码的码率R（D），就不存在平均失真D的编码。可以简述为：其中，R为信源编码码率，R（D）称为信息率失真函数，是满足失真准则（平均失真D）下，每信源符号所需最小编码比特数。,2019/12/6,电信学院江小平,41/43,香农第三定理,例如，一个等概率16个符号的离散信源，如果要求不失真信源编码，那么每个信源符号需要4个二进制符号，即平均码长为4比特。但如果允许失真，就可以减小平均码长。如果要求平均失真不超过1/2，即对编码序列进行译码时，最多允许1/2的错误。