Low-Complexity Parallel Chien Search Architecture Based on Vandermonde Matrix Decomposition

Reed-Solomon (RS) and BCH codes are among the most broadly used error-correcting codes in digital communication and storage systems. The Chien search step accounts for a significant part of the overall decoder complexity of these codes. The Chien search can be expressed as a Vandermonde matrix multiplication. This brief develops a novel Vandermonde matrix decomposition that significantly reduces the number of multiplications needed for the Chien search. Further reformulation on the matrix decomposition is also proposed to enable efficient parallel processing in hardware implementation. Accordingly, a low-complexity parallel Chien search architecture is designed. For example, <tex-math notation="LaTeX">$9$</tex-math> -error-correcting RS or BCH code over <tex-math notation="LaTeX">GF(2¹⁰)</tex-math> , the proposed design with <tex-math notation="LaTeX">$40$</tex-math> -, <tex-math notation="LaTeX">$60$</tex-math> -, and <tex-math notation="LaTeX">$80$</tex-math> -parallel processing achieves <tex-math notation="LaTeX">$11%$</tex-math> , <tex-math notation="LaTeX">$14%$</tex-math> , and <tex-math notation="LaTeX">$17%$</tex-math> , respectively, area reduction compared to the best prior design with the same throughput and similar latency.