Quali tecniche puoi utilizzare per codificare i dati su un canale unidirezionale con perdita?

Question

Immagina di avere un canale di comunicazione che è intrinsecamente in perdita e a senso unico. Cioè, c'è del rumore intrinseco che è impossibile rimuovere che provoca, diciamo, i bit casuali da attivare. Immagina anche che sia un modo: non puoi richiedere la ritrasmissione.

Ma devi inviare i dati su di esso a prescindere. Quali tecniche puoi utilizzare per inviare numeri e testo su quel canale?

1. È possibile codificare i numeri in modo tale che, anche con il twiddling casuale dei bit, possano essere interpretati come valori vicini all'originale ( trasmissione con perdita di dati )?

2. Esiste un modo per inviare una stringa di caratteri (ASCII, diciamo) in modo senza perdita ?

Questo è solo per divertimento. So che puoi usare il codice morse o qualsiasi comunicazione binaria a frequenza molto bassa. Conosco bit e checksum di parità per rilevare errori e riprovare. So che potresti anche usare un segnale analogico. Sono solo curioso di sapere se ci sono tecniche informatiche interessanti per inviare queste cose su un canale con perdita di dati.

Answer 1

A seconda di alcuni dettagli che non fornisci sul tuo canale con perdite, ti consiglio di utilizzare prima un Codice grigio per garantire che gli errori a bit singolo risultino in piccole differenze (per coprire il desiderio di mitigazione della perdita nella trasmissione con perdita), e quindi eventualmente anche codificare il flusso risultante con un po 'di "perdita senza perdita". (== cerca di essere senza perdita di dati ;-) codifica.

Reed-Solomon e le sue varianti sono particolarmente buone se il tuo gli episodi di rumore sono soggetti a piccoli scoppi (diversi errori di bit all'interno, per esempio, di un singolo byte), che dovrebbero interagire bene con la codifica Gray (poiché gli errori multi-bit sono i killer per l'aspetto "mitigazione della perdita" di Gray, progettato degradare con grazia per errori single-bit sul filo). Questo perché R-S è intrinsecamente uno schema a blocchi e più errori all'interno di un blocco sono sostanzialmente gli stessi di un singolo errore, dal punto di vista di R-S ;-).

RS è particolarmente fantastico se molti degli errori sono cancellazioni - per dirla semplicemente , una cancellazione è un simbolo che molto probabilmente è stato mutilato nella trasmissione, ma per il quale si conosce il fatto cruciale che è stato mutilato. Il livello fisico, a seconda di come è progettato, può spesso avere suggerimenti su questo fatto, e se c'è un modo per informare i livelli superiori, ciò può essere di aiuto cruciale. Lasciami spiegare un po 'le cancellature ...:

Dire per un esempio semplificato che uno 0 viene inviato come un livello di -1 volt e un 1 viene inviato come un livello di +1 volt (wrt qualche onda di riferimento), ma c'è rumore (il rumore fisico può spesso essere ben- modellato, chiedi a qualsiasi ingegnere della comunicazione competente ;-); a seconda del modello di rumore, la decodifica potrebbe essere che qualsiasi cosa da -0,7 V in giù viene considerata a 0 bit, qualsiasi cosa da +0,7 V in su viene considerata a 1 bit, qualsiasi cosa in mezzo viene considerata una cancellazione, ovvero viene detto lo strato superiore che la parte in questione è stata probabilmente alterata nella trasmissione e dovrebbe quindi essere ignorata. (A volte faccio questo come un esempio della mia tesi che a volte le astrazioni DOVREBBERO "perdere" in modo controllato e architettato: il corollario Martelli al Legge delle perdite astratte ! -).

Un codice RS con un dato rapporto di ridondanza può essere circa due volte più efficace nella correzione delle cancellazioni (errori del decoder) rispetto alla correzione di errori altrimenti sconosciuti - è anche possibile mescolare entrambi gli aspetti, correggendo entrambi alcune cancellazioni E alcuni errori altrimenti sconosciuti.

Come la ciliegina sulla torta, i codici R-S personalizzati possono essere (ragionevolmente facilmente) progettati e personalizzati per ridurre la probabilità di errori non corretti al di sotto di qualsiasi soglia richiesta & # 952; dato un modello preciso delle caratteristiche del canale fisico in termini sia di cancellazioni che di errori non rilevati (comprese probabilità e burstiness).

Non definirei l'intera area una "scienza informatica" uno, in realtà: quando mi sono laureato (MSEE, 30 anni fa), stavo principalmente cercando di evitare "CS" cose a favore della progettazione di chip, progettazione di sistemi, sistemi radio avanzati e altro; eppure mi hanno insegnato queste cose (beh, il sottoinsieme che era già nel regno dell'uso pratico dell'ingegneria ;-) abbastanza bene.

E, solo per confermare che le cose non sono cambiate molto in una generazione: mia figlia ha appena conseguito la laurea in ingegneria delle telecomunicazioni (concentrandosi esclusivamente su sistemi radio avanzati) - non può progettare praticamente nessun programma serio , algoritmo o struttura dei dati (anche se ha fatto bene nei corsi obbligatori su C e Java, lì w

Answer 2

Questa domanda è oggetto della teoria dei codici .

Answer 3

Probabilmente uno dei metodi più noti è utilizzare codice di Hamming . Potrebbe non essere il modo migliore per correggere errori su larga scala, ma è incredibilmente semplice da capire.

Answer 4

• Esiste la codifica ridondante utilizzata nei supporti ottici che può recuperare bit-loss.
  Viene utilizzato anche
  • ECC nei dischi rigidi e nella RAM
• Il TCP può gestire parecchio di perdita di dati con ritrasmissioni.

Answer 5

Codici Turbo o codici di controllo di parità a bassa densità per i dati generali, perché questi si avvicinano maggiormente al limite di Shannon - vedi wikipedia.

Answer 6

Puoi utilizzare i codici Reed-Solomon .

Answer 7

Vedi anche il Protocollo a finestra scorrevole (utilizzato da TCP).

Anche se questo include la gestione di pacchetti riordinati o persi del tutto, il che non faceva parte della definizione del problema.

Answer 8

Come dice Alex Martelli, c'è molta teoria del codice nel mondo, ma i codici Reed-Solomon sono sicuramente un punto debole. Se vuoi davvero costruire qualcosa, Jim Plank ha scritto un bel tutorial sulla codifica Reed-Solomon . Plank ha un interesse professionale nella codifica con molta esperienza pratica per il backup.

Answer 9

Vorrei scegliere alcuni di questi suggerimenti, seguiti da più invii degli stessi dati. In questo modo puoi sperare che vengano introdotti diversi errori in diversi punti dello stream e potresti riuscire a dedurre il numero desiderato molto più facilmente.