PaperlayerView exact revision on arXiv

Source-linked AI summary

Low-Latency LDPC Decoding Based on Consensus and Return Residual Belief Propagation

Allan E. Feitosa, Rodrigo C. de Lamare

arXiv:2610.14387v1cs.ITmath.IT

TL;DR

LDPC decoding must recover codewords from noisy observations while balancing iteration count, computational complexity, and latency, and greedy RBP can degrade error-rate performance. The paper proposes Consensus and Return variants that exploit updated information; both outperform comparable RBP-based methods, with C&DR-RBP requiring fewer iterations for a given error rate.

  • Problem

    Greedy RBP can propagate incorrect estimates and concentrate updates on a small group of edges, while reducing iterations through dynamic scheduling comes with greater per-iteration complexity.

    Source: §I · pp. 1–2

  • Method

    C&R-RBP and C&DR-RBP use Consensus and Return mechanisms to exploit updated information and mitigate degradation from RBP’s greedy behavior.

    Source: §I · p. 2

  • Results

    Both algorithms outperform IDS RBP-based methods at the same overall computational complexity, and C&DR-RBP needs fewer iterations for a given error-rate performance without additional computational cost.

    Source: §IX · p. 17

  • Takeaways & Limitations

    C&DR-RBP is particularly suitable for low-latency applications because it reaches a given error-rate performance in fewer iterations without additional computational cost.

    Source: §IX · p. 17

    Extending the proposed methods to more general channel models, including fading, impulsive noise, correlated channels, and other non-Gaussian environments, remains future work.

    Source: §IX · p. 17

Abstract

from arXiv · show

We propose two new decoding algorithms for low-density parity-check (LDPC) codes. The Consensus and Return residual belief propagation (C&R-RBP) algorithm reduces the number of iterations required to achieve a target decoding error rate over an AWGN channel by exploiting the availability of updated information, thereby mitigating the performance degradation caused by the greedy behavior of RBP-based algorithms and reducing error propagation. The Consensus and Delayed Return RBP algorithm (C&DR-RBP) achieves better performance in the early decoding iterations than C&R-RBP, making it particularly suitable for low-latency applications. Both proposed methods maintain the same computational complexity as the original RBP algorithm in terms of residual calculations. We also provide a formal analysis showing that the Consensus mechanism increases the probability of correct bit decisions under initial decoding conditions and in the presence of severe bit transmission errors, providing insight into the performance gains observed in the simulations. Numerical results based on the rapidly growing 5G New Radio (NR) standard, considering different code lengths, code rates, and channel models, demonstrate that both methods outperform competing RBP-based algorithms with similar overall computational complexity in terms of frame error rate (FER) and bit error rate (BER).

I. INTRODUCTION

The introduction presents two RBP-based decoders that use updated information to address RBP’s greedy behavior, while framing LDPC decoding as a trade-off between iterations, computational complexity, and latency. It then establishes the decoding background, channel and code models, and the paper’s objective.

I. INTRODUCTION

  • RBP selects the largest C2V residual for update, but its greedy schedule can propagate incorrect estimates and repeatedly favor a small group of edges.Other variable nodes may have little or no opportunity to contribute their intrinsic information when decoding fails.Source: §I · p. 1
  • Earlier RBP-based methods address greediness with strategies such as broader node updates, equal VN opportunities, residual attenuation, and partially updated residual lists.CI-RBP estimates potential improvement using conditional probabilities, at the expense of added computation.Source: §I · pp. 1–2
  • RBP-based informed dynamic scheduling can reduce iterations versus flooding and LBP, but its higher per-iteration complexity creates a throughput and latency trade-off.Min-sum approaches can have lower per-iteration complexity but may require more iterations to match SPA performance.Source: §I · p. 2
  • C&R-RBP and C&DR-RBP use Consensus and Return to exploit updated information and mitigate greedy RBP degradation while retaining the original RBP’s residual-calculation complexity.C&DR-RBP delays Return until after a small number of iterations and is reported to need fewer iterations for a given error-rate performance.Source: §I · p. 2

A. Channel Model and Modulation

  • The communication model encodes source bits into a codeword, maps bits to BPSK symbols, and models reception with AWGN; the theoretical analysis uses that channel assumption.The receiver computes soft LLRs from the received signal as initial information for iterative decoding.Source: A. Channel Model and Modulation · pp. 2–3

B. LDPC codes

  • LDPC codes are sparse linear block codes represented by Tanner graphs whose variable nodes represent codeword bits and check nodes represent parity-check equations.The 5G NR codes considered are irregular, with non-uniform node degrees.Source: B. LDPC codes · p. 3

C. Problem Statement

  • The paper targets reliable recovery of transmitted codewords from noisy observations while reducing iterations and computational complexity to limit decoding latency.The objective is to retain complexity similar to existing RBP-based algorithms.Source: C. Problem Statement · p. 3

III. PROPOSED C&R-RBP AND C&DR-RBP ALGORITHMS

The section reviews message passing and residual-based scheduling before presenting C&R-RBP’s Consensus and Return modifications to reduce error-rate degradation and the iterations needed for a target error rate.

A. Message-passing

  • Message passing exchanges C2V and V2C messages, with the update order defining the schedule and decoding stopping when checks pass or the iteration limit is reached.The Tanner graph has variable nodes for coded bits and check nodes for parity-check equations.Source: A. Message-passing · p. 3

B. Dynamic Scheduling using residuals

C. Proposed C&R-RBP Algorithm

  • C&R-RBP adds Consensus updates for the selected variable node’s remaining C2V messages and returns its V2C message to the selected check node.Consensus seeks to reduce bias from a single C2V message and error propagation; stored precomputed messages avoid increasing residual-calculation complexity.Source: C. Proposed C&R-RBP Algorithm · p. 4, Figure 3 · p. 4

D. Proposed C&DR-RBP Algorithm

C&DR-RBP delays Return to improve early-iteration performance, while the analysis examines complexity and the effect of Consensus on initial bit decisions.

D. Proposed C&DR-RBP Algorithm

IV. ANALYSIS

  • The analysis covers C2V, V2C, and residual calculations, real-value comparisons, and Consensus’s effect on correct bit decisions under initial decoding conditions.Source: §IV · p. 5

A. Computational Complexity

  • Proposed methods reuse messages computed during residual evaluation, requiring zero separate C2V calculations; C&R-RBP matches classical RBP in residual-calculation count.Table I summarizes per-iteration C2V, V2C, residual, and real-value comparison counts across methods.Source: A. Computational Complexity · p. 5, Table I · p. 6

B. Analysis of Consensus under Initial Conditions

The analysis explains how RBP's largest-residual rule can favor reliable information yet risk propagating severe errors. It shows that Consensus increases the probability of correct bit decisions under initial decoding conditions when severe bit errors occur.

1) Severe bit errors:

  • RBP's largest-residual rule tends to select the C2V message for the most reliable type-1 VN set, but can select one containing a large-magnitude flipped observation.A type-1 VN set comprises the VNs connected to one check node except the target VN, and each C2V message corresponds to a distinct set.Source: 1) Severe bit errors · p. 6

2) Probability of correct decision given severe bit error:

  • Under the AWGN assumption, independent Gaussian LLRs and properties of the C2V update establish E(∆) < 0, making the sufficient condition hold for severe-error events.The analysis uses this result to show that Consensus improves the probability of a correct bit decision under the stated initial conditions.Source: 2) Probability of correct decision… · p. 7
  • Under initial decoding conditions, Consensus increases the probability of correct bit decisions when a severe transmission error is present, mitigating degradation linked to RBP's greedy behavior.The analysis concludes that the severe-error condition implies the inequality used to establish the improvement in correct-decision probability.Source: 2) Probability of correct decision… · pp. 6–8

V. CONSIDERATIONS REGARDING 5G NR CODES

The paper discusses structural features of 5G NR LDPC codes that affect informed dynamic scheduling, then uses standard decoding settings for a common comparison of RBP-based methods.

V. CONSIDERATIONS REGARDING 5G NR CODES

  • The simulations use 5G NR coding because the authors regard the standard as practically relevant and rapidly growing.The paper frames its discussion of code structure around latency and computational complexity in informed dynamic scheduling.Source: §V · p. 8
  • 5G NR codes can make informed dynamic scheduling inefficient through degree-1 VNs and punctured VNs, motivating specialized D1VN processing and least-punctured scheduling.Repeatedly updating degree-1 VNs adds little beyond their intrinsic channel information; punctured-node patterns can also make some check-node updates especially useful.Source: §V · p. 8
  • The study uses standard decoding settings without code-structure-specific mechanisms to compare new RBP-based strategies and existing RBP-like methods under a common framework.The authors state this choice is intended to ensure a fair and consistent comparison.Source: §V · p. 8

VI. IMPLEMENTATION AND PARALLELIZATION

The paper distinguishes hardware- and software-based LDPC decoder implementation, describing trade-offs and examples of platforms and acceleration techniques.

VI. IMPLEMENTATION AND PARALLELIZATION

  • Hardware implementations using ASICs or FPGAs can provide low latency and high throughput but generally require more development effort and hardware resources.The paper notes FPGA flexibility, processing speed, and parallelism as useful for prototyping and small production runs.Source: §VI · p. 8
  • Software decoders can reduce hardware resources and development time while allowing functionality updates without changing the underlying hardware.The paper describes software implementations running compiled programs on general-purpose processors.Source: §VI · p. 9
  • Software targets such as GPUs and general-purpose processors support programmable, reconfigurable, and scalable decoding; vector units and instruction-set extensions can reduce execution time.The paper cites AVX-512 as an example used to accelerate LDPC decoding.Source: §VI · p. 9

A. Parallelization and IDS methods

The section weighs the performance cost of parallelizing residual-based decoding against its potential latency benefit, then evaluates the proposed algorithms on several 5G NR code settings. Across the reported simulations, C&DR-RBP is strongest in early iterations, while C&R-RBP generally improves over competitors after initial iterations.

A. Parallelization and IDS methods

  • Parallelizing the p largest residual updates can reduce processing time per iteration, but its performance degradation may require more iterations and offset some latency savings.The degradation tends to become more pronounced as p increases.Source: A. Parallelization and IDS methods · p. 9

A. General Framework

  • The evaluation compares C&R-RBP and C&DR-RBP with state-of-the-art methods on 5G NR codes, using Monte Carlo simulations and a residual-decay factor β = 0.85.The framework covers different code lengths, rates, and Eb/N0 ranges; the compared RBP-based methods have the same residual-calculation complexity.Source: §VII · p. 9, A. General Framework · pp. 9–10

B. Simulation 1: Code Length = 576, R = 1/2

  • C&DR-RBP outperforms all competitors at every iteration for the length-576, rate-1/2 code; C&R-RBP outperforms them from iteration 3.At Eb/N0 = 3.0 dB, C&DR-RBP also improves over C&R-RBP during initial iterations and needs fewer iterations to reach a given error rate.Source: Figure 5 · p. 9, B. Simulation 1: Code Length = 576, R… · p. 10

C. Simulation 2: Code Length = 1248, R = 1/2

D. Simulation 3: Code Length = 1248, R = 2/3

E. Simulation 4: Code Length = 576, R = 5/6

The simulations test the proposed decoders in a high-rate AWGN setting and under Rayleigh fading, alongside comparisons of iteration counts and a latency model. C&DR-RBP remains competitive in both channel settings, including early iterations.

G. Comparison Tables

E. Simulation 4: Code Length = 576, R = 5/6

  • In the high-SNR, rate-5/6 setting, C&DR-RBP has the most competitive FER and BER performance, while C&R-RBP improves after its initial iterations.C&R-RBP is weak in FER through iteration 3; its performance improves from iteration 4 for FER and iteration 3 for BER.Source: E. Simulation 4: Code Length = 576, R… · p. 11, Figure 11 · p. 12

VIII. DECODING LATENCY AND MEMORY ANALYSIS

  • The latency analysis estimates decoding time from iteration count, average operations per iteration, and processor cycles per operation, assuming sequential processing on a GPP-oriented model.It sets PCO = 1 for comparisons; results for another PCO scale by that value.Source: §VIII · pp. 12–14

F. Simulation 5: Code Length = 576, R = 1/2 (Fading Channel)

1) C2V and Residual Calculation:

  • The C2V and residual calculation estimate counts message reads, sign and magnitude calculations, nonlinear operations, and residual read, calculation, and write steps.The residual steps add four operations to the Table V total.Source: 1) C2V and Residual Calculation · p. 14

2) Approximation of Function

This section estimates the operation costs of function approximation and several RBP-based decoding algorithms. It describes how residual-search costs can be reduced in practice and reports operation-count observations for RBP and its variants.

2) Approximation of Function

  • Evaluating ϕ is computationally expensive, motivating approximation to reduce implementation complexity while preserving calculation accuracy.A cited scheme uses non-uniform quadratic segments, with parameters chosen for each segment.Source: 2) Approximation of Function · p. 14
  • For S segments, evaluation requires up to S −1 comparisons and segment-bound reads, five polynomial operations, three coefficient reads, and one result write.The polynomial is y = ax2 + bx + c.Source: 2) Approximation of Function · p. 14

3) Real Value Comparisons:

  • The theoretical search uses E −1 comparisons and E memory accesses, while maintaining per-check-node maxima can reduce the practical search cost.The procedure selects the check node with the largest stored maximum, searches its residuals, and updates that maximum.Source: 3) Real Value Comparisons · pp. 14–15, Table VI · p. 15

4) Global estimate for RBP:

  • For a 576-code with R = 1/2, residual calculations and real-value comparisons are major operation contributors, while comparisons are below the theoretical 2E −1 = 4175.The section gives average-operation estimates for RBP in Table VII.Source: 4) Global estimate for RBP · p. 15, Table VII · p. 15

5) Global estimate for RD-RBP:

  • RD-RBP adds three operations per C2V update for βi,j and two per residual evaluation; average operation estimates are reported in Table VIII.The added C2V-update operations read, multiply, and write the decay coefficient.Source: 5) Global estimate for RD-RBP · p. 15, Table VIII · p. 15

6) List-RBP:

  • List-RBP incurs list-removal and reordering costs, including 2S1( dv̄ −1)( dc̄ −1) operations for processing newly calculated residuals.The estimate uses list sizes S1 = 16 and S2 = 2, as in the simulations.Source: 6) List-RBP · p. 15, Table IX · p. 15

7) C&R-RBP and C&DR-RBP estimates:

The section estimates the proposed algorithms’ operation, latency, and memory costs. It reports lower operations per iteration for C&R-RBP, latency reductions for both methods in specified decoding settings, and modestly higher memory use.

7) C&R-RBP and C&DR-RBP estimates:

  • C&R-RBP stores precomputed C2V messages; its estimated cost per residual calculation is dc̄(K + 5) + 2, including Return-related work.C&R-RBP reduces algorithm loops from E to E − N, and the reported total operations per iteration are lower on average.Source: 7) C&R-RBP and C&DR-RBP estimates · pp. 15–16

8) Other RBP-based algorithms:

  • The estimates treat NW-RBP, SVNF, and UBP-RBP as having the same operation count as RBP because their operation counts do not differ significantly.This is a simplifying assumption for the comparison.Source: 8) Other RBP-based algorithms · p. 16

B. Estimating the Latency

C. Memory Requirements

  • For a 5G NR 576-code at rate 1/2, the proposed methods require approximately 305 KB, 5.9% more memory than other RBP-based algorithms and 13.2% more than List-RBP.The estimate includes E additional real values for storing precomputed C2V messages.Source: C. Memory Requirements · p. 17, Table XV · p. 17

IX. CONCLUSIONS

  • Both methods outperform same-complexity IDS RBP-based decoders; the analysis supports Consensus under initial and severe-error conditions, while broader channel models remain future work.The identified future settings include Rician fading, impulsive noise, correlated channels, and other non-Gaussian environments.Source: §IX · p. 17

APPENDIX A – PROOF OF THEOREM 1

The proof uses induction to establish an oddness property of a recursively defined function, then derives the stated expectation identity through successive integral transformations.

APPENDIX A – PROOF OF THEOREM 1

  • The proof establishes by induction that Gj is odd with respect to each of its arguments.The base case is immediate, and the induction step applies the recursive definition.Source: Appendix A · p. 17
  • Assuming E(M) exists, induction establishes equation (42), beginning with independent Lj variables and the base case j = 1.The proof transforms the innermost integrals and substitutes the resulting Gj functions successively to complete the induction.Source: Appendix A · pp. 17–18

APPENDIX B – PROOF OF COROLLARY 1

The proof relates the sign of E(M) to the product of the signs of the Gaussian means by analyzing the sign of the integral’s integrand.

APPENDIX B – PROOF OF COROLLARY 1

  • With Gaussian Lj, the sign of the integral determining E(M) is set by the product of hyperbolic-sine signs, matching the sign of the product of the means.The proof uses nonnegative integration variables and nonnegative weights in the integrand.Source: Appendix B · p. 18

APPENDIX C – PROOF OF THEOREM 2

The appendix examines how C&DR-RBP’s performance varies with its delay choice and refines the comparison count for List-RBP. It also closes the proof of Theorem 2 with a minimum-message expression.

APPENDIX C – PROOF OF THEOREM 2

  • Theorem 2’s proof uses properties (ii) and (iii) to obtain a minimum absolute incoming-message magnitude over neighboring variable nodes other than v_j.The displayed expression is min over v_k∈V(c_i)\{v_j} of |m_v_k→c_i|.Source: Appendix C · p. 19

APPENDIX D – REAL VALUE COMPARISONS OF LIST-RBP

  • The revised List-RBP comparison estimate includes checks for adding residuals to the local list and partially updating the main list.The first operation requires S2 comparisons per iteration, and the second requires S1S2 comparisons.Source: Appendix D · p. 19

APPENDIX E – SENSITIVITY TO i0

  • Across simulations, sensitivity to i0 is strongest in early iterations; i0=3 favors later iterations, with only negligible disadvantage beyond iteration 8.In Simulation 1, i0=3 improves iteration 2 over i0=2, slightly worsens iteration 3, and performs best for iterations i≥5; Simulation 2 reports i0>3 better at iterations 3–4, while i0=3 is better at 5–8.Source: Appendix E · p. 19
Loading 2610.14387v1…