Deletion Correcting Codes

Error correcting codes are well known. These allow for some tolerance with respect to noisy transmission. Thus a received string may differ from the transmitted string by a couple of symbols being different, but the original transmission can be received. For example, we might transmit (7 8 9 1 2) and receive (7 8 9 3 2). If the transmission is taken from a code capable of correcting one error we could recover the original transmission.

Deletion correcting codes are less well known, and significantly less research has been carried out into their properties. In the example above the length of the transmission was maintained, as was the knowledge that if an element was correct it was in the correct position. Deletion correcting codes are capable of correcting deletions, in the sense that if the transmitted word (7 8 9 1 2) is received as (8 9 2) a code capable of correcting two deletions could recover the transmitted word.

Deletion correcting codes were introduced by Levenshtein (1966) to correct synchronisation errors. Deletion correcting codes have been applied to packet loss in Internet transmission, and fairly recently, traitor tracing.

Various studies of DC codes have been made (Bours 1995, Calabi et al 1969, Klove 1995, Levenshtein 1966/1971, Mahmoodi 1998, Shalaby et al 2002, Tanaka et al 1976, Yin 2001. Sloane (2002) contains a helpful summary of results regarding single--deletion correcting codes.

---