Lecture Notes on Information Theory and Coding Baoming Bai State Key Lab.of ISN,Xidian University bmbai@mail.xidian.edu.cn May26,2020
Lecture Notes on Information Theory and Coding Baoming Bai State Key Lab. of ISN, Xidian University bmbai@mail.xidian.edu.cn May 26, 2020
Goals:The goal of this class is to establish an understanding of the instrinsic prop- erties of transmission of information and the relation between coding and the founda- mental limits of information transmission in the context of communication. Course Outline .Entropy and Mutual information (Measure of information) ·Sourse coding 。Channel capacity ·The Gaussian channel .Coding for a noisy channel(Block coding principles) .Rate distortion theory 基本内容可以概括为： r{镜能整资药务深-ind山adai感时u收sg Textbook:T M Cover and I A.Thon s Elements of info edit 版影印本：清华大学出版社，2003). References: (1)C.E.Shannon,"A mathematical theory of communication",Bell Syst.Tech.J., vol.27,1948. (2)R.G.Gallager,Information Theory and Reliable Communication,Wiley,1968. (3)R.J.McEliece,The Theory of Information and coding,1977.(Thisisa very readable small book) 田不教辰 Information Theory and Network Coding,Springer,2008. (5)J.Massey,Digital Information Theory,Course notes,ETH. (6)M.Medard,Transmission of Information,Course notes,MIT. (⑦)王有民，李晖，信息论与编码理论，第二版，高等教有出版社，2013 (⑧)仇佩亮，信息论与编码，高等教有出版社，2003 (⑨)付祖芸，信息论，电子工业出版社. (10)R.G.Gallager,"Claude E.Shannon:A retrospective on his life,work,and im- pact,"IEEE Trans.Inform.Theory,vol.47,no.7,pp.2681-2695,Nov.2001
Goals: The goal of this class is to establish an understanding of the instrinsic properties of transmission of information and the relation between coding and the foundamental limits of information transmission in the context of communication. Course Outline: • Entropy and Mutual information (Measure of information) • Sourse coding • Channel capacity • The Gaussian channel • Coding for a noisy channel (Block coding principles) • Rate distortion theory 基本内容可以概括为： IT { 通信的基本性能限 逼近性能限的方法 – Coding: source coding, channel coding, network coding Textbook: T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd edition, New York, Wiley, 2006. (中译本：信息论基础，机械工业出版社，2008；第一 版影印本：清华大学出版社，2003). References: (1) C. E. Shannon, “A mathematical theory of communication”, Bell Syst. Tech. J., vol. 27, 1948. (2) R. G. Gallager, Information Theory and Reliable Communication, Wiley, 1968. (3) R. J. McEliece, The Theory of Information and coding, 1977. (This is a very readable small book) (4) Raymond W. Yeung, Information Theory and Network Coding, Springer, 2008. (中 译本：高等教育出版社，2011) (5) J. Massey, Digital Information Theory, Course notes, ETH. (6) M. Medard, Transmission of Information, Course notes, MIT. (7) 王育民，李晖，信息论与编码理论，第二版，高等教育出版社，2013. (8) 仇佩亮，信息论与编码，高等教育出版社，2003. (9) 付祖芸，信息论，电子工业出版社. (10) R. G. Gallager, “Claude E. Shannon: A retrospective on his life, work, and impact,”IEEE Trans. Inform. Theory, vol.47, no.7, pp. 2681-2695, Nov. 2001
Chapter 1 Introduction The fundamental problem of communication is that of reproducing at one point either eractly or approrimately a message selected at another point.-Shannon 1948.Clauide E.Shannon published ap amTo of Com T s paper laid the groundw Information theory studies the transmission,processing and utilization of informa- tion. 1.1 Relationship of information theory and communica tion theory Information theory answers two fundamental questions in communication theory: 1.What is the ultimate data compression?H 2.What is the ultimate transmission rate? Information theoryals cation.(e.g.ra ding 信息理论 通信理论 其木性能图 估计理论 /网络与交 换理论等 信息现论和婚位理论的关系示意图 Shannon理论主要研究基本 通信系统传输的是信号：信号是消息的载体消息中的不确定成分是信息
Chapter 1 Introduction The fundamental problem of communication is that of reproducing at one point either exactly or approximately a message selected at another point. — Shannon In 1948, Claude E. Shannon published a landmark paper entitled “A Mathematical Theory of Communication”. This paper laid the groundwork of a entirely new scientific discipline, “Information Theory”. Information theory studies the transmission, processing and utilization of information. 1.1 Relationship of information theory and communication theory Information theory answers two fundamental questions in communication theory: 1. What is the ultimate data compression? H 2. What is the ultimate transmission rate? C Information theory also suggests means of achieving these ultimate limits of communication. (e.g. random coding, ML decoding) 网络与交 换理论等 Figure 1.1: 信 息 理 论 和 通 信 理 论 的 关 系 示 意 图. Shannon理 论 主 要 研 究 基 本 限(fundamental limits) 通信系统传输的是信号；信号是消息的载体；消息中的不确定成分是信息。 3
4 CHAPTER 1.INTRODUCTION ·狭义信息论(Shannon Theory) o在 的基础 陆 到的最性能限 以用编码方法实现这目标，并在理论上证明信系统可进 瓷产等理论外，还包括最佳接论（合号检、计与制 ·广义信息论 信息论是通信与信息系统的基础理论，是现代通信发展的动力和源泉： oupP oughs within months of each other,have launched and powered the 。信源编码定理→数据压缩技术→无线通信系统从1G变革到2G ·信道编码定理→差错控制编码(Trbo.LDPC)→3G 。数据处理定理→软判决译码 ·高斯噪声是最坏的加性噪声+多用户信息论→CDMA、多用户检测 ·MIMO容量理论→空时编码、预编码→LTE、4G ·多用户信息论协作通信、网络编码→新一代无线系统 The recent work on the information-theoretic aspects of communication concentrated on:1)Network information theory.and 2)MIMO systems. 1.2 What is information?(Measure of information) For Shannon theory,information is what we receive when uncertainty is reduced. How to measure: ·Amount of information should fulfill I≥0 .Amount of information should depend on probability P(r) For independent events:P(X,Y)=P(X)P(Y)I=I(X)+I(Y) It should has the form of log(Self-information of the eventx-z) 1.3 Applications .Data compression:voice coder,MPEG,LZ algorithm. ·Modem
4 CHAPTER 1. INTRODUCTION • 狭义信息论(Shannon Theory) Shannon在前人工作的基础上，用概率统计的方法研究通信系统。揭示了通信系 统中传送的对象是信息；系统设计的中心问题是在干扰噪声中如何有效而可靠地 传送信息。指出可以用编码方法实现这一目标；并在理论上证明了通信系统可达 到的最佳性能限。 • 一般信息论：除Shannon理论外，还包括最佳接收理论（信号检测、估计与调制 理论），噪声理论等。 • 广义信息论 信息论是通信与信息系统的基础理论，是现代通信发展的动力和源泉： I have often remarked that the transistor and information theory, two Bell Laboratories breakthroughs within months of each other, have launched and powered the vehicle of modern digital communications. Solid state electronics provided the engine while information theory gave us the steering wheel with which to guide it. — Viterbi, IT News Lett., 1998. • 信源编码定理→ 数据压缩技术→ 无线通信系统从1G变革到2G • 信道编码定理→ 差错控制编码（Turbo,LDPC）→ 3G • 数据处理定理→ 软判决译码 • 高斯噪声是最坏的加性噪声+ 多用户信息论→ CDMA、多用户检测 • MIMO容量理论→ 空时编码、预编码→ LTE、4G • 多用户信息论→ 协作通信、网络编码→ 新一代无线系统 The recent work on the information-theoretic aspects of communication concentrated on: 1) Network information theory, and 2) MIMO systems. 1.2 What is information? (Measure of information) For Shannon theory, information is what we receive when uncertainty is reduced. How to measure: • Amount of information should fulfill I ≥ 0 • Amount of information should depend on probability P(x) • For independent events: P(X, Y ) = P(X)P(Y ) → I = I(X) + I(Y ) It should has the form of log 1 PX(x) . (Self-information of the event X = x) 1.3 Applications • Data compression: voice coder, MPEG, LZ algorithm. • Modem
1.4.HISTORICAL NOTES 5 Deep space communication (and coding was called a"marriage made in heaven") ●CDMA.MIO.4G .Physical layer security(Information-theoretic securiy) Quantum communication 。Stock market 1.4 Historical notes Sampling theorem:1928 by Nyquist ●Hartley's measure of information1g28)】 I(X)=logL L=number of possible values of X. .Information theory:1948 by Shannon Investigate how to achieve the efficient and reliable communication ·Why using“entropy? Shannon与V.Neuman讨论时，V.Neuman建议用“嫡”， 1.你的不确定函数在统计力学中已经被称为熵(entropy), 2.没有人知道熵到底是什么，所以有争论时你就永远立于不敢之地 。在Shannon1948年的原文中，既没有使用“mutual information”也没有用一个 特殊符号来记它，而总是使用不确定性之差。术语“mutual information”及符 号I(X:Y)是后来由Fano入的. 。Shan was born in Michiga 1916 In 1936.he received BS degree in both electrical engine ering and mathematics from the Univ.of Michigan.Received his M.S.and Ph.D.degree from MIT.In 1941,he joined Bell Lab.In 1958,he accepted a permanent appointment at MIT.随后买了大房子，房子里有很多玩具， Sh prize for the best oublished b an author uder 30.It is widely recomized todayas the foundation of the switching field and as one of the most important Master's theses ever written. His Ph.D.dissertation,"An Algebra for Theoretical Genetics,"was completed in 1940.This thesis was never published. In 1961.Shannon published a pioneering paper "Two-way Communication Chan nels"which established the foundation for the discipline now known as "multi- user information theory";and later N.Abramson published his paper"The Aloha System-Another Alternative for Computer Communications"in 1970 which in- troduced the concept of multiple access using a shared common channel.The information theore appro n to an in 19 a coding t lope a paper"Broadcast channels
1.4. HISTORICAL NOTES 5 • Deep space communication (and coding was called a “marriage made in heaven”) • CDMA, MIMO, 4G • Physical layer security (Information-theoretic securiy) • Quantum communication • Stock market 1.4 Historical notes • Sampling theorem: 1928 by Nyquist • Hartley’s measure of information (1928) I(X) = log L, L=number of possible values of X. • Information theory: 1948 by Shannon Investigate how to achieve the efficient and reliable communication • Why using “entropy”? Shannon 与V. Neuman 讨论时, V. Neuman 建议用“熵”. 1. 你的不确定函数在统计力学中已经被称为熵(entropy). 2. 没有人知道熵到底是什么，所以有争论时你就永远立于不败之地. • 在Shannon 1948年的原文中，既没有使用“mutual information”也没有用一个 特殊符号来记它，而总是使用不确定性之差。术语“mutual information”及符 号I(X; Y )是后来由Fano引入的. • Shannon was born in Michigan, 1916. In 1936, he received B.S. degree in both electrical engineering and mathematics from the Univ. of Michigan. Received his M.S. and Ph.D. degree from MIT. In 1941, he joined Bell Lab. In 1958, he accepted a permanent appointment at MIT. 随后买了大房子, 房子里有很多玩具. • Shannon的硕士论文是关于布尔代数与交换的，他基于此研究工作发表的第一篇 论文won the 1940 Alfred Noble prize for the best paper in engineering published by an author under 30. It is widely recognized today as the foundation of the switching field and as one of the most important Master’s theses ever written. His Ph.D. dissertation, “An Algebra for Theoretical Genetics,”was completed in 1940. This thesis was never published. • In 1961, Shannon published a pioneering paper ”Two-way Communication Channels”, which established the foundation for the discipline now known as ”multiuser information theory”; and later N. Abramson published his paper ”The Aloha System - Another Alternative for Computer Communications” in 1970 which introduced the concept of multiple access using a shared common channel. The information theoretic approach to multiaccess communication began in 1972 with a coding theorem developed by Ahlswede and Liao. In 1972, T. Cover published a paper “Broadcast channels