Quasi-BP for BCH Codes and its Optimization

Quasi-Belief Propagation Decoding for BCH Codes: Architecture, Optimization, and Performance Analysis

Background and Motivation

The decoding of high-density parity-check (HDPC) codes, such as BCH codes, has traditionally relied on algebraic and hard-decision schemes to achieve reliable error correction, particularly in storage and deep-space communications owing to their superior minimum distance properties. While LDPC codes, with their sparse parity-check matrices, enable highly effective and scalable belief propagation (BP) decoding, applying BP to BCH codes has proven suboptimal due to Tanner graph density and the proliferation of short cycles, leading to degraded iterative performance and error floors at high SNR. Recent advances, including ordered statistics decoding (OSD) and neural BP techniques, have improved decoding for short codes, yet they lack parallelizability and general applicability in low-latency scenarios.

The paper "Quasi-BP for BCH Codes and its Optimization" (2604.04066) introduces a quasi-belief propagation (quasi-BP) decoder that systematically leverages knowledge of channel noise variance, the code’s cyclic automorphism property, and deliberate redundancy in the parity-check matrix (H) to enable efficient, parallelizable iterative decoding for BCH codes. By formalizing the decoder within an information-theoretic framework and using scattered EXIT charts (S-EXIT), the approach achieves performance comparable to LDPC BP decoders at similar rates and blocklengths, thus significantly narrowing a previously persistent gap.

Decoder Architecture and Information-Theoretic Analysis

The quasi-BP decoder exploits structural properties of BCH codes via two key mechanisms: redundancy augmentation in H and automorphism-driven input dilation. The decoding process is as follows:

• Preprocessing: Optimize H for redundancy using a factor $\delta_1$, and specify a dilation factor $\delta_2$ for expanded message sets.
• Initialization: Channel log-likelihood ratios (LLRs) are computed; check-to-variable messages are set to zero.
• Variable Node Update:
  • Phase One (Alignment & Merging): Incoming check-to-variable messages are blockwise cyclically reversed to harmonize with pre-dilation inputs. A merging operation, parameterized by a weight $\beta$, aggregates these messages, accelerating MI growth and aiding convergence.
  • Phase Two (Input Dilation): Using code automorphisms, the input is dilated by $\delta_2$, propagating expanded messages to check nodes.
• Check Node Update: Standard BP-style (tanh-based) updates are deployed, with min-sum or normalized min-sum (NMS) approximations available as lower-complexity alternatives.
• Hard Decision and Termination: Tentative codeword decisions are evaluated; decoding ceases early if the parity-check equations are satisfied.

The architecture supports full parallelizability, allowing identical operations on each received bit and facilitating hardware-efficient deployments.

A rigorous information-theoretic formalization is provided using MI tracking between variable and check nodes, with S-EXIT charts replacing conventional EXIT analysis to accommodate finite-length randomness. The MI evolution curves inform key optimization decisions regarding $\beta$, $\delta_1$, $\delta_2$, and iteration count $l_{\mathrm{max}}$, balancing decoding efficacy against computational burden.

Optimization via Scattered EXIT Charts

S-EXIT charts enable parameter optimization for the quasi-BP decoder. The following optimization insights are emphasized:

• Iteration Count Selection: MI evolution curves display asynchronous peaks and declines between variable and check nodes. The intersection point of their curves plus a small offset yields an empirically justified $l_{\mathrm{max}}$, minimizing complexity without loss in FER.
• Thresholding for FER Estimation: MI-based thresholds (e.g., $T=0.7$) facilitate efficient FER approximation, requiring far fewer simulated codewords for statistical stability.
• Redundancy and Dilation Factors: Larger $\delta_2$0 and $\delta_2$1 accelerate and elevate MI growth, but the benefit diminishes at higher SNRs or excessive values, mandating a careful complexity-performance tradeoff.

Numerical Results and Performance Benchmarks

Extensive simulations confirm quasi-BP’s competitive performance across BCH codes of various rates and blocklengths. Key numerical highlights include:

• BCH(127,64) vs. LDPC(128,64): Quasi-BP achieves FER performance nearly matching LDPC BP and neural BP decoders, with slopes indicating no widening gap at high SNR. Notably, the quasi-BP decoder eliminates error floors due to BCH's dense structure.
• BCH(127,99) and BCH(255,239): Quasi-BP consistently leads traditional NMS and neural BP-RNN decoders by at least 0.5–0.6 dB at relevant BER/FER levels. The gap to ML decoding remains, but concatenation with OSD can bridge this with modest latency overhead.
• Complexity Analysis: Although quasi-BP introduces a worst-case complexity multiplier ($\delta_2$2 per iteration), MI convergence is rapid, reducing the average iteration count and yield. S-EXIT based parameter tuning mitigates practical computational costs.

A distinct performance advantage is observed for quasi-BP in high-rate, long BCH codes, particularly under parallelized hardware execution, where early hard-decision decoders or sequential OSD would be prohibitive.

Practical and Theoretical Implications

From a practical standpoint, quasi-BP validates the feasibility of high-performance parallel soft decoding for HDPC codes, challenging entrenched perceptions about BP suitability. The decoder's full parallelizability aligns with modern hardware accelerators (GPU, TPU), paving the way for real-time, high-throughput BCH code deployment in communication and storage.

Theoretically, the work demonstrates that S-EXIT chart analysis extends efficiently to dense, finite-length codes, quantifying convergence and guiding optimization. The merging and dilation steps, leveraging code automorphism and matrix redundancy, constitute a robust mechanism for mitigating short-cycle induced message correlation while driving MI growth.

Future research avenues include numerically stable approaches for the tanh product computation in long BCH codes, further complexity reductions, and hybridization with OSD or neural methods to approach ML performance seamlessly.

Conclusion

The quasi-BP decoder for BCH codes represents a substantial enhancement in soft iterative decoding for HDPC structures, achieving performance parity with LDPC BP decoders without sacrificing parallelizability or hardware compatibility. By integrating channel knowledge, code automorphisms, and scattered EXIT chart optimization, the architecture enables efficient decoding across a wide array of code parameters. The research opens new potential for practical BCH deployment in advanced communication systems and justifies further investigation into hybrid decoding architectures and numerical stability techniques for long codes.