Threshold Saturation for Spatially Coupled Turbo-like Codes over the Binary Erasure Channel

Saeedeh Moloudi, Michael Lentmaier, Alexandre Graell i Amat

Abstract

In this paper we prove threshold saturation for spatially coupled turbo codes (SC-TCs) and braided convolutional codes (BCCs) over the binary erasure channel. We introduce a compact graph representation for the ensembles of SC-TC and BCC codes which simplifies their description and the analysis of the message passing decoding. We demonstrate that by few assumptions in the ensembles of these codes, it is possible to rewrite their vector recursions in a form which places these ensembles under the category of scalar admissible systems. This allows us to define potential functions and prove threshold saturation using the proof technique introduced by Yedla et al..

Introduction

In coding theory, a fundamental performance gap exists between iterative Belief Propagation (BP) decoding and optimal Maximum A Posteriori (MAP) decoding. While BP is computationally efficient, its threshold (the maximum noise level for reliable communication) is typically lower than the MAP threshold. Spatially coupled codes, formed by linking small code blocks into a chain, have demonstrated the remarkable property of "threshold saturation," where the BP threshold improves to match the MAP threshold of the underlying uncoupled code. Although well-established for Low-Density Parity-Check (LDPC) codes, this phenomenon remained largely a numerical observation for "Turbo-like" codes. This work provides the first formal proof of threshold saturation for spatially coupled turbo-like codes over the Binary Erasure Channel (BEC).

Methods

The proof relies on three key technical innovations:

Compact Graph Representation

Traditional factor graphs for convolutional codes are often too complex for direct analysis of spatially coupled ensembles. The authors introduce a compact graph representation where entire trellises are treated as single factor nodes and groups of bits as single variable nodes. This abstraction facilitates the derivation of Density Evolution (DE) equations, which characterize the error-correction process.

Compact graph representations for various turbo-like code ensembles.

Scalar Admissible Systems

Decoding turbo-like codes generally involves vector recursions to track multiple probability types. By assuming identical component encoders, the authors demonstrate that these complex multi-variable systems can be simplified into scalar recursions. This reduction allows the ensembles to be classified as "scalar admissible systems," making them amenable to established proof techniques.

Potential Functions

The authors apply a technique using potential functions to analyze decoding stability. In this framework, the success of the decoder is tied to the existence of a unique minimum at zero error in the system's potential function.

Results

The primary contribution is the formal proof that for Spatially Coupled Parallel Concatenated Codes (SC-PCCs), Serially Concatenated Codes (SC-SCCs), and Braided Convolutional Codes (BCCs), the BP threshold saturates to the MAP threshold.

A quantitative example for a rate-1/3 Parallel Concatenated Code illustrates this effect. The standard BP threshold is $\epsilon_{BP} \approx 0.6428$. Through spatial coupling, the threshold saturates to $\epsilon_{MAP} \approx 0.6554$. Figure 5 visualizes the potential function $U(x; \epsilon)$ for various erasure probabilities $\epsilon$. The transition in the shape of the potential function clearly indicates the threshold saturation point.

Potential function $U(x; \epsilon)$ for a rate-1/3 SC-PCC at various erasure probabilities.

The study also confirms that fixed points of the decoding recursion correspond to stationary points of the derived potential functions, providing a geometric interpretation of the decoding process.

Conclusion

This work establishes that threshold saturation is a fundamental property of spatial coupling applicable to a wide range of concatenated code structures. Future research will aim to extend these proofs to non-identical component encoders, which currently require a more complex "coupled vector recursion" framework, and to more challenging channel models such as the Additive White Gaussian Noise (AWGN) channel.

Summary updated

Abstract

In this paper we prove threshold saturation for spatially coupled turbo codes (SC-TCs) and braided convolutional codes (BCCs) over the binary erasure channel. We introduce a compact graph representation for the ensembles of SC-TC and BCC codes which simplifies their description and the analysis of the message passing decoding. We demonstrate that by few assumptions in the ensembles of these codes, it is possible to rewrite their vector recursions in a form which places these ensembles under the category of scalar admissible systems. This allows us to define potential functions and prove threshold saturation using the proof technique introduced by Yedla et al..
BibTeX
@inproceedings{moloudi2015threshold,
  author = {Saeedeh Moloudi and Michael Lentmaier and Alexandre Graell i Amat},
  title = {{Threshold Saturation for Spatially Coupled Turbo-like Codes over the Binary Erasure Channel}},
  booktitle = {ITW Fall},
  year = {2015},
  doi = {10.1109/itwf.2015.7360750},
}
Figure