Improved Decoding of Interleaved AG-Codes

We analyze a generalization of a recent algorithm of Bleichenbacher et al.~for decoding interleaved codes on the $Q$-ary symmetric channel for large $Q$. We will show that for any $m$ and any $\epsilon$ the new algorithms can decode up to a fraction of at least $\frac{\beta m}{\beta m+1}(1-R-2Q^{- 1/2m})-\epsilon$ errors (where $\beta = \frac{\ln(q^m - 1)}{\ln(q^m)}$), and that the error probability of the decoder is upper bounded by $O(1/q^{\epsilon n})$, where $n$ is the block-length. The codes we construct do not have a- priori any bound on their length.

Published in:
Proc. 10th IMA Conf. on Cryptography and Coding, 1, 1, 37-46
Presented at:
IMA Conf. on Cryptography and Coding, Cirencester, UK, 19--21 December 2005
Year:
2005
Keywords:
Laboratories: