Design of RateCompatible RAType LowDensity ParityCheck Codes Using Splitting
summer project pal Active In SP Posts: 308 Joined: Jan 2011 
29012011, 07:28 PM
Design of RateCompatible RAType LowDensity ParityCheck Codes Using Splitting
SEMINAR REPORT Submitted by Bibina V.C. First Semester M.Tech, Signal Processing DEPARTMENT OF ELECTRONICS AND COMMUNICATION ENGINEERING COLLEGE OF ENGINEERING TRIVANDRUM 2010 Design of RateCompatible RAType LowDensity parity check codes using splitting.pdf (Size: 468.04 KB / Downloads: 53) ABSTRACT Here a new ratecontrol scheme splitting is proposed to construct lowrate codes from high rate codes. It splits rows of paritycheck matrices of repeat accumulate type (RAType) LDPC codes by adding new parity bit. Splitting does not introduce shorter cycles and can increase the girth. When a highdegree check node is split into two lowdegree check nodes, the performance of lowrate codes can be improved. By using splitting,we can explicitly construct RC BLDPC code achieving code rates 1/3, 1/2, 2/3, and 4/5. RC BLDPC code using splitting gives better performance and higher throughput than other RC BLDPC codes. CHAPTER 1 INTRODUCTION It is known that the encoding complexity of LDPC codes is quadratic in the block length resulting in slow encoding. Fast encodable LDPC codes with dualdiagonal parity structure are called repeat accumulatetype (RAType) LDPC codes. The dual diagonal parity structure can allow many degree2 parity nodes while keeping the stability and enables the lineartime encoding. Many ratecontrol schemes such as data puncturing (shortening), puncturing and extending have been proposed to construct ratecompatible (RC) LDPC codes. These schemes have several problems such as slow decoding convergence speed, high decoding complexity, and performance degradation. To overcome such shortcomings, a new ratecontrol scheme called splitting has been introduced. 1.1 Overview of LDPC codes Lowdensity paritycheck (LDPC) codes have emerged as one of the top contenders for nearchannel capacity error correction. Recently, more and more sophisticated classes of LDPC codes have been forwarded by members of the research community, each offering advances in one area or another. Lowdensity paritycheck (LDPC) codes are a class of linear block codes. The name comes from the characteristic of their paritycheck matrix which contains only a few 1s in comparison to the amount of 0s. Their main advantage is that they provide a performance which is very close to the capacity for a lot of different channels and linear time complex algorithms for decoding. Furthermore are they suited for implementations that make heavy use of parallelism.They have been shown to offer  over a variety of channels  performance comparable to or better than that offered by other stateoftheart codes such as turbo codes. They were first introduced by Robert G Gallager in his PhD thesis in 1960 along with an elegant iterative decoding scheme whose complexity grows only linearly with the code block length. Despite of their promises, LDPC codes were largely forgotten for several decades, primarily because of the computational effort in implementing their coder and encoder. In 1993 Berrou introduced turbo codes. Parallel to the researches on turbo codes and influenced by the focus on turbo codes in 1996 Mac Kay and Neal rediscovered the long forgotten LDPC codes. Today the value of LDPC codes is widely recognized and their remarkable capacity approaching performance ensures that they will not be forgotten again. 1.1.1 Representations for LDPC codes Basically there are two different possibilities to represent LDPC codes. Like all linear block codes they can be described via matrices.The second possibility is a graphical representation Matrix Representation Lets look at an example for a lowdensity paritycheck matrix first. The matrix defined in equation (1.1) is a parity check matrix with dimension nm for a (8, 4) code. H = 2 6666664 0 1 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 1 1 0 0 1 1 0 1 0 3 7777775( 1.1) We can now define two numbers describing these matrix. wr for the number of 1s in each row and wc for the columns. For a matrix to be called lowdensity the two conditions wc << n and wr << m must be satisfied. Graphical Representation Tanner introduced an effective graphical representation for LDPC codes.Tanner graphs are bipartite graphs. That means that the nodes of the graph are separated into two distinctive sets and edges are only connecting nodes of two different types. The two types of nodes in a Tanner graph are called variable nodes (vnodes) and check nodes (cnodes). Figure 1.1 is an example for such a Tanner graph and represents the same code as the matrix in 1.1. It consists of m check nodes (the number of parity bits) and n 2 Figure 1.1: Tanner graph variable nodes (the number of bits in a codeword). Check node ci is connected to variable node vj if the element hij of H is a 1. In the bipartite graph representing a LDPC code, a loop (or cycle) is a closed path with no repeated nodes, and must therefore be of even length. There is at most one edge between any two nodes, and so the shortest length a loop can have is 4. Such loops are referred to as 41oops. In general a loop of length m is called an mloop. The girth of the graph is defined as the length of the shortest loop. A Stopping set S is a subset of V, the set of variable nodes, such that all neighbors of S are connected to S at least twice. The stopping number of a code is the size of its smallest stopping set, and the stopping number lower bounds the minimum distance of the code. The stopping number of a code can be increased by increasing its girth, and hence codes with larger girth have lower error floors. 1.1.2 Regular and irregular LDPC codes A LDPC code is called regular if wc is constant for every column and wr = wcn=m) is also constant for every row. The example matrix from equation (1.1) is regular with wc = 2 and wr = 4. It is also possible to see the regularity of this code while looking at the graphical representation. There is the same number of incoming edges for every vnode and also for all the cnodes. If H is low density but the numbers of 1s in each row or column are not constant the code is called a irregular LDPC code. Richardson and Luby defined ensembles of irregular LDPC codes parameterized by the degree polynomials (x) and (x), defined 3 as s = x + c (1.2) Irregular LDPC codes in general perform better than regular LDPC codes. In fact, it is an irregular LDPC code with block length 107 that currently holds the distinction of being the world’s best performing rate 1/2 code, outperforming all other known codes, and falling only 0.0045 dB short of the Shannon limit for the AWGN channel. 1.1.3 Constructing LDPC codes Several different algorithms exists to construct suitable LDPC codes. Gallager himself introduced one. Furthermore MacKay proposed one to semirandomly generate sparse parity check matrices.In fact, completely randomly chosen codes are good with a high probability. The problem that will arise, is that the encoding complexity of such codes is usually rather high. 1.2 Repeataccumulate code In computer science, repeataccumulate codes (RA codes) are a low complexity class of errorcorrecting codes. They were devised so that their ensemble weight distributions are easy to derive. RA codes were introduced by Divsalar. In an RA code, an information block of length N is repeated q times, scrambled by an interleaver of size qN, and then encoded by a rate 1 accumulator. The accumulator can be viewed as a truncated rate 1 recursive convolutional encoder with transfer function 1 / (1 + D), but Divsalar prefer to think of it as a block code whose input block and output block are related by the formula x1 = z1 and xi = xi 


