Improving analysis and performance of modern error-correction schemes:

Improving analysis and performance of modern error-correction schemes:

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

Recently Viewed Presentations

  • Recombination-based genomics: a genetic variance analysis in ...

    Recombination-based genomics: a genetic variance analysis in ...

    Recombination based population genomics Jaume Bertranpetit Marta Melé Francesc Calafell Asif Javed Laxmi Parida Recall: IRiS Identification of Recombinations in Sequences IRiS is a computational method developed with biological insight detects evidence of historical recombinations minimizes number of recombinations in...
  • Coordinators Meeting  October 2006 New York, NY National

    Coordinators Meeting October 2006 New York, NY National

    Arial Times New Roman Default Design Microsoft Office Excel Chart Coordinators Meeting - October 2006 New York, NY Questions From Coordinators Use of NSGF State Funds Sub-Account Balances as of 30 September 2006 Use of NSGF State Funds Expense Examples...
  • You have not lived a perfect day, unless

    You have not lived a perfect day, unless

    Pythagorean Theorem 9 16 25 There are at least 80 different ways to prove the Pythagorean theorem Link to AgileMinds #13, Patty Paper Proof, 1-8 Pythagorean Theorem Find the missing measures √27 12.7 Converse of the Pythagorean Th. Determine whether...
  • MARTTI (My Accessible Real Time Trusted Interpreter)

    MARTTI (My Accessible Real Time Trusted Interpreter)

    MARTTI (My Accessible Real Time Trusted Interpreter). Medical Center Hospital has an Interpreter Services Program.. Call Quality and Service Excellence Division at ext. 1240 for directions on this service
  • MarketspaceU - Chapter 3 Enhanced Lecture Slides

    MarketspaceU - Chapter 3 Enhanced Lecture Slides

    Chapter 3 Enhanced Lecture Slides ... via phone Brochure Purchase in-store Purchase via phone In-store specials Specials offered via phone *CSR = Customer service representative Flower / Gift Decision Process Need Recognition Search for Ideas and Offerings Purchase Decision Message...
  • LMU, 7. Dezember 2011 Kausaler Strukturenrealismus

    LMU, 7. Dezember 2011 Kausaler Strukturenrealismus

    Times MS Pゴシック Arial Monotype Sorts Palatino Wingdings Symbol Vorlage New directions in the foundations of physics, Washington DC, 24 April 15 The measurement problem and the primitive ontology of quantum physics The methodology The paper The measurement problem (Tim...
  • Introduction to Geo-medicine - Yola

    Introduction to Geo-medicine - Yola

    Module Name: Introduction to Geo-medicine ... Geo environment and health expect. Encourage research in the area of producing more effective methodologies for the study of geological factors in environment medicine. Essential elements in life systems.
  • Finding Your Way Into a Topic