We analyze a generalization of a recent algorithm of Bleichenbacher et al.~for decoding interleaved codes on the -ary symmetric channel for large . We will show that for any and any the new algorithms can decode up to a fraction of at least errors (where ), and that the error probability of the decoder is upper bounded by , where is the block-length. The codes we construct do not have a- priori any bound on their length.
Andreas Peter Burg, Mohammad Rowshan