PaperlayerView exact revision on arXiv

Source-linked AI summary

Protograph-Based Raptor-Like LDPC Codes

Tsung-Yi Chen, Kasra Vakilinia, Dariush Divsalar, Richard D. Wesel

arXiv:1403.2111v1cs.ITmath.IT

TL;DR

Rate-compatible LDPC families support incremental-redundancy systems, but punctured finite-length LDPC codes can degrade at high rates. The paper proposes Raptor-like protograph-based codes, reporting strong long-blocklength comparisons against standardized alternatives while retaining extensive rate compatibility.

Abstract

from arXiv · show

This paper proposes a class of rate-compatible LDPC codes, called protograph-based Raptor-like (PBRL) codes. The construction is focused on binary codes for BI-AWGN channels. As with the Raptor codes, additional parity bits are produced by exclusive-OR operations on the precoded bits, providing extensive rate compatibility. Unlike Raptor codes, the structure of each additional parity bit in the protograph is explicitly designed through density evolution. The construction method provides low iterative decoding thresholds and the lifted codes result in excellent error rate performance for long-blocklength PBRL codes. For short-blocklength PBRL codes the protograph design and lifting must avoid undesired graphical structures such as trapping sets and absorbing sets while also seeking to minimize the density evolution threshold. Simulation results are shown in information block sizes of $k=192$, $16368$ and $16384$. Comparing at the same information block size of $k=16368$ bits, the PBRL codes outperform the best known standardized code, the AR4JA codes in the waterfall region. The PBRL codes also perform comparably to DVB-S2 codes even though the DVB-S2 codes use LDPC codes with longer blocklengths and are concatenated with outer BCH codes.

I. INTRODUCTION

The paper motivates rate-compatible LDPC families for incremental-redundancy systems and positions its Raptor-like protograph design among prior puncturing, extension, and asymptotic approaches.

I. INTRODUCTION

  • Rate-compatible LDPC families are motivated by the goal of high throughput in incremental-redundancy systems as received symbols improve error protection.The paper notes that finite-length punctured LDPC codes are commonly observed to degrade more than punctured turbo codes at high rates.Source: §I · p. 1, A. Rate-Compatible Channel Codes · p. 2

A. Rate-Compatible Channel Codes

  • Combining extension with puncturing was reported to yield better rate-compatible codes than puncturing alone, and this paper uses similar techniques.Its focus is a protograph-code class intended to offer encoding and decoding complexity benefits alongside performance across rates.Source: A. Rate-Compatible Channel Codes · p. 2
  • Raptor-like structure distinguishes this density-evolution design of rate-compatible protograph families from earlier designs, and keeps construction and optimization manageable.The paper also contrasts its finite-length focus with prior spatial-coupling work centered on asymptotic thresholds.Source: A. Rate-Compatible Channel Codes · p. 2
  • Earlier spatial-coupling analysis focused on asymptotic decoding thresholds with negligible rate loss from time spreading, whereas this paper also studies finite-length codes.The paper focuses on memoryless channels and both short- and long-blocklength regimes, unlike work focused on long-blocklength codes for wireless fading channels.Source: A. Rate-Compatible Channel Codes · p. 2

B. Main Contributions and Organization

The paper proposes PBRL codes and outlines their construction through protographs, lifting, and a Raptor-like arrangement of precode and LT components.

B. Main Contributions and Organization

  • PBRL codes are proposed as rate-compatible LDPC codes that show outstanding performance against existing codes while providing extensive rate compatibility.The paper identifies AR4JA, DVB-S2, and protograph codes as comparison families.Source: B. Main Contributions and Organization · p. 2

II. PROTOGRAPH-BASED RAPTOR-LIKE LDPC CODE

A. Overview of Protograph Codes and Raptor Codes

  • Protograph codes begin with a small bipartite graph, which is copied and permuted through lifting to produce larger LDPC graphs.The overview describes protograph codes as structured codes supporting efficient hardware implementation.Source: A. Overview of Protograph Codes and… · pp. 2–3
  • The overview situates LT and Raptor codes as related to LDPC codes and notes their capacity universality for the binary erasure channel.It also cautions that cited Raptor-code results rely heavily on large information blocks.Source: A. Overview of Protograph Codes and… · p. 3

B. The Structure of PBRL Codes

PBRL protographs combine a precode with an LT-like extension, enabling rate-compatible transmission and deterministic parity generation; their structure also supports joint decoding.

B. The Structure of PBRL Codes

  • A PBRL protograph combines a precode with LT-part check nodes, each connected to precode variables and a degree-one variable; transmitting the precode alone gives the example’s highest rate, 2/3.Lower rates add LT-part variables, starting from the top node.Source: B. The Structure of PBRL Codes · p. 3
  • The degree-one LT variables are encoded from precoded symbols, giving PBRL a Raptor-like structure with deterministic rather than random symbol combinations.Encoding the LT part after the precode requires only exclusive-or operations on precode output symbols.Source: B. The Structure of PBRL Codes · p. 3, C. Decoding and Encoding of PBRL Codes · p. 4
  • A PBRL protograph is represented by a protomatrix formed from the precode and LT-part matrices and an identity block.The paper says specifying Hp and HLT suffices to express the protomatrix.Source: B. The Structure of PBRL Codes · p. 3

C. Decoding and Encoding of PBRL Codes

  • Always transmitting precode symbols and using deterministic LT connections facilitate joint decoding of the precode and LT parts.The precode symbols also give PBRL codes the potential for successful decoding after the initial transmission, unlike randomized Raptor encoding in the described setting.Source: C. Decoding and Encoding of PBRL Codes · p. 3
  • Despite its restrictive Raptor-like structure, careful protograph design and lifting can yield very low iterative thresholds and finite-length codes that outperform less-constrained rate-compatible LDPC codes.At high rates, LT check nodes whose degree-one variables are not transmitted can be deactivated, reducing implementation complexity.Source: C. Decoding and Encoding of PBRL Codes · pp. 3–4

III. OPTIMIZATION OF PROTOGRAPH-BASED RAPTOR-LIKE LDPC CODES

The paper optimizes PBRL protographs by minimizing iterative decoding thresholds, using a modified reciprocal channel approximation (RCA) that supports degree-one variable nodes. The method approximates density evolution for BI-AWGN channels and enables threshold estimation by iteration.

III. OPTIMIZATION OF PROTOGRAPH-BASED RAPTOR-LIKE LDPC CODES

  • The optimization procedures primarily minimize iterative decoding thresholds, using a modified RCA to compute them efficiently.The section covers construction procedures for both short- and long-blocklength PBRL codes.Source: §III · p. 4

A. Density Evolution with Reciprocal Channel Approximation

  • The BI-AWGN asymptotic iterative decoding threshold is the minimum SNR for reliable transmission as blocklength grows to infinity.It characterizes the ensemble defined by a specified protograph.Source: A. Density Evolution with Reciprocal… · p. 4
  • RCA approximates exact density evolution quickly, with reported deviation below 0.01 dB.Threshold search uses bisection based on monotonicity; lookup tables and linear interpolation speed computation.Source: A. Density Evolution with Reciprocal… · pp. 4–5
  • The RCA approximates density evolution with a single real-valued SNR parameter, using reciprocal SNRs whose channel capacities sum to one.The reciprocal energy function maps the parameters s and r to each other.Source: A. Density Evolution with Reciprocal… · p. 4
  • RCA initializes punctured-node messages to zero and other messages to the channel SNR, then iterates message updates through a maximum of N iterations.The original RCA determines the threshold as the minimum channel SNR meeting its terminal reliability condition.Source: A. Density Evolution with Reciprocal… · p. 4
  • The original RCA is unsuitable for degree-one variable nodes, so the modified RCA tracks each variable node's overall reliability instead of every edge's reliability.It computes a meaningful decoding threshold for protographs containing degree-one variable nodes.Source: A. Density Evolution with Reciprocal… · p. 4

B. Optimizing the Precode Protograph of PBRL Codes

The precode design balances minimum-distance growth against threshold improvement. Its variable nodes are constrained to degree at least three because the LT part already contains degree-one nodes.

B. Optimizing the Precode Protograph of PBRL Codes

  • A minimum variable-node degree of three or higher guarantees linear growth of minimum distance with blocklength for the cited code ensembles [23, Sec.III].The cited work also notes that adding some degree-two or degree-one nodes can improve the threshold.Source: B. Optimizing the Precode Protograph… · p. 5
  • Precode variable nodes are constrained to degree at least three because the LT part inherently contains degree-one nodes.The selected precode structures are inspired by examples in and further optimized through density evolution and LDPC simulation.Source: B. Optimizing the Precode Protograph… · p. 5

C. Optimizing the LT Code Protograph of PBRL Codes

The LT protograph is built iteratively by adding degree-one variables and optimizing their check-node connections for the lowest threshold. Its nested rate-compatible structure limits optimization at lower rates.

C. Optimizing the LT Code Protograph of PBRL Codes

  • Each LT extension adds a check node and degree-one variable, then selects connections to precoded symbols that minimize the threshold.The process repeats until the desired lowest rate is reached, then the protograph is lifted with circulant permutations selected by cPEG,.Source: C. Optimizing the LT Code Protograph… · p. 5
  • For short-blocklength codes, parallel edges can create short cycles during lifting, so the examples keep them to at most one pair.The authors empirically found this restriction supports good waterfall and error-floor performance, although parallel edges can facilitate very low thresholds.Source: C. Optimizing the LT Code Protograph… · p. 5
  • As code rate decreases across 6/9 through 6/18, the threshold-to-capacity gap increases because inherited connections restrict each new protograph's optimization.Each step can optimize only the connections from one added check node, which must connect to a new degree-one variable node.Source: C. Optimizing the LT Code Protograph… · p. 5
  • The short-blocklength PBRL family begins at rate 3/4 and adds LT variable nodes to obtain rates 6/9 through 6/18.Table I presents thresholds for the optimized protograph, but the supplied passages do not give its cell values.Source: C. Optimizing the LT Code Protograph… · p. 5, Table I · p. 5

D. Punctured-Node PBRL Codes

PN-PBRL codes puncture at least one precode node, a variant introduced because protograph puncturing can improve threshold performance. Their optimization also uses a tie-breaking heuristic intended to aid short-blocklength decoding.

D. Punctured-Node PBRL Codes

  • Puncturing a precode node defines PN-PBRL codes, a variant motivated by the possibility of improved threshold performance.The precode optimization otherwise follows the earlier procedure, with one variable node punctured.Source: D. Punctured-Node PBRL Codes · p. 5
  • The example protograph punctures the first precode variable node, shown as a white circle, and transmits LT variables from the top downward to form lower rates.The depicted precode has rate 6/7; the initial rate can instead be 3/4 by transmitting the first LT variable node.Source: Figure 3 · p. 6, D. Punctured-Node PBRL Codes · p. 6
  • For threshold-tied LT connections, the PN-PBRL heuristic prefers one with no edge to the punctured node.The heuristic helps prevent performance degradation for blocklengths below 1000 and speeds convergence because the punctured node is less reliable early in decoding.Source: D. Punctured-Node PBRL Codes · p. 6
  • The subsequent code rates 6/9, 6/10, …, 6/18 are obtained by transmitting the LT-code protograph variable nodes from top to bottom.Source: D. Punctured-Node PBRL Codes · p. 6

E. Optimization for Long-Blocklength PN-PBRL Codes

Long-blocklength PN-PBRL design allows parallel edges in the LT protograph to lower decoding thresholds, while lifting quality and error-rate behavior constrain how many such edges to use. The optimization connects the punctured node broadly and uses larger protographs and improved lifting to balance threshold gains with error-rate performance.

E. Optimization for Long-Blocklength PN-PBRL Codes

  • A good precode has minimum distance growing linearly with blocklength, while the LT part needs different criteria to achieve good thresholds at subsequent rates.The long-blocklength approach permits parallel edges because lifting can avoid short cycles even when they occur in the LT protograph.Source: E. Optimization for Long-Blocklength… · p. 6
  • The punctured precode node must connect to every LT check node at least once; removing those edges experimentally degrades low-rate thresholds.Those connections induce high-degree punctured variable nodes at low rates.Source: E. Optimization for Long-Blocklength… · p. 6
  • Additional parallel-edge pairs further lower thresholds, but gains diminish and numerous pairs can yield high error floors with cPEG-only lifting.A larger protograph and lifting optimized with cPEG and optionally ACE are proposed to improve lifted-code performance.Source: E. Optimization for Long-Blocklength… · pp. 6–7
  • The construction adds a check node and degree-one variable node iteratively, optimizes connections by modified RCA, then lifts with cPEG and optionally ACE.The maximum number of parallel edges to the punctured node is predetermined; other LT edges may be single or parallel depending on protograph size.Source: E. Optimization for Long-Blocklength… · p. 7
  • Table III gaps fall below 0.5 dB, with all but one below 0.4 dB, mainly by adding a parallel-edge pair and requiring a high-degree punctured node.These thresholds improve on the example in Sec. III-D, whose largest gap exceeded 1 dB.Source: E. Optimization for Long-Blocklength… · p. 7, Table III
  • Adding parallel edges between the punctured node and all LT check nodes improves threshold-capacity gaps to below 0.34 dB except at the precode rate, but cPEG-lifted codes do not perform well in error rate.A larger protograph is needed both to improve thresholds and to control the punctured node’s parallel-edge count.Source: E. Optimization for Long-Blocklength… · p. 7
  • Table IV thresholds have gaps to capacity within 0.164 dB, following heuristic parallel-edge placement and greedy RCA optimization.The connections from LT check nodes to unpunctured precoded nodes may be single or parallel edges.Source: Table IV · p. 7, E. Optimization for Long-Blocklength… · p. 8

IV. EXAMPLES AND SIMULATIONS OF PBRL CODES

The simulations compare PBRL codes at short and long blocklengths with rate-compatible channel codes from the literature. They use iterative decoding with floating-point computation and a flooding message-passing schedule unless otherwise stated.

IV. EXAMPLES AND SIMULATIONS OF PBRL CODES

  • Simulations cover PBRL information block sizes k = 192, 16368, and 16384 and compare codes with similar-blocklength channel codes from the literature.The section includes both short- and long-blocklength regimes.Source: §IV · p. 8
  • The simulations use floating-point iterative decoders with flooding message passing unless stated otherwise.Decoding stops upon a successful parity check or after 100 iterations unless stated otherwise.Source: §IV · p. 8
  • The simulation setup compares PBRL codes against other channel codes with similar blocklengths reported in the literature.Source: §IV · p. 8

A. Short-Blocklength PBRL Codes

Short-blocklength examples compare PBRL and PN-PBRL codes with RCPT codes, with PN-PBRL gaining an advantage at sufficiently high SNR and showing no error floor in the reported cases. Direct protograph lifting with cPEG is used for the examples, and PN-PBRL performs better than PBRL at a slight encoding-complexity cost.

A. Short-Blocklength PBRL Codes

  • Direct lifting of the k = 192 PBRL protograph yields better codes than the two-stage lifting described in.cPEG avoids length-4 cycles and minimizes length-6 cycles in these short-blocklength examples.Source: A. Short-Blocklength PBRL Codes · p. 8
  • The rate-1/3 figure reports no sign of an error floor for either PBRL or PN-PBRL.Source: Figure 5 · p. 8
  • PN-PBRL outperforms PBRL consistently with a slight increase in encoding complexity due to the punctured node.The comparison plots FER and BER at rates 3/4 and 1/3.Source: A. Short-Blocklength PBRL Codes · p. 9
  • At rate 3/4, PN-PBRL performs similarly to RCPT, then outperforms it above 3 dB in FER and 4 dB in BER; at rate 1/3, its advantage begins above 3.5 dB in FER and 4 dB in BER.Across the reported cases, PN-PBRL outperforms RCPT at sufficiently high SNR, with the crossover occurring at higher FER/BER for higher rates.Source: Figure 4 · p. 8, Figure 5 · p. 8, A. Short-Blocklength PBRL Codes · p. 9
  • With the same precode and information blocklength 192, the tested Raptor codes have much higher FER than PBRL and PN-PBRL at all rates, even before accounting for LT-connection signaling overhead.The paper attributes the comparison in part to Raptor codes not transmitting precode symbols and randomly drawing output-node degrees.Source: A. Short-Blocklength PBRL Codes · p. 9

B. Long-Blocklength PBRL Codes

Long-blocklength PN-PBRL codes are constructed by two-stage lifting and evaluated across rates. Their waterfall-region performance surpasses AR4JA and DVB-S2, while a smaller Raptor-like protograph has thresholds comparable to prior rate-compatible protographs.

B. Long-Blocklength PBRL Codes

  • 4 x 682 two-stage lifting yields k = 16368; successive LT-output transmission gives rates 6/8 through 6/18, with added variable nodes enabling intermediate rates.The pre-lift removes parallel edges before the second lift to the desired blocklength.Source: B. Long-Blocklength PBRL Codes · p. 9
  • In the waterfall region, PN-PBRL outperforms AR4JA and DVB-S2, despite DVB-S2's longer blocklength and optional BCH concatenation.Comparisons are at rates 1/2 and 2/3; PN-PBRL has information length 16,368 bits, while DVB-S2 blocklength is 64,800 bits.Source: Figure 7 · p. 10, B. Long-Blocklength PBRL Codes · p. 10
  • No error floor was observed for FER greater than 10^-6 in the long-blocklength code results.The described curves include frame and bit error rates for the protograph based on (14) and (15).Source: Figure 6 · p. 9, B. Long-Blocklength PBRL Codes · p. 10
  • The 33-variable Raptor-like protograph achieves thresholds comparable to those in, whose 47-variable protograph had lower thresholds than those in Table III.The section presents a lifted-code comparison with the rate-compatible protograph codes proposed in at rates 1/3 and 1/2.Source: B. Long-Blocklength PBRL Codes · p. 10, Figure 9 · p. 10
  • For V33, cPEG enforces girth 8 while ACE constraints are progressively relaxed after failed searches.The lifting combines cPEG and ACE; the relaxation schedule eventually reaches (6, 18).Source: B. Long-Blocklength PBRL Codes · p. 10
  • The comparison with uses different decoder settings: its simulations used 8-bit quantization and 200 iterations, whereas these used floating point.The decoder-setting difference is reported alongside the comparison at rates 1/3 and 1/2.Source: B. Long-Blocklength PBRL Codes · p. 10

V. CONCLUDING REMARKS

The concluding results show strong performance for lifted PBRL codes across short- and long-blocklength settings, while highlighting that threshold gains do not guarantee better lifted-code performance. The design uses density-evolution-based optimization and lifting choices tailored to code length.

V. CONCLUDING REMARKS

  • Optimization uses density evolution with a modified reciprocal channel approximation, while circulant assignments use cPEG and ACE.The modified approximation is used for a fast, accurate estimate of PBRL thresholds.Source: §V · p. 11
  • Puncturing precode variable nodes improves PBRL thresholds, but slightly complicates the encoder for the initial transmission.Source: §V · p. 11
  • Long-blocklength design uses density-evolution guidance; short-blocklength design must avoid undesirable graph structures while minimizing the threshold.Source: §V · p. 11
  • Threshold saturation appears as rate decreases; one parallel-edge pair works best for k = 192, while two give excellent results for k = 16368 and 16384.More parallel-edge pairs can alleviate saturation but do not always improve lifted-code performance; multiple pairs call for larger protographs and better lifting.Source: §V · p. 11
  • Short-blocklength PBRL codes outperform RCPT at high SNR but underperform at low SNR; long-blocklength codes outperform AR4JA and DVB-S2 and show no error floor down to FER 10^-7.Although their RCA thresholds are larger than those reported in, the lifted codes outperform the rate-compatible LDPC codes in.Source: §V · p. 11
Loading 1403.2111v1…