The Theory of Information and Coding (Encyclopedia of Mathematics and its Applications No. 86)

Basic hypergeometric series E. Torgersen Comparison of statistical experiments A. Neumaier Intervals methods for systems of equations N. Korneichuk Exact constants in approximation theory R. A. Brualdi and H. J. Ryser Combinatorial matrix theory N. White ed.) Matroid applications S. Sakai Operator algebras in dynamical systems W. Hodges Model theory H. Stahl and V. Totik General orthogonal polynomials R. Schneider Convex bodies G. Da Prato and J. Zabczyk Stochastic equations in in®nite dimensions A. Bjorner, M. Las Vergnas, B. Sturmfels, N. White and G. Ziegler Oriented matroids E. A. Edgar and L. Sucheston Stopping times and directed processes C. Sims Computation with ®nitely presented groups T. Palmer Banach algebras and the general theory of à -algebras F. Borceux Handbook of categorical algebra I F. Borceux Handbook of categorical algebra II F. Borceux Handbook of categorical algebra III A. Katok and B. Hassleblatt Introduction to the modern theory of dynamical systems V. N. Sachkov Combinatorial methods in discrete mathematics V. N. Sachkov Probabilistic methods in discrete mathematics P. M. Cohn Skew Fields This Is A Revised Edition Of Mceliece's Classic. It Is A Self-contained Introduction To All Basic Results In The Theory Of Information And Coding (invented By Claude Shannon In 1948). This Theory Was Developed To Deal With The Fundamental Problem Of Communication, That Of Reproducing At One Point, Either Exactly Or Approximately, A Message Selected At Another Point. There Is A Short And Elementary Overview Introducing The Reader To The Concept Of Coding. Then, Following The Main Results, The Channel And Source Coding Theorems, There Is A Study Of Specific Coding Schemes Which Can Be Used For Channel And Source Coding. This Volume Can Be Used Either For Self-study, Or For A Graduate/undergraduate Level Course At University. It Includes Dozens Of Worked Examples And Several Hundred Problems For Solution. The Exposition Will Be Easily Comprehensible To Readers With Some Prior Knowledge Of Probability And Linear Algebra. Part 1 Information Theory -- 1 Entropy And Mutual Information 17 -- 1.1 Discrete Random Variables 17 -- 1.2 Discrete Random Vectors 33 -- 1.3 Nondiscrete Random Variables And Vectors 37 -- 2 Discrete Memoryless Channels And Their Capacity-cost Functions 50 -- 2.1 The Capacity-cost Function 50 -- 2.2 The Channel Coding Theorem 58 -- 3 Discrete Memoryless Sources And Their Rate-distortion Functions 75 -- 3.1 The Rate-distortion Function 75 -- 3.2 The Source Coding Theorem 84 -- 4 The Gaussian Channel And Source 95 -- 4.1 The Gaussian Channel 95 -- 4.2 The Gaussian Source 99 -- 5 The Source-channel Coding Theorem 112 -- 6 Survey Of Advanced Topics For Part One 123 -- 6.2 The Channel Coding Theorem 123 -- 6.3 The Source Coding Theorem 131 -- Part 2 Coding Theory -- 7 Linear Codes 139 -- 7.1 Introduction: The Generator And Parity-check Matrices 139 -- 7.2 Syndrome Decoding On Q-ary Symmetric Channels 143 -- 7.3 Hamming Geometry And Code Performance 146 -- 7.4 Hamming Codes 148 -- 7.5 Syndrome Decoding On General Q-ary Channels 149 -- 7.6 Weight Enumerators And The Macwilliams Identities 153 -- 8 Cyclic Codes 167 -- 8.2 Shift-register Encoders For Cyclic Codes 181 -- 8.3 Cyclic Hamming Codes 195 -- 8.4 Burst-error Correction 199 -- 8.5 Decoding Burst-error Correcting Cyclic Codes 215 -- 9 Bch, Reed-solomon, And Related Codes 230 -- 9.2 Bch Codes As Cyclic Codes 234 -- 9.3 Decoding Bch Codes, Part One: The Key Equation 236 -- 9.4 Euclid's Algorithm For Polynomials 244 -- 9.5 Decoding Bch Codes, Part Two: The Algorithms 249 -- 9.6 Reed-solomon Codes 253 -- 9.7 Decoding When Erasures Are Present 266 -- 9.8 The (23,12) Golay Code 277 -- 10 Convolutional Codes 293 -- 10.2 State Diagrams, Trellises, And Viterbi Decoding 300 -- 10.3 Path Enumerators And Error Bounds 307 -- 10.4 Sequential Decoding 313 -- 11 Variable-length Source Coding 330 -- 11.2 Uniquely Decodable Variable-length Codes 331 -- 11.3 Matching Codes To Sources 334 -- 11.4 The Construction Of Optimal Ud Codes (huffman's Algorithm) 337 -- 12 Survey Of Advanced Topics For Part Two 347 -- 12.2 Block Codes 347 -- 12.3 Convolutional Codes 357 -- 12.4 A Comparison Of Block And Convolutional Codes 359 -- 12.5 Source Codes 363 -- A Probability Theory 366 -- B Convex Functions And Jensen's Inequality 370 -- C Finite Fields 375 -- D Path Enumeration In Directed Graphs 380 -- 1 General Reference Textbooks 384 -- 2 An Annotated Bibliography Of The Theory Of Information And Coding 384. R.j. Mceliece. Previous Ed.: Reading, Mass. : Addison-wesley, 1977. Includes Bibliographical References And Index. Cover......Page 1 ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS 86......Page 2 The Theory of Information and Coding - Second Edition......Page 4 Copyright - ISBN: 0521000955......Page 5 Contents......Page 6 Editor's statement......Page 9 Foreword......Page 10 Preface to the first edition......Page 11 Preface to the second edition......Page 13 Introduction......Page 14 Problems......Page 25 Notes......Page 26 Part one - Information theory......Page 28 1.1 Discrete random variables......Page 30 1.2 Discrete random vectors......Page 46 1.3 Nondiscrete random variables and vectors......Page 50 Problems......Page 57 Notes......Page 62 2.1 The capacity-cost function......Page 63 2.2 The channel coding theorem......Page 71 Problems......Page 81 Notes......Page 86 3.1 The rate-distortion function......Page 88 3.2 The source coding theorem......Page 97 Problems......Page 104 Notes......Page 106 4.1 The Gaussian channel......Page 108 4.2 The Gaussian source......Page 112 Problems......Page 118 Notes......Page 123 5. The source-channel coding theorem......Page 125 Problems......Page 133 Notes......Page 135 6.2 The channel coding theorem......Page 136 6.3 The source coding theorem......Page 144 Part two - Coding theory......Page 150 7.1 Introduction: The generator and parity-check matrices......Page 152 7.2 Syndrome decoding on q-ary symmetric channels......Page 156 7.3 Hamming geometry and code performance......Page 159 7.4 Hamming codes......Page 161 7.5 Syndrome decoding on general q-ary channels......Page 162 7.6 Weight enumerators and the MacWilliams identities......Page 166 Problems......Page 171 Notes......Page 178 8.1 Introduction......Page 180 8.2 Shift-register encoders for cyclic codes......Page 194 8.3 Cyclic Hamming codes......Page 207 8.4 Burst-error correction......Page 211 8.5 Decoding burst-error-correcting cyclic codes......Page 227 Problems......Page 232 Notes......Page 240 9.1 Introduction......Page 242 9.2 BCH codes as cyclic codes......Page 246 9.3 Decoding BCH codes, Part one: the key equation......Page 248 9.4 Euclid's algorithm for polynomials......Page 256 9.5 Decoding BCH codes, Part two: the algorithms......Page 261 9.6 Reed-Solomon codes......Page 265 9.7 Decoding when erasures are present......Page 278 9.8 The (23, 12) Golay code......Page 289 Problems......Page 294 Notes......Page 304 10.1 Introduction......Page 305 10.2 State diagrams, trellises, and Viterbi decoding......Page 312 10.3 Path enumerators and error bounds......Page 319 10.4 Sequential decoding......Page 325 Problems......Page 334 Notes......Page 341 11.1 Introduction......Page 342 11.2 Uniquely decodable variable-length codes......Page 343 11.3 Matching codes to sources......Page 346 11.4 The construction of optimal UD codes (Huffman's algorithm)......Page 349 Problems......Page 354 Notes......Page 357 12.2 Block codes......Page 359 12.3 Convolutional codes......Page 369 12.4 A comparison of block and convolutional codes......Page 371 12.5 Source codes......Page 375 Appendix A - Probability theory......Page 378 Appendix B - Convex functions and Jensen's inequality......Page 382 C.1 Construction......Page 387 C.3 Conjugation and minimal polynomials......Page 388 C.4 Factorization of x^n - 1 over F_q......Page 390 Appendix D - Path enumeration in directed graphs......Page 392 2. An annotated bibliography of the theory of information and coding......Page 396 3. Original papers cited in the text......Page 398 Index of theorems......Page 400 Index......Page 402 "This volume is a self-contained introduction to all basic results in the theory of information and coding (invented by Claude Shannon in 1948). This theory was developed to deal with the fundamental problem of communication, that of reproducing at one point, either exactly or approximately, a message selected at another point. There is a short and elementary overview introducing the reader to the concept of coding. Then, following the main results, the channel and source coding theorems, there is a study of specific coding schemes which can be used for channel and source coding. This volume can be used either for self-study, or for a graduate/undergraduate level course at university. It includes dozens of worked examples and several hundred problems for solution. The exposition will be easily comprehensible to readers with some prior knowledge of probability and linear algebra." -- BOOK JACKET This is a self-contained introduction to the theory of information and coding. It can be used either for self-study or as the basis for a course at either the graduate or, undergraduate level. The text includes dozens of worked examples and several hundred problems for solution.