Decoding of Interleaved Reed Solomon Codes over Noisy Data

Daniel Bleichenbacher, Aggelos Kiayias, Moti Yung

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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
Title of host publicationAutomata, Languages and Programming
Subtitle of host publication30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 -- July 4, 2003 Proceedings
EditorsJos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Woeginger
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages12
ISBN (Electronic)978-3-540-45061-0
ISBN (Print)978-3-540-40493-4
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


Dive into the research topics of 'Decoding of Interleaved Reed Solomon Codes over Noisy Data'. Together they form a unique fingerprint.

Cite this