Improved Decoding of Interleaved Reed Solomon Codes in the Non-Binary Symmetric Channel

We consider error-correction over the Non-Binary Synmmetric Channel (NBSC), a natural probabilistic extension of the traditional Binary Symmetric Channel (BSC). We propose a new decoding algorithm for interleaved Reed-Solomon Codes that attempts to correct all "interleaved" codewords simultaneously. Our decoding method takes advantage of the NBSC model and it is capable of correcting any asymptotically feasible error-rate. Our probabilistic algorithm is a "multi-dimensional" probabilistic extension of the classical Berklekamp-Welch RS-Decoding algorithm. Analysis of our method involves a "minor matrix decomposition" technique and Schwartz's Lemma.