Abstract
Reed-Solomon (RS) codes are among the most widely utilized block error-correcting codes in modern communication and computer systems. Compared to its hard-decision counterpart, soft-decision decoding offers considerably higher error-correcting capability. The recent development of soft-decision RS decoding algorithms makes their hardware implementations feasible. Among these algorithms, the Koetter-Vardy (KV) algorithm can achieve substantial coding gain for high-rate RS codes, while maintaining a polynomial complexity with respect to the code length. 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 in this paper to speed up the factorization step. As a result, the time-consuming exhaustive-search-based root computation in each iteration level, except the first one, 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.4%.
Original language | English (US) |
---|---|
Pages (from-to) | 413-426 |
Number of pages | 14 |
Journal | IEEE Transactions on Very Large Scale Integration (VLSI) Systems |
Volume | 13 |
Issue number | 4 |
DOIs | |
State | Published - Apr 2005 |
Bibliographical note
Funding Information:Manuscript received April 30, 2004; revised October 9, 2004. This work was supported by the Army Research Office under Grant W911NF-04-1-0272. The authors are with the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA (e-mail: [email protected]; [email protected]). Digital Object Identifier 10.1109/TVLSI.2004.842914
Keywords
- Chien search
- Factorization
- Guruswami-Sudan algorithm
- Koetter-Vardy (KV) algorithm
- Reed-Solomon (RS) code
- Root-order prediction
- Soft-decision decoding
- VLSI architecture