HartungGorre Verlag
Inh.: Dr.
Renate Gorre D78465
Konstanz Fon:
+49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartunggorre.de

S

Series in Signal and Information Processing, Vol. 11
edited by HansAndrea Loeliger
Pascal O. Vontobel
Algebraic Coding for Iterative Decoding
1. Auflage/1^{st}
edition 2003, XVI, 246 Seiten/pages,
€ 64,00.
ISBN 3896498657
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 summaryproduct 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 summaryproduct algorithm, namely the
sumproduct and the maxproduct algorithm. We also show how different
iteratively decodable channel codes fit very naturally into this picture.
For loopless factor graphs the summaryproduct 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 summaryproduct 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 suboptimal algorithm on a loopy factor
graph than to perform an optimal algorithm on a loopless 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 summaryproduct algorithm successfully, experimental
evidences seem to indicate that it is advisable that the factor graph looks
locally treelike, i.e. that there are no short cycles. This helps the messages
of the summaryproduct 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 lowdensity
paritycheck codes and turbo codes. Especially by using more complex subcodes than simple paritycheck 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 loopless 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
sumproduct update rule for an indicator function of a subcode,
namely the BCJR algorithm, the onesweep 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,
summaryproduct algorithm, sumproduct algorithm, maxproduct algorithm,
lowdensity paritycheck codes, turbo codes, algebraic code constructions.
Series / Reihe "Series
in Signal and Information Processing" im HartungGorre Verlag
Direkt bestellen
bei / to order directly from
HartungGorre Verlag / D78465
Konstanz / Germany