Success Probability of Decoding Interleaved Alternant Codes

Interleaved Reed–Solomon codes admit efficient decoding algorithms which correct burst errors far beyond half the minimum distance in the random errors regime, e.g., by computing a common solution to the Key Equation for each Reed–Solomon code, as described by Schmidt et al. If this decoder does not succeed, it may either fail to return a codeword or miscorrect to an incorrect codeword, and good upper bounds on the fraction of error matrices for which these events occur are known. The decoding algorithm immediately applies to interleaved alternant codes as well, i.e., the subfield subcodes of interleaved Reed–Solomon codes, but the fraction of decodable error matrices differs, since the error is now restricted to a subfield. In this paper, we present new general lower and upper bounds on the fraction of decodable error matrices by Schmidt et al.’s decoding algorithm, thereby making it the only decoding algorithm for interleaved alternant codes for which such bounds are known.

I. Introduction

A codeword of an ℓ-interleaved code can be seen as ℓ codewords of possibly different constituent codes of the same length n stacked above each other. A common error model for these codes are burst errors, where a codeword of the ℓ-interleaved code is corrupted by an additive ℓ × n error matrix with t nonzero columns (we refer to t as the weight of the matrix). For a variety of algebraic interleaved codes, it is possible to correct a larger fraction of errors by adopting a collaborative decoding approach. For this reason, interleaved codes have many applications in which burst errors occur naturally or artificially, e.g., replicated file disagreement location [1], correcting burst errors in data-storage applications [2], [3], outer codes in concatenated codes [4]–[8], ALOHA-like random-access scheme [5], decoding non-interleaved codes beyond half-the-minimum distance by power decoding [9]–[12], and code-based cryptography [13], [14].