3
$\begingroup$

I am very familiar with error correcting codes. However, it is not obvious how to apply them to adaptive streaming data. There also doesn't seem to be much literature on the problem.

The naive approach might be to take small codewords of data and use forward error correction until there is a statistically significant chance that the client has received them. Then, move to the next codeword.

My question is whether there are known pitfalls with the naive approach and whether there exists a more comprehensive or performant solution (let's ignore the use of locally decodeable codes for now).

$\endgroup$
1
$\begingroup$

tl;dr: This solution is quite good for random noise, but fails for bursty noise, or if you wish to get extremely low failure probability.

Random Noise

Assume the average noise (across the entire stream) is 10%, that is, each symbol is flipped with probability 0.1. The naive approach you suggest can be summarized as taking small chunks of data ("small" with respect to the size of the stream), and encoding each chunk individually via some ECC. For instance, a single chunk may be of length $\log N$, while the stream is of length $N$. Then, if you use ECC on that chunk (and expand it into length $C\log N$, for some large constant$~C$), there is a probability of $\approx 2^{-C\log N}$ that it will be decoded incorrectly. Taking a union bound over the entire stream, there is only a polynomially small probability that some chunk of data will fail.

If polynomially-small failure probability is good for you - you are golden. Otherwise, you will have to take ECC with larger redundancy, and this may be impractical. There's also an issue of delay, but that is secondary here.

Bursty noise

A different problem arises when the noise is not random, but adversarial, or even simpler, just bursty. Here again we can assume that 10% of the transmissions are noise, however they can come as a single burst of noise, corrupting $N'/10$ consecutive transmissions. Clearly, the above naive solution will fail, since there are many codewords that will be completely noisy. Note that even if you increase the redundancy of each encoding, this will not help. The only solution is to increase the chunk size (that is, to send at most 10 encoded chunks), but this is terrible in terms of delay.

One solution to the bursty noise is send the information in a random order. If the transmission is long enough and the information is spread across this transmission quite evenly, then even a burst of noise "behaves" like a random noise with high probability (i.e., it will corrupt the codewords in balanced manner, and will have low probability to completely corrupt a single codeword). This might not be enough.

Using stronger codes (that have an "online" property) can help resisting more noise, improve the delay and reduce the failure property to be exponentially small. See Franklin et al., "Optimal Coding for Streaming Authentication and Interactive Communication" (IEEE Trans. Info. Theory. 61:133-145, 2015). There is also a similar encoding scheme that works for sliding windows rather than unbounded streams, see "Efficient Error-Correcting Codes for Sliding Windows".

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Techniques based on rateless codes can work better for correcting erasures on streaming data, especially when you do not have a good sense of the channel properties, or the channel varies significantly. The coded-datagram protocol, for example, handles this case.

If you are really interested in arbitrary errors, take a look at convolutional codes.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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