This book provides an up-to-date introduction to information theory. It provides the first comprehensive treatment of the theory of I-Measure, network coding theory, Shannon and non-Shannon type information inequalities, and a relation between entropy and group theory.

A First Course in Information Theory is an up-to-date introduction to information theory. In addition to the classical topics discussed, it provides the first comprehensive treatment of the theory of I-Measure, network coding theory, Shannon and non-Shannon type information inequalities, and a relation between entropy and group theory. ITIP, a software package for proving information inequalities, is also included. With a large number of examples, illustrations, and original problems, this book is excellent as a textbook or reference book for a senior or graduate level course on the subject, as well as a reference for researchers in related fields.

Includes supplementary material: sn.pub/extras

Autorentext

Shenghao Yang was born in China on March 19, 1978. He received his B.S. degree from Nankai University in 2001, an M.S. degree from Peking University in 2004, and a Ph.D. degree in Information Engineering from The Chinese University of Hong Kong in 2008. He was a visiting student at the Department of Informatics, University of Bergen, Norway in Spring 2017. He was a Postdoctoral Fellow in the University of Waterloo from 2008 to 2009 and in the Institute of Network Coding, The Chinese University of Hong Kong from 2010 to 2012. He was with the Tsinghua University from 2012 to 2015 as an Assistant Professor. He is currently a Research Assistant Professor at The Chinese University of Hong Kong, Shenzhen. His research interests include network coding, information theory, coding theory, network computation, big data processing, and quantum information. He has published more than 40 papers in international journals and conferences. He is a co-inventor of BATS code and has two U.S. patents granted. Raymond W. Yeung was born in Hong Kong on June 3, 1962. He received B.S., M.Eng., and Ph.D. degrees in electrical engineering from Cornell University, Ithaca, NY, in 1984, 1985, and 1988, respectively. He was on leave at Ecole Nationale Superieure des Telecommunications, Paris, France, during Fall 1986. He was a Member of Technical Staff of AT&T Bell Laboratories from 1988 to 1991. Since 1991, he has been with the Department of Information Engineering at The Chinese University of Hong Kong, where he is now Choh-Ming Li Professor of Information Engineering. Since January 2010, he has been serving as Co-Director of the Institute of Network Coding at The Chinese University of Hong Kong. He was a Consultant at the Jet Propulsion Laboratory in Pasadena, CA, on a project to salvage the malfunctioning Galileo Spacecraft, and a Consultant for NEC, USA. He is the author of the textbooks A First Course in Information Theory (Kluwer Academic/Plenum 2002) and its revision Information Theory and Network Coding (Springer 2008), which have been adopted by over 100 institutions around the world. In Spring 2014, he gave the first MOOC in the world on information theory that reached over 25,000 students. His research interests include information theory and network coding. Dr. Yeung was a member of the Board of Governors of the IEEE Information Theory Society from 1999 to 2001. He has served on the committees of a number of information theory symposiums and workshops. He was General Chair of the First and the Fourth Workshop on Network, Coding, and Applications (NetCod 2005 and 2008), a Technical Co-Chair for the 2006 IEEE International Symposium on Information Theory, and a Technical Co-Chair for the 2006 IEEE Information Theory Workshop, Chengdu, China. He currently serves as an Editor-at-Large of Communications in Information and Systems, an Editor of Foundation and Trends in Communications and Information Theory and of Foundation and Trends in Networking, and was an Associate Editor for Shannon Theory of the IEEE Transactions on Information Theory from 2003 to 2005. He was a recipient of the Croucher Foundation Senior Research Fellowship for 2000/2001, the Best Paper Award (Communication Theory) of the 2004 International Conference on Communications, Circuits and System, the 2005 IEEE Information Theory Society Paper Award, the Friedrich Wilhelm Bessel Research Award of the Alexander von Humboldt Foundation in 2007, and the 2016 IEEE Eric E. Sumner Award (for "pioneering contributions to the field of network coding"). In 2015, he was named an Outstanding Overseas Chinese Information Theorist by the China Information Theory Society. He is a Fellow of the IEEE, Hong Kong Academy of Information Sciences, and Hong Kong Institution of Engineers.

Inhalt

1. The Science of Information.- Information Measures.- 2.1 Independence and Markov Chains.- 2.2 Shannon's Information Measures.- 2.3 Continuity of Shannon's Information Measures.- 2.4 Chain Rules.- 2.5 Informational Divergence.- 2.6 The Basic Inequalities.- 2.7 Some Useful Information Inequalities.- 2.8 Fano's Inequality.- 2.9 Entropy Rate of Stationary Source.- Problems.- Historical Notes.- 3. Zero-Error Data Compression.- 3.1 The Entropy Bound.- 3.2 Prefix Codes.- 3.3 Redundancy of Prefix Codes.- Problems.- Historical Notes.- 4. Weak Typicality.- 4.1 The Weak.- 4.2 The Source Coding Theorem.- 4.3 Efficient Source Coding.- 4.4 The Shannon-McMillan-Breiman Theorem.- Problems.- Historical Notes.- 5. Strong Typicality.- 5.1 Strong.- 5.2 Strong Typicality Versus Weak Typicality.- 5.3 Joint Typicality.- 5.4 An Interpretation of the Basic Inequalities.- Problems.- Historical Notes.- The I-measure.- 6.1 Preliminaries.- 6.2 The I-Measure for Two Random Variables.- 6.3 Construction of the I-Measure ?.- 6.4 ? Can be Negative.- 6.5 Information Diagrams.- 6.6 Examples of Applications.- Appendix 6.A: A Variation of the Inclusion-Exclusion Formula.- Problems.- Historical Notes.- 7. Markov Structures.- 7.1 Conditional Mutual Independence.- 7.2 Full Conditional Mutual Independence.- 7.3 Markov Random Field.- 7.4 Markov Chain.- Problems.- Historical Notes.- 8. Channel Capacity.- 8.1 Discrete Memoryless Channels.- 8.2 The Channel Coding Theorem.- 8.3 The Converse.- 8.4 Achievability of the Channel Capacity.- 8.5 A Discussion.- 8.6 Feedback Capacity.- 8.7 Separation of Source and Channel Coding.- Problems.- Historical Notes.- 9. Rate-Distortion Theory.- 9.1 Single-Letter Distortion Measures.- 9.2 The Rate-Distortion Function R(D).- 9.3 The Rate-Distortion Theorem.- 9.4 The Converse.- 9.5 Achievability of RI(D).- Problems.- Historical Notes.- The Blahut-Arimoto Algorithms.- 10.1 Alternating Optimization.- 10.2 The Algorithms.- 10.3 Convergence.- Problems.- Historical Notes.- 11. Single-Source Network Coding.- 11.1 A Point-to-Point Network.- 11.2 What is Network Coding?.- 11.3 A Network Code.- 11.4 The Max-Flow Bound.- 11.5 Achievability of the Max-Flow Bound.- Problems.- Historical Notes.- 12. Information Inequalities.- 12.1 The Region ?*n.- 12.2 Information Expressions in Canonical Form.- 12.3 A Geometrical Framework.- 12.4 Equivalence of Constrained Inequalities.- 12.5 The Implication Problem of Conditional Independence.- Problems.- Historical Notes.- 13. Shannon-Type Inequalities.- 13.1 The Elemental Inequalities.- 13.2 A Linear Programming Approach.- 13.3 A Duality.- 13.4 Machine Proving.- 13.5 Tackling the Implication Problem.- 13.6 Minimality of the Elemental Inequalities.- Appendix 13.A: The Basic Inequalities and the Polymatroidal Axioms.- Problems.- Historical Notes.- Problems.- Historical Notes.- 14. Beyond Shannon-Type Inequalities.- 14.1 Characterizations of ?*2,?*3, and ?*n.- 14.2 A Non-Shannon-Type Unconstrained Inequality.- 14.3 A Non-Shannon-TypeConstrained Inequality.- 14.4 Applications.- Problems.- Historical Notes.- 978-1-4419-8608-5_15.- 15.1 Two Characteristics.- 15.2 Examples of Application.- 15.3 A Network Code for Acyclic …