Fast factorization architecture in soft-decision Reed-Solomon decoding

Xinmiao Zhang, Keshab K. Parhi

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


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 languageEnglish (US)
Pages (from-to)413-426
Number of pages14
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Issue number4
StatePublished - 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:; Digital Object Identifier 10.1109/TVLSI.2004.842914


  • Chien search
  • Factorization
  • Guruswami-Sudan algorithm
  • Koetter-Vardy (KV) algorithm
  • Reed-Solomon (RS) code
  • Root-order prediction
  • Soft-decision decoding
  • VLSI architecture


Dive into the research topics of 'Fast factorization architecture in soft-decision Reed-Solomon decoding'. Together they form a unique fingerprint.

Cite this