PaperlayerView exact revision on arXiv

Source-linked AI summary

Spatially Coupled LDPC Codes Constructed from Protographs

David G. M. Mitchell, Michael Lentmaier, Daniel J. Costello

arXiv:1407.5366v1cs.IT

TL;DR

The paper addresses how to combine the capacity-approaching waterfall performance of irregular LDPC codes with the linear minimum-distance growth of regular codes. It constructs protograph-based spatially coupled ensembles by edge-spreading L uncoupled protographs, and finds that sufficiently large coupling lengths produce BP thresholds approaching the underlying codes’ MAP thresholds while retaining asymptotically good distance behavior.

  • Problem

    Regular LDPC codes have linear minimum-distance growth but sub-capacity iterative-decoding performance, whereas optimized irregular codes approach capacity but can suffer error floors.

  • Method

    The paper constructs spatially coupled LDPC ensembles by edge-spreading and coupling L uncoupled protographs, using protograph lifting to preserve their structural properties.

  • Results

    For sufficiently large L, BP thresholds saturate to values numerically indistinguishable from the underlying LDPC ensembles’ MAP thresholds, while minimum distance grows linearly with block length in the stated regular and irregular cases.

  • Takeaways & Limitations

    Spatial coupling combines capacity-approaching BP thresholds with linear minimum-distance growth, and increasing graph density reduces the gap to capacity.

Abstract

from arXiv · show

In this paper, we construct protograph-based spatially coupled low-density parity-check (SC-LDPC) codes by coupling together a series of L disjoint, or uncoupled, LDPC code Tanner graphs into a single coupled chain. By varying L, we obtain a flexible family of code ensembles with varying rates and frame lengths that can share the same encoding and decoding architecture for arbitrary L. We demonstrate that the resulting codes combine the best features of optimized irregular and regular codes in one design: capacity approaching iterative belief propagation (BP) decoding thresholds and linear growth of minimum distance with block length. In particular, we show that, for sufficiently large L, the BP thresholds on both the binary erasure channel (BEC) and the binary-input additive white Gaussian noise channel (AWGNC) saturate to a particular value significantly better than the BP decoding threshold and numerically indistinguishable from the optimal maximum a-posteriori (MAP) decoding threshold of the uncoupled LDPC code. When all variable nodes in the coupled chain have degree greater than two, asymptotically the error probability converges at least doubly exponentially with decoding iterations and we obtain sequences of asymptotically good LDPC codes with fast convergence rates and BP thresholds close to the Shannon limit. Further, the gap to capacity decreases as the density of the graph increases, opening up a new way to construct capacity achieving codes on memoryless binary-input symmetric-output (MBS) channels with low-complexity BP decoding.

I. INTRODUCTION

The introduction contrasts regular and irregular LDPC codes, then presents protograph-based spatial coupling as a way to combine their desirable decoding and distance properties. The paper analyzes how coupling length, protograph structure, and termination affect rates and code performance.

  • Regular LDPC codes have minimum distance growing linearly with block length for J > 2 but fall short of capacity under iterative decoding.
  • Optimized irregular LDPC codes approach capacity in the waterfall region but can exhibit error floors due to degree-two variable nodes.
  • SC-LDPC codes couple L disjoint LDPC Tanner graphs into one chain, yielding convolutional codes when unterminated and block codes when terminated.
  • The paper extends density-evolution and weight-enumerator analyses to general regular and irregular protograph-based SC-LDPC ensembles.
  • The study varies coupling length L to obtain code ensembles with increasing rates and analyzes their construction, distance properties, and iterative decoding behavior.
  • Protograph lifting preserves rate, degree distribution, and computation graphs while enabling Tanner graphs of different sizes.

C. Convolutional Protographs and Spatial Coupling

Spatial coupling is constructed by spreading protograph edges across neighboring time instants, thereby connecting disjoint block protographs into a convolutional chain. The same framework applies to regular and irregular protographs, including ARJA and AR4JA families.

  • A convolutional protograph connects a sequence of disjoint block protographs by applying an edge-spreading operation across time.
  • The Edge Spreading Rule distributes each variable-to-check edge bundle across w + 1 neighboring check-node positions.
  • The resulting SC-LDPC-CC ensemble has design rate R = 1 − bc/bv and constraint length ν = (w + 1)Mbv.
  • Edge spreading preserves the original block protograph’s design rate, degree distribution, and computation graphs.
  • For a (3, 6)-regular protograph, the illustrated construction uses coupling width w = 2 and spreads each variable-node edge across three successive time positions.
  • The same procedure constructs ARJA and AR4JA convolutional protographs with w = 1 and design rates R = 1/2 and R = (1 + e)/(2 + e), respectively.
  • The coupled convolutional protograph can be viewed as an infinite graph lifting of the block protograph, preserving local computation structure for BP decoding.

D. Spatially Coupled LDPC Block Codes

Termination converts the infinite convolutional construction into finite-length block codes. The resulting boundary structure introduces a decoding improvement while preserving flexible spatially coupled code construction.

  • In practice, the infinite convolutional protograph is terminated at finite starting and ending times to obtain convolutional-like block codes.
  • Termination significantly improves the iterative BP threshold of SC-LDPC convolutional codes.

1) Terminated SC-LDPC-CC ensembles:

Terminating a convolutional protograph couples L block protographs into a finite SC-LDPC-BC, introducing boundary irregularity and rate loss that diminish as L increases.

  • Construction: A terminated SC-LDPC-BC is formed from the variable nodes over time instants 0 through L−1 of a convolutional protograph.The ensemble consists of M-fold graph covers of the terminated protograph, with block length n = MLbv.
  • Construction: Termination couples L disjoint block protographs while adding check nodes at the right boundary across w additional time instants.The terminated base matrix has dimensions (L+w)bc × Lbv.
  • Structural properties: Termination introduces structured irregularity because boundary check nodes generally have fewer edge connections than check nodes in the chain interior.For the (3, 6)-regular construction, each variable node has degree 3, middle check nodes have degree 6, and boundary checks have degree 2 or 4.
  • Rate: For finite L, termination causes a design-rate loss, with RL < R; the rate and irregularity become vanishingly small as L increases.Here R is the design rate of the unterminated convolutional and uncoupled block protographs.
  • Examples: The C(3, 6, L) ensembles retain essentially the beneficial structural properties of (3, 6)-regular ensembles while improving iterative BP thresholds.The ensemble is obtained by terminating the associated C(3, 6) SC-LDPC-CC ensemble with coupling length L.
  • Decoding behavior: During BP decoding, reliable messages from lower-degree boundary checks create a wave that moves from both ends toward the chain centre.For C(3, 6, 20) on a BEC, the average bit erasure probability near the ends decreases quickly and the effect propagates inward.

2) Tail-biting LDPC-CC ensembles:

Tail-biting terminates a convolutional protograph by reconnecting its boundary checks, preserving regularity and design rate while retaining a block-code structure.

  • Construction: Tail-biting combines the final w check-node sections with corresponding sections at the beginning of a convolutional protograph.This construction applies when the coupling length satisfies L > w.
  • Construction: A TB-SC-LDPC-BC ensemble is obtained as the collection of all M-fold graph covers of the tail-biting convolutional protograph.Its block length is n = MLbv.
  • Properties: The tail-biting protograph retains the convolutional protograph’s design rate and degree distribution, introducing neither structured irregularity nor rate loss.The construction therefore provides a block protograph of desired length while retaining convolutional-protograph properties.
  • Notation and applications: The Ctb(J, K, L) ensemble denotes the tail-biting SC-LDPC-BC obtained from C(J, K, L) with coupling length L.Tail-biting constructions also support lower bounds on free distance and minimum trapping-set size.
  • Regular example: In the regular example, every variable node has degree 3 and every check node has degree 6, so the tail-biting graph remains (3, 6)-regular.Its ensemble design rate is Rtb.

E. Discussion

The discussion situates protograph-based spatial coupling among edge-spreading and unwrapping constructions, including extensions to time-varying protographs and related code ensembles.

  • Convolutional protograph construction: A convolutional protograph can be built using time-varying edge spreading, with a different edge spreading applied at each time instant.The generalization need not preserve the original degree distribution or computation graphs.
  • Direct edge spreading: Edge spreading can be applied directly to an LDPC block-code Tanner graph or parity-check matrix without first constructing a block protograph.The literature describes two major construction approaches in this category.
  • Prior work: Earlier work studied direct constructions, unwrapping, and related SC-LDPC-BC ensembles closely related to the C(J, K, L) family.These approaches connect the paper’s constructions to established SC-LDPC literature.
  • Unwrapping: Unwrapping constructs time-varying LDPC convolutional codes from disjoint LDPC block-code Tanner graphs while preserving the underlying computation graph.This approach was introduced by Jimenez-Felström and Zigangirov in 1999.

3) Kudekar’s Randomized SC-LDPC-BC Ensemble:

Prior randomized SC-LDPC-BC ensembles achieve threshold saturation but have less favorable rate–threshold–block-length trade-offs and fewer implementation advantages than protograph-based ensembles.

  • Randomized ensemble: The randomized ensemble’s BP threshold improves to the optimal MAP threshold of the underlying regular LDPC-BC ensemble.This phenomenon is termed threshold saturation and combines globally optimal decoding performance with low-complexity iterative BP decoding.
  • Protograph-based construction: Protograph-based SC-LDPC-BC ensembles exhibit threshold saturation and minimum distance growth linear in block length.These properties target strong performance in both waterfall and error-floor regions.
  • Implementation: Highly structured protograph-based ensembles are attractive because their structure can simplify encoding and decoder design.QC members can use simple feedback shift-register encoders and exploit decoder-design efficiencies.
  • Protograph-based construction: Varying the coupling length L produces SC-LDPC-BCs with different rates and frame lengths while preserving similar performance.This flexibility supports applications and standards requiring multiple frame lengths without designing a separate LDPC-BC for each length.

III. MINIMUM DISTANCE AND THRESHOLD TRADE-OFFS FOR SC-LDPC-BC ENSEMBLES

The section combines weight-enumerator analysis with density-evolution analysis to evaluate minimum-distance growth and iterative decoding thresholds of protograph-based SC-LDPC-BC ensembles.

  • III. MINIMUM DISTANCE AND THRESHOLD TRADE-OFFS FOR SC-LDPC-BC ENSEMBLES: The analysis first studies asymptotic weight enumerators and then uses density evolution to obtain BEC and AWGNC iterative decoding thresholds.Together, these analyses test asymptotic goodness and threshold saturation.

A. Weight Enumerators

The paper uses protograph weight enumerators and asymptotic spectral-shape analysis to characterize minimum-distance growth, finding asymptotically good SC-LDPC-BC ensembles across coupling lengths and rates.

  • A. Weight Enumerators: The ensemble average weight enumerator counts codewords by their protograph-induced variable-node weight distributions.When some variable nodes are punctured, the calculation sums over punctured and transmitted partial weight patterns.
  • A. Weight Enumerators: The asymptotic spectral shape function is derived from the normalized logarithm of the ensemble average weight distribution.Its first positive zero crossing defines the minimum distance growth rate when the function is negative below that crossing.
  • A. Weight Enumerators: A minimum distance growth rate δmin implies minimum distance at least nδmin with high probability when low-weight codewords occur with vanishing probability.Such ensembles are called asymptotically good because minimum distance grows linearly with block length.
  • A. Weight Enumerators: Finite-L C(J, 2J, L) ensembles have average check degree below 2J, increasing toward 2J as L grows, while variable degree remains J.This describes how coupling length affects ensemble complexity.
  • A. Weight Enumerators: For C(4, 8, L), distance growth rates exceed those of C(3, 6, L) at the same rate, while C(5, 10, L) provides a smaller improvement.Scaled growth rates converge as L increases, enabling estimates for L > 20.

B. Thresholds for the BEC

Density-evolution results show that increasing coupling length improves BEC thresholds toward MAP-level or near-capacity values, while distance growth, complexity, and rate exhibit coupling-dependent trade-offs.

  • B. Thresholds for the BEC: Protograph-based C(J, K, L) ensembles achieve at least doubly exponential error-probability decay with iterations when J ≥ 3.This condition corresponds to all variable nodes having degree at least three.
  • B. Thresholds for the BEC: For C(3, 6, L), the BEC threshold saturates at ε∗ = 0.488, leaving a 0.012 gap to capacity as L grows.At L = 10, ε∗ = 0.505 and the gap is 0.095; around L = 20, the threshold reaches its limiting value.
  • B. Thresholds for the BEC: For C(3, 6, L), the saturated threshold is numerically indistinguishable from the underlying ensemble’s MAP threshold εMAP = 0.4881 and exceeds its BP threshold ε∗ = 0.429.The underlying regular ensemble still has a small gap to capacity under optimal decoding.
  • B. Thresholds for the BEC: For C(J, 2J, L), increasing L reduces the gap to capacity, while increasing J worsens thresholds at fixed rate and small L.The corresponding regular ensembles show the same small-L behavior.
  • B. Thresholds for the BEC: For large L, saturated thresholds improve with J: ε∗ = 0.4881, 0.4977, and 0.4994 for C(3, 6, L), C(4, 8, L), and C(5, 10, L).These values are numerically indistinguishable from the MAP thresholds of the underlying regular ensembles.
  • B. Thresholds for the BEC: The construction yields asymptotically good ensembles with varying thresholds and minimum-distance growth rates across a broad range of design rates.Edge spreading can further extend achievable rates by coupling protographs of higher or lower rate.
  • B. Thresholds for the BEC: CARJA(L) thresholds saturate at ε∗ = 0.4996, close to εsh = 0.5 for rate R∞ = 1/2 and above the underlying ARJA BP threshold.Their distance growth rates also converge as L increases.
  • B. Thresholds for the BEC: CAR4JA(e, L) permits tuning between distance growth and threshold by choosing extension parameter e and coupling length L.Intermediate L values provide small capacity gaps while retaining reasonable distance growth and only a small rate loss.

C. Thresholds for the AWGNC

The AWGNC analysis shows that increasing coupling length improves SC-LDPC-BC thresholds toward the MAP thresholds of underlying LDPC ensembles, while creating a threshold–distance-growth trade-off. Finite-length simulations confirm performance close to the asymptotic thresholds.

  • Threshold analysis: RCA analysis extends the AWGNC threshold study to protograph-based SC-LDPC-BC ensembles.Exact density evolution is more complex on the AWGNC, motivating the reciprocal channel approximation technique.
  • Threshold saturation: σ*=0.948 for L→∞ in C(3, 6, L) matches the underlying (3, 6)-regular ensemble’s MAP threshold and approaches σSh=0.979.The underlying ensemble’s BP threshold is σ*=0.881, so coupling substantially improves the threshold toward the Shannon limit.
  • Threshold saturation: As L increases, thresholds saturate to the underlying ensembles’ MAP thresholds while the gap to capacity decreases.This behavior holds across the regular and irregular ensembles considered and does not continue degrading as L approaches infinity.
  • Design trade-off: Varying L produces ensembles with different rates and a trade-off between iterative-decoding threshold and minimum-distance growth rate.The coupling length therefore controls both rate-related threshold behavior and distance-growth properties.
  • Rate and density effects: Increasing L raises design rates toward 1/2 and improves thresholds toward the Shannon limit, whereas small-L threshold gains can worsen as graph density increases.For large L, thresholds approach the MAP threshold, which itself approaches capacity as variable-node degree increases.
  • Finite-length performance: For R=0.49, C(3, 6, 100) and C(4, 8, 150) SC-LDPC-BCs show waterfall performance within 0.2dB of threshold at M=6000.The SC-LDPC-BCs operate beyond the threshold of the (3, 6)-regular LDPC-BC, with improvement expected for larger M and L.

IV. FREE DISTANCE GROWTH RATES OF SC-LDPC-CC

This section relates the free distance of periodically time-varying SC-LDPC convolutional codes to minimum distances of terminated spatially coupled block codes. For sufficiently large periods, the bounds coincide and yield exact free-distance growth rates that remain meaningful as coupling length grows.

  • Choosing a distance measure: δ_min(L) is useful for block-code comparison, but δ_free is more appropriate for large-L performance because it is independent of L and scales with constraint length.The constraint length ν=M(w+1)bv increases with M but not with L.
  • Practical implication: Sliding-window decoding uses a fixed window tied to constraint length rather than the full chain length, supporting low latency and memory requirements as L grows.This motivates evaluating SC-LDPC-BC distance through an L-independent convolutional measure.
  • Connection to terminated codes: The analysis introduces periodically time-varying SC-LDPC-CC sub-ensembles to connect convolutional free distance with terminated block-code minimum distance.A period-T convolutional ensemble corresponds to a terminated SC-LDPC-BC with coupling length L=T.
  • Distance bounds: Every terminated-code codeword can be extended by zeros into the corresponding unterminated code, so free distance is at most terminated-code minimum distance.The one-to-one correspondence between paired ensemble members transfers the bound to ensemble averages.
  • C(3, 6) example: For C(3, 6, L), δ_min(L) decreases monotonically toward zero as L→∞, while the free-distance growth rate levels off at δ_free=0.086 for T≥12.The leveling-off occurs because minimum-weight convolutional codewords also appear in terminated block codes once L exceeds 11.
  • C(3, 6) example: δ_free=0.086 exceeds the underlying (3, 6)-regular LDPC-BC minimum-distance growth rate δ_min=0.023.At sufficiently large periods, the upper and lower free-distance bounds coincide numerically.

V. CONCLUDING REMARKS

The proposed spatially coupled ensembles combine capacity-approaching BP thresholds with linear minimum-distance growth, while coupling length and graph design expose explicit performance tradeoffs.

  • Construction and properties: Coupling L disjoint protographs through edge spreading creates flexible SC-LDPC ensembles with varying rates and code properties under a shared architecture.The coupling operation introduces memory into the code design, and L controls the resulting family.
  • Threshold behavior: For sufficiently large L, BP thresholds on the BEC and AWGNC become significantly larger than the uncoupled BP threshold and numerically indistinguishable from the underlying MAP threshold.This threshold saturation occurs for both channels considered.
  • Distance and decoding: The C(J, K, L) ensembles combine capacity-approaching BP thresholds with minimum distance that grows linearly with block length.They are almost regular while retaining these two desirable properties in one design.
  • Distance tradeoff: As L increases, design rates increase while minimum-distance growth rates decline, converging to an L-independent bound related to the SC-LDPC-CC free-distance growth rate.This motivates using a distance measure independent of L, particularly with sliding-window decoding.
  • Design implications: Boundary-induced structured irregularity drives threshold performance, and threshold saturation extends to both regular and irregular LDPC block-code ensembles.Careful edge spreading and denser component graphs can further improve performance.
Loading 1407.5366v1…