信息论第1章绪论

1、Information Theory and CodingOriginally used textbook：“Information Theory & Coding (English Edition)” 梁建武梁建武 郭迎郭迎 编著；中国水利水电出版社编著；中国水利水电出版社Instructor：Prof. Yueheng Li (李岳衡)Email: Yueheng_Office：No. 4415, QingXue BuildingReference books：1. T. M. Cover & J. A. Thomas , “Elements of Information Theory ”

2、，Addison-Wesley Pub, 1990, 清华影印 。2. 曹雪红、张宗橙，信息论与编码， 清华大学出版社，2009年，第二版。3. 傅祖芸，信息论基础理论与应用， 电子工业出版社，2012，第三版。 Grading method： “Final End-term Report” plus “Course Attendance”Course schedule:Curriculum objectivesUnderstanding the basic concepts and fundamental computation of Information Theory instead o

3、f the complicated proofMastering the basic concepts of classical Information Measure and Source CodingChapter 1. IntroductionShannon information measureDiscrete Source InformationChannel and Channel CapacityLossless source coding theorem - Shannon first theoremIntroduction to Info. Theory & Coding (

4、1). Main contents of the course(2).Importance of the Info. TheoryThe Info. Theory is the elementary theory of Info. Science and Technology.Without the foundation of Info. Theory, one cannot be engaged in the corresponding field research and innovation, nor can he touch the edge of this discipline (学

5、科) . 1.1 Whats Information Although there is no accurate definition of Info., it has two obvious characteristics : widespread and abstractive widespread （广泛性） The objective world is filled with “information” The humanity cannot leave information abstractive （抽象性） Its hard to be understood and to est

6、ablish the concept in our mind.InformationInformation：Without information, we cannot use the matter and the energy well. Also it is a higher level that man knows the objective world (客观世界). 1. In a narrow sense, the information in correspondence can be divided into three levels : Signal, Message, In

7、formation.Signal: is the physical expression level of the information. It is the most concrete level. It is a physical quantity, an entity to load information, and may be surveyed, described and demon-strated.Message：(also named symbol) is the mathematical expression level of the information. Althou

8、gh it is not a physical quantity, but it can be described in a form of quantity. It is the further mathematical abstract of a concrete physical signal. The concrete physical signal is divided into two types: the discrete (numeral) message, is a group of unknown quantities; may be described with the

9、random sequence : U=(U1 Ui UL)the continuous (analog) message, is a group of unknown quantity; it may be described with the stochastic process (随机过程) : U(t,) Information: It is a more higher level of philosophy abstract, that is, it is the higher expression level of signal and message. In these thre

10、e levels, the signal is the most concrete, and the information is the most abstract. To understand: information may be considered as the connotation (内涵) of a concrete physical signal and the mathematical description of a message, namely, the concrete loaded content of signal and message description

11、. Conversely, signal is the extension of an abstract information in the physical level. Message is the extension of the abstract information in mathematical level expression. Shannon Info.(Probability information)The information is the description of state of motion or the indefinite existence way o

12、f the matter.It seemed that the message is transmitted in a communication system, but actually the info. is transmitted .sourcedestinationchannelmessageInterference or noise（transmitter）（receiver）Fig.1.1 Communications system block diagramcodingdecodingmessagesignalsignalSample space: since things m

13、ay have various appearance, we call the message set (符号集) of all possibilities sample space.Regarding the discrete message set, the probability measure is to assign a probability to each possibility. A sample space and its probability measure is called probability space. Expressed as:X，P(x)In discre

14、te case： In this expression， is the selected symbol; is the probability of message, called prior probability. )(,),(),(,)(2121qqaPaPaPaaaxPXia)(iaPSelf-Info. of the message（symbol）：A Posteriori Probability：also called conditional probability: the probability that the receivers received message (symb

15、ol) is , whereas the transmitter has transmitted . Mutual information: the self information minus the conditional self information (information contents which the receiver obtains)ia1()loglog()()iiiI aP aP a )|(jibaPjbia(),(|)1(|)11(;)logloglog0,(|)()()(|)(),(|)0iijijijijiiijiijI aP abP abI a bP abP

16、 aP aP abP aP abCould be positive, negative and zero.allpartnot at all 自信息物理意义：自信息物理意义：是对事件 不确定性的一种数学度量，该度量值体现了当不确定事件 发生时，其对我们知觉的一种“冲击性”或“震撼性”（也即我们平时所谓的“信息”）的一种数学定量描述。iaia1.2 Whats Information TheoryIt is the theory that C. E. Shannon summarized from the martial intelligence transmission question in

17、 late 1940s. The theory regards the objective probability information as the research objects. Its main research questions include:source description, information ratio measurement, analysis and computation channel description, the channel transmission ratio measurement, analysis and computation. st

18、atistical match between source, channel and communication systems, as well as optimization of communication systems - i.e. the three Shannon coding theorems. The Info. Theory has been developed for more than 60 years; until now, it is still the basic theory to instruct the development of communicati

19、on technology, and it is also the fountainhead (origin) of innovating new correspondence system .Current status:Origin and Development of Info. TheoryIn humanitys historical development, the information transmission and the dissemination method have experienced five steps:First transformation: produ

20、ction of language Second transformation: production of writing Third transformation: invention of printing method Fourth transformation: invention of telegram and telephoneFifth transformation: both computer technology and communication are unified, which have promoted the so-called network developm

21、entContribution of ShannonIn 1948, Shannon published the famous paper “A Mathematical Theory of Communications (通信中的数学理论)” , which symbolized the birth of Info. Theory; In 1949, he published “Communication Theory of Secrecy Systems.” In this theory, he first used the viewpoint of Info. Theory to mak

22、e comprehensive elaboration on information security ; In 1959, he published “ discrete source coding theorem with the fidelity criterion “. In this paper, he proposed the data rate loss theory, and laid the theoretical foundation for the source compression coding research;In 1961, he published the b

23、i-channel communication , which developed the multi-user information theory (network information theory);Claude Elwood Shannon (1916-2001)l The father of information theoryl The father of practical digital circuit design theoryl Bell Laboratories (1941-1972), MIT(1956-2001)Research category of Infor

24、mation TheoryGeneralized Info. TheoryEngineering oriented Info. TheoryEssential Info. Theory Elemental Info. Theory Research the mathematical description and quantitative analysis of a communication system. Research the optimization of systems, namely the theoretically potential power of a communica

25、tion system and its mathematical limit. Also called Mathematical Info. Theory.Engineering oriented Info. Theory Primarily engaged in technical questions in engineering. Mainly includes:source coding, decoding theory and its design structure methodchannel coding, decoding theory and its design struct

26、ure method optimal modulation and demodulation theory and realization best examination, estimate value and best receiving theory and realization optimal information processing theory, method and algorithmGeneralized Info. Theory (GIT)The classical information theory founded by Shannon is “probabilit

27、y-based information theory”;GIT was developed to broadly treat uncertainty-based information, not restricted to probabilistic formalization of uncertainty.3. The goal of GIT is to develop the capability to deal with any type of uncertainty-based information that we can recognize;4. The primary conce

28、pt of GIT is uncertainty, and information is defined in terms of uncertainty reduction achieved by a relevant action1. G. J. Klir, Generalized information theory. Fuzzy Sets and Systems, 40(1): 127-142, 1991. 2. G. J. Klir, Generalized information theory: aims, results, and open problems. Reliabilit

29、y Engineering and System Safety, 85 (1) 2138, 2004. Development of Shannon Info. Science (傅祖芸信息论基础理论与应用)2.The application and achievement of Info. TheoryVoice signal compression Voice signal is the earliest form of information to be transmitted. Image signal compression The compression of image has

30、significant significance to saving/transmitting images due to huge redundant info. in it. Some example standards and their compression ratios: H.261 48:1 (TV conference) JPEG 24:1 (Static image) MPEG-1 50:1 （Dynamic image）File compression Until now there are more than 20 kinds of compression algorit

31、hms. Source programs, destination codes, papers, novels, scientific data, books can all be compressed by 30 percent. They are all lossless compression.Enhancing data transmission speed in analog telephone channel According to the Info. Theory, when the bandwidth of one channel is 4KHz, and the ratio

32、 of signal-to-noise is 25dB, the speed in this channel will be 25Kbit/s. Namely , the speed was 100bit/s19.2Kbit/s before and now almost reaches the limitation 25Kbit/s.Reducing the transmitting power According to Info. Theory : if we use the information encoding with low code rate, we are possible

33、to reduce the ratio of the energy-to-noise ratio. Fault-tolerant coding Storage error is inevitable (e.g. the face of the disk is apt to be damaged). So we need to take measures to check and correct the errors. For storage checking: Fire code, BCH code, RS code. Recovery and rebuilding of image sign

34、als It is an important content of image processing, for example, the Max Entropy Method. Pattern classification To use entropy in distinction information, mutual information, will yield very good results in the language recognition. Other achievements Many great achievements have been achieved in linguistics, biology, medicine, neural network, economi