Fast Syndrome-Based Chase Decoding of Binary BCH Codes Through Wu List Decoding

Yaron Shany, Amit Berman

TL;DR

This paper introduces a significantly faster syndrome-based Chase decoding algorithm for binary BCH codes, achieving a roughly 5x reduction in complexity over previous state-of-the-art methods. By establishing a novel theoretical link between Wu list decoding and Chase decoding, the authors demonstrate that for binary alphabets, assigning a "multiplicity of 1" to a bit is mathematically equivalent to flipping it, allowing for much more efficient polynomial updates.

What Problem Does This Paper Address?

Binary Bose-Chaudhuri-Hocquenghem (BCH) codes are workhorses in modern digital storage (like Flash memory) and communication systems. While Hard-Decision (HD) decoding is fast, it leaves performance on the table. Soft-Decision (SD) decoding, specifically Chase decoding, improves reliability by testing multiple "error patterns" on the least reliable bits of a received message.

The challenge is that Chase decoding is computationally expensive; it essentially requires running a decoder many times. "Fast Chase" algorithms attempt to share computations between these trials using a tree structure. However, existing fast Chase algorithms—often adapted from Reed-Solomon (RS) codes—don't fully exploit the unique properties of the binary alphabet, leading to higher-than-necessary polynomial degrees and redundant iterations.

Methods

The authors combine algebraic geometry and coding theory to streamline the decoding process:

  1. Solution-Module Isomorphism: They prove a mathematical isomorphism between the standard "key equation" (used to find error locations) and a "modified key equation." In the binary case, this allows them to halve the problem's dimensions, working with polynomials of much lower degrees.
  2. Single Kötter Iteration: Traditional fast Chase algorithms for RS codes require two Kötter iterations (the standard update step for these polynomials) per edge of the decoding tree. The authors reduce this to a single iteration per edge by exploiting the binary nature of the code.
  3. The Wu Connection: They leverage the Wu list decoding algorithm. A key theoretical insight is that when the list size is 1, assigning a multiplicity of 1 to a coordinate in the Wu algorithm has the same effect as flipping that bit in a Chase trial.
  4. Gröbner Bases: The algorithm is formulated using Gröbner bases over modules, providing a systematic way to track and update the Error Locator Polynomials (ELPs) as the decoder moves through the trial tree.

Datasets

As a theoretical and algorithmic paper, it does not use standard "big data" sets. Instead, the authors evaluate their algorithm using:

  • Synthetic Error Patterns: They use random error vectors and simulated channel reliability information to test the algorithm's stopping criteria.
  • Specific Code Parameters: For example, they demonstrate empirical results using a $q=256$ ($n=255$) code with a designed distance of $t=8$.

Key Insights and Ideas

  • Multiplicity = Bit Flipping: The "aha moment" is the realization that the complex "multiplicity" math used in advanced list decoding simplifies perfectly into "bit flipping" for binary codes. This bridges two previously distinct areas of algebraic decoding.
  • Halving the Dimensions: By using the binary-specific isomorphism, the authors show that HD decoding can be performed in a module with half the dimensions, which is inherently faster than treating a binary code as a general $q$-ary code.
  • Lower Degree Polynomials: Because the algorithm tracks "coefficient polynomials" rather than the full ELP, the degrees of the polynomials being updated are much lower (roughly $2r$ vs $2(t+r)$), leading to massive savings in multiplications.

Key Results

  • 5x Speedup: The complexity of polynomial updates is reduced by a factor of approximately 5 compared to the authors' own recent state-of-the-art fast Chase algorithm for RS codes (IEEE Trans. IT, 2022).
  • Efficiency per Edge: The number of multiplications required to move along an edge in the decoding tree is reduced to $4r + 1$, compared to $20r + 3$ in previous benchmarks.
  • Syndrome-Based Advantage: Unlike "time-domain" algorithms that work on the entire received vector, this algorithm works on the much shorter syndrome vector, making it highly efficient for high-rate BCH codes used in hardware.

Limitations and Future Work

  • Stopping Criterion False Positives: The algorithm uses a "discrepancy-based" stopping criterion to avoid unnecessary exhaustive searches. While highly effective, it can occasionally trigger a false positive (estimated at a probability of $1/q$), which slightly increases average complexity but does not affect decoding accuracy.
  • Degraded Success Probability: To achieve the 5x speedup, the algorithm requires $r+1$ errors on unreliable coordinates (instead of $r$) to guarantee success in certain edge cases, a minor trade-off in decoding performance for a major gain in speed.
  • Future Directions: The authors suggest that their module-based approach could be formalized further and potentially applied to find new connections between other decoding algorithms, such as those for Reed-Solomon codes.

Summary updated

BibTeX
@article{shany2023fast,
  author = {Yaron Shany and Amit Berman},
  title = {{Fast Syndrome-Based Chase Decoding of Binary BCH Codes Through Wu List Decoding}},
  journal = {IEEE Trans. Information Theory},
  year = {2023},
  doi = {10.1109/tit.2023.3263185},
}
Figure