# Presentation: 612758

## Diagnosis of Weaknesses in Modern 

_**Error-Correction Codes: Physics Approach**_*                  *

- Phys.Rev.Lett. 93, 198702 (2004)
- IT workshop, San Antonio 10/2004
- CNLS workshop, Santa Fe 01/2005
- Phys.Rev.Lett. -- Nov. 25 (2005)
- arxiv.org/abs/cond-mat/0506037
- arxiv.org/abs/it/0507031
- IT workshop, Allerton 09/2005

- Misha Chertkov (Theory Division, LANL)
- Misha Stepanov (Theory Division, LANL)
- Vladimir Chernyak (Department of Chemistry, Wayne State)
- Bane Vasic (Department of ECE, University of Arizona)

**Notes:**
Title

## Menu:

-  Analogous vs Digital _[&](slide3.xml)_
-  Analogous Error-Correction _[&](slide4.xml)_
-  Digital Error-Correction _[&](slide5.xml)_
-  LDPC, Tanner graph, Parity Check _[&](slide6.xml)_
-  Inference, Maximum-Likelihood, MAP _[&](slide8.xml)_
-  MAP vs Belief Propagation (sum-product) _[&](slide9.xml)_
-  BP is exact on the tree _[&](slide10.xml)_
-  Error-correction Optimization _[&](slide11.xml)_
-  Shannon-Transition _[&](slide12.xml)_
-  Error-floor _[&](slide13.xml)_

- Introduction

-  Instanton method – the idea _[&](slide15.xml)_
-  Instanton-amoeba (efficient numerical method) _[&](slide16.xml)_
-  Instantons on the tree (loops are neglected) _[&](slide17.xml)_
-  Test code: (155,64,20) LDPC _[&](slide18.xml)_
-  Different channels (Gaussian and Laplacian) _[&](slide19.xml)_
-  Instantons for the Gaussian channel (Results) _[&](slide20.xml)_
-  BER: Monte-Carlo vs Instanton (Gaussian channel) _[&](slide21.xml)_
-  Rational structure of the instatnon (computational tree analysis) _[&](slide22.xml)_
-  Instantons as medians between pseudo-codewords &
-  Instantons for the Laplacian channel (Results) &
-  BER: Monte-Carlo vs Instanton (Laplacian channel) &

-  Conclusions &
-  Path Forward &

- Instanton: proof
-  of principles test

**Notes:**
Menu

## 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](slide2.xml)_

**Notes:**
Analogous vs digital

## Error-correction for analogous 

**One iteration**

- _[menu](slide2.xml)_

**Notes:**
Analogous error-correction

## channel

_**Digital Error-Correction**_

*Coding*

*Decoding*

- N > L     R=L/N  -  code rate

- white

-  Gaussian
- symmetric

- example

- noise

- _[menu](slide2.xml)_

**Notes:**
Digital error-correction

## Low Density Parity Check Codes 

- _[menu](slide1.xml)_

-   N=10
- variable
-   nodes

-    M=N-L=5
-     checking
-       nodes

- Parity check matrix

- Tanner graph

- “spin” variables -

- - set of constraints

- (linear coding)

**Notes:**
LDPC, Tanner graph, Parity check

## Inference

- Maximum-Likelihood (ML) Decoding

- _[menu](slide2.xml)_

**Notes:**
Inference, ML

## Decoding (optimal)

- “magnetic” field
- log-likelihood

- “magnetization”=a-posteriori log-likelihood

- _[menu](slide2.xml)_

**Notes:**
MAP.ML

## Sub-optimal but efficient decoding

-  Belief Propagation (BP=sum-product)
-  Gallager’63;Pearl ’88;MacKay ‘99

- =solving Eqs. on the graph

-  Iterative solution of BP
- = Message Passing (MP)

- Q*m*N steps    instead   of
- 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?

-  * (no loops!)

- _[menu](slide2.xml)_

## Tree -- no loops -- approximation

- MAP

- BP

- Belief Propagation is optimal (i.e. equivalent
- to Maximum-A-Posteriori decoding) on a tree (no loops)

- Analogy:
- Bethe lattice (1937)

- Gallager ’63; Pearl ’88; MacKay ’99
- Vicente, Saad, Kabashima ’00; Yedidia, Freeman, Weiss ‘01

- _[menu](slide2.xml)_

**Notes:**
BP is exact on a tree

## Bit Error Rate (BER)

- measure of unsuccessful
-         decoding

- _Probability of making an error in the bit “i” _

- probability density for given
- magnetic field/noise realization
- (channel)

- _Digital error-correction scheme/optimization_

-  describe the channel/noise  --- External
-  suggest coding scheme
-  suggest decoding scheme
-  measure BER/FER
- If BER/FER is not satisfactory (small enough) goto 2

- _[menu](slide2.xml)_

**Notes:**
Error-correction optimization

## Shannon transition/limit

- From R. Urbanke,  “Iterative coding systems”

- SNR, s

- BER, B

_**Shannon transition/limit**_

- _[menu](slide2.xml)_

**Notes:**
Shannon transition

## Error floor     (finite size & BP-approximate)

_**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](slide2.xml)_

**Notes:**
Error-floor

## 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](slide2.xml)_

**Notes:**
BER estimation -objective

## Instanton Method

- Laplace method
- Saddle-point method
- Steepest descent

- menu

## Instanton-amoeba (efficient-numerical scheme)

- To minimize BER with respect to the unit vector !!

- error-surface

- unite vector in the noise space

- Minimization method of our choice
-  is simplex-minimization (amoeba)

- _[menu](slide2.xml)_

**Notes:**
Instanton-amoeba

## Instantons on the tree (semi-analytical)

- menu

- PRL 93, 198702 (2004)

- ITW 2004,  San Antonio

- m=2, l=3, n=3

- m=3, l=5, n=2

## Parity check matrix of Tanner’s (155,64,20) code

- _[menu](slide2.xml)_

**Notes:**
Tanner graph for (155,64,20)

## Different noise models for different channels

- White

-  Gaussian

- Linear

- Symmetric

- simplifications

-  Laplacian

- _[menu](slide2.xml)_

## Instantons for (155,64,20) code: Gaussian channel

- Phys. Rev. Lett  -- Nov 25, 2005

- menu

## Bit-Error-Rate: Gaussian channel

- menu

## Rational structure of instanton 

- (computational tree analysis/explanation)

- min-sum

- 4 iterations

- based on Wiberg ‘96

*PRL  -- Nov 25,  2005*

- Minimize effective action
- keeping the condition

- _[menu](slide2.xml)_

## Instantons as medians of pseudo-codewords

_***Instantons as medians of pseudo-codewords***_

- _[menu](slide2.xml)_

*PRL  -- Nov 25,  2005*

## Instantons for (155,64,20) code: Laplacian channel

- menu

- IT workshop, Allerton 09/2005

## Bit-Error-Rate: Laplacian channel

- menu

## Conclusions

- _[menu](slide2.xml)_

**Notes:**
Conclusions

## Path Forward

- Inter-symbol interference (1d and 2d + error-correction)
- Network coding
- Combinatorial optimization

- _[menu](slide2.xml)_

**Notes:**
Path forward