E 'possibile fare la correzione degli errori rudimentale con CRC?

Question

Lo so tutta intenzione di utilizzare CRC è quello di fare il rilevamento degli errori, ma ho sentito stato qualcuno che può essere usato per fare la correzione degli errori di base, oltre a rilevamento degli errori. Ero curioso di sapere se questo era il caso, e se sì, quanto potente è? Voglio dire, di solito si riferisce a CRC come in grado di eseguire il rilevamento x-bit, ma sono curioso di sapere se è in grado di eseguire la correzione x-bit. Se è così, come funziona? Grazie.

Answer 1

E 'possibile fare la correzione degli errori single-bit con un CRC. Si supponga una ha un CRC "registrati" e ha funzioni per eseguire l'algoritmo CRC avanti e indietro un po 'alla volta, ignorando dati in arrivo

int crc_forward(int old_value, int data_bit)
{
  if (old_value & 0x8000)
    return ((old_value ^ 0x8000) SHL 1) ^ 0x1021 ^ data_bit;
  else
    return (old_value SHL 1) ^ data_bit;
}

int crc_reverse(int old_value)
{
  if (old_value & 1)
    return (old_value SHR 1) ^ 0x8810;
  else
    return old_value SHR 1;
}

supporre ha un pacchetto che viene calcolato in modo che l'inizializzazione del CRC di un certo valore e funzionante crc_forward per ogni bit (MSB prima) dovrebbe produrre zero. Se si ottiene un valore CRC diverso da zero, si può eseguire l'algoritmo (ignorando bit di dati) inversa finché il valore CRC calcolato è 1. Questo è la posizione del bit errato.

Si noti che questo approccio può essere sufficiente per la correzione degli errori del software in cose come NAND flash. Per utilmente impiegare per la correzione degli errori hardware, si dovrebbe essere sia in grado di ritardare operazioni di lettura fino alla ECC potrebbe essere elaborato, altrimenti avrebbe bisogno di una tabella di valori 'sindrome' e posizioni di bit.

Answer 2

Si può fare la correzione degli errori multi-bit con CRC. Guardando wikipedia, con riferimenti a Koopmans lavoro, un CRC in grado di rilevare i suoi errori hamming_distance-1. La distanza di Hamming dipende dalla lunghezza di carico utile, e il polinomio CRC in uso. Così, per esempio Koopmans polinomio di 0xBA0DC66B in grado di rilevare fino a 5 bit di errori nei messaggi fino a 16360 bit. L'algoritmo descritto nei precedenti due messaggi può essere esteso fino al maggior numero di bit come necessario, ma il tempo sale in modo esponenziale con il numero di bit di correzione.

1. Calcolare errore CRC = CRC_gotten ^ CRC_expected.
2. Guardare attraverso tutti i possibili messaggi di 1 bit (vale a dire tutti 0, un 1 e tutti 0) (ci sono casi message_length per valutare. Nota: questo è BITS non byte) e il bit di errore è il messaggio che genera l'errore CRC.
3. Inverti il ??bit rilevato per correggere l'errore.

Se non riesci a trovare 1 bit corrispondenti l'errore CRC, sguardo attraverso tutte 2-bit, 3-bit fino al vostro hamming_distance-1. Si noti che questo diventa lento veloce, message_length quadrato per 2 bit, cubetti di 3 bit fino a quinta potenza per cinque bit.

Answer 3

Recentemente ho lavorato su di rilevamento degli errori CRC16 e correzione di errore di bit singolo.

Ecco l'idea di base:

1. Si supponga di avere un singolo errore di bit.
2. Se i dati + CRC include alcun errore, il CRC sarà 0, altrimenti non lo è.
3. Si definisce il CRC inviato come CRC e CRC ricevuti come CRCR.
4. Poi i bit di errore sono date da CRCox = CRCs ^ CRCr.
5. Il risultato comprende sia errori CRC e dati errori.
6. Abbia un'occhiata a quello rapporto tra CRCox e l'errore di bit è.

E 'chiaro? Ho un documento su questo. Se volete saperne di più, fammelo sapere.