IEEE Transactions on Information Theory

Turbo Codes in Binary Erasure Channel

Jeong W. Lee, Rudiger L. Urbanke, Richard E. Blahut

Published Mar 27, 2008• 7 citations

Abstract

In this correspondence, the stopping set of turbo codes with iterative decoding in the binary erasure channel is defined. Block and bit erasure probabilities of turbo codes are studied by using the stopping set analysis. It is found that block and bit erasure probabilities of turbo codes with iterative decoding are higher than those with maximum-likelihood decoding, where the differences are negligible in the error floor region. It is shown that in the error floor region, block and bit erasure probabilities of turbo codes with iterative decoding are dominated by small stopping sets and are asymptotically dominated by low weight codewords.

DOI: 10.1109/tit.2008.917723

Related papers

Turbo Decoding on the Binary Erasure Channel: Finite-Length Analysis and Turbo Stopping Sets

Eirik Rosnes, Øyvind Ytrehus

This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms ofstopping sets. We describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of stopping sets to turbo decoding and state an exact condition for decoding failure. Apply turbo decoding until the transmitted codeword has been recovered, or the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum-sizeturbo stopping setwhich is also a subset of the set of erased positions. Furthermore, we present some improvements of the basic turbo decoding algorithm on the BEC. The proposed improved turbo decoding algorithm has substantially better error performance as illustrated by the given simulation results. Finally, we give an expression for the turbo stopping set size enumerating function under the uniform interleaver assumption, and an efficient enumeration algorithm of small-size turbo stopping sets for a particular interleaver. The solution is based on the algorithm proposed by Garelloet al.in 2001 to compute an exhaustive list of all low-weight codewords in a turbo code.

arXiv:cs/0602072IEEE Transactions on Information TheoryNov 1, 200727 citations

Finite-length analysis of turbo decoding on the binary erasure channel

Eirik Rosnes, Øyvind Ytrehus

This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation (BP) decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms of stopping sets. In the first part we describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of stopping sets to turbo decoding and state an exact condition for decoding failure. Apply turbo decoding until the transmitted codeword has been recovered, or until the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum size turbo stopping set which is also a subset of the set of erased positions. In the second part we present some improvements of the basic turbo decoding algorithm on the BEC. The proposed improved turbo decoding algorithm has substantially better error performance as illustrated by the given simulation results

IEEE International Symposium on Information Theory (ISIT)Jan 1, 20054 citations

On Decoding Failure Probabilities for Linear Block Codes on the Binary Erasure Channel

Jos H. Weber, Khaled Abdel-Ghaffar

It has been claimed that the performance of a linear block code under iterative decoding on the binary erasure channel is determined by the stopping distance, i.e., the size of the smallest non-empty stopping set in the associated Tanner graph. Indeed, this is true from the perspective of code word retrieval. However, we show that with respect to the retrieval of just the information bits within the code word, the stopping distance may not be the main performance indicator since the smallest non-empty stopping sets might not hit the information set. We present expressions for decoding failure probabilities for code/information words/bits under optimal or iterative decoding and demonstrate the importance of the choice of the set of bits carrying the information for a fixed code with a fixed decoder

IEEE Information Theory Workshop (ITW)Oct 1, 20063 citations

Ensemble Decoding Thresholds for LDPC and Turbo Codes

W.E. Ryan, Shu Wen Lin

The previous chapter examined code properties responsible for the floor region (high-SNR region) of LDPC and turbo codes. Specifically, the emphasis was on the computation of various weight enumerators for LDPC and turbo code ensembles because a poor weight spectrum leads to poor performance in a code's floor region both for iterative decoders and for maximum-likelihood decoders. That chapter also introduced ensemble enumerators for trapping sets and stopping sets, both of which can lead to poor floor performance in iterative decoders. In this chapter we examine the iterative decoding performance of LDPC and turbo code ensembles in the complementary low-SNR region, the “waterfall” region. We show that the iterative decoding of long LDPC and turbo codes displays a threshold effect in which communication is reliable beyond this threshold and unreliable below it. The threshold is a function of code ensemble properties and the tools introduced in this chapter allow the designer to predict the decoding threshold and its gap from Shannon's limit. The ensemble properties for LDPC codes are the degree distributions which are typically the design targets for the code-design techniques presented in subsequent chapters. The ensemble properties for turbo codes are the selected constituent codes. Our development borrows heavily from the references listed at the end of the chapter and our focus is on the binary-input AWGN channel. The references and the problems consider other channels. Density Evolution for Regular LDPC Codes We first summarize the main results of [1] with regard to iterative (message passing) decoding of long, regular LDPC codes.

Cambridge University Press eBooksSep 17, 20090 citations

Stopping Set Analysis of Iterative Row-Column Decoding of Product Codes

Eirik Rosnes

In this paper, we introduce stopping sets for iterative row-column decoding of product codes using optimal constituent decoders. When transmitting over the binary erasure channel (BEC), iterative row-column decoding of product codes using optimal constituent decoders will either be successful, or stop in the unique maximum-size stopping set that is contained in the (initial) set of erased positions. Let Cpdenote the product code of two binary linear codes Ccand Crof minimum distances dc and drand second generalized Hamming weights d2(Cc) and d2(Cr), respectively. We show that the size sminof the smallest noncode- word stopping set is at least mm(drd2(Cc),dcd2(Cr)) > drdc, where the inequality follows from the Griesmer bound. If there are no codewords in Cpwith support set S, where S is a stopping set, then S is said to be a noncodeword stopping set. An immediate consequence is that the erasure probability after iterative row-column decoding using optimal constituent decoders of (finite-length) product codes on the BEC, approaches the erasure probability after maximum-likelihood decoding as the channel erasure probability decreases. We also give an explicit formula for the number of noncodeword stopping sets of size smin, which depends only on the first nonzero coefficient of the constituent (row and column) first and second support weight enumerators, for the case when d2(Cr)rand d2(Cc)c. Finally, as an example, we apply the derived results to the product of two (extended) Hamming codes and two Golay codes.

IEEE Transactions on Information TheoryMar 27, 200810 citations

A probabilistic algorithm for finding the minimum-size stopping sets of LDPC codes

Masanori Hirotomo, Yoshiho Konishi, Masakatu Morii

On the binary erasure channel, the performance of LDPC codes decoded by iterative algorithms is dominated by small-size stopping sets, especially minimal stopping sets. In this paper, we propose a probabilistic algorithm for computing the minimum size of stopping sets of LDPC codes. In this algorithm, we generate efficiently small-size stopping sets by using the relation between small-size stopping sets and low-weight codewords. In numerical experiments, we could compute the minimum size of stopping sets of LDPC codes of length about 500, 1000 and 5000 with high reliability, and could find smaller stopping sets than that found by conventional methods.

IEEE Information Theory Workshop (ITW)May 1, 20087 citations