codici di correzione degli errori destinati a CPU lente che trasmettono a CPU veloci

Question

Sto cercando un codice di correzione degli errori in avanti che sia relativamente facile/veloce da codificare su un microcontrollore; la decodifica verrà eseguita su un PC in modo che possa essere più complicata.

Non so molto sui codici di correzione degli errori e, a parte i semplici codici di Hamming, sembrano essere tutti più complicati di quanto io possa gestire.

Qualche consiglio?

Edit: ho intenzione di tagliar corto e di accettare la risposta di Carl ... Credo che c'erano due cose che non ho menzionato:

(1) Io non strettamente necessità la correzione degli errori, è solo vantaggiosa per me, e ho pensato che potrebbe esserci qualche algoritmo di correzione degli errori che è stato un vantaggio ragionevole per un costo minimo. I codici di Hamming hanno probabilmente la giusta misura e anche sembra che potrebbero essere troppo costosi per la mia applicazione di codifica.

(2) Il vantaggio maggiore rispetto alla correzione dell'errore è la possibilità di risincronizzare correttamente i pacchetti che seguono un errore. (se non vengo fuori sincrono per molto tempo, è male) Quindi penso che sia meglio se mantengo le cose semplici.

Answer 1

Il problema con i codici di correzione degli errori è che ti consentono di recuperare da errori a bit singolo o forse a 2 bit, ma solitamente non rilevano o danneggiano i danni maggiori.

Pertanto, la mia raccomandazione sarebbe quella di dividere i flussi di dati in blocchi (1 KB, 10 KB, ... 1 MB al massimo) e calcolare un checksum per ciascun blocco. Quindi, quando i dati arrivano sull'altra CPU, è possibile verificare se è corretto e richiedere la ritrasmissione di quel blocco se non lo è. Quindi il computer ricevente riconoscerebbe e attenderà il blocco successivo, o il riconoscimento negativo e si aspetterà un nuovo invio.

Sì, stiamo implementando un sottoinsieme di TCP/IP qui. Ma c'è una ragione per cui questo protocollo ha avuto tanto successo: funziona!

Per un checksum, consiglierei CRC-32. Richiede una tabella di (penso) 256 numeri a 32 bit e alcuni calcoli ragionevolmente semplici (indicizzazione di array, OR e XOR, soprattutto), quindi è abbastanza facile per una CPU "stupida" calcolare.

Answer 2

Non ho ancora capito quanto sovraccarico ci si possa permettere. Nel tuo commento dici che un codice di rilevamento/correzione degli errori a 16 bit è corretto, ma non specifichi quanto grande è il blocco a cui stai pensando di collegarlo. Per essere significativo, dovresti probabilmente esprimere l'overhead ammissibile come percentuale. 16 bit di correzione degli errori per 64 bit di dati sono molto diversi da 16 bit di correzione degli errori di un kilobyte di dati ..

Se puoi permetterti qualcosa come il 15-20% di overhead o così, probabilmente puoi usare un codice convoluzionale con decodificatore di Viterbi. Questo è altamente assimmetrico: il codificatore convoluzionale è piuttosto semplice (fondamentalmente un registro a scorrimento, con i colpetti di uscita che portano a XOR). Uno molto grande potrebbe usare un registro a 16 bit con una mezza dozzina di XOR.

Fortunatamente si dispone di un computer più pesante per gestire la decodifica, perché un decodificatore di Viterbi può essere una bestia terrificante. Soprattutto quando si utilizza un encoder più grande per ridurre il sovraccarico, la dimensione del decodificatore esplode. La dimensione del decodificatore è esponenziale rispetto alla dimensione del gruppo di codice.

Codici turbo citati.Questi possono fare un uso migliore della larghezza di banda disponibile rispetto ai codici convoluzionali con i decodificatori di Viterbi - ma usano un codificatore molto più complesso - un minimo di due codificatori convoluzionali di un tipo specifico (encoder ricorsivi sistematici convoluzionali). In quanto tali, non sembrano adattarsi alle vostre specifiche.

Answer 3

Suggerirei di utilizzare un modulo di correzione forward-error basato su pacchetti. Se devi inviare sei pacchetti di lunghezza uguale, invia ognuno di essi con informazioni sufficienti per identificarlo come "pacchetto 1 di 6", "2 di 6", ecc. Insieme ad un altro pacchetto il cui primo byte di carico utile è l'xor di il primo byte di payload dei pacchetti 1-6, il cui secondo byte di carico utile è l'xor del secondo byte del pacchetto 1-6, ecc. Il codice che riceve sei pacchetti fuori dal totale sette sarà in grado di ricostruire quello mancante. Come lieve miglioramento, usa un pacchetto "parità" per i pacchetti "pari" e un altro per quelli "dispari". Se lo fai, il sistema sarà in grado di recuperare da qualsiasi errore di burst che non è più lungo di un pacchetto.