# Presentation: 585288

## Local Theory of BER for LDPC Codes: Instantons on a Tree

- Vladimir Chernyak
- Department of Chemistry
- Wayne State University

**In collaboration with:**
**Misha Chertkov (LANL)**
**Misha Stepanov (LANL)**
**Bane Vasic (Arizona)**

**Special thanks:**
**Fred Cohen (Rochester)**

## Outline

- Introduction and terminology: Linear Block and LDPC codes, parity checks and Tanner graphs
- Effective spin models for decoding: sMAP and BP approaches
- Local and global structures of LDPC codes: The role of trees
- Instanton (optimal fluctuation) approach to BER
- Low SNR case: High-symmetry “local” instantons, Shannon transition
- High SNR case: Low-symmetry “global” instantons
- From high to low SNR: Instantons with intermediate symmetries
- Towards non-tree instantons: High SNR case, quasi-instantons and related painted structures
- Summary and future plans

## Linear block codes (parity check representation)

- Parity check matrix

- - “spin” variables

- Tanner graph

- - set of constraints

## Linear block codes and Tanner graphs

- variable (bit) nodes

- connections

- checking nodes

- words (spin representation)

- code words

- Equivalent codes (gauge invariance)

- Gauge group

## Effective spin models and decoding approaches

- Set of magnetic fields (measurement outcome)
-  = log-likelihoods

- sMAP decoding
- (gauge invariant)

- auxiliary variables defined on connections

- “Approximate” gauge non-invariant
- schemes

- Iterative belief propagation (BP)

- Belief propagation (BP) equation

- All three schemes are equivalent in the loop-free case

- _Stat Mech interpretation_
- was suggested by
- N. Sourlas (Nature ‘89)

- Gallager ’63; Pearl ’88; MacKay ’99

- magnetization
- =a-posteriori log-likelihoods

## Post FEC bit-error rate (BER) and instantons

- PDF of magnetization

- Probability of a measurement outcome

- Probability of a bit error

- Gaussian symmetric noise case

*Instanton (optimal fluctuation) approach: PDF is dominated*
*by the most probable noise configuration (saddle point)*

- SNR

- Lagrange factor

## Geometry of Tanner graphs

- Local structure: Each node
- has a tree “neighborhood”

- Universal covering tree
- (similar to Riemann surfaces)

- fundamental group

- free group with g generators

- Gauss-Bonnet theorem (Euler characteristic)

- genus

- local curvature

- Graphs with constant curvature

***The covering tree is universal***
***and possesses high symmetry***

- Wiberg ’95
- Weiss ‘00

##  BP iterative algorithm and decoding tree

- Decoding tree for BP with the
- fixed number of iterations

- On a tree the auxiliary field can
- be defined in variable nodes

- the only in-bound nearest-neighbor
- checking node

- The field that represents the
- history of iterations

***BP magnetization is represented by the fixed point of BP***
***equation (that coincides with sMAP) on the decoding tree***

## Tree instantons

- Local theory (no repetitions of magnetic fields)

- shortest loop length (girth)

- Express magnetic fields in terms of magnetization

- Effective action for an instanton problem

## High-symmetry low SNR local instantons

- Symmetric instanton effective action

## High symmetry: Shannon transition

- corresponds to the maximum of

***Shannon’s transition is a local***
***property of a code***

## Low-symmetry high SNR global instantons

- Painted structure

***High SNR instantons are associated with painted structures***

## Intermediate instantons with partially-broken symmetry

***Symmetry is described by partially-painted structures***

## Instanton phases on a tree

- m=4, n=5, l=4. Curves of different colors correspond to the instantons/phases of
- different symmetries.

## Full numerical optimization (no symmetry assumed)

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

- m=2 n=3 l=3

## NO MORE TREES

**We apply the concept of the covering (decoding) tree**

- Wiberg ’95
- Weiss ‘00

**For higher SNR instantons reflect the**
**global geometry of the Tanner graph**
**(loop structure)**

**How do instantons look in the high SNR limit?**

## High SNR instantons for LDPC codes: approximate BP equations

- Relevant “multiplication” operation

- High SNR limit approximate formula

- Reduced variables

- Infinite SNR limit “multiplication” formula
- for reduced variables

- Min-sum

## High SNR instantons: painted structure representation

- Painted structure

- Discrete (Ising) variables

- Expressions for magnetization

***Quasi-instantons***

## High SNR instantons: pseudo-code word representation

- Successful (matched) competition of two
- pseudo-code words

***Quasi-instanton relation***

*If B is a stopping set (graph)*

## Summary

- We have analyzed instantons for BER on trees
- Depending on SNR  BER is dominated by instantons of different symmetry
- Shannon transition for an LDPC code is determined by local structure of the code (“curvature”)
- For BP iterative decoding we have identified candidates that dominate BER
- Adiabatic expanding of instantons from high to lower SNR

## Truth ...

_**Truth ...**_

- _[menu](slide2.xml)_

- _[main](slide20.xml)_
- _[slide](slide20.xml)_