Fast factorization architecture in soft-decision Reed-Solomon decoding

Reed-Solomon (RS) codes are among the most widely utilized block error-correcting codes in modern communication and computer systems. Compared to hard-decision decoding, soft-decision decoding offers considerably higher error-correcting capability. Among the soft-decision decoding algorithms, the polynomial time complexity Koetter-Vardy (KV) algorithm can achieve substantial coding gain for high-rate RS codes. In the KV algorithm, the factorization step can consume a major part of the decoding latency. A novel architecture based on root-order prediction is proposed to speed up the factorization step. As a result, the time-consuming exhaustive-search-based root computation in each iteration of the factorization step is circumvented with more than 99% probability. Using the proposed architecture, a speedup of 141% can be achieved over prior efforts for a (255, 239) RS code, while the area consumption is reduced to 31.9%.