Decoding interleaved Reed–Solomon codes over noisy channels

Daniel Bleichenbacher, Aggelos Kiayias, Moti Yung

Research output: Contribution to journalArticlepeer-review


We consider error correction over the Non-Binary Symmetric Channel (NBSC) which is a natural probabilistic extension of the Binary Symmetric Channel (BSC). We propose a new decoding algorithm for interleaved Reed–Solomon codes that attempts to correct all “interleaved” codewords simultaneously. In particular, interleaved encoding gives rise to multi-dimensional curves and more specifically to a variation of the Polynomial Reconstruction Problem, which we call Simultaneous Polynomial Reconstruction. We present and analyze a novel probabilistic algorithm that solves this problem. Our construction yields a decoding algorithm for interleaved RS codes that allows efficient transmission arbitrarily close to the channel capacity in the NBSC model.
Original languageEnglish
Pages (from-to)348 - 360
Number of pages13
JournalTheoretical Computer Science
Issue number3
Publication statusPublished - 15 Jun 2007


  • Polynomial reconstruction


Dive into the research topics of 'Decoding interleaved Reed–Solomon codes over noisy channels'. Together they form a unique fingerprint.

Cite this