WIXLIB

Optimal Bit Decoding - BEC Maximum a posteriori (MAP) bit decoding rule minimizesbit error probability:xˆ iMAP ( y ) arg max PX i Y (b y )b {0 ,1} arg maxb {0 ,1} PX Y( x y)x Cxi b Assume that codewords are transmitted equiprobably. If every codeword x X(y) satisfies xi b, then setxˆ MAP ( y ) b Otherwise, declare a bit erasure in position i.5/ 31/ 07LDPC Codes44

MAP Decoding Complexity Let E {1, ,n} denote the positions of erasures in y, and letF denote its complement in {1, ,n}. Let wE and wF denote the corresponding sub-words of word w. Let HE and HF denote the corresponding submatrices of theparity check matrix H. Then X(y), the set of codewords compatible with y, satisfiesX( y ) { x C xF yF and H E xET H F yFT} So, optimal (MAP) decoding can be done by solving a set oflinear equations, requiring complexity at most O(n3). For large blocklength n, this can be prohibitive!5/ 31/ 07LDPC Codes45

Simpler Decoding We now describe an alternative decoding procedurethat can be implemented very simply. It is a “local” decoding technique that tries to fill inerasures “one parity-check equation at a time.” We will illustrate it using a very simple and familiarlinear code, the (7,4) Hamming code. We’ll compare its performance to that of optimal bitwise decoding. Then, we’ll reformulate it as a “message-passing”decoding algorithm and apply it to LDPC codes.5/ 31/ 07LDPC Codes46

Local Decoding of Erasures dmin 3, so any two erasures can beuniquely filled to get a codeword. Decoding can be done locally:Given any pattern of one or twoerasures, there will always be aparity-check (circle) involvingexactly one erasure. The parity-check represented by thecircle can be used to fill in the erasedbit.5271436 This leaves at most one more erasure.Any parity-check (circle) involving itcan be used to fill it in.5/ 31/ 07LDPC Codes47

Local Decoding - Example All-0’s codeword transmitted. Two erasures as shown.0 Start with either the red parityor green parity circle. The red parity circle requiresthat the erased symbol inside itbe 0.5/ 31/ 07LDPC Codes?00?0048

Local Decoding -Example Next, the green parity circle orthe blue parity circle can beselected.0 Either one requires that theremaining erased symbol be 0.005/ 31/ 07LDPC Codes0?0049

Local Decoding -Example Estimated codeword:[0 0 0 0 0 0 0] Decoding successful!! This procedure would haveworked no matter whichcodeword was transmitted.5/ 31/ 070LDPC Codes00000050

Decoding with the Tanner Graph:an a-Peeling Decoder Initialization: Forward known variable nodevalues along outgoing edges Accumulate forwarded values atcheck nodes and “record” theparity Delete known variable nodes andall outgoing edges5/ 31/ 07LDPC Codes51

Peeling Decoder – Initialization5/ 31/ 07xx00?00?00?11LDPC CodesForwardForwardknownknownvaluesvalues52

Peeling Decoder - InitializationxxAccumulate parity00?00?00?115/ 31/ 07LDPC CodesDelete known variablenodes and edges53

Decoding with the Tanner Graph:an a-Peeling Decoder Decoding step: Select, if possible, a check node with one edge remaining;forward its parity, thereby determining the connectedvariable node Delete the check node and its outgoing edge Follow procedure in the initialization process at the knownvariable node Termination If remaining graph is empty, the codeword is determined If decoding step gets stuck, declare decoding failure5/ 31/ 07LDPC Codes54

Peeling Decoder – Step 1x0Find degree-1 check node;forward accumulated parity;determine variable node valuex00000?00?115/ 31/ 07LDPC CodesDelete check node and edge;forward new variable node value55

Peeling Decoder – Step 1xAccumulate parityx000000?00?115/ 31/ 07LDPC CodesDelete known variablenodes and edges56

Peeling Decoder – Step 2xFind degree-1 check node;forward accumulated parity;determine variable node valuex0000001100?115/ 31/ 07LDPC CodesDelete check node and edge;forward new variable node value57

Peeling Decoder – Step 2xAccumulate parityx0000001100?115/ 31/ 07LDPC CodesDelete known variablenodes and edges58

Peeling Decoder – Step 3xFind degree-1 check node;forward accumulated parity;determine variable node valuex000000110011115/ 31/ 07LDPC CodesDelete check node and edge;decoding complete59

Message-Passing Decoding The local decoding procedure can bedescribed in terms of an iterative,“message-passing” algorithm inwhich all variable nodes and allcheck nodes in parallel iterativelypass messages along their adjacentedges. The values of the code bits areupdated accordingly. The algorithm continues until allerasures are filled in, or until thecompletion of a specified number ofiterations.5/ 31/ 07LDPC Codes60

Variable-to-Check Node Messageu?from channelv uuu ?v ?edgeedge eeedgeedge ee?Variable-to-check message on edge eIf all other incoming messages are ?, send message v ?If any other incoming message u is 0 or 1, send v u and,if the bit was an erasure, fill it with u, too.(Note that there are no errors on the BEC, so a message thatis 0 or 1 must be correct. Messages cannot be inconsistent.)5/ 31/ 07LDPC Codes61

Check-to-Variable Node Messageu ?u v1 v2 v3v1edgeedge eeedgeedge eev1v2v2v3Check-to-variable message on edge eIf any other incoming message is ?, send u ?If all other incoming messages are in {0,1},send the XOR of them, u v1 v2 v3.5/ 31/ 07LDPC Codes62

Message-Passing Example – Initializationyyxx yy0000 00? ?0000 00? ?0000 00? ?1111 115/ 31/ 07LDPC CodesVariable-to-CheckVariable-to-Check63

Message-Passing Example – Round 1x yx yCheck-to-Variable0 00 0? ?0 ?0 00 0? ? ?0 00 0? ? ?1 11 15/ 31/ 07LDPC CodesVariable-to-Check64

Message-Passing Example – Round 2x yx yCheck-to-Variable0 00 00 ?0 ?0 00 0? ?1 ?0 00 0? ? ?1 11 15/ 31/ 07LDPC CodesVariable-to-Check65

Message-Passing Example – Round 3x yx yCheck-to-Variable0 00 00 ?0 ?0 00 01 ?1 ?0 00 0? ?1 ?1 11 15/ 31/ 07LDPC CodesVariable-to-CheckDecoding complete66

Sub-optimality of Message-Passing DecoderHamming code: decoding of 3 erasures There are 7 patterns of 3 erasures thatcorrespond to the support of a weight-3codeword. These can not be decoded byany decoder!0 The other 28 patterns of 3 erasures can beuniquely filled in by the optimal decoder. We just saw a pattern of 3 erasures thatwas corrected by the local decoder. Arethere any that it cannot? Test:5/ 31/ 07?0?0?1?0 010LDPC Codes67

Sub-optimality of Message-Passing Decoder Test:?0 0100 There is a unique way to fill theerasures and get a codeword:1100 010The optimal decoder would find it.101001 But every parity-check has at least 2erasures, so local decoding will notwork!5/ 31/ 07LDPC Codes68

Stopping Sets A stopping set is a subset S of the variable nodes suchthat every check node connected to S is connected toS at least twice. The empty set is a stopping set (trivially). The support set (i.e., the positions of 1’s) of anycodeword is a stopping set (parity condition). A stopping set need not be the support of a codeword.5/ 31/ 07LDPC Codes69

Stopping Sets Example 1: (7,4) Hamming codeCodewordsupport setS {4,6,7}5/ 31/ 0712345670001011LDPC Codes70

Stopping Sets Example 2: (7,4) Hamming code15/ 31/ 072345LDPC Codes6771

Stopping Sets Example 2: (7,4) Hamming codeNot the supportset of a codewordS {1,2,3}15/ 31/ 072345LDPC Codes6772

Stopping Set Properties Every set of variable nodes contains a largest stopping set(since the union of stopping sets is also a stopping set). The message-passing decoder needs a check node withat most one edge connected to an erasure to proceed. So, if the remaining erasures form a stopping set, the decodermust stop. Let E be the initial set of erasures. When the messagepassing decoder stops, the remaining set of erasures is thelargest stopping set S in E. If S is empty, the codeword has been recovered. If not, the decoder has failed.5/ 31/ 07LDPC Codes73

Suboptimality of Message-Passing Decoder An optimal (MAP) decoder for a code C on the BECfails if and only if the set of erased variables includesthe support set of a codeword. The message-passing decoder fails if and only the setof erased variables includes a non-empty stopping set. Conclusion: Message-passing may fail where optimaldecoding succeeds!!Message-passing is suboptimal!!5/ 31/ 07LDPC Codes74

Comments on Message-Passing Decoding Bad news: Message-passing decoding on a Tanner graph isnot always optimal. Good news: For any code C, there is a parity-check matrix onwhose Tanner graph message-passing is optimal,e.g., the matrix of codewords of the dual code C . Bad news: That Tanner graph may be very dense, so evenmessage-passing decoding is too complex.5/ 31/ 07LDPC Codes75

Another (7,4) Code 1 1 0 1 0 0 0 H 0 0 1 1 0 1 0 0 0 0 1 1 0 1 R 4/7dmin 2All stopping sets contain codeword supports.Message-passing decoder on this graph is optimal!(Cycle-free Tanner graph implies this.)5/ 31/ 07LDPC Codes76

Comments on Message-Passing Decoding Good news: If a Tanner graph is cycle-free, the messagepassing decoder is optimal! Bad news: Binary linear codes with cycle-free Tanner graphsare necessarily weak. Good news: The Tanner graph of a long LDPC code behavesalmost like a cycle-free graph!5/ 31/ 07LDPC Codes77

Analysis of LDPC Codes on BEC In the spirit of Shannon, we can analyze theperformance of message-passing decoding onensembles of LDPC codes with specified degreedistributions (λ,ρ). The results of the analysis allow us to design LDPCcodes that transmit reliably with MP decoding at ratesapproaching the Shannon capacity of the BEC. In fact, sequences of LDPC codes have been designedthat actually achieve the Shannon capacity. The analysis can assume the all-0’s codeword is sent.5/ 31/ 07LDPC Codes78

Key Results - 1 Concentration With high probability, the performance of ℓ roundsof MP decoding on a randomly selected (n, λ, ρ)code converges to the ensemble averageperformance as the length n . Convergence to cycle-free performance The average performance of ℓ rounds of MPdecoding on the (n, λ, ρ) ensemble converges to theperformance on a graph with no cycles of length 2ℓ as the length n .5/ 31/ 07LDPC Codes79

Key Results - 2 Computing the cycle-free performance The cycle-free performance can be computed by atractable algorithm – density evolution. Threshold calculation There is a threshold probability p*(λ,ρ) such that,for channel erasure probability ε p*(λ,ρ), thecycle-free error probability approaches 0 as thenumber of iterations ℓ .5/ 31/ 07LDPC Codes80

Asymptotic Performance Analysis We assume a cycle-free (λ,ρ) Tanner graph. Let p0 ε, the channel erasure probability. We find a recursion formula for pℓ , theprobability that a randomly chosen edge carries avariable-to-check erasure message in round ℓ. We then find the largest ε such that pℓ convergesto 0, as ℓ . This value is called the threshold. This procedure is called “density evolution”analysis.5/ 31/ 07LDPC Codes81

Density Evolution-1 messages.messages.Pr (u ? ) Pr (vi ?, for some i 1, , d 1) 1 Pr (vi ?, for all i 1, , d 1) 1 (1 p 1 )1d 1 The probability that edge e connects toa check node of degree d is ρd , soPr (u ?) dc uu edge ev edge eρ d (1 (1 p 1 ) d 1 )vd 2vd 1d 1 1 dc ρ d (1 p 1 ) d 1d 1 1 ρ (1 p5/ 31/ 07 1)LDPC Codes82

Density Evolution-2vvedgeedge eeu0from channelu1ud 2u d 1 Consider a variable node of degreed with independent incomingmessages.Pr (v ?) Pr (u 0 ?) Pr (ui ?, for all i 1, , d 1) p0 [1 ρ (1 p 1 ) ]d 1 The probability that edge e connects toa variable node of degree d is λd , soPr (v ?) dv λd p0 [1 ρ (1 pd 1 p0 λ (1 ρ (1 p 1d 1)] 1))pℓ p0 λ (1–ρ(1–pℓ-1))5/ 31/ 07LDPC Codes83

Threshold Propertypℓ p0 λ (1–ρ(1–pℓ-1)) There is a threshold probability p*(λ, ρ) such thatifthenp0 ε p * (λ , ρ ),lim p 0. 5/ 31/ 07LDPC Codes84

Threshold Interpretation Operationally, this means that using a code drawnfrom the ensemble of length-n LDPC codes withdegree distribution pair (λ, ρ), we can transmit asreliably as desired over the BEC(ε) channel ifε p * (λ , ρ ) ,for sufficiently large block length n .5/ 31/ 07LDPC Codes85

Computing the Threshold Define f (p,x) p λ (1–ρ(1–x)) The threshold p*(λ, ρ) is the largest probability p suchthatf (p,x) – x 0on the interval x (0,1]. This leads to a graphical interpretation of thethreshold p*(λ, ρ)5/ 31/ 07LDPC Codes86

Graphical Determination of the Threshold Example: (j,k) (3,4)(f ( x, p ) x p 1 (1 x))3 2 xp* 0.6474p 0.7p 0.6474p 0.6p 0.55/ 31/ 07LDPC Codes87

(j,k)-Regular LDPC Code Thresholds There is a closed form expression for thresholds of(j,k)-regular LDPC codes. Examples:5/ 31/ 07(j,k)(3,4)(3,5)(3,6)(4,6)R1/42/51/21/3pSh¾ 0.753/5 0.6½ 0.5⅔ 0.67p*(j,k) 0.6474 0.5176 0.4294 0.5061(4,8)1/2½ 0.5 0.3834LDPC Codesp * (3,4) 31253672 252 21 0.64742688

Degree Distribution Optimization Two approaches: Fix design rate R(λ,ρ) and find degreedistributions λ(x), ρ(x) to maximize the thresholdp*(λ,ρ). Fix the threshold p*, and find degree distributionsλ(x), ρ(x) to maximize the rate R(λ,ρ). For the latter, we can: start with a specific ρ(x) and optimize λ(x); then, for the optimal λ(x), find the optimal checkdistribution; ping-pong back and forth until satisfied with theresults.5/ 31/ 07LDPC Codes89

Variable Degree Distribution Optimization Fix a check degree distribution ρ(x) and threshold ε. Fix maximum variable degree lmax . Defineg ( x, λ2 , , λl max ) ελ (1 ρ (1 x)) x ε λ (1 ρ (1 x))ii 1 xi 2 Use linear programming to findl max lmax max (λi / i ) λi 0; λi 1; g 0 for x [0,1] λ i 2 i 2 Since the rate R(λ,ρ) is an increasing function of λi/i,this maximizes the design rate.5/ 31/ 07LDPC Codes90

Practical Optimization In practice, good performance is found for a check degreedistribution of the form:ρ ( x) ax r 1 (1 a) x r Example 1: lmax 8, r 6, design rate ½λ ( x) 0.409 x 0.202 x 2 0.0768 x 3 0.1971x 6 0.1151x 7ρ ( x) x 5 Rate: Threshold:5/ 31/ 07R(λ,ρ) 0.5004p*(λ,ρ) 0.4810LDPC Codes91

Bound on the Threshold Taylor series analysis yields the general upper bound:1p * (λ , ρ ) .λ ′(0) ρ ′(1) For previous example with p*(λ,ρ) 0.4810, the upper boundgives:11 0.4890λ ′(0) ρ ′(1) (0.409) 55/ 31/ 07LDPC Codes92

EXIT Chart Analysis Extrinsic information transfer (EXIT) charts provide a nicegraphical depiction of density evolution and MP decoding[tenBrink,1999] Rewrite the density evolution recursion as:f ( x, p ) pλ (1 ρ (1 x)) v p (c( x))wherev p ( x ) pλ ( x )c( x) 1 ρ (1 x)5/ 31/ 07LDPC Codes93

EXIT Chart Analysis Recall that the MP convergence condition wasf ( x, p ) x, for all x (0,1) Since λ(x) is invertible, the condition becomes 1c( x) v p ( x), for all x (0,1) Graphically, this says that the curve for c(x) must lie 1below the curve for v p ( x) for all p p*.5/ 31/ 07LDPC Codes94

EXIT Chart Example Example: (3,4)-regular LDPC code, p* 0.6474λ ( x) x 2v p ( x) pλ ( x)ρ ( x) x 3c( x) 1 ρ (1 x) px 2 x v ( x) p 1p5/ 31/ 07 1 (1 x) 312LDPC Codes95

EXIT Chart Example Example: (3,4)-regular LDPC code, p* 0.647410.9p 0.5p 0.60.8 x v p1 ( x) p p 0.7p 0.80.70.6for variousvalues ofinitial erasureprobability p0.5p* 0.64740.4120.3c( x) 1 (1 x) 30.20.105/ 31/ 0700.10.20.30.40.50.6LDPC Codes0.70.80.9196

EXIT Charts and Density Evolution EXIT charts can be used to visualize densityevolution. Assume initial fraction of erasure messages p0 p. The fraction of erasures emitted successively by checknode qi and by variable nodes and pi are obtained bysuccessively applying c(x) and vp(x).q1 c( p0 )p1 v p (q1 ) v p (c( p0 ))[note : v p1 ( p1 ) q1 ]q 2 c( p1 )p 2 v p (q 2 ) v p (c( p1 ))5/ 31/ 07LDPC Codes[note : v p1 ( p 2 ) q 2 ]97

EXIT Charts and Density Evolution Graphically, this computation describes a staircasefunction. If p p*, there is a “tunnel” between vp-1(x) and c(x)through which the staircase descends to ground level,i.e., no erasures. If p p*, the tunnel closes, stopping the staircasedescent at a positive fraction of errors.5/ 31/ 07LDPC Codes98

Density Evolution Visualization - 1 Example: (3,4)-regular LDPC code, p 0.61 x v0 .16 ( x) 0.6 0.90.8120.70.6c( x) 1 (1 x) 30.50.40.30.20.105/ 31/ 0700.10.20.30.40.50.6LDPC Codes0.70.80.9199

Density Evolution Visualization-2 Example: (3,4)-regular LDPC code1p0 0.60.9qfrac

Review of Shannon's Paper 5/ 31/ 07 LDPC Codes 12 A pioneering paper: Shannon, C. E. "A mathematical theory of communication. Bell System Tech. J. 27, (1948). 379-423, 623-656 A regrettable review: