Mathematical aspects of high performance codes: state of the art and open problems
30 January 2006 - 3 February 2006Aims
The event will consist in three short courses held by:
- Prof. Andrea Montanari, Ecole Normale Superieure, Paris, France - Prof. Tom Richardson, Flarion Technologies - Prof. Pascal Vontobel, M.I.T.
Beside, the young reaserchers will have an opportunity to present and discuss their research topics.
Research Directions
Main goal of this school is to expose PhD students and young researchers from mathematics, physics and from communication engineering to the theory of high performance codes (turbo codes, LDPC). Particular attention will be devoted to the fondational theoretical aspects of these coding schemes. Topics will include ensemble of codes defined on graphs, asymptotical averaged performance analysis, iterative decoding algorithm analysis. The mathematical techniques that allowed to obtain the most recent and important achievements (combinatorics of permutations, random graphs, concentration theory) will be introduced and studied. Open problems will be individuated and discussed.
COURSES:
Large random systems: from coding to optimization and statistical mechanics Andrea Montanari – 9 hours
Topics: (M1) Codes on graphs as a Markov Random Field. Examples of Markov Random Fields from combinatorial optimizationdecision problems, and statistical mechanics. Factor graph description. Free energy and Gibbs free energy. Threshold phenomena (phase transitions).
(M2) A toy model: the ferromagnetic Ising model on random graphs. Belief propagation as an algorithm for computing marginals. Belief propagation as a proof technique. Bethe free energy.
(M3) Phase diagram of LDPC ensembles. GEXIT functions, and generalized area theorems. The threshold for MAP (Maximum a Posteriori Probability) decoding.
(M4) continuation from the previous lecture if necessary Solving large optimization problems through belief propagation: the example of independent sets.
(M5) Proliferation of pure states. Algorithmic consequences.
(M6) Dynamics. Local search algorithms: application (and analysis) for coding and optimization.
Low density and turbo codes: structure and iterative decoding Tom Richardson – 9 hours
Topics:
(R1) LDPC codes and Turbo codes. Ensembles, weight spectra, bounds on ML decoding based on spectra, typical pairs decoding bounds.
(R2) Iterative Decoding. (Asymptotic) analysis, symmetry, concentration theorems, density evolution, monotonicity theorems, thresholds, fixed points, stability, physical degradation.
(R3) Special case of the BEC. Finite length analysis, stopping sets finite length scaling, Luby codes.
(R4) Design, optimization techniques, EXIT functions, advanced ensembles (e.g. multi-edge, implementation oriented graphs (e.g. matched lifting).
(R5) General Encoding of LDPC, connection to the BEC.
(R6) Expanders, flipping decoding.
Codes over graphs and decoding algorithms Pascal Vontobel – 8 hours
Topics:
(V1) Brief reminder of important notions of coding theory. FactorTanner graphs and the sum-product algorithm (including introduction to LDPC codes, turbo codes, iterative decoding).
(V2) Linear programming (LP) decoding, connections between iterative decoding and LP decoding, connections between Bethe free energy minimization and LP decoding.
(V3) Pseudo-codewords, pseudo-weight and its connection to stopping sets, near codewords, and trapping sets, the geometry of the fundamental polytope and cone, minial codewords and minimal pseudo-codewords (ML vs. LP decoding)
(V4) Construction of codes based on graphs with large girth (algebraic and random constructions), based on finite geometries and related objects, quasi-cyclic LDPC codes.
(V5) Applications of factor graphs and the sum-product algorithm beyond pure channel coding (Equalization, Kalman filtering, Inference, Fourier and Legendre transform) (Part 1)
(V6) Applications of factor graphs and the sum-product algorithm beyond pure channel coding (Equalization, Kalman filtering, Inference, Fourier and Legendre transform) (Part 2).