CRT-Based High-Speed Parallel Architecture for Long BCH Encoding

Hao Chen

Abstract

Bose-Chaudhuri-Hocquenghen (BCH) error-correcting codes are fundamental components in modern digital communication and storage systems. However, traditional encoding methods based on Linear Feedback Shift Registers (LFSRs) face significant scalability issues when applied to long BCH codes. These issues primarily stem from serial-in/serial-out limitations and the "fanout effect," where high-degree generator polynomials require a single signal to drive an excessive number of XOR gates, creating propagation delays. This paper proposes a novel parallel architecture based on the Chinese Remainder Theorem (CRT) to eliminate these bottlenecks. By decomposing the encoding operation into parallel paths based on the irreducible factors of the generator polynomial, the architecture limits the maximum gate delay to a factor of $\log_2 N$, where $N$ is the code length.

Introduction

As data transmission speeds increase in optical and satellite communications, the demand for robust, long-block-length error correction codes has grown. BCH codes are widely favored for their performance, but their hardware implementation at high speeds is non-trivial. The standard LFSR-based encoder is inherently serial. While parallelization techniques like J-unfolding have been proposed, they often involve complex algebraic manipulations and do not always resolve the fanout bottleneck effectively. In a long BCH code, the generator polynomial $g(x)$ can have a very high degree, leading to hardware designs where a single signal must drive hundreds of XOR gates simultaneously, forcing a reduction in the system's clock frequency.

The CRT-Based Parallel Architecture

The proposed architecture leverages the mathematical structure of the BCH generator polynomial. A generator polynomial $g(x)$ is the product of several smaller, distinct irreducible polynomials $w_1(x), w_2(x), \dots, w_r(x)$.

Mathematical Decomposition

Instead of performing a single division by $g(x)$ to find the remainder (the parity bits), the CRT-based approach decomposes the process into four primary steps:

  1. Decomposition: The input message is split into $r$ parallel paths.
  2. Parallel Processing: The system performs smaller multiplications and divisions modulo each irreducible factor $w_i(x)$ simultaneously.
  3. Intermediate Computation: The results from the parallel paths are processed through dedicated LFSR circuits.
  4. Reconstruction: The final codeword is reconstructed by summing the results of these parallel operations.

Because the degree of each irreducible factor $w_i(x)$ is much lower than the degree of $g(x)$—typically around $\log_2 N$—the number of XOR gates any single signal must drive is strictly capped. This allows the hardware to maintain a much higher clock frequency.

Performance Evaluation and Results

The architecture was evaluated using several BCH code configurations to demonstrate the reduction in hardware complexity and the increase in potential throughput.

Fanout Reduction

The primary metric of success is the reduction of the maximum fanout. In a test case involving a long BCH code with a length of 2047 and a degree-121 generator polynomial, the CRT architecture reduced the maximum fanout from over 100 to just 11. In an even longer code (length 8191, degree-507), the fanout was capped at 13. This reduction is critical because it allows the clock period to be significantly shorter, enabling higher bits-per-second throughput despite the increased complexity of the parallel paths.

Hardware Complexity

While the CRT approach is highly efficient in terms of speed, it does require a larger silicon area. For the degree-507 code, the architecture utilizes approximately 20,865 XOR gates. However, the authors argue that this trade-off is necessary and superior to previous parallel methods for high-speed applications where the serial bottleneck of traditional LFSRs is the primary limiting factor.

Discussion and Limitations

While the CRT-based architecture offers a significant speed advantage for BCH codes, it has specific limitations:

  • Incompatibility with CRCs: This method cannot be applied to long Cyclic Redundancy Check (CRC) codes. CRC generator polynomials are typically irreducible, meaning they cannot be factored into smaller components to facilitate the CRT decomposition.
  • Latency: The multi-stage nature of the architecture (multiplication, division, and reconstruction) introduces inherent latency. While the throughput (total data processed over time) is high, the time taken for a single message to be encoded may be higher than in a serial design.
  • Optimization Potential: Future work may focus on selecting generator polynomials whose factors have fewer non-zero coefficients (low weight), which would further reduce the total XOR gate count and power consumption.

Conclusion

The CRT-based parallel architecture provides a mathematically grounded solution to the fanout bottleneck in long BCH encoding. By shifting the hardware limitation from the total degree of the generator polynomial to the degree of its irreducible factors, the architecture ensures that encoding speeds can scale with the logarithm of the code length. This makes it a highly viable candidate for next-generation, high-speed communication systems.

Summary updated

Abstract

Bose-Chaudhuri-Hocquenghen (BCH) error-correcting codes are now widely used in communication system and digital technology. The direct linear feedback shifted register (LFSR)-based encoding of a long BCH code suffers from the large fan-out effect of some XOR gates. This makes the LFSR-based encoders of long BCH codes not keep up with the data transmission speed in some applications. The technique for eliminating the large fan-out effect by J-unfolding method and some algebraic manipulation has been proposed. In this brief, we present a Chinese remainder theorem (CRT)-based parallel architecture for long BCH encoding. Our novel technique can be used to eliminate the fan-out bottleneck. The only restriction on the speed of long BCH encoding of our CRT-based architecture is log <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> N, where N is the length of the BCH code.
BibTeX
@article{chen2009crt,
  author = {Hao Chen},
  title = {{CRT-Based High-Speed Parallel Architecture for Long BCH Encoding}},
  journal = {IEEE Transactions on Circuits \& Systems II Express Briefs},
  year = {2009},
  doi = {10.1109/tcsii.2009.2024247},
}
Figure