References & Further Reading

References

  1. I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems, Cambridge University Press, 2nd ed., 1998

    The definitive reference for the method of types. Chapters 1–2 develop the combinatorial framework; Chapters 5–6 derive the error exponents. Our treatment follows their notation and proof structure closely.

  2. T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley, 2nd ed., 2006

    Chapter 11 provides an accessible introduction to the method of types, and Chapter 10 covers error exponents. Our presentation bridges the two approaches.

  3. R. G. Gallager, Information Theory and Reliable Communication, Wiley, 1968

    The original source for the random coding and expurgated error exponents. Gallager's bounding technique (the "$\\rho$-trick") remains the most elegant approach to achievability bounds.

  4. C. E. Shannon, R. G. Gallager, and E. R. Berlekamp, Lower Bounds to Error Probability for Coding on Discrete Memoryless Channels, 1967

    The two-part paper establishing the sphere-packing bound — the strongest known converse for error exponents of DMCs.

  5. Y. Polyanskiy, H. V. Poor, and S. Verdú, Channel Coding Rate in the Finite Blocklength Regime, 2010

    Introduces the normal approximation and channel dispersion for finite-blocklength analysis, providing much tighter bounds than error exponents for short codes.

  6. A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications, Springer, 2nd ed., 1998

    The standard reference for large deviations theory beyond the i.i.d. setting. Chapters 2–3 generalize Sanov's theorem to abstract alphabets and Markov chains.

Further Reading

For readers who want to go deeper into error exponents and large deviations.

  • Exact error exponent for the BSC

    A. Barg and G. D. Forney, 'Random Codes: Minimum Distances and Error Exponents,' IEEE Trans. Inform. Theory, vol. 48, no. 9, pp. 2568–2573, Sep. 2002

    Shows that for the BSC, the exact reliability function is known in closed form at all rates — one of the few channels where this is the case.

  • Error exponents for LDPC and polar codes

    S. B. Korada, 'Polar Codes for Channel and Source Coding,' Ph.D. thesis, EPFL, 2009, Ch. 3

    Analyzes the error exponent of polar codes, showing they achieve $2^{-\sqrt{n}}$ decay — sub-exponential but with favorable scaling for practical blocklengths.

  • Large deviations beyond i.i.d.

    A. Dembo and O. Zeitouni, *Large Deviations Techniques and Applications*, Springer, 1998, Ch. 3

    Extends Sanov's theorem and Cramér's theorem to Markov chains and more general processes. Essential for understanding error exponents of channels with memory.

  • Refined asymptotics: moderate deviations

    I. Altug and A. B. Wagner, 'Moderate Deviations in Channel Coding,' IEEE Trans. Inform. Theory, vol. 60, no. 8, pp. 4417–4426, Aug. 2014

    Fills the gap between the error exponent regime (fixed rate below capacity) and the normal approximation regime (rate approaching capacity). Shows how the two frameworks connect through the moderate deviations principle.

ExercisesCh 5 →