Reliable Communication over Channels with Insertions, Deletions and Substitutions.

Matthew C. Davey and David J.C. MacKay


A new block code is introduced which is capable of correcting multiple insertion, deletion and substitution errors present in a single block. The code consists of non-linear inner codes, which we call `watermark' codes, concatenated with low-density parity-check codes over non-binary fields. The inner code allows probabilistic resynchronisation and provides soft outputs for the outer decoder, which then completes decoding. We present codes of rate 0.7 and transmitted length 5000 bits that can correct 30 insertion/deletion errors per block. We also present codes of rate 3/14 and length 4600 bits that can correct 450 insertion/deletion errors per block.

Status: Submitted to IEEE Transactions on Information Theory, December 1999. Updated May 2000. Final revision and accepted for publication September 2000.

Download