An Ordered-Reliability-Bits Chase Decoding Algorithm for BCH Codes

Technical Summary: Ordered-Reliability-Bits Chase Decoding Algorithm for BCH Codes

Problem Statement
Short block-length channel coding is critical for applications such as ultra-reliable low-latency communications (URLLC) and optical transport networks (OTN). Bose-Chaudhuri-Hocquenghem (BCH) codes are widely used in these scenarios due to their strong algebraic structure and large minimum distance. While hard-decision decoding algorithms like Berlekamp-Massey (BM) are efficient, they are limited by the code's inherent error correction capability and cannot fully realize the potential performance of the code. Soft-decision decoding (SDD) offers improved performance but often incurs high computational complexity. Existing SDD approaches, such as the Chase algorithm and Guessing Random Additive Noise Decoding (GRAND), face a trade-off: achieving near-maximum-likelihood (ML) performance typically requires an exponential increase in decoding complexity (e.g., traversing $2^p$ test patterns in Chase decoding). The paper addresses the challenge of reducing this complexity while maintaining high decoding performance.

Methodology
The authors propose a low-complexity Ordered-Reliability-Bits Chase (ORB-Chase) decoding algorithm. This method modifies the traditional Chase algorithm in two primary ways:

1. Logical Weight-Based Test Error Pattern (TEP) Generation:
   Instead of generating test patterns based solely on the least reliable bits (LRB) or fixed combinations, the algorithm utilizes the logical weight as a metric to order TEPs.

   • Bits are sorted by reliability (ascending order of LLR magnitude).
   • The logical weight $w_L(e_n)$ of a test pattern is defined as the sum of the positions of the flipped bits in this sorted sequence ($w_L(e_n) = \sum i \cdot e_i$).
   • TEPs are generated in ascending order of their logical weights. For patterns with identical logical weights, an integer partition generator ensures they are sorted by ascending Hamming weight. This ordering approximates the likelihood of noise sequences, prioritizing the most probable error patterns.

2. Integer-Based Early Termination Criterion:
   The algorithm introduces a criterion to determine if a generated candidate codeword is the ML codeword, allowing the decoding process to terminate early without generating the full list of candidates.

   • The method adapts the "Optimality Criterion" from prior literature, which compares the correlation discrepancy of a codeword against a lower bound derived from the most reliable bits.
   • To reduce computational overhead, the authors replace floating-point reliability values with integer reliability representations. This is achieved by fitting a piecewise linear curve to the sorted reliability values and quantizing the slope to 1.
   • The termination condition checks if the sum of integer reliabilities of the flipped bits is less than or equal to the sum of integer reliabilities of the most reliable bits that could potentially be flipped to improve the metric. If satisfied, the current codeword is accepted as ML, and decoding stops.

Key Contributions

• Algorithm Design: The proposal of the ORB-Chase algorithm, which integrates logical weight ordering for TEP generation and an integer-based early termination mechanism.
• Complexity Reduction: The introduction of a flexible limit on the maximum number of test patterns ($\ell_{max}$) and an early termination condition that significantly reduces the number of required Berlekamp-Massey (BM) decoding calls compared to the traditional Chase algorithm.
• Approximation Validation: The demonstration that the integer-based criterion provides an accurate practical approximation of the ML identification process, with negligible performance loss compared to the floating-point Optimality Criterion.

Results
Simulation results were conducted for (127, 113, 5) BCH codes and (256, 239, 6) extended BCH (eBCH) codes over an AWGN channel with BPSK modulation.

• Performance vs. ORBGRAND: For the (127, 113, 5) code, the ORB-Chase algorithm with $\ell_{max}=16$ outperformed the ORBGRAND algorithm with $\ell_{max}=16$ by approximately 1.5 dB at a Block Error Rate (BLER) of $10^{-3}$. The ORB-Chase algorithm with $\ell_{max}=200$ approached the ML lower bound, whereas ORBGRAND required significantly more queries ($\ell_{max}=10^5$) to achieve similar performance.
• Complexity Comparison with Chase:
  • The average number of BM decoding calls was used as the primary complexity metric.
  • For the (127, 113, 5) code, at $E_b/N_0 = 6$ dB, the ORB-Chase algorithm reduced the average number of BM calls by 92.3% (for $\ell_{max}=16$) and 98.0% (for $\ell_{max}=200$) compared to the Chase algorithm achieving the same BLER performance.
  • Similar trends were observed for the (256, 239, 6) eBCH code, with complexity reductions of up to 98.1% at high SNR.
• Termination Efficacy: The integer-based early termination criterion was shown to make the same early-termination decisions as the floating-point Optimality Criterion in almost all simulated cases, validating its accuracy.

Significance and Claims
The paper claims that the ORB-Chase algorithm offers an excellent trade-off between error correction performance and computational complexity. By achieving near-ML performance with significantly fewer test patterns and BM decoding calls, the algorithm is presented as a promising candidate for practical applications requiring efficient soft-decision decoding of short BCH codes. The authors note that the algorithm's efficiency increases with higher $E_b/N_0$, where the average number of decoding attempts drops rapidly. Future work is identified as potentially optimizing the generation order of test error patterns further, but the current contribution focuses on the efficacy of the logical weight ordering and integer-based termination.