第1章 信息论预编码绪论

2023/2/51信息论与编码理论

40学时张延良计算机学院ylzhang119@TEL:136139147852023/2/52教材教材：《信息论与编码》第2版电子工业出版社十一五规划教材陈运主编参考书：《信息与编码理论基础》

上海大学出版社万旺根主编《信息论基础》北京航空航天大学出版社周荫清主编《信息论与编码》清华大学出版社2023/2/53前续课程概率论与数理统计信号与系统后继课程通信原理计算机网络移动通信2023/2/54主要内容2.12345概论信源熵信道容量信息率失真函数信源编码147信道编码密码学62023/2/55第1章概论主要内容：1.1信息的一般概念1.2通信系统模型1.3信息论的起源、发展1.4信息论的研究内容2023/2/56第2章信源熵主要内容：2.1单符号离散信源

2.2多符号离散平稳信源及熵2.3连续信源及熵2023/2/57第3章信道容量主要内容：3.1信道的数学模型与分类3.2单符号离散信道的信道容量3.3多符号离散信道的信道容量3.4连续信道及其容量2023/2/58第4章信息率失真函数主要内容：4.1基本概念4.2

离散无记忆信源R(D)的计算4.3连续无记忆信源的R(D)的计算

2023/2/59第5章信源编码主要内容：5.1离散信源最佳变长编码5.2连续信源编码2023/2/510第6章信道编码主要内容：6.1信道编码简介6.2线性分组码6.3循环码6.4卷积码2023/2/511第7章密码学主要内容：密码基本知识古典密码体制现代密码体制2023/2/512主要内容2.12345概论信源熵信道容量信息率失真函数信源编码147信道编码密码学6离散信源连续信源单符号离散信源多符号离散信源离散信道容量连续信道容量：信源压缩编码的理论基础离散信源连续信源定长编码变长编码线性分组码循环码卷积码2023/2/513第1章概论主要内容：1.1信息的一般概念1.2通信系统模型1.3信息论的起源、发展1.4信息论的研究内容2023/2/514信息社会人类社会的生存和发展，时刻离不开接收信息、传递信息、处理信息和利用信息。古代烽火台上的狼烟，传递的是战争信息，通知人们有敌来犯。花儿开放时的色彩和花香，传递的是信息，引诱蜜蜂蝴蝶为其授粉。天冷了，感觉到身上起鸡皮疙瘩，传递的是冷暖信息，告诉人们该添衣服了。张贴画像，传递的是人的相貌信息，用于寻人。2023/2/515信息是人们对客观事物运动规律及其存在状态的认识结果。信息的价值在于它为人们能动地改造外部世界提供了可能。2023/2/516信息的传输手段信息的传输手段的变革，传输速度的快慢，决定了一个社会的现代化程度和发展速度。战争情报（信息）：古代用烽火狼烟、快马来报现代用计算机网络、无线通信手段来报寻人（信息）：古代用张贴画像现代用互联网通缉、人肉搜索讲课传授知识（信息）：以前用板书现在用多媒体课件2023/2/517信息的定义通俗地理解：信息被认为是消息、知识、情报。信息与其联系密切，但信息的定义更深刻、广泛。信息不等同于消息：有神秘人士告诉你两条绝密消息：世界银行要招副总裁比尔盖茨要为女儿择婿知识是一种具有普遍性和概括性的高层次的信息情报是军事上专用的一类特定的信息信息就是信息，它既不是物质也不是能量（1948年，维纳）。信息、物质和能量是构成一切系统的三大要素。2023/2/518信息与消息的关系信息是系统中传送（或存储、处理）的对象，它包含在消息之中。同一信息可用不同消息形式（如语言、文字、图像）来传递。如巴菲特、比尔盖茨要来中国开慈善晚宴的信息通过电视新闻、广播、网络、报纸等传输媒介以图像、声音、文字的消息形式为人所知。消息是信息的载体，是比较具体的形式，如语言，文字，数字，图像。所有这些形式都是可以被人们所感觉到的。2023/2/519消息与信号的关系信号是消息的载体。是用来表示消息的物理量（声音信号、电信号、光信号）可用不同类型的信号（如声、光、电）传递同一消息。如“日军轰炸珍珠港”的信息，用汉文“日军轰炸珍珠港”的消息来表述，然后用电报系统把汉字转化为莫尔斯码，再转化，调制成电信号进行传输。此时电信号里载荷有汉文消息“日军轰炸珍珠港”。2023/2/520信号携带消息，消息表征信息。同一信息可以用不同的信号来表示高考成绩（信息）可以通过电话查询（电信号）得到；也可以通过网络查询得到（数字信号）。同一信号在不同的情况下表示不同的信息红绿灯信号在十字路口表示是否通行的信息在电子仪器板上，表示仪器是否正常工作的信息信号消息信息2023/2/521信息的主要特征信息是无形的，看不见，摸不着，不具实体性，它必须依赖一定的消息形式才能为人所获知。信息有大小，可以度量：如考试成绩：有人考的不好，估计就在50分上下，及格的概率为51%，那么这个同学一旦获知考试及格了，会非常的兴奋，会认为这个消息包含的信息量很大。有人考的好，估计在80分上下，及格的概率为99.9%，那么这个同学如果获知考试及格了，会很平静，认为在意料之中，那么这个消息包含的信息量就很小。消息在收到之前未知（以一定的概率存在），收到之后可以获取信息，从而认识事物。信息可以共享（互联网就是一个共享各种信息的平台）。信息可以压缩，传输，接收，消失。有一定的时效性。2023/2/522信息科学信息科学是一门综合性学科，它研究信息及其运动规律。研究的内容包括：信息的本质及其度量，信息的产生、获取、传播、存储及处理。研究的目的：扩展人们获取信息的手段和速度，提高信息的利用能力2023/2/523信息科学带来的信息产业信息产业是专门从事信息的生产、传播、出售和服务的行业。包括：信息技术设备制造：手机生产、天线制造、交换机生产、光缆/光传输设备生产…….信息服务：手机增值业务开发、电子出版、数据库服务、网络接入服务、网络应用服务（企业信息化建设、电子商务）、网络推广…….2023/2/524第1章概论（简介）主要内容：1.1信息的基本概念1.2通信系统模型1.3信息论的起源、发展、研究内容1.4研究内容2023/2/525通信系统通信系统：信息的传输系统。如：电话、计算机系统2023/2/5261.2通信系统模型信源、信道、信宿信源是消息的来源信道是消息传送媒介信宿是消息的目的地信源编码器信道译码器信宿干扰源2023/2/527通信系统模型进一步细分信源信源编码器纠错编码器调制器信道干扰源解调器信道译码器信源译码器信宿等效离散信道等效离散信源等效信宿信道编码器信道译码器产生消息的源，消息可以是文字，语言，图像。可以离散，可以连续。随机发生。研究的主要问题是消息的统计特性和产生信息的速率对信源输出进行变换，重在有效性对信源编码输出变换，提高抗干扰性将信道编码输出变成适合信道传输的方式信号从发端传到收端的介质信道的中心问题是研究信道的统计特性和传信能力，即信道容量系统各部分引入的干扰，包括衰落，多径，码间干扰，非线性失真，加性噪声。这种干扰源的统计特性是划分信道的重要因素，并且是决定其传输能力的决定因素。译码器：编码器的逆变换中心问题是研究各种可实现的解调和译码方法信息的接收者2023/2/528通信系统模型组成信源信宿信源编/译码信源编码集中于解决传输的有效性问题；去除冗余信息例：语音压缩编码Vocoder图象压缩编码JPEGMEPG文本压缩编码Winzip

信道编/译码信道编码集中于解决抗信道干扰和失真问题，即解决传输的可靠性问题。需要添加冗余信息例：卷积码、级联码、Turbo码调制/解调电波辐射传播多址接入信道复接躲避和抑制干扰信道加性噪声乘性衰落2023/2/529信息传输系统的性能要求可靠性：使信源发出的消息经信道传输后，尽可能准确地、不失真地在接收端重现。有效性：用尽可能短的时间和尽可能少的设备来传输一定数量的信息。保密性：隐蔽或保护通信系统中传输的信息，使它只能被授权接收者获取，非授权接收者不能接收和理解。认证性：接收者能够正确判断接收到的消息的正确性。验证消息的完整性，判定不是伪造或篡改的。可靠性、有效性、保密性和完整性共同构成现代通信传输系统的全面要求。2023/2/530第1章概论（简介）主要内容：1.1信息的基本概念1.2通信系统模型1.3信息论的起源、发展1.4研究内容2023/2/5311948年以前信息论的发展Telegraph(Morse,1830’s);Telephone(Bell,1876);WirelessTelegraph(Marconi,1887);AMRadio(early1900’s)Single-SidebandModulation(Carson,1922);1924年H.Nyquist：信号带宽与信息速率的关系。指出如果以一定的速率来传输信号，则需要一定的带宽，将信息率和带宽联系起来了。Television(1925-1927);1928年，R.V.Hartley：提出用对数度量信息。Teletype(1931);FrequencyModulation(Armstrong,1936)：增大带宽，可以提高抗干扰能力。基于此思想，提出宽频移调制。Pulse-CodeModulation(PCM)(Reeves,1937-1939);Vocoder(Dudley,1939)：广泛应用于广播、电视。提出了通信带宽>=传送的消息带宽SpreadSpectrum(1940’s).2023/2/532控制论之父——维纳N.Winner（维纳）20世纪30年代“广义谐波分析理论”，首次对信息系统中的随机过程进行谱分析。20世纪40年代：将随机过程和数理统计的观点引入通信和控制领域，揭示信息传输和处理过程的统计本质。20世纪50年代：提出干扰作用下的最佳滤波定理。2023/2/533信息论鼻祖——香农Shannon1948年“通信的数学理论”（“Amathematicaltheoryofcommunication”）文章的发表，标志着信息论的正式诞生。指明通信的实质：“Thefundamentalproblemofcommunicationisthatofreproducingatonepointeitherexactlyorapproximatelyamessageselectedatanotherpoint.”提出无失真信源编码定理，给出了简单的编码方法（香农编码）2023/2/534无失真信源编码的发展1956年，麦可米伦（B.Mcmillan）首先证明了唯一可译变长码的克拉夫特（Craft）不等式。1952年，费诺（Fano）提出了一种费诺码。1952年，哈夫曼（D.A.Huffman）首先构造了一种哈夫曼编码方法，并证明为最佳码。1977年，通用信源编码算法-LZ码由齐弗(J.Ziv)和兰佩尔（A.Lempel）提出.1978年，他们又提出了改进算法，并证明此方法可以达到信源的熵值。1990年，贝尔（Bell）又对LZ算法进行了一系列的变化和改进。目前，LZ广泛应用于文本的数据压缩。语音编码标准:MP3,MP4图象编码标准:MPEG42023/2/535信道编码理论的发展60年代起，信道编码技术有了长足发展。1950年，出现了汉明码（HammingCode）和循环码（CyclicCode），把代数方法引入纠错码的研究，形成了代数编码理论。但代数编码的渐进性较差，无法实现香农信道编码定理所指出的结果。1960年左右，提出了卷积码（ConvolutionCode）的概率译码。形成一系列概率译码理论。几十年来，相继出现很多编码算法，性能与香农限相差甚远，以致人们认为香农限是不可能达到的。1993年，法国学者C.Berrou等人提出了Turbo码的并行级联卷积码，其性能与香农限非常接近(误码率达10-5)，且复杂度较低可以实现，为信道编码领域带来一场革命。2023/2/536限失真信源编码定理的发展限失真信源编码的研究较信道编码和无失真信源编码晚了近十年。香农在1948年的论文中已体现了率失真函数的思想。1959年，香农发表了“保真度准则下的离散信源编码定理”（“Codingtheoremsforadiscretesourcewithafidelitycriterion”），首先提出了率失真函数和率失真信源编码定理。从此，发展成为信息率失真编码理论。1971年，伯格尔（T.Beger）给出了更一般信源的率失真编码定理。率失真信源编码定理是信源编码的核心问题，是频带压缩、数据压缩（信源压缩编码）的理论基础。2023/2/537网络信息论的发展1961年，香农发表的论文“双路通信信道”开拓了多用户信息理论。随着卫星通信、计算机通信网的迅速发展，多用户理论的研究取得了突破性的进展。20世纪70年代以后，人们从经典的香农单向通信的信息论推广到多用户信息理论。多用户信息理论成为当前信息论的中心研究课题之一。2023/2/538第1章概论（简介）主要内容：1.1信息的基本概念1.2通信系统模型1.3信息论的起源、发展1.4研究内容2023/2/5391.4信息论研究的内容狭义信息论（经典信息论）即Shannon信息论研究信息测度，信道容量以及信源和信道编码理论信息的度量信道的容量信息率失真函数信源编码信道编码2023/2/540Shannon信息论的中心问题信息传输中出现的问题：

问题一：信源消息常常不能够完全发送。（否则发送量巨大，比如：信源消息是一片无尽的天空。因此优先拣有用的发送。什么是有用的？就是信息量大的。什么是信息量大的？）问题二：信道因干扰而出现差错，必须进行检错和纠错。（否则所收到的消息无法识别。）

信源信道信宿2023/2/541Shannon信息论针对以上问题的解决方法：问题一：如何拣有用的信源信息来发送。通过信源编码，去掉冗余的信息，提高有效性。问题二：如何抵抗或抵消传输中遇到的干扰引起的误码。通过信道编码，增加多余的信息，使各符号间相互存在一定的牵连关系，提高可靠性。如：传输用户的密码信息：aqv分析：26种符号每个符号最少用5位二进制来进行信源编码000000101001110想增加抗干扰能力，最简单的信道编码时奇偶校验码，即增加一位，使和其它各位相加后结果为0：0000000101000111012023/2/542狭义信息论体系结构Shannon信息论压缩理论有失真编码无失真编码等长编码定理Shannon1948McMillan1953变长编码定理Shannon1948McMillan1956Huffman码(1952)、Fano码算术码(1976,1982)LZ码(1977,1978)率失真理论ShannonGallagerBerger压缩编码JPEGMPEG传输理论信道编码定理网络信息理论纠错码编码调制理论网络最佳码2023/2/5431.4信息论的研究内容

——续一般信息论研究信息传输和处理问题，除经典信息论外还包括噪声理论，信号滤波和预测，统计检测和估值理论，调制理论，信息处理理论和保密理论一般信息论：香农信息论+Winner的滤波理论Shannon

：研究的对象是信源到信宿的传输全过程，是收发端联合优化问题。解决的方法是编码。Winner：研究消息在传输中受到干扰时，如何在接收端将消息从干扰中提取出来。包括解决方法是滤波。重点在接收端。2023/2/544广义信息论：用信息基本理论来研究一切可以抽象为广义通信系统模型的过程或系统。除一般信息论研究的内容外，还包括自然和社会领域有关信息的内容，如模式识别，计算机翻译，心理学，遗传学，神经生理学1.4信息论的研究内容

——续2023/2/545克劳德.艾尔伍德.香农（ClaudeElwoodShannon）

——数学家、信息论的创始人

香农（1916—2001）：1916年4月30日出生于美国密歇根州的加洛德（Petoskey）1936年毕业于密歇根大学并获得数学和电子工程学士学位1940年获得麻省理工学院（MIT）数学博士学位和电子工程硕士学位1941年他加入贝尔实验室数学部，工作到1972年。1956年他成为麻省理工学院（MIT）客座教授，并于1958年成为终生教授，1978年成为名誉教授。香农博士于2001年2月26日去世，享年84岁。返回2023/2/546维纳维纳是美国数学家，控制论的创始人。维纳1894年11月26日生于密苏里州的哥伦比亚，1964年3月18日卒于斯德哥尔摩。

维纳认为他父亲是天生的学者，集德国人的思想、犹太人的智慧和美国人的精神于一身。从童年到青年，维纳一直在他的熏陶下生活，并逐步成长为一个学者。2023/2/547维纳趣事20世纪著名数学家诺伯特·维纳，从小就智力超常，三岁时就能读写，十四岁时就大学毕业了。几年后，他又通过了博士论文答辩，成为美国哈佛大学的科学博士。在博士学位的授予仪式上，执行主席看到一脸稚气的维纳，颇为惊讶，于是就当面询问他的年龄。维纳不愧为数学神童，他的回答十分巧妙：“我今年岁数的立方是个四位数，岁数的四次方是个六位数，这两个数，刚好把十个数字0、1、