rilevamento blocco nel flusso ripetuto

Question

Ho bisogno di recuperare un blocco di dati da un flusso ripetuto di dati. Sto cercando di vedere cosa possono già esistere algoritmi per questo in quanto non si sente come una situazione nuova.

Ecco le specifiche:

1. È presente un blocco N-lunghezza di dati contenuti in un flusso
2. Il blocco viene ripetuto molte volte nel flusso
3. i dati sono fortemente danneggiato, alcuni byte potrebbero essere solo sbagliato, dove come gli altri possono essere rilevate come mancanti (cancellature)
4. C'è una funzione F(data) che può dire se un blocco rappresenta dati validi (la probabilità di un falso positivo è praticamente nulla)
5. F può anche fornire un valore di probabilità che anche se il blocco non è dato valido se il blocco stesso è valida (ma ha solo troppa corruzione da recuperare)
6. La possibilità di dati danneggiati è molto basso rispetto ai dati mancanti

Ad esempio, dire che ho questo flusso di dati e desidera recuperare la sequenza 1234567890 10 di lunghezza. Il dato è solo un esempio visivo grezza (non posso garantire il recupero è in realtà possibile da questo bit). Un . rappresenta un byte mancante e <break> indica un blocco sconosciuta di dati (dati e non lunghezza nota). Nota anche le Qs come un esempio di dati corrotti.

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

Come posso prendere un tale flusso di dati e di recupero probabilmente blocchi di dati N? Poiché i dati attuale comprende il recupero di errore in avanti il ??recupero necessità blocco non essere perfetto. Tutto ciò che deve fare è dare probabili blocchi ricostruiti di dati e la funzione F tenterà di fare il recupero di errore. Così mi aspetto di riempimento F deve essere chiamato più volte.

Mi piacerebbe trovare qualcosa di meglio di F semplicemente chiamando in ogni punto nel flusso dal momento che il tasso di errore potrebbe essere abbastanza alto che nessun singolo blocco corsa di N può essere recuperata - le ripetizioni nel flusso deve essere utilizzato in qualche modo .

Answer 1

Credo che ciò che si vuole è impossibile fare a meno di ulteriori ipotesi sulla F.

Si consideri il seguente, flusso di dati piuttosto semplice per una lunghezza di dati di destinazione di 5:

123441233512245113451255513555 ...

Si noti che non un singolo blocco contiene 12345 (i nostri dati originali). Al fine di trovare una corretta combinazione di parti di dati, si avrebbe di controllo tutti combinazioni, in generale. Qual è la probabilità che una combinazione diversa da 12345 è accettato da F? E questo è su un flusso senza dati validi perso o simboli corrotti e ignorando il problema delle sovrapposizioni tra i blocchi che potrebbero accidentalmente essere!

Quindi, penso che mantenere un buffer di dimensioni $ N $ e funzionante F in ogni passo il tempo è il migliore che si può fare. Si noti che è possibile saltare la valutazione di F se c'è un simbolo corrotto nel buffer (condizione che si può individuare quelli). Hai ancora il problema degli errori di sovrapposizione e blocchi validi sbagliate, però.

avere più potenziale se F ha delle belle proprietà, ad esempio, se è in grado di identificare valido parti dei dati. Quindi è possibile memorizzare solo le parti valide massimi e quelli piece insieme. Inoltre, la formattazione del flusso di dati può aiutare; un semplice esempio potrebbe essere marcatori per l'inizio di un blocco di dati (che sarebbe sbarazzarsi di problemi con le sovrapposizioni e ridurre la quantità di chiamate a F). Inoltre, le ipotesi usuali come "probabilità di errore è piccolo" può fare in attesa di una copia completa valida dei dati vitali; molti protocolli di abbattere se praticamente ogni altro simbolo è danneggiato.

Tutti questi non sono problemi nuovi. Suggerisco ulteriore lettura su

• Codici di rilevamento e correzione degli errori ,
• codici in generale e
• protocolli di comunicazione .