[attachment=8548]

ABSTRACT
Here a new rate-control scheme splitting is proposed to construct low-rate codes
from high rate codes. It splits rows of parity-check matrices of repeat accumulate type
(RA-Type) LDPC codes by adding new parity bit. Splitting does not introduce shorter
cycles and can increase the girth. When a high-degree check node is split into two
low-degree check nodes, the performance of low-rate codes can be improved. By using
splitting,we can explicitly construct RC B-LDPC code achieving code rates 1/3, 1/2,
2/3, and 4/5. RC B-LDPC code using splitting gives better performance and higher
throughput than other RC B-LDPC 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 dual-diagonal parity
structure are called repeat accumulate-type (RA-Type) LDPC codes. The dual diagonal
parity structure can allow many degree-2 parity nodes while keeping the stability
and enables the linear-time encoding. Many rate-control 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 rate-control scheme called splitting has been
introduced.
1.1 Overview of LDPC codes
Low-density parity-check (LDPC) codes have emerged as one of the top contenders
for near-channel 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.
Low-density parity-check (LDPC) codes are a class of linear block codes. The
name comes from the characteristic of their parity-check 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 state-of-theart
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 en-coder. 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 low-density parity-check 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 low-density 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 (v-nodes) and check nodes
(c-nodes).
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 4-1oops. In general a loop of length m is called an m-loop. 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 v-node and also for all the c-nodes.
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 semi-randomly 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 Repeat-accumulate code
In computer science, repeat-accumulate codes (RA codes) are a low complexity
class of error-correcting 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