PaperlayerView exact revision on arXiv

Source-linked AI summary

Windowed Decoding of Protograph-based LDPC Convolutional Codes over Erasure Channels

Aravind Iyengar, Marco Papaleo, Paul Siegel, Jack Wolf, Alessandro Vanelli-Coralli, Giovanni Corazza

arXiv:1010.4548v2cs.IT

TL;DR

The paper addresses how to obtain low-latency decoding for LDPC convolutional codes while retaining strong performance over erasure channels. It analyzes BP-based windowed decoding and designs protograph ensembles for memoryless and bursty erasures, finding near-capacity performance on memoryless channels but structural limits with channel memory.

  • Problem

    The paper asks how LDPC-CC ensembles can provide good performance-latency trade-offs under random and burst erasures while retaining the convolutional structure needed for windowed decoding.

  • Method

    The paper analyzes BP-based windowed decoding and derives protograph design rules targeting good thresholds and large stopping-set spans.

  • Results

    The designed ensembles achieve performance close to capacity on the memoryless erasure channel, while LDPC-CC structure bounds performance strictly away from optimal MDS performance on erasure channels with memory.

  • Takeaways & Limitations

    Windowed decoding offers latency flexibility and low complexity, but preserving convolutional structure creates a performance trade-off for channels with memory.

Abstract

from arXiv · show

We consider a windowed decoding scheme for LDPC convolutional codes that is based on the belief-propagation (BP) algorithm. We discuss the advantages of this decoding scheme and identify certain characteristics of LDPC convolutional code ensembles that exhibit good performance with the windowed decoder. We will consider the performance of these ensembles and codes over erasure channels with and without memory. We show that the structure of LDPC convolutional code ensembles is suitable to obtain performance close to the theoretical limits over the memoryless erasure channel, both for the BP decoder and windowed decoding. However, the same structure imposes limitations on the performance over erasure channels with memory.

I. INTRODUCTION

LDPC convolutional codes combine strong iterative-decoding performance with sparse, structured parity-check matrices, but full-codeword BP decoding can be impractical for long codes. The paper studies windowed decoding and protograph-based ensemble design to reduce latency while preserving performance over erasure channels.

  • LDPC-CC ensembles can approach capacity with BP decoding while achieving good performance using relatively simple regular ensembles.
  • Long LDPC-CCs can have impractical BP complexity, motivating windowed decoding to exploit parity-check sparsity.
  • The proposed study identifies LDPC-CC ensemble characteristics that balance decoding performance and latency over erasure channels, including long erasure bursts.
  • LDPC-CCs are constructed from block matrices with memory ms, and terminated codes have finite parity-check matrices.
  • Protographs generate larger Tanner graphs through copy-and-permute expansion while preserving controlled edge connections for code design.

B0 B1 B0 ... B1

The modified LDPC-CC construction broadens protograph design beyond the classical construction by decoupling memory from degree distribution and allowing nonidentical component matrices. This extra flexibility includes classical ensembles and can construct cases unavailable classically.

  • Classical construction: The classical construction cannot realize every (J, K) regular LDPC-CC ensemble, including cases where relatively prime J and K force zero memory.Edge spreading was proposed to address this limitation.
  • Modified construction: The modified construction makes the LDPC-CC memory independent of its degree distribution and permits nonidentical component matrices with parallel edges.The component matrices retain size J′ × K′.
  • Example: For J = 3 and K = 4, the modified construction permits m_s = 1 even though the classical construction is not possible.This provides a concrete example of the modified construction’s broader applicability.
  • Edge spreading: Edge spreading distributes protograph edges across component matrices to obtain regular LDPC-CC ensembles with memory m_s = 1.The passage describes this as a technique related to the modified construction.
  • Design flexibility: The classical ensemble family is contained within the modified family, giving the modified construction more degrees of freedom for protograph design.Thus, the best classical ensemble is included among the ensembles allowed by the modified construction.

C. Polynomial representation of LDPC-CC ensembles

The polynomial representation specifies terminated protograph-based LDPC-CC ensembles through column polynomials and provides ordering and boundary operations for analyzing their structure. It also supports the regular-ensemble notation used later.

  • Polynomial representation: An LDPC-CC ensemble can be specified by L and K′ column polynomials whose coefficients encode the entries of the component-matrix stack.The lth column of the terminated base matrix corresponds to a shifted polynomial x^(J′i)p_j(x).
  • Notation: The polynomial representation makes column indices and column polynomials interchangeable for describing the terminated protograph.This notation also treats collections of corresponding columns as polynomial summations.
  • Modulo polynomials: Modulo polynomials collect coefficients whose exponents have the same residue modulo J′, producing reduced-degree polynomials for structural analysis.The paper denotes the resulting sets by P_l.
  • Example: For (J, 2J) codes, each of the two protograph columns is represented by a polynomial of degree at most m_s, with shifts identifying columns across time.The first and second columns use p_1(x) and p_2(x), respectively.
  • Polynomial ordering: The partial ordering a(x) ⪯ b(x) requires matching minimum and maximum degrees while comparing coefficients componentwise.This ordering is defined for polynomials with non-negative integer coefficients.
  • Boundary polynomial: The boundary polynomial β(a(x)) retains only the terms at the minimum and maximum exponents of a(x).When those exponents coincide, the boundary polynomial contains only that single term.

A. Belief-Propagation (BP)

BP decoding is impractical or too latent for some LDPC-CC settings because it requires the full codeword, whereas windowed decoding operates on sliding subgraphs and targeted symbols. Window size controls a performance–latency trade-off and can provide substantial latency reduction.

  • Belief-propagation limitations: BP decoding latency is Λ_BP = T_cw + T_dec because decoding starts only after the entire codeword is received.For non-terminated LDPC-CCs, a BP decoder cannot be employed.
  • Structural basis: The convolutional structure prevents sufficiently separated variables from sharing parity checks, enabling a sliding-window decoder and parallel message-passing regions.The same structure supports pipeline decoding across different Tanner-graph regions.
  • Windowed decoding: The windowed decoder applies BP within a subgraph containing W sets of J′ check nodes and the columns involved in those checks.The window contains WJ′M rows and up to (W + m_s)K′ columns in the parity-check matrix.
  • Decoding process: At each decoding instant, BP targets the first K′ symbols, then the window advances after at least a fraction 1 − δ is recovered or the iteration limit is reached.The process continues across decoding instants until the codeword is recovered.
  • Latency: The windowed-decoding latency for K′ targeted symbols is Λ_WD = T_W + T_dec(W), where reception and decoding times depend on the selected window.At most (W + m_s)K′ symbols are required to process the targeted symbols.
  • Latency reduction: w_min = 2m_s+1/L is an upper bound on the fraction of BP latency supported by the code-decoder system.For fixed finite W, the latency of the sequence of ensembles indexed by L vanishes as O(1/L).
  • Performance–latency trade-off: Increasing W generally improves decoding performance while increasing latency, allowing latency to be adjusted according to application requirements.The paper also considers adaptive schemes that increase or decrease W based on whether target erasure probabilities are achieved.
  • Channel and target: The memoryless-channel analysis uses a binary erasure channel parameterized by the channel erasure rate ε.The target erasure probability δ is a decoder parameter, and setting δ = 0 is not necessarily most efficient.

A. Asymptotic analysis

The asymptotic analysis characterizes BP and windowed-decoding thresholds for protograph-based LDPC convolutional ensembles, identifying structural choices that improve performance under latency constraints. It also shows that finite-length performance can diverge from asymptotic predictions, especially as windows shrink.

  • Threshold analysis: Protograph-based ensemble performance is evaluated through erasure-rate thresholds under infinite blocklength and infinite decoder iterations.For windowed decoding, success additionally depends on window size W and target erasure probability δ.
  • Finite-length implications: The asymptotic windowed analysis is not directly a finite-length latency model: shrinking the window reduces the subcode blocklength and is expected to increase the gap from asymptotic ensemble performance.In the infinite-blocklength limit, every window has infinite latency, but the analysis provides lower bounds on finite-length decoder failure probability.
  • Design rules: Avoiding degree-1 variable nodes within a window is recommended for Cm(J, K′J) ensembles because degree-1 nodes can force the windowed threshold to zero.The stated rule requires p(dj) ≥ 2 for all j, where dj is the minimum variable-node degree associated with the relevant polynomial.
  • Windowed-decoding performance: For W = 3, a modified protograph has threshold ε∗(B′, W = 3, δ = 0) ≈ 0.3331, reaching about 68.3% of the BP threshold with less than 10% of BP latency.The threshold improvement also occurs with an increased ensemble rate, with ms = 1 for the modified construction.
  • Design rules: Strong termination at the beginning of the code improves windowed performance, while stronger termination at the end can dominate BP performance and make larger windows less helpful.The analysis attributes BP gains to low-degree checks in the terminated portion and recommends keeping the beginning termination at least as strong as the ending termination.

B. Finite length performance evaluation

Finite-length evaluation compares SER and CER for BP and windowed decoding over the BEC, including a Singleton-bound reference. Code C2 outperforms C1 at small window sizes, while differences disappear at larger windows.

  • Finite-length iterative-decoding performance over the BEC depends on the number and size of stopping sets in the parity-check matrix.
  • The evaluation compares SER and CER for codes C1 and C2 from two defined ensembles, constructed using circulant expansions, PEG, and ACE techniques.
  • C2 outperforms C1 for small window sizes W = 3, 5, confirming the effectiveness of the proposed windowed-decoding design rules.
  • For W = 10, the two codes show no marked performance difference; circulant-permutation constructions outperform random-permutation constructions for M < 128, with the gap diminishing at larger M.
  • The CER results include the Singleton bound PSB as a reference for performance achievable by an idealized binary MDS code.The paper notes that such a binary code does not exist for all values of k and n.

V. ERASURE CHANNELS WITH MEMORY

The paper evaluates LDPC convolutional codes on a two-state Gilbert–Elliott erasure channel and explains why preserving convolutional structure limits the use of interleaving against correlated erasures.

  • The Gilbert–Elliott channel models erasure memory with good and erasure states governed by a first-order Markov process.
  • The channel is parameterized by (ε, ∆), which corresponds one-to-one with the alternative parameter pair (b, g).
  • For an ergodic correlated binary erasure channel, capacity remains 1 − ε, matching the memoryless channel's capacity.
  • Interleaving can randomize erasures, but permuting parity-check-matrix columns destroys convolutional structure and prevents use of windowed decoding.
  • Bursty-channel code optimization commonly permutes parity-check-matrix columns to maximize the maximum resolvable erasure burst length, ∆max.

A. Asymptotic Analysis

The asymptotic analysis characterizes protograph stopping-set spans and derives design rules and bounds for maximizing them. For important regular ensembles, suitable constructions attain optimal or tight spans, while larger memory can reduce finite-length rate.

  • Stopping-set structure: Protograph structure constrains stopping-set sizes and locations, motivating design criteria that avoid single-variable-node stopping sets and maximize minimum span.The analysis seeks protographs whose minimum spans approach the largest achievable value.
  • Stopping-set structure: Protograph stopping sets are variable-node subsets whose neighboring check nodes each connect to the subset at least twice; their minimum span bounds decoding-related quantities.The minimum span and minimum size need not belong to the same stopping set.
  • Bounds and design rules: For Cm(J, 2J) protographs with J > 2, the optimal minimum stopping-set span is ⟨S(J, 2J, ms)⟩∗ = 2ms.A necessary condition for achieving this span is incorporated as a design criterion.
  • Design trade-offs: Increasing memory can enlarge the achievable minimum stopping-set span, but for fixed termination length L it decreases the code rate RL linearly.The modified construction also permits ensembles with a wider range of targeted minimum spans.
  • Bounds and design rules: For Cm(J, K′J) protographs, pairwise stopping-set analysis gives ⟨S(J, K′J, ms)⟩∗ ≤ K′ms, but this bound is loose in general.A constructed family with ms = u(K′ − 1) + 1 achieves ⟨S⟩∗ = K′u + 2 for all u ∈ [L − 1].
  • Bounds and design rules: For terminated Cm(J, K) protographs, the minimum stopping-set span satisfies ⟨S⟩∗ ≤ K′L, although this can be looser than Proposition 4 when ms ≪ L.The paper also proves ⟨S(J, K, ms)⟩∗ ≥ ⟨S(a, K, ms)⟩∗ for a = gcd(J, K) ≥ 2.
  • Example performance: A constructed Cm(4, 6) ensemble achieves ε∗(C8, ms + 1, 10^-12) ≈ 0.6469, close to the Shannon limit εSh = 2/3 with the smallest possible window size.The associated protograph has no degree-1 variable nodes in B0.

B. Finite length analysis

The finite-length analysis bounds the maximum burst length recoverable by BP and windowed decoding through protograph stopping-set spans. These bounds show linear growth with span but also establish a structural gap from MDS burst performance for a specified ensemble family.

  • BP decoding: For any (J, K) regular LDPC-CC, the maximum burst length is bounded above by Δmax ≤ M⟨S⟩∗ − 1.A burst covering the lifted columns corresponding to a minimum-span protograph stopping set cannot be fully recovered.
  • Structural limitation: A terminated Cm(J, K′J) ensemble with ms = u(K′ − 1) + 1 cannot achieve the maximum burst length of an MDS code.The conclusion follows from the Singleton bound and the ensemble’s stopping-set-span bound.
  • BP decoding: For any (J, K) regular LDPC-CC, the maximum guaranteed burst length satisfies Δmax ≥ M(⟨S⟩∗ − 2) + 1.The lower bound grows linearly with the expansion factor M and the minimum stopping-set span.
  • Constructed ensembles: For the family with ms = u(K′ − 1) + 1, the paper constructs codes whose maximum burst length is proportional to ms.This follows by combining the family’s span characterization with the general lower bound.
  • Windowed decoding: For windowed decoding with W ≥ ms + 1 and Design Rule 3, M(⟨S(B, W)⟩∗ − 2) + 1 ≤ Δmax(W) ≤ M⟨S(B, W)⟩∗ − 1.The targeted symbols are the first K′ symbols within the window.

C. Numerical results

Finite-length simulations show that the proposed design improves burst tolerance without reducing code rate, while code comparisons depend on window size, burst length, and decoder.

  • Burst-erasure performance: 1023 and 1751 were the MBLs for codes C1 and C2, respectively, with achieved fractions of 9.1% and 15.5% of the maximum possible MBL.The design increased MBL by more than 70% compared with corresponding codes from the reference ensembles, without decreasing code rate.
  • GEC performance: For W = 3, code C2 always outperforms code C1 over the tested GEC conditions, whereas the advantage disappears for W = 5 when ∆ = 100.The experiments cover ∆ = 10, 50, and 100 with ε ∈ [0.1, 0.6].
  • GEC performance: For W = 10 and BP decoding, code C1 slightly outperforms code C2.This reverses the small-window comparison observed for W = 3.
  • GEC performance: At small ε with ∆ = 100, code C2 outperforms C1 for large windows and BP decoding because rare bursts are likely to resemble a single burst in a codeword.The paper relates this regime to C2’s stronger single-burst performance.
  • Limits: The significant gap between BP performance and the Singleton bound indicates that LDPC-CC remain far from MDS performance with BP or windowed decoding.The Singleton bound represents performance achievable by an idealized binary MDS code.

VI. CONCLUSIONS

The paper studies windowed decoding for LDPC convolutional codes over erasure channels and develops ensemble design rules for performance, latency, and burst tolerance. It finds near-capacity performance on the BEC but a structural gap from MDS performance on channels with memory.

  • Contributions: The proposed windowed decoder trades decoding performance for reduced latency when decoding terminated LDPC-CC.The study also provides examples and finite-length simulations supporting the proposed ensemble design rules.
  • Contributions: Design rules target good thresholds on the BEC and large stopping-set spans on erasure channels with memory.The rules are applied to ensembles, and finite-length codes are used to verify their relevance to performance.
  • Conclusions: Close-to-optimal performance approaching capacity is achievable on the BEC, but LDPC-CC structure bounds performance strictly away from MDS performance on erasure channels with memory.The conclusion contrasts memoryless and memory channels as different performance regimes.
  • Conclusions: Low complexity, latency flexibility, simple structure, and good performance remain attractive characteristics for practical systems.The practical appeal is stated within the scope of erasure-channel decoding.

APPENDIX I PROOF OF PROPOSITION 1

The proof establishes that enlarging a non-terminated decoding window cannot reduce the a-posteriori mutual information of targeted symbols. It does so by augmenting computation trees and applying monotonicity of check-node and variable-node operations.

  • Window containment: The Tanner graph for a window of size W is contained in the graph for size W + 1, with additional edges connecting existing variables to newly included checks and variables.The proof represents the two windows as graphs A and B and compares their computation trees.
  • Monotonicity: Monotonicity of CN and VN operations lets bounds on incoming mutual information propagate to bounds on outgoing messages and the root a-posteriori information.Repeated application of the two lemmas yields bounds for the computation-tree root.
  • Tree construction: The augmented tree T_A^+ matches the larger-window tree structurally while assigning zero mutual information to edges absent from the smaller window.These zero-information messages effectively erase the contributions from the additional checks.
  • Conclusion: The proof obtains I_TA = I_TA+ and compares corresponding edge informations to conclude I_TA ≤ I_TB.Thus, the smaller-window targeted-symbol information is no greater than that obtained with the larger window.

APPENDIX II PROOF OF PROPOSITION 2

The proof constructs explicit polynomial combinations whose column supports form protograph stopping sets. Counting their spans and matching an upper bound yields the exact stopping-set span for the specified ensemble.

  • Construction: Under Design Rule 3, the polynomial intervals satisfy 0 ≤ i_l < j_l ≤ m_s, with minimum start 0 and maximum end m_s.These endpoint conditions determine the interval configurations used in the stopping-set construction.
  • Stopping-set proof: The selected columns form a protograph stopping set because the resulting polynomial has coefficients greater than 1.The argument verifies this through the polynomial representation and coefficient comparison.
  • Span bounds: The four interval-ordering cases produce the stated upper bounds on the stopping-set span.The cases distinguish the relative positions of i_1, i_2, j_1, and j_2.
  • Tightness: The ensemble satisfies ⟨S(J, 2J, m_s)⟩* = 2^m_s.This follows by combining the explicit construction with the upper bound from Proposition 2.
Loading 1010.4548v2…