References & Further Reading
References
- T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley-Interscience, 2nd ed., 2006
Chapter 3 covers the AEP and typical sets. Chapter 11 covers the method of types. The treatment is accessible and complete.
- A. El Gamal and Y.-H. Kim, Network Information Theory, Cambridge University Press, 2011
Chapter 2 gives the cleanest treatment of strong typicality, joint typicality, and the packing/covering lemmas. The modular framework for constructing achievability proofs is particularly valuable.
- I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems, Cambridge University Press, 2nd ed., 2011
The definitive reference for the method of types. Chapters 1-2 develop the combinatorial foundations; the rest of the book builds coding theorems using types as the primary tool.
- R. G. Gallager, Information Theory and Reliable Communication, Wiley, 1968
Gallager's error exponent analysis (Chapter 5) provides the motivation for moving beyond the typical-set approach to the method of types.
- C. E. Shannon, A Mathematical Theory of Communication, 1948
Shannon's original observation of the equipartition property and the first use of random coding for channel coding achievability.
- D. Slepian and J. K. Wolf, Noiseless Coding of Correlated Information Sources, 1973
Proves that separate encoding with joint decoding achieves the same rate region as joint encoding. The random binning technique introduced here is foundational for distributed source coding.
- E. Arıkan, Channel Polarization: A Method for Constructing Capacity-Achieving Codes, 2009
Polar codes are the first deterministic construction provably achieving capacity with polynomial complexity. Now used in 5G NR control channels.
- T. Richardson and R. Urbanke, Modern Coding Theory, Cambridge University Press, 2008
Comprehensive treatment of LDPC and turbo codes. Bridges the gap between random coding existence proofs and practical iterative decoding on sparse graphs.
- Y. Polyanskiy, H. V. Poor, and S. Verdú, Channel Coding Rate in the Finite Blocklength Regime, 2010
Establishes the normal approximation for finite-blocklength rates. Shows the gap to capacity scales as $\sqrt{V/n}$ where $V$ is the channel dispersion.
- A. Somekh-Baruch and G. Caire, The Error Exponent of the Binary Symmetric Channel for Mismatched Decoding, 2014
Extends error exponent analysis to mismatched decoding using the method of types. Characterizes when mismatched decoding incurs an exponent penalty versus the matched case.
Further Reading
Resources for deepening your understanding of typicality and coding arguments.
Error exponents and the method of types
Book ITA, Ch. 4 — The Method of Types and Error Exponents
Chapter 4 develops the method of types in full depth, leading to the random coding exponent, sphere-packing exponent, and their implications for practical code design.
Practical codes approaching capacity
T. Richardson and R. Urbanke, Modern Coding Theory, Cambridge, 2008
The gap between random coding and practical codes is bridged by LDPC and turbo codes. This book provides a rigorous treatment of iterative decoding on sparse graphs.
Polar codes: from theory to practice
E. Arıkan, 'Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels,' IEEE Trans. IT, 2009
Polar codes are the first deterministic construction provably achieving capacity with polynomial complexity. They are now part of the 5G NR standard for control channels.
Large deviations beyond types
A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications, Springer, 2010
For continuous alphabets and non-i.i.d. sources, the method of types is replaced by general large deviation theory. This book provides the mathematical framework.