# Presentation: 196452

## Error correction on a tree: Instanton approach

*                  **Misha Chertkov **(LANL)*

- In collaboration with:
-  V. Chernyak (Corning)
-  M. Stepanov (UA, Tucson)
-  B. Vasic (UA, Tucson)

- Thanks:
- I. Gabitov (Tucson/LANL)

- Boulder:  04/15/04

- Submitted to Phys.Rev.Lett.

## Tree as an approximation: BP is exact . From LDPCC to a tree 

- Forward-Error-Correction (FEC).    Channel    Noise.
- Coding.
-        Low Density Parity Check codes (LDPC) - Tanner graph
- Decoding.
-     Marginal-A-Posteriori (MAP) – Stat Mech interpretation
-     Belief Propagation (BP) – Message Passing (MP)
- Post-Error-Correction Bit-Error-Rate (BER).
-     Optimization.  Shannon transition/limit . Error floor - Evaluation.

- Tree as an approximation: BP is exact . From LDPCC to a tree
- BER in the center of the tree
-  High Signal-to-Noise Ratio (SNR) phase. Hamming distance.
- Symmetry. * Broken Symmetry. *
- Instantons/phases on the tree.

- Introduction:

- What is next? *

- Our objectives

## channel

_**Forward-Error-Correction**_

*Coding*

*Decoding*

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

- white

-  Gaussian
- symmetric

- example

- _[menu](slide2.xml)_

- noise

## Low Density Parity Check Codes 

- _[menu](slide2.xml)_

-   N=10
- variable
-   nodes

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

- Parity check matrix

- Tanner graph

- “spin” variables -

- - set of constraints

- (linear coding)

## Decoding (optimal)

- _[menu](slide2.xml)_

## Sub-optimal but efficient decoding

-  Belief Propagation (BP)
-  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)_

## Post-Error-Correction Bit Error Rate (BER)

- measure for unsuccessful
-         decoding

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

- probability density for given
- magnetic field/noise realization

- _Foreword-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)_

## menu

- From R. Urbanke,  “Iterative coding systems”

- _[menu](slide2.xml)_

- SNR, s

- BER, B

_**Shannon transition/limit**_

## Error floor

_**Error floor**_

- 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.

- _[menu](slide2.xml)_

- No-go zone for brute-force
- Monte-Carlo numerics.
- Estimating very low BER
-  is the major bottleneck
-   of the coding theory

## Our objective:

- For given (a) channel (b) coder (c) decoder
- to estimate BER/FER 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/saddle-point approach is the right way to identify
- the “bad” configurations and thus to estimate BER!

- _[menu](slide2.xml)_

## menu

_**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

## From a finite-size LDPCC to a tree:

- 1)  Fix the variable node where BER needs to be calculated
- 2)  Choose shortest loop on the graph coming  through the “0”th node. Length of the loop is (n+1).
- 3)  Count n-generations from the tree center and cut the rest.

_*Regular graph/tree  is characterized by:*_
- m   -  number of checking nodes connected to
-          a variable node
- k    -  number of variable nodes connected to
-          a checking node
- n   -   number of generations on the tree

- m=2,k=3,n=4

- _[menu](slide2.xml)_

## BER in the center of the tree

- _[menu](slide2.xml)_

- Remarks: 1)  Optimal configuration/instanton depends on SNR, s;
-                  2)  There are may be many competing instantons;
-                  3)  Looking for instantons pay attention to the symmetry

*Instanton equations!*

- _Effective action_

## High Signal-to-Noise-Ratio (SNR) phase

- _[menu](slide2.xml)_

- Original code word = “+1” on the entire tree

- The next “closest” code word
-              =  “-1” on the colored branches,
-              = “+1” on the remaining variable nodes

- Hamming distance between the two code words
- = number of the colored variable nodes

- Analogy with a low-temperature phase in  stat-mech:
- High SNR value of effective action ~ self energy

## Low SNR -- symmetric -- phase

- menu

- Symmetric phase:        at any node on the tree depends
- primarily on the generation (counted from the center)

- for  j=0,...,n-2

- instanton
- equations

- _“__zero momentum” configuration/approximation_

- guarantees estimation
- from above for eff. action

## In general:

- There are many (!!!)
- broken symmetry
- instanton solutions

- Remark:
- Broken symmetry instantons may be related
- to the “near codewords” suggested  by
- Richardson ‘03 in the context of the
- error-floor phenomenon explanation

- menu

- _Broken symmetry_

- High SNR
- (low temp)

-  Low SNR
- (high temp)

## Instanton phases on the tree

- different symmetries.

_**Instanton phases on the tree**_

- _[menu](slide2.xml)_

- truth ...

## m=2 l=3 n=3

_**Full numerical optimization**_ (no symmetry breaking was assumed !!!)

- Area of a circle surrounding any variable node is proportional
- to the value of the noise on the node.

- menu

## What is next?

- We plan to develop and extend this instanton approach to:
- Regular codes with loops. This task will require developing a perturbation theory with respect to the inverse length of the closed loop and/or with respect to the small density of closed loops.
- Other types of codes, e.g. convolutional, turbo, etc.
- Calculation of the Frame Error Rate (FER), thereby measuring the probability of making an error in a code word.
- Finite-number of iteration in message-passing version of the BP algorithm. The particular interest here lies in testing how BER in general and the error floor phenomena in particular depend on the number of iterations.
- Other types of fast but, probably, less efficient decoding schemes.
- Other types of uncorrelated channels (noise), e.g. binary eraser channel.
- Correlated channels, with both positive and negative types of correlations between neighboring slots.  This is particularly relevant for linear and nonlinear (soliton) transmission in fiber optics communications.
- Accounting for Gaussian fluctuations (i.e. second order effects) around  the instantons.

- _[menu](slide2.xml)_

## Truth ...

_**Truth ...**_

- menu

- main
- slide