Improving analysis and performance of modern error-correction schemes: a physics approach UoC, 04/10/06 Misha Chertkov (Theory Division, LANL) Vladimir Chernyak (Department of Chemistry, Wayne State) Misha Stepanov (Theory Division, LANL) Bane Vasic (Department of ECE, University of Arizona) Analyzing error-floor for LDPC codes Phys.Rev.Lett. 93, 198702 (2004) IT workshop, San Antonio 10/2004 CNLS workshop, Santa Fe 01/2005 Phys.Rev.Lett. 95, 228701 (2005) arxiv.org/abs/cond-mat/0506037 arxiv.org/abs/cs.IT/0507031 IT workshop, Allerton 09/2005 arxiv.org/abs/cs.IT/0601070 arxiv.org/abs/cs.IT/0601113 Understanding Belief-Propagation: Loop Calculus MC,VC arxiv.org/abs/cond-mat/0601487 arxiv.org/abs/cond-mat/0603189 towards improving

Belief Propagation Menu: Introduction (first part) Analogous vs Digital & Analogous Error-Correction & Digital Error-Correction & LDPC, Tanner graph, Parity Check & Inference, Maximum-Likelihood, MAP & MAP vs Belief Propagation (sum-product) & BP is exact on the tree & Error-correction Optimization & Shannon-Transition & Error-floor & Instanton: proof of principles test Instanton method the idea & Instanton-amoeba (efficient numerical method) & Test code: (155,64,20) LDPC & Instantons for the Gaussian channel (Results) & BER: Monte-Carlo vs Instanton &

Conclusions & Path Forward & Analogous vs digital Analogous Digital continuous hard to copy discrete easy to copy 0111100101 camera picture music on tape typed text computer file real number better/worse integer number yes/no menu

Error-correction for analogous One iteration 4 iteration 16 iteration clean menu menu menu Digital Error-Correction N>L R=L/N - code rate Coding L N Decoding

L noise example ( in ) ( out ) (in ) x x x white N x x1 ,, xN N ( out ) ( in ) P( x | x ) p( xi( out ) | xi( in ) ) i 1 2 s Gaussian p( x | y ) exp x y 2 s 2 2

2 symmetric channel menu (linear coding) Low Density Parity Check Codes N=10 variable nodes v1 v2 v 3 v4 v5 H v6 v7 v

8 v9 v10 Tanner graph M=N-L=5 checking nodes spin variables - Parity check matrix 0 0 0 mod 2 0

0 i 2 xi 1 1 M i ,1 1 i - set of constraints i 1,, N 1,, M menu Parity check matrix (155,64,20) code

Tanner graph (155,64,20) code menu Inference Given the detected (real) signal --- xout To find the most probable (integer) pre-image --- xin decoding max arg ~xin [ allowed ] P( ~ xin | xout ) Maximum-Likelihood (ML) Decoding menu Decoding (optimal) constraints partition function Z ( h ) exp F ( h )

P( x ( out ) | x ( in ) ) { } free energy M N i ,1 exp hk k 1 i k 1 (out ) magnetic field h ( x ) log-likelihood

F (h ) m( h ) h magnetization=a-posteriori log-likelihood (symbol to symbol) Maximum-A-Posteriori (MAP) decoding (close to optimal) Stat Mech interpretation was suggested by N. Sourlas (Nature 89) output j (h ) sign m( h ) To notice spin glass (replica) approach for random codes: e.g. Rujan 93, Kanter, Saad 99; Montanari, Sourlas 00; Montanari 01; Franz, Leone, Montanari, Ricci-Tersenghi 02 Efficient but Expensive:

requires 2 L operations menu Sub-optimal but efficient decoding Belief Propagation (BP=sum-product) j j Gallager63;Pearl 88;MacKay 99 j i 1 m j tanh h j tanh tanh i i j =solving Eqs. on the graph

Iterative solution of BP = Message Passing (MP) Q*m*N steps i h j tanh tanh i i j 1 j i (t ) h j tanh tanh i i j hi ( t 1) j

i(t ) instead of 1 2L Q - number of MP iterations m - number of checking nodes contributing a variable node What about efficiency? Why BP is a good replacement for MAP? menu * (no loops!) Tree -- no loops -- approximation Analogy: Bethe lattice (1937) MAP Z ( h ) exp F ( h )

{ } M N i ,1 exp hk k 1 i k 1 j 1 X j ( h ) i ,1 exp hk k { } { } i {k }

j 1 Y j ( h ) i ,1 exp hk k { } { } i {k } j X j i 1 i exp( h j ) ( X i Yi ) ( X i Yi ) 2 i j i j j 1 i Y j exp( h j ) ( X i Yi ) 2 i j

BP j i ( X Y ) i i i j j ln(Y j / X j ) / 2 j i h j tanh tanh i i j

1 Belief Propagation is optimal (i.e. equivalent to Maximum-A-Posteriori decoding) on a tree (no loops) Gallager 63; Pearl 88; MacKay 99 Yedidia, Freeman, Weiss 01 menu Bit Error Rate (BER) Probability of making an error in the bit i probability density for given magnetic field/noise realization (channel) ( out ) ( out ) ( out ) Bi dx mi ( x ) P( x | 1) measure of unsuccessful decoding

{+1} is chosen for the initial code-word Digital error-correction scheme/optimization 1. describe the channel/noise --- External 2. suggest coding scheme 3. suggest decoding scheme 4. measure BER/FER 5. If BER/FER is not satisfactory (small enough) goto 2 menu BER, B Shannon transition/limit SNR, s From R. Urbanke, Iterative coding systems menu Error floor (finite size & BP-approximate) Error floor prediction for some regular (3,6) LDPC Codes using a 5-bit decoder.

From T. Richardson Error floor for LDPC codes, 2003 Allerton conference Proccedings. No-go zone for brute-force Monte-Carlo numerics. Estimating very low BER is the major bottleneck in coding theory/practice menu Our (current) objective: For given (a) channel (b) coder (c) decoder to estimate BER by means of analytical and/or semi-analytical methods. Hint: BER is small and it is mainly formed at some very special bad configurations of the noise/magnetic field Instanton approach is the right way to identify the bad configurations and thus to estimate BER! menu Instanton Method noise2 Laplace method Saddle-point method Steepest descent

Point at the ES closest to zero errors noise... no errors BER = d(noise) Weight(noise) BER noise1 instanton config. Weight of the noise instanon config of the noise

Error-surface (ES) Point at the ES closest to zero menu Parity check matrix (155,64,20) code Tanner graph (155,64,20) code menu Found with numerical instanton-amoeba scheme instanton-amoeba menu Instantons for (155,64,20) code: Gaussian channel 2 46 l

10.076 210 2 ef 806 2 lef 10.203 79 2 44 lef2 10.298 188 Phys. Rev. Lett -- Nov 25, 2005 menu menu Conclusions (for the first part error floor analysis) We suggested amoeba-instanton method for efficient numerical evaluation of BER in the regime of high SNR (error floor). The main idea: error-floor is controlled by only a few most damaging configurations of the noise (instantons).

Results of the amoeba-instanton are successfully validated against brut-force Monte-Carlo (in the regime of moderate SNR) menu Path Forward Extend the amoeba-instanton test to study the error-floor to develop universal computational tool-box for the error-floor analysis Other codes Other decoding schemes (e.g. number of iterations) Other channels (e.g. magnetic recording and fiber-optics specific) New decoding ?! Major challenge !!!! to improve BP qualitatively New coding ?! Efficient (channel specific) LDPC optimization Inter-symbol interference + noise (2d and 3d + error-correction) Distributed coding, Network coding Combinatorial optimization menu

Understanding Belief Propagation Questions: Why it works so well even when it should not? -- BP is gauge fixing condition Can one constructs a full solution (MAP) from BP? -- yes one can!/loop series Answers: arxiv.org/abs/cond-mat/0601487 arxiv.org/abs/cond-mat/0603189 Making use of the loop calculus/series Improving BP approximate algorithms first slide LDPC decoding SATisfiability resolution Data reconstruction Clustering etc Ising variables on edges

Vertex Model Partition function Z f a a { } a X X {edges} Probability 1 p ( ) Z f a a a X Reduction to bipartite graph (error-correction): 1, f i ( i ) 0, ab ba 1 ( 12 , 14 , 18 , 23 , 34 , 45 , )

1 ( 12 , 14 , 18 ) 2 ( 12 , 13 ) a {i, } i i , , i otherwise hi i f ( ) i ,1 exp i ,1 exp i i i qi improving BP Bethe Free Energy --- Variational Approach F ba a ln f a a ba a ln ba a

a a self-energy Constraints (introduce in minimization through Lagrange multipliers) a a a, c; ca : a, c; ca : a, c; F b

0 Generalization of Yedidia, Freeman,Weiss 01 entropy ca : b ln b ac ( a ,c ) ac ac ac ac entropy correction 0 ba ( a ) , bac ( ac ) 1 b

( a a ) bac ( ac ) 1 a ac bac ( ac ) a \ ac ba ( a ) c \ ac bc ( c ) Belief Propagation (Bethe-Peierls) equations

improving BP Loop series =C bab --- beliefs (prob.) calculated within BP ! Z 0 ln FBethe BP is special, not only without loops! Gauge invariant representation! Three alternative derivations: improving BP integral representation algebraic representation gauge representation Loop series (derivation #1) Z ' f a ( a )

a 1 bc cb f a ( a ) 2 a ( b ,c ) ' { 12 , 21 ,} 1 coshbc bc sinhbc cosh cb cb sinh cb cosh Vbc 1 sinh bc cosh sinh cb cosh vertex 1 bc cb Vbc * bc cb 1 propagator

Z 2 cosh Pa Vbc ( b ,c ) ( b ,c ) ' a Pa ( a ) f a ( a ) (cosh ab ba sinh ab ) ba ab --- gauge degrees of freedom (at our disposal !) improving BP Loop series (derivation #2) Z ~ Pa Vbc ' a ( b ,c ) Expand the vertex (edge) term 1

* * "colored " contrib . Each node enters the product only once Node is colored if it contains at least one colored edge Calculate resulting terms one-by-one ** Gauge fixing condition: ab * --- gauge degrees of freedom (at our disposal !) To forbid loose end contribution for any node !! improving BP Loop series (derivation #3) fixing the gauge!! to kill loops

equations Belief Propagation !! Loop series has just been derived!! improving BP Conclusions ( for the second part Understanding/Improving BP) Loopy BP works well because BP is nothing but GAUGE FIXING condition Simple finite series --- LOOP SERIES --for MAP is constructed in terms of BP solution Future work Approximate algorithms --- leading loop, next after leading,.. --- apply to LDPC decoding --- different graphs, lattices Generalization --- Ising Potts (longer alphabets) --- continuous alphabets (XY,Heisenberg,Quantum models) improving BP first slide

Instantons on the tree (semi-analytical) m=2, l=3, n=3 m=3, l=5, n=2 PRL 93, 198702 (2004) ITW 2004, San Antonio menu Instanton-amoeba (efficient-numerical scheme) * (u ) u l* (u ) m0 (* (u )) 0 unite vector in the noise space error-surface Bi ~ max u P(1 * (u ) | 1) P(1 * (uef ) | 1)

To minimize BER with respect to the unit vector !! Minimization method of our choice is simplex-minimization (amoeba) instanton-amoeba for Tanner code uef arg max u P (1 * (u ) | 1) lef l* (uef ) menu Different noise models for different channels White N ( out ) ( in ) P( x

| x ) p( xi( out ) | xi( in ) ) i 1 Symmetric p ( x | y ) p ( y | x) Gaussian Laplacian s2 2 s2 p ( x | 1) exp 2 2 p ( x | 1) ( s / 2) exp s p ( xi | 1) 1 hi 2 log xi 2s p ( xi | 1) hi

p ( xi | 1) 1 log 2s p ( x | 1 ) i simplifications Linear ( out ) (in ) x 1 x 1 1 u l (u ) 1, i 2

1 i ,2 i 0 1,0 i menu Phys.Rev.Lett. 95, 228701 (2005) Rational structure of instanton (computational tree analysis/explanation) min-sum 4 iterations Minimize effective action keeping the condition menu based on Wiberg 96 Bit-Error-Rate: Gaussian channel menu Instantons for (155,64,20) code: Laplacian channel

lef 7.6 lef 8.0 IT workshop, Allerton 09/2005 lef 8.0 menu Instantons as medians of pseudo-codewords PRL -- Nov 25, 2005 menu Bit-Error-Rate: Laplacian channel menu