Hartung-Gorre Verlag

Inh.: Dr. Renate Gorre

D-78465 Konstanz

Fon: +49 (0)7533 97227

Fax: +49 (0)7533 97228



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

Telefon: +49 (0) 7533 97227  Telefax: +49 (0) 7533 97228
http://www.hartung-gorre.de   eMail: verlag@hartung-gorre.de