Thorsten Hehn

Optimized Belief-Propagation Decoding for Low-Delay Applications in Digital Communications

Band 25, Erlanger Berichte aus Informations- und Kommunikationstechnik, Herausgeber: A. Kaup, W. Koch, J. Huber. Shaker Verlag, Aachen, 2009.


All modern communications systems apply channel coding schemes in order to guarantee the quality of service expected by the user. It is the aim of coding theorists to design schemes with high decoding performance, low-complexity decoder implementations, and a low data delay. Since 1993 it is known that iterative decoding of channel codes is one way to obtain good performance results with realizable decoders. Current research activities focus mainly on the class of low-density parity-check codes and the iterative belief-propagation decoder, usually applied to decode these codes. It was shown that near-optimum transmission is possible using low-density parity-check codes of very long length and belief-propagation decoding. However, long block codes impose a high delay on the transmitted data stream and ask for more decoding complexity. This is also an issue for the low-density parity-check codes used in digital communication standards.

In this thesis, we investigate how a good decoding performance can be obtained by codes of short to moderate delay which are decoded by an iterative decoder. As a first step, channel coding schemes used for signaling over the binary erasure channel are considered. It was shown recently that the decoding performance of short algebraic codes, decoded by a belief-propagation decoder, can be improved significantly if the iterative decoder is provided with a redundant code description.

We introduce a novel decoding method for this type of channel. This approach creates the required redundancy on request and outperforms the schemes currently known in literature. Furthermore, we deduct by theoretical considerations that a certain kind of code description is most suitable for decoding these codes in an iterative manner. With this, a method to improve the decoding performance on the binary erasure channel for given delay is found. However, algebraic codes are required to apply the method.

A second step transfers the results for the binary erasure channel to a channel model which distorts the transmitted data with additive white Gaussian noise. In this case, the received data allows to calculate reliability values for each position in a codeword. Consequently, more sophisticated iterative decoders can be applied. However, these schemes are not optimal, what is due to the feedback of non-independent and possibly distorted data within this process. This poses a challenge for the use of redundant code descriptions, as the redundancy intensifies the feedback process. Hence, the straightforward application of redundant code descriptions leads to impaired performance results when compared to usual iterative decoding. The multiple-bases belief-propagation approach, to be introduced in this thesis, mitigates this problem, as it partitions a redundant code description to a multitude of belief-propagation decoders in such a way that each decoder observes no or only little redundancy. This approach, together with the ability to merge the results of the different decoders, allows to use the redundant code description efficiently and to obtain performance improvements. Several variations of this approach are introduced and their advantages and disadvantages are shown using algebraic codes of short length. Subsequently, the field of application is extended to codes from the IEEE 802.16e WiMAX standard, as well as codes generated by the progressive edge-growth algorithm. Especially the latter codes are of interest, as they currently provide the best performance on an iterative decoder when rate and length of the code are given. It is a remarkable result that the performance of these codes can be improved further by the proposed scheme. Concluding, a way is found to improve the decoding performance at a given delay when transmitting over the additive white Gaussian noise channel.

Currently, the codes optimized by the progressive edge-growth algorithm considered in this work show a gap of at most 0.50 dB to the Gallager bound, a well-known existence bound from the field of information theory. Included in this result is a code-length dependent gain of 0.08 dB to 0.57 dB which is obtained by the multiple-bases belief-propagation approach.

As a third step, we assess our results in a more general manner and compare them to further schemes from channel coding. We introduce the structural delay which is an indicator of the delay solely imposed by the channel coding scheme. The structural delay allows to compare the proposed approach to schemes which are not block-oriented, such as convolutional codes, while keeping the focus on both the decoding performance and the imposed data latency. As convolutional codes are known to yield good performance results at low data latency, it is of great interest to relate them to the modern low-density parity-check codes using the introduced decoding approaches. A general recommendation in favor of one class of codes cannot be given, but application-dependent recommendations can be made. If a very short delay is targeted, convolutional codes are clearly ahead of their block-oriented counterpart. However, starting from a moderate delay, block codes using the proposed scheme significantly outperform convolutional codes in terms of decoding performance. As a final step, it is shown that the structural delay is a valid measure for the overall delay which includes the latency introduced by limited computational power.