0122229现代数字通信与编码理论 November 10.2011 XDU,Fall 2011 Lecture Notes 4.8 Low-Density Parity-Check Codes Low-density parity-check (LDPC)codes are a class of linear block codes with near capacity performance, which was invented by Gallager in the in his Ph.D.thesis and were rediscovered in late 1990's.They are constructed using sparse bipartite graph(hence the name low-density),and can be decoded iteratively based on sum-product algorithm. LDPC codes have proved capable of approaching the Shannon limit more closely than any other class of codes. Ever since thei rediscovery,desig construction,decoding.efficient encoding performance analysis,and applications of LDPC codes in digital communication and storage systems have become focal points of research. Note:Some of material presented in this section is based on Prof.Shu Lin's lecture notes and S.J.Johnson's notes. 4.8.1 Definitions and Basic Concepts Although LDPC codes can be generalized to nonbinary alphabets,we will consider only binary codes in this section for the sake of simplicity. A binary LDPC code is a special class of(n)linear block codes whose parity-check matrix H=[h]contains mostly 0's and relatively few I's;i.e.,H is sparse.This sparsity renders low complexity decoding and leads to simple implementations.In particular,an (n,d de)regular LDPC code is a binary linear block code of length n,whose parity-check matrix H contains exactly d I's in each column and d I's in each row.This means that every coded bit participates in exactly ns and that every such check equation involves exactlycoded bits.A formal definition is as follows Definition 4.8.1:A binary regular LDPC code is defined as the null space of a sparse parity-check matrix H over GF(2)with the following structural properties: 1)Each row has constant weightd 2)Each has constant weight 3)No two rows(or two columns)have more than one 1-component in common;and 4)Both de and d,are small compared to code length and the number of rows in H. The H with these properties will be said to be(dde)-regular,and the code generated by such H will be called a(d,de)-regular LDPC code. to as the row and column (RC)const The RC-constraint on the rows and columns of H ensures that nodor fewer columns of H can be added to zero.As a result,the minimum distance of the LDPC code given by the null space of H is at least d+1. Because both de and d,are small compared to code length and the number of rows in the matrix,H therefore has a low density of I's.In literature,the density r of the parity-check1 0122229 现代数字通信与编码理论 November 10, 2011 XDU, Fall 2011 Lecture Notes 4.8 Low-Density Parity-Check Codes Low-density parity-check (LDPC) codes are a class of linear block codes with near capacity performance, which was invented by Gallager in the early 1960’s in his Ph.D. thesis and were rediscovered in late 1990’s. They are constructed using sparse bipartite graph (hence the name low-density), and can be decoded iteratively based on sum-product algorithm. LDPC codes have proved capable of approaching the Shannon limit more closely than any other class of codes. Ever since their rediscovery, design, construction, decoding, efficient encoding, performance analysis, and applications of LDPC codes in digital communication and storage systems have become focal points of research. Note: Some of material presented in this section is based on Prof. Shu Lin’s lecture notes and S. J. Johnson’s notes. 4.8.1 Definitions and Basic Concepts Although LDPC codes can be generalized to nonbinary alphabets, we will consider only binary codes in this section for the sake of simplicity. A binary LDPC code is a special class of (n, k) linear block codes whose parity-check matrix [ ]ij H = h contains mostly 0’s and relatively few 1’s; i.e., H is sparse. This sparsity renders low complexity decoding and leads to simple implementations. In particular, an (n, dv, dc) regular LDPC code is a binary linear block code of length n, whose parity-check matrix H contains exactly dv 1’s in each column and dc 1’s in each row. This means that every coded bit participates in exactly dv parity-check equations and that every such check equation involves exactly dc coded bits. A formal definition is as follows. Definition 4.8.1: A binary regular LDPC code is defined as the null space of a sparse parity-check matrix H over GF(2) with the following structural properties: 1) Each row has constant weight dc ; 2) Each column has constant weight dv ; 3) No two rows (or two columns) have more than one 1-component in common; and 4) Both dc and dv are small compared to code length and the number of rows in H. The H with these properties will be said to be (dv, dc)-regular, and the code generated by such H will be called a (dv, dc)-regular LDPC code. Property 3) is referred to as the row and column (RC) constraint. The RC-constraint on the rows and columns of H ensures that no dv or fewer columns of H can be added to zero. As a result, the minimum distance of the LDPC code given by the null space of H is at least dv+1. Because both dc and dv are small compared to code length and the number of rows in the matrix, H therefore has a low density of 1’s. In literature, the density r of the parity-check