Finite length weight enumerator analysis of braided convolutional codes

Saeedeh Moloudi, Michael Lentmaier, Alexandre Graell i Amat

Here is a summary of the paper tailored for a technically literate audience:

TL;DR

Braided Convolutional Codes (BCCs) are a promising class of spatially coupled turbo-like codes with excellent theoretical performance, but how do they fare at practical, finite block lengths? This paper derives the weight enumerator function to analyze their finite-length performance, revealing that while uncoupled BCCs suffer from high error floors due to a few "bad" permutations, removing these (expurgation) or applying spatial coupling drastically improves performance. The authors also mathematically prove that spatial coupling strictly maintains or improves the minimum distance of the code.

What Problem Does This Paper Address?

In coding theory, spatially coupled codes (like SC-LDPC codes) are highly regarded because they exhibit "threshold saturation"—meaning practical Belief Propagation (BP) decoders can achieve the theoretical limits of optimal Maximum A-Posteriori (MAP) decoders. Braided Convolutional Codes (BCCs) are a turbo-like equivalent to these codes and show excellent asymptotic (infinite-length) performance.

However, real-world communication systems require finite block lengths. The authors noticed that in the finite block-length regime, uncoupled BCC ensembles exhibit unexpectedly high error floors. This paper investigates why this happens by analyzing the distance properties of the codes, and explores how techniques like expurgation (removing bad codes) and spatial coupling can mitigate these error floors.

Methods

To analyze the finite-length performance of BCCs, the authors employ several analytical and mathematical techniques:

  • Weight Enumerator Functions (WEF): They derive the Input-Parity WEF for the component rate-2/3 convolutional encoders using transition matrices. This allows them to compute the average WEF for the entire uncoupled BCC ensemble over all possible uniform random permutations.
  • Union Bounds: Using the WEF, they calculate the truncated union bounds for Bit Error Rate (BER) and Frame Error Rate (FER) over an Additive White Gaussian Noise (AWGN) channel.
  • Expurgation: Because the standard union bound predicted a terrible error floor, the authors computed an "expurgated" union bound. This involves mathematically excluding a small fraction of codes (permutations) with poor distance properties to reveal the true potential of the broader ensemble.
  • Mathematical Proofs: They formulate a theorem to connect the uncoupled and coupled ensembles, proving that the codeword weights of a coupled BCC are lower-bounded by those of an uncoupled BCC.

Datasets

Not discussed in the paper in the traditional machine learning sense. The authors evaluate their theoretical bounds using simulated data transmitted over an Additive White Gaussian Noise (AWGN) channel, testing specific permutation sizes (e.g., $N = 128, 256, 512, 1000, 5000$).

Key Insights and Ideas

  • Bad apples spoil the bunch: The unexpectedly high error floor of the uncoupled BCC ensemble isn't an inherent flaw of the code structure itself. Instead, it is heavily skewed by a tiny fraction of permutations that result in poor distance properties.
  • Linear growth of minimum distance: By excluding just 5% of the worst codes (expurgation), the minimum distance of the remaining BCC ensemble grows linearly with the permutation size. This indicates that a randomly chosen, fixed permutation is highly likely to perform very well.
  • Coupling is strictly beneficial for distance: The authors mathematically prove that the spatial coupling process cannot decrease the Hamming weight of a valid code sequence. Therefore, the minimum distance of a coupled BCC is guaranteed to be at least as large as its uncoupled counterpart, meaning the low error floors estimated for the expurgated uncoupled codes also apply to coupled codes.

Key Results

  • Expurgation works: For uncoupled BCCs, using fixed permutations instead of uniformly random ones drops the error floor significantly. For example, at $E_b/N_0 = 2.5$ dB, the Frame Error Rate improves from $9.5 \times 10^{-5}$ to $6.8 \times 10^{-7}$.
  • Coupling dominates: Coupled Type-II BCCs drastically outperform uncoupled BCCs. For a permutation size of $N=5000$, spatial coupling improves performance by almost $1.5$ dB in the waterfall region, with error floors so low they cannot be observed in simulation.
  • Latency efficiency: Even when constraining the coupled code to have the same decoding latency as the uncoupled code (comparing $N=1000$ coupled vs. $N=5000$ uncoupled), the coupled version still yields significantly better performance.

Limitations and Future Work

  • Decoder Assumptions: The theoretical bounds derived in this paper assume an optimal Maximum Likelihood (ML) decoder.
  • Practical Realities: In practice, these codes are decoded using Belief Propagation (BP) decoders. For BP decoders, the error floor is often dictated by "absorbing sets" (or trapping sets) rather than strictly the minimum distance of the code.
  • Future Work: The authors explicitly note that future research should focus on analyzing the absorbing sets of BCCs to better predict and optimize practical BP decoder performance.

Summary updated

Abstract

Braided convolutional codes (BCCs) are a class of spatially coupled turbo-like codes (SC-TCs) with excellent belief propagation (BP) thresholds. In this paper we analyze the performance of BCCs in the finite block-length regime. We derive the average weight enumerator function (WEF) and compute the union bound on the performance for the uncoupled BCC ensemble. Our results suggest that the union bound is affected by poor distance properties of a small fraction of codes. By computing the union bound for the expurgated ensemble, we show that the floor improves substantially and very low error rates can be achieved for moderate permutation sizes. Based on the WEF, we also obtain a bound on the minimum distance which indicates that it grows linearly with the permutation size. Finally, we show that the estimated error floor for the uncoupled BCC ensemble is also valid for the coupled ensemble by proving that the minimum distance of the coupled ensemble is lower bounded by the minimum distance of the uncoupled ensemble.
BibTeX
@inproceedings{moloudi2016finite,
  author = {Saeedeh Moloudi and Michael Lentmaier and Alexandre Graell i Amat},
  title = {{Finite length weight enumerator analysis of braided convolutional codes}},
  booktitle = {ISITA},
  year = {2016},
  url = {https://openreview.net/forum?id=C_6CiwzZLCT},
}

Loading related content...

Figure