Improved Decoding of Interleaved AG-Codes

• Presented at: IMA Conf. on Cryptography and Coding, Cirencester, UK, 19--21 December 2005
• Published in: Proc. 10th IMA Conf. on Cryptography and Coding, vol. 1, num. 1, p. 37-46
• Series: Lecture Notes in Computer Science 3796
• : , 2005

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.

Keywords: Reed-Solomon ; Algebraic-Geometric ; interleaved ; code ; algoweb_agcodes

Reference

• ALGO-CONF-2007-001
• View record in Web of Science

Record created on 2007-03-01, modified on 2012-03-20