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:
- There is an N-length block of data contained in a stream
- The block is repeated many times in the stream
- the data is highly corrupted, some bytes could just be wrong, where as others can be detected as missing (erasures)
- There is a function
F(data)which can say if a block represents valid data (the probability of a false positive is virtually zero)
Fcan 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)
- 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.
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.