3
$\begingroup$

I need to recover a data block from a repeated stream of data. I'm looking to see what algorithms may already exist for this as it does not feel like a novel situation.

Here are the specifics:

  1. There is an N-length block of data contained in a stream
  2. The block is repeated many times in the stream
  3. the data is highly corrupted, some bytes could just be wrong, where as others can be detected as missing (erasures)
  4. There is a function F(data) which can say if a block represents valid data (the probability of a false positive is virtually zero)
  5. F can also provide a probability value that even if the block is not valid data whether the block itself is valid (but just has too much corruption to be recovered)
  6. The chance of corrupted data is very low compared to missing data

For example, say I have this data stream and wish to recover the 10 length sequence 1234567890. The data is just a rough visual example (I can't guarantee recovery is actually possible from this bit). A . represents a missing byte, and <break> indicates an unknown block of data (no data and not length known). Note also the Qs as an example of corrupt data.

23.5678901.3456789<break>2345678..1..4567QQ012345678..3456

How can I take such a stream of data and recovery probably blocks of N data? As the actual data includes forward error recovery the block recovery need not be perfect. All it needs to do is give probable reconstructed blocks of data and the F function will attempt to do error recovery. Thus I expect F fill have to be called several times.

I'd like to find something better than simply calling F at each point in the stream since the error rate could be high enough that no single run block of N can be recovered -- the repetitions in the stream must be used somehow.

$\endgroup$
3
$\begingroup$

I think what you want is impossible to do without further assumptions on F.

Consider the following, rather simple data stream for a target data length of 5:

123441233512245113451255513555 ...

Note that not a single block contains 12345 (our original data). In order to find a proper combination of data parts, you would have check all combinations, in general. What is the probability that some combination other than 12345 is accepted by F? And this is on a stream without lost or corrupt symbols and ignoring the problem of overlaps between blocks which might by accident be valid data!

Therefore, I think keeping a buffer of size $N$ and running F in every time step is the best you can do. Note that you can skip evaluation of F if there is a corrupt symbol in the buffer (provided you can identify those). You still have the problem of overlap errors and wrong valid blocks, though.

You have more potential if F has nice properties, for example if it is able to identify valid parts of data. Then you can store only maximal valid parts and piece those together. Also, formatting the data stream can help; a simple example would be markers for the beginning of a data block (that would get rid of problems with overlaps and reduce the amount of calls to F). Furthermore, usual assumptions such as "error probability is small" can make waiting for a full valid copy of the data viable; many protocols break down if virtually every other symbol is corrupt.

All these are not new problems. I suggest further reading on

$\endgroup$
  • $\begingroup$ The blocks will be 256 bytes, probably using Reed Solomon FEC, with checksums and data markers. The chance that F produces a false positive is thus virtually zero. Corrupt symbols can't be detected, only erasures (byte not received). $\endgroup$ – edA-qa mort-ora-y May 25 '12 at 11:24
  • $\begingroup$ I'm asking because I've not found any error recovery mechanism that makes use of the redundant data stream. Most of the systems, and examples, all assume you've already identified the correct blocks and simply fail if they are too corrupt. $\endgroup$ – edA-qa mort-ora-y May 25 '12 at 11:25
  • $\begingroup$ @edA-qamort-ora-y: Well, as I write above: as long as you can not identify block beginnings and check partial blocks for integrity, I don't see how redundancy in the stream can be exploited (and I claim it can't). $\endgroup$ – Raphael May 25 '12 at 11:30
  • $\begingroup$ Okay, then let's say F can, if the block is not valid, nonetheless return a probability that the block is a legitimate block, just too corrupt. That is, I also have a way to identify the likely blocks in the stream. Say of 10 stream blocks I might be able to identify 4 likely candidates, how can I make use of that information? $\endgroup$ – edA-qa mort-ora-y May 25 '12 at 11:37
  • $\begingroup$ @edA-qamort-ora-y: Without assumptions on error probability and/or the ability to identify valid parts, nothing. If error probability is bounded, you can do symbol-wise majority vote (works with high probability if you have enough candidates). If you can identify valid parts, you can obviously puzzle. Without either, you can construct counterexamples for any method (claim). $\endgroup$ – Raphael May 25 '12 at 11:40

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.