Software implementation of Chien search process for strong BCH codes

The Chien search process is the most time- consuming portion in the software decoding of Bose-Chaudhuri- Hochquenghem (BCH) codes. It can be parallelized using a table look-up method, but a large memory space is required for a high parallel factor. In this paper, we propose to perform the Chien search process not on the standard basis but on the shifted one. By simply shifting the basis, we can reduce the size of the look-up table significantly, thereby shortening the execution time with a much larger parallel factor. The experimental results show that the parallel factor is approximately doubled while using the same memory space, and up to 35% of speedup is achieved.