1
$\begingroup$

Let's say I receive a large sequence $s$ of numbers $n_0$, $n_1$, $n_2$, $\ldots$ Later I expect to receive the same sequence $s^*$ with the same numbers $n_0$, $n_1$, $n_2$, $\ldots$ but errors might occur. For instance $n_2$ gets altered. I'd like to detect errors as soon as possible with high probability.

  1. solution: store cumulative hash sum every $k$ elements (but here I detect the error too late)
  2. solution: store the whole sequence (way too large to store on disk)

Is there anything in between those two trade-offs that allows me to detect the error per element with high probability?

$\endgroup$
  • $\begingroup$ What kind of errors are you worried about? If it's just transmission errors then you should probably forget about the fact that you see the sequence twice but just use an error-correcting code for the second transmission. $\endgroup$ – David Richerby Jan 16 at 12:33
  • 1
    $\begingroup$ You could store a very short hash of each element of the sequence. E.g. just the parity for each number. Assuming that the sequence are 32 bit integer, and the numbers are uniformly distributed, then you can find an error with 50% probability instantly, with only 1/32th of the memory. If you use more than 1 bit, e.g. compute for each element a 4-bit hash, than you still only use 1/8th of the memory and have a high (1/16) probability of recognizing errors. Additionally you can use your idea 1. $\endgroup$ – Jakube Jan 16 at 12:39
  • $\begingroup$ ^ that should be 1 - 1/16 = 93.75%. $\endgroup$ – Jakube Jan 16 at 12:58
  • $\begingroup$ @DavidRicherby An error might be that a number gets replaced by a different one or might even be missing. It's less a transmission error check more an equality check of sequences on-the-fly. $\endgroup$ – Holarel Jan 16 at 14:04
  • 3
    $\begingroup$ If you're just trying to guard against transmission errors and you trust the sender to try to send the correct sequence, use an error-correcting code. But I'm having a hard time imagining a scenario where somebody's supposed to send me the same sequence twice, I need to receive it twice and the only errors I'm trying to guard against are transmission errors. This whole thing smells of an X-Y problem (one where you're trying to solve X, you've (usually incorrectly) decided that you need to do Y, you're having problems with Y, so you ask about Y instead of your real problem, X). $\endgroup$ – David Richerby Jan 16 at 21:12

Your Answer

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

Browse other questions tagged or ask your own question.