Essential Coding Theory

Venkatesan Guruswami, Atri Rudra and Madhu Sudan

If you have any comments, please email them to

The plan is to put up a draft of the whole book sometime in 2017(?).

Chapters

Below are links to the individual chapters:

Part I: Basics

Chapter 1: The Fundamental Question. (Jul 16, 2014)
Chapter 2: A Look at Some Nicely Behaved Codes: Linear Codes. (Feb 21, 2017)
Chapter 3: Probability as Fancy Counting and the q-ary Entropy Function. (Aug 15, 2014)

Part II: Combinatorics

Chapter 4: What Can and Cannot Be Done-I (Feb 5, 2017)
Chapter 5: The Greatest Code of Them All: Reed-Solomon Codes (May 8, 2015)
Chapter 6: What Happens When the Noise is Stochastic: Shannon's Theorem (Jul 21, 2015)
Chapter 7: Bridging the Gap Between Shannon and Hamming: List Decoding (Apr 28, 2013)
Chapter 8: What Cannot be Done- II (Apr 28, 2013)

Part III: Code Constructions

Chapter 9: From Large to Small Alphabets: Code Concatenation (Apr 28, 2013)
Chapter 10: Codes from Graphs: Expander Codes (Apr 30, 2013)

Part IV: Algorithms

Chapter 11: Decoding Concatenated Codes (May 1, 2013)
Chapter 12: Efficiently Achieving the Capacity of the BSC_p (May 1, 2013)
Chapter 13: Efficient Decoding of Reed-Solomon Codes (May 1, 2013)
Chapter 14: Efficiently Achieving List Decoding Capacity (May 1, 2013)

Part V: Applications

Chapter 15: Cutting Data Down to Size: Hashing (Mar 30, 2012)
Chapter 16: Securing Your Fingerprints: Fuzzy Vaults (April 1, 2013)
Chapter 17: Finding Defectives: Group Testing (Aug 15, 2014)

Appendix

Notation Table (Feb 29, 2012)

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

Acknowledgment

The material in this webpage is supported in part by the National Science Foundation under CAREER grant CCF-0844796. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).