The Theory of Information and Coding.pdf-资料库

xiaoxiao89811-3399198-4744302542913987865.pdf-第1页.png

第1页 / 共408页

xiaoxiao89811-3399198-4744302542913987865.pdf-第2页.png

第2页 / 共408页

xiaoxiao89811-3399198-4744302542913987865.pdf-第3页.png

第3页 / 共408页

xiaoxiao89811-3399198-4744302542913987865.pdf-第4页.png

第4页 / 共408页

xiaoxiao89811-3399198-4744302542913987865.pdf-第5页.png

第5页 / 共408页

xiaoxiao89811-3399198-4744302542913987865.pdf-第6页.png

第6页 / 共408页

xiaoxiao89811-3399198-4744302542913987865.pdf-第7页.png

第7页 / 共408页

xiaoxiao89811-3399198-4744302542913987865.pdf-第8页.png

第8页 / 共408页

ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS FOUNDING EDITOR G.-C. ROTA Editorial Board R. S. Doran, M. Ismail, T.-Y. Lam, E. Lutwak, R. Spigler Volume 86 The Theory of Information and Coding Second Edition Downloaded from Cambridge Books Online by IP 222.66.175.241 on Wed Nov 17 08:08:50 GMT 2010. Cambridge Books Online © Cambridge University Press, 2010 Cambridge Books Online © Cambridge University Press, 2009

ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS 4 W. Miller, Jr. Symmetry and separation of variables 6 H. Minc Permanents J. Aczel and J. Dhombres Functional equations containing several variables J. R. Bastida Field extensions and Galois theory J. R. Cannon The one-dimensional heat equation 11 W. B. Jones and W. J. Thron Continued fractions 12 N. F. G. Martin and J. W. England Mathematical theory of entropy 18 H. O. Fattorini The Cauchy problem 19 G. G. Lorentz, K. Jetter and S. D. Riemenschneider Birkhoff interpolation 21 W. T. Tutte Graph theory 22 23 25 A. Salomaa Computation and automata 26 N. White (ed.) Theory of matroids 27 N. H. Bingham, C. M. Goldie and J. L. Teugels Regular variation 28 P. P. Petrushev and V. A. Popov Rational approximation of real functions 29 N. White (ed.) Combinatorial geometrics 30 M. Pohst and H. Zassenhaus Algorithmic algebraic number theory 31 32 M. Kuczma, B. Chozewski and R. Ger Iterative functional equations 33 R. V. Ambartzumian Factorization calculus and geometric probability 34 G. Gripenberg, S.-O. Londen and O. Staffans Volterra integral and functional equations 35 G. Gasper and M. Rahman Basic hypergeometric series 36 E. Torgersen Comparison of statistical experiments 37 A. Neumaier Intervals methods for systems of equations 38 N. Korneichuk Exact constants in approximation theory 39 R. A. Brualdi and H. J. Ryser Combinatorial matrix theory 40 N. White (ed.) Matroid applications 41 S. Sakai Operator algebras in dynamical systems 42 W. Hodges Model theory 43 H. Stahl and V. Totik General orthogonal polynomials 44 R. Schneider Convex bodies 45 G. Da Prato and J. Zabczyk Stochastic equations in in®nite dimensions 46 A. Bjorner, M. Las Vergnas, B. Sturmfels, N. White and G. Ziegler Oriented matroids 47 E. A. Edgar and L. Sucheston Stopping times and directed processes 48 C. Sims Computation with ®nitely presented groups 49 T. Palmer Banach algebras and the general theory of -algebras Jan Krajicek Bounded arithmetic, propositional logic, and complex theory 50 F. Borceux Handbook of categorical algebra I 51 F. Borceux Handbook of categorical algebra II 52 F. Borceux Handbook of categorical algebra III 54 A. Katok and B. Hassleblatt Introduction to the modern theory of dynamical systems 55 V. N. Sachkov Combinatorial methods in discrete mathematics 56 V. N. Sachkov Probabilistic methods in discrete mathematics 57 P. M. Cohn Skew Fields 58 Richard J. Gardner Geometric tomography 59 George A. Baker, Jr. and Peter Graves-Morris PadeÂ approximants 60 61 H. Gromer Geometric applications of Fourier series and spherical harmonics 62 H. O. Fattorini In®nite dimensional optimization and control theory 63 A. C. Thompson Minkowski geometry 64 R. B. Bapat and T. E. S. Raghavan Nonnegative matrices and applications 65 K. Engel Sperner theory 66 D. Cvetkovic, P. Rowlinson and S. Simic Eigenspaces of graphs 67 F. Bergeron, G. Labelle and P. Leroux Combinatorial species and tree-like structures 68 R. Goodman and N. Wallach Representations of the classical groups 69 T. Beth, D. Jungnickel and H. Lenz Design Theory volume I 2 ed. 70 A. Pietsch and J. Wenzel Orthonormal systems and Banach space geometry 71 George E. Andrews, Richard Askey and Ranjan Roy Special Functions 72 R. Ticciati Quantum ®eld theory for mathematicians 76 A. A. Ivanov Geometry of sporadic groups I 78 T. Beth, D. Jungnickel and H. Lenz Design Theory volume II 2 ed. 80 O. Stormark Lie's Structural Approach to PDE Systems 81 C. F. Dunkl and Y. Xu Orthogonal polynomials of several variables 82 83 C. Foias, R. Temam, O. Manley and R. Martins da Silva Rosa Navier±Stokes equations and turbulence 84 B. Polster and G. Steinke Geometries on Surfaces 85 D. Kaminski and R. B. Paris Asymptotics and Mellin±Barnes integrals J. Mayberry The foundations of mathematics in the theory of sets Downloaded from Cambridge Books Online by IP 222.66.175.241 on Wed Nov 17 08:08:50 GMT 2010. Cambridge Books Online © Cambridge University Press, 2010 Cambridge Books Online © Cambridge University Press, 2009

ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS The Theory of Information and Coding Second Edition R. J. McELIECE California Institute of Technology Downloaded from Cambridge Books Online by IP 222.66.175.241 on Wed Nov 17 08:08:50 GMT 2010. Cambridge Books Online © Cambridge University Press, 2010 Cambridge Books Online © Cambridge University Press, 2009

          The Pitt Building, Trumpington Street, Cambridge, United Kingdom    The Edinburgh Building, Cambridge CB2 2RU, UK 40 West 20th Street, New York, NY 10011-4211, USA 477 Williamstown Road, Port Melbourne, VIC 3207, Australia Ruiz de Alarcón 13, 28014 Madrid, Spain Dock House, The Waterfront, Cape Town 8001, South Africa http://www.cambridge.org © Cambridge University Press 2004 First published in printed format 2002 ISBN 978-0-511-60626-7 OCeISBN ISBN 0-521-00095-5 hardback Downloaded from Cambridge Books Online by IP 222.66.175.241 on Wed Nov 17 08:08:50 GMT 2010. Cambridge Books Online © Cambridge University Press, 2010 Cambridge Books Online © Cambridge University Press, 2009

Contents Editor'sstatementpageviii Sectioneditor'sforewordix Prefacetothe®rsteditionx Prefacetothesecondeditionxii Introduction1 Problems12 Notes13 Part one: Information theory 1Entropyandmutualinformation17 1.1Discreterandom variables17 1.2Discreterandom vectors33 1.3Nondiscreterandom variablesandvectors37 Problems44 Notes49 2Discretememorylesschannelsandtheircapacity±cost functions50 2.1Thecapacity±costfunction50 2.2Thechannelcodingtheorem Problems68 Notes73 3 Discrete memoryless sources and their rate-distortion functions75 3.1Therate-distortionfunction75 3.2Thesourcecodingtheorem 58 84 Problems91 Notes93 v Downloaded from Cambridge Books Online by IP 222.66.175.241 on Wed Nov 17 08:09:19 GMT 2010. Cambridge Books Online © Cambridge University Press, 2010 Cambridge Books Online © Cambridge University Press, 2009

123 131 vi 4 Contents TheGaussianchannelandsource95 4.1TheGaussianchannel95 4.2TheGaussiansource99 Problems105 Notes110 5Thesource±channelcodingtheorem112 Problems120 Notes122 6Surveyofadvancedtopicsforpartone123 6.1Introduction123 6.2Thechannelcodingtheorem 6.3Thesourcecodingtheorem Part two: Coding theory 7Linearcodes139 7.1Introduction:Thegeneratorandparity-checkmatrices139 7.2Syndromedecodingonq-arysymmetricchannels143 7.3Hamminggeometryandcodeperformance146 7.4Hammingcodes148 7.5Syndromedecodingongeneralq-arychannels149 7.6WeightenumeratorsandtheMacWilliamsidentities153 Problems158 Notes165 8Cycliccodes167 8.1Introduction167 8.2Shift-registerencodersforcycliccodes181 8.3CyclicHammingcodes195 8.4Burst-errorcorrection199 8.5Decodingburst-errorcorrectingcycliccodes215 Problems220 Notes228 9BCH,Reed±Solomon,andrelatedcodes230 9.1Introduction230 9.2BCHcodesascycliccodes234 9.3DecodingBCHcodes,Partone:thekeyequation236 9.4Euclid'salgorithm forpolynom ials244 9.5DecodingBCHcodes,Parttwo:thealgorithms249 9.6Reed±Solomoncodes253 9.7Decodingwhenerasuresarepresent266 Downloaded from Cambridge Books Online by IP 222.66.175.241 on Wed Nov 17 08:09:19 GMT 2010. Cambridge Books Online © Cambridge University Press, 2010 Cambridge Books Online © Cambridge University Press, 2009

Preface vii 9.8The(23,12)Golaycode277 Problems282 Notes292 10Convolutionalcodes293 10.1Introduction293 10.2Statediagrams,trellises,andViterbidecoding300 10.3Pathenumeratorsanderrorbounds307 10.4Sequentialdecoding313 Problems322 Notes329 11Variable-lengthsourcecoding330 11.1Introduction330 11.2Uniquelydecodablevariable-lengthcodes331 11.3Matchingcodestosources334 11.4 The construction of optimal UD codes (Huffman's algorithm)337 Problems342 Notes345 12SurveyofadvancedtopicsforParttwo347 12.1Introduction347 12.2Blockcodes347 12.3Convolutionalcodes357 12.4Acomparisonofblockandconvolutionalcodes359 12.5Sourcecodes363 Appendices AProbabilitytheory366 BConvexfunctionsandJensen'sinequality370 CFinite®elds375 DPathenumerationindirectedgraphs380 References 1Generalreferencetextbooks384 2 An annotated bibliography of the theory of information and coding384 3Originalpaperscitedinthetext386 IndexofTheorems388 Index390 Downloaded from Cambridge Books Online by IP 222.66.175.241 on Wed Nov 17 08:09:19 GMT 2010. Cambridge Books Online © Cambridge University Press, 2010 Cambridge Books Online © Cambridge University Press, 2009

Editor's statement A large body of mathematics consists of facts that can be presented and described much like any other natural phenomenon. These facts, at times explicitly brought out as theorems, at other times concealed within a proof, make up most of the applications of mathematics, and are the most likely to survive changes of style and of interest. This ENCYCLOPEDIA will attempt to present the factual body of all mathematics. Clarity of exposition, accessibility to the non-specialist, and a thorough bibliography are required of each author. Volumes will appear in no particular order, but will be organized into sections, each one comprising a recognizable branch of present-day mathematics. Numbers of volumes and sections will be reconsidered as times and needs change. It is hoped that this enterprise will make mathematics more widely used where it is needed, and more accessible in ®elds in which it can be applied but where it has not yet penetrated because of insuf®cient information. Information theory is a success story in contemporary mathematics. Born out of very real engineering problems, it has left its imprint on such far-¯ung endeavors as the approximation of functions and the central limit theorem of probability. It is an idea whose time has come. Most mathematicians cannot afford to ignore the basic results in this ®eld. Yet, because of the enormous outpouring of research, it is dif®cult for anyone who is not a specialist to single out the basic results and the relevant material. Robert McEliece has succeeded in giving a presentation that achieves this objective, perhaps the ®rst of its kind. Gian-Carlo Rota viii Downloaded from Cambridge Books Online by IP 222.66.175.241 on Wed Nov 17 08:09:26 GMT 2010. http://dx.doi.org/10.1017/CBO9780511606267.001 Cambridge Books Online © Cambridge University Press, 2010 Cambridge Books Online © Cambridge University Press, 2009

资料库

The Theory of Information and Coding.pdf

相关推荐

信息化

热门标签

最新资料