detección de bloque en la corriente repetida

Question

I necesita para recuperar un bloque de datos de una corriente repetida de datos. Estoy mirando para ver lo que pueden existir ya algoritmos para esto ya que no se siente como una situación nueva.

Aquí están los detalles:

1. Hay un bloque de longitud N de los datos contenidos en una corriente
2. El bloque se repite muchas veces en la corriente
3. los datos son muy dañado, algunos bytes podrían simplemente estar equivocado, en tanto que otras pueden ser detectados como desaparecidas (borrones)
4. Hay una F(data) función que puede decir si un bloque representa datos válidos (la probabilidad de un falso positivo es prácticamente cero)
5. F también puede proporcionar un valor de probabilidad de que incluso si el bloque no es datos válidos si el bloque en sí es válida (pero sólo tiene demasiada corrupción que se recuperó)
6. La posibilidad de que los datos dañados es muy bajo en comparación con los datos que faltan

Por ejemplo, decir que tengo este flujo de datos y el deseo de recuperar la longitud de la secuencia 10 1234567890. Los datos son sólo un ejemplo visual en bruto (no puedo garantizar la recuperación es en realidad posible de este bit). A . representa un byte que falta, y <break> indica un bloque desconocido de datos (sin datos y no longitud conocida). Tenga en cuenta también las Qs como un ejemplo de datos corruptos.

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

¿Cómo puedo tener un flujo de datos y la recuperación probablemente bloques de datos N tal? Como los datos reales incluye la recuperación de errores hacia delante la necesidad de recuperación de bloque no sea perfecto. Todo lo que necesita hacer es dar a los bloques reconstruidos probables de datos y la función F tratará de hacer la recuperación de errores. Por lo tanto espero relleno F tiene que ser llamado varias veces.

Me gustaría encontrar algo mejor que F simplemente llamando en cada punto en la corriente ya que la tasa de error podría ser lo suficientemente alto que ningún bloque de ejecución única del N se puede recuperar - las repeticiones en la secuencia deben ser utilizadas de alguna manera .

Answer 1

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

• error detection and correction codes,
• codes in general and
• communication protocols.