3 RSA Laboratories

Abstract. We consider error-correction over the Non-Binary Symmet-ric Channel (NBSC) which is a natural probabilistic extension of the Binary Symmetric Channel (BSC). We propose a new decoding algo-rithm for interleaved Reed-Solomon Codes that attempts to correct all “interleaved ” codewords simultaneously. In particular, interleaved en-coding gives rise to multi-dimensional curves and more specifically to a variation of the Polynomial Reconstruction Problem, which we call Si-multaneous 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 trans-mission arbitrarily close to the channel capacity in the NBSC model.