Quale algoritmo per errori non burst estremamente elevati?

Question

Ho un flusso binario con un tasso di errore molto elevato. Il tasso di errore è del 50%, il che significa che ogni bit ha una probabilità del 50% di essere capovolto. L'errore non si verifica nelle esplosioni ed è completamente casuale, quindi i codici Reed-Solomon non funzionerebbero bene.

Quale schema o algoritmo dovrei applicare allo stream? Non mi interessa affatto il sovraccarico.

Questo è tutto teorico, quindi non ha senso chiedere se potrei semplicemente ridurre l'errore del flusso.

Modifica

Non dire che non è possibile, la prima risposta che ti dice che è possibile con canale rumoroso teorema di codifica.

Answer 1

Il teorema di codifica dei canali rumorosi dice che puoi effettivamente raggiungere la capacità di Shannon per il canale. non indica che il canale ha una capacità diversa da zero!

Se randomizzi il 100% dei bit nel canale, il 50% di essi rimarrà invariato, quindi capovolgi solo un 50% casuale dei bit. Dovrebbe essere ovvio che non è possibile inviare dati su tale canale: la sua capacità di Shannon è zero.

Answer 2

Se il tasso di errore è del 50%, questo è fondamentalmente un rumore casuale, no? Voglio dire, considera solo il tentativo di trasmettere un singolo bit. Se invii un flusso infinito del bit giusto, con un tasso di errore del 50% otterrai metà 1 e metà 0 se il bit giusto è 1 o 0.

Se in realtà è inferiore al 50% (ad es. il 50% dei bit sarà "casuale" anziché "capovolto"), allora potresti semplicemente ripetere i dati - trasmettere ogni bit 128 volte e capire quale ottieni di più di per ogni 100 bit ricevuti. Questa è la soluzione semplice da codificare, estremamente inefficiente, per nulla matematica :)

Answer 3

Bene, il punto centrale della correzione degli errori Reed-Solomon è che la maggior parte degli errori del mondo reale si verificano nelle esplosioni, quindi interleave e de-interleave i dati. Se i tuoi errori sono completamente casuali, ovvero distribuiti da Poisson, allora funzionerà semplicemente aggiungendo ridondanza allo stream in modo semplice e matematicamente efficiente. Una cosa che potresti guardare è una specie di modello Markov nascosto, come codice trellis. Questo è fondamentalmente solo un modo matematicamente efficiente di aggiungere ridondanza.

Inoltre, dai un'occhiata al teorema di codifica dei canali rumorosi. A rigor di termini, non lo fa non si applica ai dati digitali, ma se la fonte di questi bit è un processo analogico o se potessi modellare i tuoi bit come se fossero il risultato di un processo analogico, potrebbero darti un'idea in quale potrebbe essere il meglio che potresti fare. Ciò ti impedirebbe di perdere tempo a cercare di fare meglio di quanto sia matematicamente possibile.

Answer 4

Man mano che il canale si avvicina al 50% di rumore reale, non è più possibile trasmettere alcuna informazione. Alla risposta di Jon Skeet, se il tasso di errore è inferiore al 50% del rumore, è possibile ottenere i dati eseguendo esplosioni più lunghe dei dati previsti in modo ridondante e osservando statisticamente il risultato a un certo livello di confidenza nel valore originale. La lunghezza di scoppio e i livelli di confidenza necessari per una determinata lunghezza verrebbero quindi derivati ??sulla base di una caratterizzazione del rumore. Comprendi, tuttavia, che cosa stai facendo qui sta effettivamente riducendo la velocità dei dati per migliorare il rapporto segnale-rumore netto del flusso trasmesso.

Nella tua domanda, potresti averlo escluso come opzione, ma uno schema di codifica migliore potrebbe essere basato sull'esistenza relativa (o meno) del flusso di dati stesso. In altre parole, per trasmetterne uno binario .... inviare un flusso alternato di 1/0. Per inviare uno zero, non inviare nulla o forse inviare un livello costante. L'idea è che l'invio (e la ricezione) di qualsiasi cosa rappresenti uno stato e l'invio (e la ricezione) di nulla rappresenti l'altro stato. Ciò assomiglierebbe effettivamente a un tipo di codifica bipolare dei dati.

Answer 5

Se il tasso di errore è del 50%, il flusso di bit È casuale e NON porta CORRELAZIONE al flusso di bit originale. È come se XORing il flusso con un flusso di bit completamente casuale e il risultato è completamente casuale. E non c'è niente che tu possa fare al riguardo.

La frequenza di vibrazione deve essere inferiore al 50% affinché qualsiasi schema funzioni. Certo, potrebbe essere SUPERIORE al 50%, ma poi puoi prima invertire lo stream e quindi elaborarlo come se il tasso di errore fosse inferiore al 50%.

Se gli errori sono completamente casuali e molto frequenti (ad es. il 25% dei bit viene capovolto), è molto difficile trovare un solido schema di rilevamento degli errori. È necessario aggiungere una notevole quantità di ridondanza.

Answer 6

Hai esaminato i codici turbo?

- MarkusQ

Doh! Ho letto male che come randomizzato al 50%, non capovolto al 50%.

Answer 7

Se esattamente il 50% dei bit viene capovolto in una determinata trasmissione, anziché ogni bit che viene capovolto con una probabilità del 50%, è possibile inviare un bit di informazione inviando una trasmissione di due bit - - invia uno 0 come 00 e un 1 come 01. Se il primo bit della parola in codice ricevuta è 1, l'altro bit viene sbloccato.