Expander Codes, LDPC Codes, and Fountain Codes
Stub. Low-density parity-check (LDPC) codes and expander codes, which build good error-correcting codes directly from the pseudorandom/expansion properties of a sparse bipartite graph rather than from algebraic structure; and fountain (rateless) codes, which can generate an unbounded stream of encoding symbols on the fly so a receiver can stop listening as soon as it has received enough, whatever the channel's actual loss rate turned out to be.
Corresponds to Lecture topic 9. LDPC and expander codes replace the algebraic constructions of earlier notes with a graph-theoretic one: a sparse bipartite “Tanner” graph between codeword bits and parity checks, where a codeword is any assignment satisfying every check, and good expansion of this graph (see expander-graphs-fundamentals) is exactly what makes the resulting code have good minimum distance and an efficient (often linear-time) decoding algorithm — see explicit-constructions-of-biased-distributions-and-codes for the Sipser-Spielman Tanner-graph LDPC construction covered there in a pseudorandomness context, directly applicable here. Fountain (rateless) codes solve a different problem: rather than fixing a code rate in advance, a fountain encoder can produce as many encoding symbols as needed on the fly, such that a receiver can decode the original message from any sufficiently large subset of symbols received — ideal for broadcast/erasure channels where the actual loss rate isn’t known ahead of time.
Outline (TODO — flesh out each)
- Expander graphs and expander codes
- Low-density parity-check (LDPC) codes
- Tanner graphs and message-passing decoding
- Fountain codes — rateless encoding