Hartung-Gorre Verlag
Inh.: Dr.
Renate Gorre D-78465
Konstanz Fon:
+49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartung-gorre.de
|
S
|
Series in Signal and Information Processing, Vol. 11
edited by Hans-Andrea Loeliger
Pascal O. Vontobel
Algebraic Coding for Iterative Decoding
1. Auflage/1st
edition 2003, XVI, 246 Seiten/pages,
€ 64,00.
ISBN 3-89649-865-7
Since the publication of
Shannon's 1948 paper ”A Mathematical Theory of Communication” the quest has
been on to find practical channel coding schemes that live up to the promises
given by Shannon. Traditionally, coding theory focused on finding codes with
large minimum distance and then to find an efficient decoding algorithm for
such a code. In the realm of iterative decoding the picture is reversed: given
an iterative decoding algorithm, one has to look out for codes that are
suitable for such an algorithm.
To understand iterative decoding algorithms, it is advantageous to have a basic
knowledge of factor graphs and the summary-product algorithm. Therefore, in a
first step we show how the detection problems in a data transmission system can
be modeled very naturally by factor graphs and solved with the help of the most
popular instances of the generic summary-product algorithm, namely the
sum-product and the max-product algorithm. We also show how different
iteratively decodable channel codes fit very naturally into this picture.
For loop-less factor graphs the summary-product algorithm gives back the
desired results; for loopy factor graphs the results are only approximations to
the desired ones. As we do not want that the summary-product algorithm becomes
prohibitively computationally intense, we have to bound
the local state space sizes. Under these circumstances, it seems favorable in
our applications at hand to perform a sub-optimal algorithm on a loopy factor
graph than to perform an optimal algorithm on a loop-less factor graph. One
reason for this phenomenon lies in the fact that under the above restrictions
much stronger codes can be achieved when allowing factor graphs with cycles
than without cycles.
In order to apply the summary-product algorithm successfully, experimental
evidences seem to indicate that it is advisable that the factor graph looks
locally tree-like, i.e. that there are no short cycles. This helps the messages
of the summary-product algorithm to be as independent as possible. To be able
to construct factor graphs of codes having these desirable properties, our next
step is therefore to consider constructions of graphs having large girth, i.e.
graphs whose length of the shortest cycle is large. We then unify different
constructions of graphs that have a large girth and we propose some extensions.
Finally, we come to the heart of our thesis, namely the algebraic construction
of codes suitable for iterative decoding. Based on graphs with large girth, we
propose various algebraic constructions of regular and irregular low-density
parity-check codes and turbo codes. Especially by using more complex subcodes than simple parity-check subcodes
and by using bit nodes of different degrees, one can obtain a rich class of
codes.
Apart from this main line, we treat several topics that are still within the
subject at hand. Namely, we discuss why codes which have a loop-less Tanner graph representation cannot be asymptotically good;
we give a shorter and more intuitive proof of this fact than available in the
literature. We unify different algorithms that can be used to perform the
sum-product update rule for an indicator function of a subcode,
namely the BCJR algorithm, the one-sweep algorithm, and decoding on the dual
code. Finally, we propose some variations of a lower bound first given by
Tanner on the minimum distance of codes.
Keywords:Digital data transmission, channel coding, iterative
decoding, factor graphs, graphs with large girth, finite geometries,
summary-product algorithm, sum-product algorithm, max-product algorithm,
low-density parity-check codes, turbo codes, algebraic code constructions.
Series / Reihe "Series
in Signal and Information Processing" im Hartung-Gorre Verlag
Direkt bestellen
bei / to order directly from
Hartung-Gorre Verlag / D-78465
Konstanz / Germany