Error Correction Advice?

Question

I have an application that ideally would allow 25% of errors to be corrected with an original message that would be 12 to 16 bytes (8-bit bytes) long. The constraints are the message cannot be retransmitted and if parts of message aren't received it will be unknown which bytes did not show up. For example, let's say, I'm using something like Reed Solomon and I add 8 bytes of codeword to the initial 16 byte message, that would fit the bill for 25% of the errors being corrected, but what if only 20 of the 24 bytes are actually received? Is there a error correction algorithm or combination of algorithms that would allow the correction of such a situation?

Thanks,
Ben

Answer 1

Here's a very inefficient scheme I've just thought of -

Assume your original message was composed of the following bytes a(1),a(2),a(3),...,a(n), to which you add some very strong error correction code a(n+1),a(n+2),a(n+3),...,a(n+m). Now, send this message interleaved with the stream 1,2,3,4,5 ..., that is send:

1,a(1),2,(2),...,n,a(n),n+1,a(n+1),...,n+m,a(n+m)

On the receiving side of the message, look for blocks of consecutive bytes of the form k,S,k+1. This tells you that a(k)=S. Moreover, if you see the two triplets i,S,i+1...k,T,k+1 and no j,P,j+1 between those two such that i<j<k, assume you've lost all the bytes between the i'th and the k'th byte in your original message and write down zeros in place. Using this scheme you may throw away some of the bytes that actually passed through but at least you will be sure where to place some of the bytes. You can then use your very strong error correction code to fill up the lost bytes and correct errors in those bytes you actually have written down.

(* For this to work neatly, you'll also have to be sure that the message bytes cannot be confused with the interleaved sequence bytes, but that's an easy problem to solve by transformation - for example, base64 your bytes before transmission so their MSB is 0, and interleave them with bytes whose MSB is set to 1)