Introduction to LDPC Codes - CMRR STAR

1 An Introduction to Low- density parity - check Codes Paul H. Siegel Electrical and Computer Engineering University of California, San Diego 5/ 31/ 07. 1. Copyright Copyright2007. 2007by byPaul PaulH. Siegel Outline Shannon's Channel Coding Theorem Error-Correcting Codes State-of-the-Art LDPC Code Basics Encoding Decoding LDPC Code Design Asymptotic performance analysis Design optimization 5/ 31/ 07 LDPC Codes 2. Outline EXIT Chart Analysis Applications Binary Erasure Channel Binary Symmetric Channel AWGN Channel Rayleigh Fading Channel Partial-Response Channel Basic References 5/ 31/ 07 LDPC Codes 3.

2 A Noisy Communication System INFORMATION. SOURCE TRANSMITTER RECEIVER DESTINATION. CHANNEL. SIGNAL RECEIVED. SIGNAL. MESSAGE. MESSAGE. NOISE. SOURCE. 5/ 31/ 07 LDPC Codes 4. Channels Binary erasure channel BEC( ). 1- . 0 0.. ? 1 1. 1- . Binary symmetric channel BSC(p). 1-p 0 0. p p 1 1. 1-p 5/ 31/ 07 LDPC Codes 5. More Channels Additive white Gaussian noise channel AWGN. f ( y | 1) f ( y | 1). P P. 5/ 31/ 07 LDPC Codes 6. Shannon Capacity Every communication channel is characterized by a single number C, called the channel capacity. It is possible to transmit information over this channel reliably (with probability of error 0).

3 If and only if: # information bits def R= <C. channel use 5/ 31/ 07 LDPC Codes 7. Channels and Capacities Binary erasure channel BEC( ) C = 1 . 1- . 0 0. 1. ? 1 1 1- . 0. 0 1. Binary symmetric channel BSC(p) C = 1 H 2 ( p). 1-p 1. 0 0 p p 1 1 0. 0 1. 1-p H 2 ( p ) = p log 2 p (1 p ) log 2 (1 p ). 5/ 31/ 07 LDPC Codes 8. More Channels and Capacities Additive white Gaussian noise channel AWGN. P . C = log 2 1 + 2 . 1.. f ( y | 1) f ( y | 0) 2. P. P 1. 0. -10 -8 -6 -4 -2 0 2 4 6 8 10. 5/ 31/ 07 LDPC Codes 9. Coding We use a code to communicate over the noisy channel. x = x1 , x2 , , xk c = c1 , c2 , , cn Source Encoder Channel Sink Decoder x = x 1 , x 2 , , x k y = y1 , y 2 , , y n Code rate: R= k n 5/ 31/ 07 LDPC Codes 10.

4 Shannon's Coding Theorems If C is a code with rate R>C, then the probability of error in decoding this code is bounded away from 0. (In other words, at any rate R>C, reliable communication is not possible.). For any information rate R < C and any > 0, there exists a code C of length n and rate R, such that the probability of error in maximum likelihood decoding of this code is at most . C = Max (H(x) H y (x)). Proof: Non-constructive! 5/ 31/ 07 LDPC Codes 11. Review of Shannon's Paper A pioneering paper: Shannon, C. E. A mathematical theory of communication. Bell System Tech. J.

5 27, (1948). 379 423, 623 656. A regrettable review: Doob, , Mathematical Reviews, MR0026286 (10,133e). The discussion is suggestive throughout, rather than mathematical, and it is not always clear that the author's mathematical intentions are honorable.. Cover, T. Shannon's Contributions to Shannon Theory, AMS Notices, vol. 49, no. 1, p. 11, January 2002. Doob has recanted this remark many times, saying that it and his naming of super martingales (processes that go down instead of up) are his two big regrets.. 5/ 31/ 07 LDPC Codes 12. Finding Good Codes Ingredients of Shannon's proof: Random code Large block length Optimal decoding Problem Randomness + large block length + optimal decoding =.

6 COMPLEXITY! 5/ 31/ 07 LDPC Codes 13. State-of-the-Art Solution Long, structured, pseudorandom Codes Practical, near-optimal decoding algorithms Examples Turbo Codes (1993). Low- density parity - check (LDPC) Codes (1960, 1999). State-of-the-art Turbo Codes and LDPC Codes have brought Shannon limits to within reach on a wide range of channels. 5/ 31/ 07 LDPC Codes 14. Evolution of Coding Technology LDPC. Codes from Trellis and Turbo Coding, Schlegel and Perez, IEEE Press, 2004. 5/ 31/ 07 LDPC Codes 15. Linear Block Codes - Basics Parameters of binary linear block code C. k = number of information bits n = number of code bits R = k/n dmin = minimum distance There are many ways to describe C.

7 Codebook (list). parity - check matrix / generator matrix Graphical representation ( Tanner graph ). 5/ 31/ 07 LDPC Codes 16. Example: (7,4) Hamming Code (n,k). (n,k)==(7,4). (7,4),, RR==4/7. 4/7. ddmin =3. min = 3. single singleerror errorcorrecting correcting 5. double doubleerasure erasurecorrecting correcting Encoding Encodingrule: rule: 2 3. Insert 1. Insertdata databits bitsin in1,1,2,2,3,3, 7 6. Insert Insert parity . parity bits bitsin in5,5,6,6,77 4. to toensure ensureananeven evennumber number of of1's 1'sin ineach eachcircle circle 5/ 31/ 07 LDPC Codes 17. Example: (7,4) Hamming Code 2k=16 codewords Systematic encoder places input bits in positions 1, 2, 3, 4.

8 parity bits are in positions 5, 6, 7. 0000 000 1000 111. 0001 011 1001 100. 0010 110 1010 001. 0011 101 1011 010. 0100 101 1100 010. 0101 110 1101 001. 0110 011 1110 100. 0111 000 1111 111. 5/ 31/ 07 LDPC Codes 18. Hamming Code parity Checks 11 22 33 44 55 66 77. 5. 1 1 1 0 1 0 0. 2 3 1 0 1 1 0 1 0. 1. 7 6 1 1 0 1 0 0 1. 4. 5/ 31/ 07 LDPC Codes 19. Hamming Code: Matrix Perspective parity check matrix H c = [c1 , c2 , c3 , c4 , c5 , c6 , c7 ]. 1 1 1 0 1 0 0 0 . H = 1 0 1 1 0 1 0 H c = 0 . T. 1 1 0 1 0 0 1 0 . Generator matrix G. 1 0 0 0 1 1 1 u = [u1 , u 2 , u3 .u 4 ]. c = [c1 , c2 , c3 , c4 , c5 , c6 , c7 ].

9 0 1 0 0 1 0 1 . G= . 0 0 1 0 1 1 0 .. 0 0 0 1 0 1 1 . u G = c 5/ 31/ 07 LDPC Codes 20. parity - check Equations parity - check matrix implies system of linear equations. 1 1 1 0 1 0 0 c1 + c2 + c3 + c5 = 0. H = 1 0 1 1 0 1 0 c1 + c3 + c4 + c6 = 0. 1 1 0 1 0 0 1 c1 + c2 + c4 + c7 = 0. parity - check matrix is not unique. Any set of vectors that span the rowspace generated by H. can serve as the rows of a parity check matrix (including sets with more than 3 vectors). 5/ 31/ 07 LDPC Codes 21. Hamming Code: Tanner Graph Bi-partite graph representing parity - check equations c1. c2. c3. c1 +c2 +c3 +c5 =0.

10 C4. c1 +c3 +c4 +c6 =0. c5. c6. c1 +c2 +c4 +c7 =0. c7. 5/ 31/ 07 LDPC Codes 22. Tanner Graph Terminology variable nodes (bit, left) check nodes (constraint, right). The Thedegree degreeof ofaanode nodeisisthe thenumber number of ofedges edgesconnected connectedtotoit. it. 5/ 31/ 07 LDPC Codes 23. Low- density parity - check Codes Proposed by Gallager (1960). Sparseness of matrix and graph descriptions Number of 1's in H grows linearly with block length Number of edges in Tanner graph grows linearly with block length Randomness of construction in: Placement of 1's in H. Connectivity of variable and check nodes Iterative, message-passing decoder Simple local decoding at nodes Iterative exchange of information (message-passing).