# Error correction code handling deletions and insertions

I have data which is expressed in form of fixed-length sequence of decimal digits, typically 10 digits in length.

I'm looking for error correction code that would allow me to append one or more characters to the end of my digit sequence and prevent data from being corrupted following ways:

1. Individual char replacement (...12345 => ...92345)
2. Swapping of two neighbor characters (...12345 => ...12435)
3. Deletion of character (...12345 => ....1245)
4. Insertion of character (...12345 => ..123X45)

I can extend an alphabet of digits to include hexadecimal digits too in sake of reliability, so redundant code can use A-F letters too. When represented number is smaller than it's required, I can pad it either way with some pad symbol, which could be either plain zero or in range A-F if necessary.

I would greatly appreciate if this code will not have an overhead larger than two lengths of message itself.

I've already looked at Reed-Solomon code implementations, but as I lack finite field math knowledge yet, I was able only to play with existing implementation over GF(28) — I packed the number as 32-bit representation, applied various kinds of distortions and could only achieve stability with error code itself being twice as long as message itself (e.g. 64 bits), so now I'm searching for something shorter.

Does the code like above exist? If no, could you please point out to restrictions that have to be relaxed in order for it to exist?

-
"[...]prevent data from being corrupted[...]" Are you looking for error correction, or just error detection? –  Snowball Feb 6 '13 at 2:57
Your data packets are so short that I would try an RS-code over $GF(2^4)$. I need to think about the necessary amount of redundancy. Can you always tell from the received message that an insertion/deletion has taken place? IOW are your data packets of a constant length? –  Jyrki Lahtonen Feb 6 '13 at 8:33
A probably related topic: Levenshtein distance. Another useful buzzword may be the error detection code used in Norwegian social security numbers. People often refer to that as a model for protection agains this type of errors. I have sat at a dinner table with the dude who designed that code on a number of occasions, but I have never familiarized myself with the details of the construction. You may be able to find something by googling that :-) –  Jyrki Lahtonen Feb 6 '13 at 8:39
@Snowball, I'm looking for error correction, as error detection can be achieved by some kind of CRC only — this will not give me way to restore original message. –  modchan Feb 6 '13 at 11:47
@JyrkiLahtonen, no, unfortunately, I currently cannot determine insertion or deletion. Data packets formally are variable in size, but have upper length bound (10 chars) and can be zero-padded out to constant width to aid ECC. –  modchan Feb 6 '13 at 11:51