INTRODUCTION
TRANSMITTING information reliably over a noisy communication
channel is a very general problem that has
attracted significant interest. Shannon, in 1948, in his seminal
paper, ’A Mathematical Theory of Communication’, formalized
the notions of information, noisy channel and other
information theoretic concepts[1]. A communication channel
can be modeled as a triple with input and output alphabets
and probabilities of transition from a symbol in the input
alphabet to a symbol in the output alphabet. In other words,
this distribution specifies the probability of receiving an output
symbol given that an input symbol was transmitted. This type
of channel with a discrete set of input and output alphabets and
transition probabilities that only depend on the current input
symbol being sent is called a discrete memoryless channel.
Since channel noise is probabilistic, in principle noise may
corrupt the input so severely that recovery of information
becomes impossible. Adding redundancy to the transmitted
information will increase the probability of successfully recovering
the message sent. However, we would expect that to
make the probability of errors go to zero, an infinite amount
of redundancy must be added. Shannon proved that ‘this is by
no means true’[1].
OVERVIEW
The question that motivated this paper is: “What is it about
LDPC codes that makes it so powerful?” We will try to answer
this question by outlining the general theory of LDPC codes
with numerous examples of LDPC codes in action. In section
III we define LDPC codes and introduce the notion of regular
vs irregular LDPC codes and the design rate of LDPC codes.
Section IV, the major section of this paper, discusses the
decoding of LDPC codes. We discuss a variety of decoders
that fall under the class of message passing decoders and are
almost exclusively the decoder of choice for LDPC codes. We
demonstrate the operation of each decoder via examples. In
section V we demonstrate the technique of density evolution
used for asymptotic analysis of its performance. For this
analysis it is extremely convenient to consider an ensemble
of LDPC codes instead of just a single one. Section VI is
on irregular LDPC codes and the generalization of density
evolution to this case. Also, in this section we outline how it
is possible to achieve capacity for the Binary Erasure Channel
using irregular LDPC codes. Section VII is a compilation of
what I think are the major gaps in our understanding of LDPC
codes. Finally section VIII concludes the paper.
THE PERFORMANCE OF LDPC CODES
There is no known general way to theoretically analyze
the performance of specific LDPC codes under message passing
decoders. Experimental simulation is the only recourse
available. Nonetheless we would like to understand the performance
of LDPC codes to be able to come up with criteria
for designing better ones. Therefore, we consider an ensemble
of LDPC codes and analyze the expected behavior of the
ensemble. This behavior of individual codes turn out to be
sharply concentrated around the ensemble average and hence
picking a code at random from the ensemble is very likely
to result in performance close to the theoretically calculated
expected performance of the ensemble. Furthermore, message
passing decoders are not amenable to analysis when the graph
of the code has cycles
Shannon’s Theorem
The year 1948 marks the birth of information theory. In that year, Claude E. Shannon published his
epoch making paper [1] on the limits of reliable transmission of data over unreliable channels and
methods on how to achieve these limits. Among other things, this paper formalized the concept of
information, and established bounds for the maximum amount of information that can be transmitted
over unreliable channels.
A communication channel is usually defined as a triple consisting of an input alphabet, an output
alphabet, and for each pair (i, o) of input and output elements a transition probability p(i, o).
Semantically, the transition probability is the probability that the symbol o is received given that i
was transmitted over the channel.
reference;
http://documents.tips/documents/anchorin...-2012.html