SOGRAND decoding of LDPC codes

Technical Summary: SOGRAND Decoding of LDPC Codes

Problem Statement
Long forward error correction (FEC) codes, such as Low-Density Parity-Check (LDPC) codes used in 5G, are typically constructed by concatenating shorter component codes. The performance of these systems relies heavily on the accuracy and hardware implementability of the Soft-Input Soft-Output (SISO) decoders for these component codes. LDPC codes utilize Single Parity Check (SPC) component codes. While Gallager's Sum-Product Algorithm (SPA) provides perfect soft output for SPC codes, its reliance on computationally intensive hyperbolic tangent functions ($\tanh$ and $\tanh^{-1}$) makes it difficult to implement efficiently in hardware. Consequently, approximations like Normalized Min-Sum (NMS) are widely used; they avoid complex functions but require identifying minimum values in "leave-one-out" sets for every bit, which presents specific circuit design challenges. The authors seek an alternative Check Node (CN) update algorithm that offers hardware-friendly complexity while maintaining or exceeding the performance of SPA and NMS.

Methodology
The paper introduces a specialization of the recently developed Soft Output Guessing Random Additive Noise Decoding (SOGRAND) algorithm for use as a CN update rule in LDPC decoding.

1. SOGRAND Fundamentals: Unlike traditional decoders that directly evaluate marginal per-bit extrinsic log-likelihood ratios (LLRs), SOGRAND identifies block-wise beliefs (likelihoods of codewords) by sequentially inverting putative noise effects. These noise effects are queried in order of likelihood based on channel properties and soft input.
2. Specialization to SPC: The authors apply SOGRAND to SPC codes, which are "even" codes (every codeword has zero parity). In this context, a noise effect $z_n$ identifies a valid codeword if and only if its parity matches the parity of the demodulated sequence.
3. Two Novel CN Update Rules: The paper derives two distinct update rules based on how the noise queries are generated:
   • Rule 1 (General): Uses a collection of noise queries $C$ without strictly enforcing parity constraints during the query generation phase. The update rule (Eq. 5) calculates the posterior probability by summing the likelihoods of valid codewords found in the query list, adjusting for the probability mass of unqueried sequences.
   • Rule 2 (Parity-Constrained): Restricts queries strictly to those with the correct parity. Since every such query identifies a codeword, the update rule (Eq. 6) simplifies the calculation by utilizing a fixed number of queries $L$ to guarantee $L$ codewords are found, replacing the summation term with a correction factor $\Psi$ derived from Gallager's formula.
4. Implementation Strategy: To determine the query order, the authors propose using a fixed table based on the ORBGRAND generator. This table defines a small set of patterns (e.g., $2L$ patterns for $L$ even and $L$ odd sequences) based on the rank-ordered reliability of the least reliable bits. This approach avoids complex real-time sorting, allowing the entire CN update to be computed in parallel within a small number of clock cycles (estimated at 3 or fewer).

Key Contributions

• Novel CN Update Algorithms: The paper establishes two new CN update rules for LDPC decoding derived from SOGRAND principles.
• Hardware Efficiency: The proposed algorithms are designed to be hardware-friendly. They replace the "leave-one-out" minimum finding of NMS and the transcendental functions of SPA with parallel likelihood computations and table lookups.
• Theoretical Distinction: The work highlights a philosophical shift from direct marginal bit evaluation (SPA) to block-wise belief identification followed by marginalization (SOGRAND).
• Performance Validation: The authors demonstrate that these new rules can achieve performance comparable to or better than SPA and NMS with a small list size ($L$).

Results
Simulations were conducted using 5G NR LDPC codes over an Additive White Gaussian Noise (AWGN) channel with BPSK modulation.

• List Size Impact: For list sizes $L \ge 8$, the Block Error Rate (BLER) and Bit Error Rate (BER) performance showed negligible improvement with further increases in $L$.
• Comparison with Baselines: With a list size of $L=10$ and a scaling factor $\alpha=0.9$, the SOGRAND-based decoders matched or outperformed both the standard SPA and the NMS approximations.
• Robustness: The results were consistent regardless of whether the "even code" property was explicitly exploited (Rule 2) or if both even and odd parity queries were processed (Rule 1).
• Complexity: The authors note that existing hardware implementations of GRAND can compute the necessary likelihoods in a single clock cycle, suggesting the new CN updates can be integrated with minimal latency overhead.

Significance and Claims
The paper claims to provide an alternative to existing CN update mechanisms that is both hardware-efficient and high-performing. By specializing SOGRAND to SPC codes, the authors establish a new means of decoding LDPC codes that avoids the computational bottlenecks of SPA and the specific circuit complexities of NMS. The work suggests that the block-wise belief approach of SOGRAND offers a viable path for high-speed, low-complexity LDPC decoding in future communication systems. The authors modestly frame this as a new update rule within the iterative decoding framework, while noting that the underlying ability of SOGRAND to assess multiple parity checks simultaneously may offer opportunities for further development.