Stochastic erasure-only list decoding algorithms for Reed-Solomon codes

Chang Ming Lee*, Yu-Ted Su

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


We present a novel stochastic decoding algorithm for Reed-Solomon codes. We apply an iterative Monte Carlo based approach called the Cross-Entropy method to produce, in every iteration, a set of random error locator vectors, each indicates n-k possible erasure positions within a received word. We associate each error locator vector with a candidate codeword by erasures-only decoding the received word, using the error locator vector to locate the erasures. Each iteration results in a new elite set that contains the best E candidate codewords. To increase the search radius and enhance the decoder performance we use the randomly drawn samples to generate what we call virtual received words from which extra candidate codewords and thus candidate elite members can be obtained. The proposed algorithms offer both complexity and performance advantages over some existing algebraic decoding algorithms for high rate RS codes.

Original languageEnglish
Pages (from-to)691-694
Number of pages4
JournalIEEE Signal Processing Letters
Issue number8
StatePublished - 19 Jun 2009


  • Complexity theory
  • Convergence
  • Cross-Entropy method
  • Data mining
  • Decoding
  • Iterative decoding
  • List decoding
  • Monte Carlo methods
  • Probability density function
  • Reed-Solomon code

Fingerprint Dive into the research topics of 'Stochastic erasure-only list decoding algorithms for Reed-Solomon codes'. Together they form a unique fingerprint.

Cite this