《信息论与编码技术》课程教学资源（书籍文献）Information of Theory and Network Coding，Raymond W. Yeung.pdf_大学文库

PrefaceThis book is an evolution from my book A First Course in InformationTheory published in 2002 when network coding was still at its infancy. Thelast fewvearshavewitnessedtherapiddevelopment of networkcodingintoa research field of its own in information science. With its root in informa-tion theory, network coding has not only brought about a paradigm shift innetwork communications at large,but also had significant influence on suchspecificresearch fields as coding theory,networking, switching,wireless com-munications, distributed data storage, cryptography, and optimization theory.While new applications of network coding keep emerging, the fundamental re-sults that lay the foundation of the subject are more or less mature. One ofthe main goals of this book therefore is to present these results in a unifyingand coherentmanner.Whilethe previous bookfocused only on information theoryfor discreterandom variables, the current book contains two new chapters on informationtheory for continuous random variables, namely the chapter on differentialentropy and the chapter on continuous-valued channels. With these topicsincluded, the book becomes more comprehensive and is more suitable to beused as a textbook for a course in an electrical engineering department.What Is inThis bookOut of the 21 chapters in this book,the first 16 chapters belong to Part I.Components of InformationTheory,and thelast 5 chapters belong to Part II,Fundamentals of Network Coding.PartIcovers thebasictopics in informationtheory and prepares the reader for the discussions in Part II. A brief rundownof the chapters will give a better idea of what is in this book.Chapter 1 contains a high-level introduction to the contents of this book.First, there is a discussion on the nature of information theory and the mainresults in Shannon's original paper in 1948 which founded the field.There arealso pointers to Shannon's biographies and his works.Chapter 2 introduces Shannon's information measures for discrete ran-dom variables and their basic properties. Useful identities and inequalities in

Preface This book is an evolution from my book A First Course in Information Theory published in 2002 when network coding was still at its infancy. The last few years have witnessed the rapid development of network coding into a research field of its own in information science. With its root in information theory, network coding has not only brought about a paradigm shift in network communications at large, but also had significant influence on such specific research fields as coding theory, networking, switching, wireless communications, distributed data storage, cryptography, and optimization theory. While new applications of network coding keep emerging, the fundamental results that lay the foundation of the subject are more or less mature. One of the main goals of this book therefore is to present these results in a unifying and coherent manner. While the previous book focused only on information theory for discrete random variables, the current book contains two new chapters on information theory for continuous random variables, namely the chapter on differential entropy and the chapter on continuous-valued channels. With these topics included, the book becomes more comprehensive and is more suitable to be used as a textbook for a course in an electrical engineering department. What Is in This book Out of the 21 chapters in this book, the first 16 chapters belong to Part I, Components of Information Theory, and the last 5 chapters belong to Part II, Fundamentals of Network Coding. Part I covers the basic topics in information theory and prepares the reader for the discussions in Part II. A brief rundown of the chapters will give a better idea of what is in this book. Chapter 1 contains a high-level introduction to the contents of this book. First, there is a discussion on the nature of information theory and the main results in Shannon’s original paper in 1948 which founded the field. There are also pointers to Shannon’s biographies and his works. Chapter 2 introduces Shannon’s information measures for discrete random variables and their basic properties. Useful identities and inequalities in

VIIIPrefaceinformation theory are derived and explained. Extra care is taken in handlingjoint distributions with zero probability masses. There is a section devotedto the discussion of maximum entropy distributions. The chapter ends with asection on the entropy rate of a stationary information source.Chapter 3 is an introduction to the theory of I-Measure which establishesa one-to-one correspondence between Shannon's information measures andset theory.Anumber of examples are given to showhowthe use of informa-tion diagrams can simplify the proofs of many results in information theory.Such diagrams are becoming standard tools for solving information theoryproblems.Chapter 4 is a discussion of zero-error data compression by uniquely de-codable codes, with prefix codes as a special case. A proof of the entropybound for prefix codes which involves neither the Kraft inequality nor thefundamental inequality is given. This proof facilitates the discussion of theredundancy of prefix codes.Chapter 5 is a thorough treatment of weak typicality. The weak asymp-totic equipartition property and the source coding theorem are discussed.Anexplanation of thefact that a good data compression scheme produces almosti.i.d. bits is given. There is also an introductory discussion of the Shannon-McMillan-Breiman theorem.The concept of weak typicality will be furtherdeveloped in Chapter 10 for continuous random variables.Chapter 6 contains a detailed discussion of strong typicality which appliesto random variables with finite alphabets.The results developed in this chap-ter will be used for proving the channel coding theorem and the rate-distortiontheorem inthenexttwo chapters.The discussion in Chapter 7 of the discrete memoryless channel is an en-hancement of the discussion in the previous book. In particular,the newdefinition of the discrete memoryless channel enables rigorous formulationand analysis of coding schemes for such channels with or without feed-back.The proof of the channel coding theorem uses a graphical modelapproach that helps explain the conditional independence of the randomvariables.Chapter 8 is an introduction to rate-distortion theory.The version of therate-distortion theorem here, proved by using strong typicality, is a strongerversion of the original theorem obtained by Shannon.In Chapter 9, the Blahut-Arimoto algorithms for computing the channelcapacity and the rate-distortion function are discussed, and a simplified prooffor convergence is given. Great care is taken in handling distributions withzero probability masses.Chapters 10 and 1l are devoted to the discussion of information theory forcontinuous random variables. Chapter 10 introduces differential entropy andrelated information measures, and their basic properties are discussed. Theasymptotic equipartitionpropertyfor continuous randomvariables is proved.The last section on maximum differential entropy distributions echoes thesection in Chapter 2 on maximum entropy distributions

VIII Preface information theory are derived and explained. Extra care is taken in handling joint distributions with zero probability masses. There is a section devoted to the discussion of maximum entropy distributions. The chapter ends with a section on the entropy rate of a stationary information source. Chapter 3 is an introduction to the theory of I-Measure which establishes a one-to-one correspondence between Shannon’s information measures and set theory. A number of examples are given to show how the use of information diagrams can simplify the proofs of many results in information theory. Such diagrams are becoming standard tools for solving information theory problems. Chapter 4 is a discussion of zero-error data compression by uniquely decodable codes, with prefix codes as a special case. A proof of the entropy bound for prefix codes which involves neither the Kraft inequality nor the fundamental inequality is given. This proof facilitates the discussion of the redundancy of prefix codes. Chapter 5 is a thorough treatment of weak typicality. The weak asymptotic equipartition property and the source coding theorem are discussed. An explanation of the fact that a good data compression scheme produces almost i.i.d. bits is given. There is also an introductory discussion of the Shannon– McMillan–Breiman theorem. The concept of weak typicality will be further developed in Chapter 10 for continuous random variables. Chapter 6 contains a detailed discussion of strong typicality which applies to random variables with finite alphabets. The results developed in this chapter will be used for proving the channel coding theorem and the rate-distortion theorem in the next two chapters. The discussion in Chapter 7 of the discrete memoryless channel is an enhancement of the discussion in the previous book. In particular, the new definition of the discrete memoryless channel enables rigorous formulation and analysis of coding schemes for such channels with or without feedback. The proof of the channel coding theorem uses a graphical model approach that helps explain the conditional independence of the random variables. Chapter 8 is an introduction to rate-distortion theory. The version of the rate-distortion theorem here, proved by using strong typicality, is a stronger version of the original theorem obtained by Shannon. In Chapter 9, the Blahut–Arimoto algorithms for computing the channel capacity and the rate-distortion function are discussed, and a simplified proof for convergence is given. Great care is taken in handling distributions with zero probability masses. Chapters 10 and 11 are devoted to the discussion of information theory for continuous random variables. Chapter 10 introduces differential entropy and related information measures, and their basic properties are discussed. The asymptotic equipartition property for continuous random variables is proved. The last section on maximum differential entropy distributions echoes the section in Chapter 2 on maximum entropy distributions

PrefaceIXChapter 1l discusses a variety of continuous-valued channels, with thecontinuous memoryless channel being thebasic building block.In proving thecapacity of the memoryless Gaussian channel,a careful justification is givenforthe existence of the differential entropy of the output random variable.Basedon this result, the capacity of a system of parallel/correlated Gaussian chan-nels is obtained.Heuristic arguments leading to theformula for the capacity ofthe bandlimited white/colored Gaussian channel are given. The chapter endswith a proof of thefact that zero-mean Gaussiannoise is theworst additivenoise.Chapter 12 explores the structure of the I-Measure for Markov structures.Set-theoretic characterizations of full conditional independence and Markovrandom field are discussed.The treatment of Markov random field here maybetoo specialized for the average reader, but the structure of the I-Measureand the simplicity of the information diagram for a Markov chain are bestexplained as a special case of a Markov random field.Information inequalities are sometimes called the laws of informationtheory because they govern the impossibilities in information theory.InChapter 13, thegeometrical meaning of information inequalities and the re-lation between information inequalities and conditional independence are ex-plained in depth.The framework for information inequalities discussed hereis the basis of the next two chapters.Chapter 14 explains how the problem of proving information inequalitiescan be formulated as a linear programming problem. This leads to a completecharacterization of all information inequalities provable by conventional tech-niques.These inequalities, called Shannon-type inequalities, can beproved bytheWorldWideWebavailable softwarepackageITIP.Itis also shownhowShannon-type inequalities can be used to tackle the implication problem ofconditional independence in probability theory.Shannon-type inequalities are all the information inequalities known dur-ing the first half century of information theory.In the late1990s,a few newinequalities, called non-Shannon-type inequalities, were discovered.These in-equalities implytheexistenceof lawsin informationtheorybeyond thoselaiddownby Shannon.In Chapter 15,wediscuss theseinequalities and theirap-plications.Chapter 16 explains an intriguing relation between information theoryand group theory.Specifically, for every information inequality satisfied byany joint probability distribution, there is a corresponding group inequalitysatisfied by any finite group and its subgroups and vice versa. Inequalitiesof the latter type govern the orders of any finite group and their subgroups.Group-theoretic proofs of Shannon-type information inequalities are given.Atthe end of the chapter, a group inequality is obtained from a non-Shannon-type inequality discussed in Chapter 15. The meaning and the implication ofthis inequality are yet to be understood.Chapter 17 starts Part II of the book with a discussion of the butterflynetwork, theprimary example in network coding.Variations of the butterfly

Preface IX Chapter 11 discusses a variety of continuous-valued channels, with the continuous memoryless channel being the basic building block. In proving the capacity of the memoryless Gaussian channel, a careful justification is given for the existence of the differential entropy of the output random variable. Based on this result, the capacity of a system of parallel/correlated Gaussian channels is obtained. Heuristic arguments leading to the formula for the capacity of the bandlimited white/colored Gaussian channel are given. The chapter ends with a proof of the fact that zero-mean Gaussian noise is the worst additive noise. Chapter 12 explores the structure of the I-Measure for Markov structures. Set-theoretic characterizations of full conditional independence and Markov random field are discussed. The treatment of Markov random field here maybe too specialized for the average reader, but the structure of the I-Measure and the simplicity of the information diagram for a Markov chain are best explained as a special case of a Markov random field. Information inequalities are sometimes called the laws of information theory because they govern the impossibilities in information theory. In Chapter 13, the geometrical meaning of information inequalities and the relation between information inequalities and conditional independence are explained in depth. The framework for information inequalities discussed here is the basis of the next two chapters. Chapter 14 explains how the problem of proving information inequalities can be formulated as a linear programming problem. This leads to a complete characterization of all information inequalities provable by conventional techniques. These inequalities, called Shannon-type inequalities, can be proved by the World Wide Web available software package ITIP. It is also shown how Shannon-type inequalities can be used to tackle the implication problem of conditional independence in probability theory. Shannon-type inequalities are all the information inequalities known during the first half century of information theory. In the late 1990s, a few new inequalities, called non-Shannon-type inequalities, were discovered. These inequalities imply the existence of laws in information theory beyond those laid down by Shannon. In Chapter 15, we discuss these inequalities and their applications. Chapter 16 explains an intriguing relation between information theory and group theory. Specifically, for every information inequality satisfied by any joint probability distribution, there is a corresponding group inequality satisfied by any finite group and its subgroups and vice versa. Inequalities of the latter type govern the orders of any finite group and their subgroups. Group-theoretic proofs of Shannon-type information inequalities are given. At the end of the chapter, a group inequality is obtained from a non-Shannontype inequality discussed in Chapter 15. The meaning and the implication of this inequality are yet to be understood. Chapter 17 starts Part II of the book with a discussion of the butterfly network, the primary example in network coding. Variations of the butterfly