Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
"[...]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

1 Answer 1

The capacity of channels with deletions and insertions remains poorly understood. Still some lower and upper bounds are known, you can easily google for that.

As for codes that work under such circumstances you also have some literature to browse, I'd suggest that you take a look at the seminal work by MacKay and Davey: "Reliable communication over channels with insertions, deletions, and substitutions" and from there you can explore the different works citing it.

share|improve this answer
1  
The first work would probably be Levenstein's paper (cited in the next paper), which a very nice updated result is given in arXiv:1302.6562 [cs.IT] (arxiv.org/pdf/1302.6562.pdf) - Cullina, Kiyavash "An Improvement to Levenshtein's Upper Bound on the Cardinality of Deletion Correcting Codes". –  Batman Aug 4 at 2:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.