Est-il possible de faire une correction d'erreur rudimentaire avec CRC?

Question

Je sais que toute l'intention d'utiliser CRC est de faire la détection d'erreur, mais j'ai entendu quelqu'un dire qu'il peut être utilisé pour effectuer une correction d'erreur de base en plus de la détection d'erreur. J'étais curieux de savoir si c'était le cas, et si oui, quelle est sa puissance? Je veux dire, nous nous référons généralement à CRC comme capable d'effectuer la détection de bits x, mais je suis curieux de savoir s'il est capable d'effectuer une correction x-bit. Si oui, comment cela fonctionne-t-il? Merci.

Answer 1

Il est possible d'effectuer une correction d'erreur sur un seul bit avec un CRC. Supposons que l'on a un CRC « registre » et a des fonctions pour exécuter l'algorithme CRC vers l'avant et vers l'arrière un bit à la fois, en ignorant les données entrantes

 
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; 
} 

une Supposons a un paquet qui est calculée de telle sorte que l'initialisation du CRC à un certain La valeur et l'exécution de crc_forward pour chaque bit (MSB en premier) devrait donner zéro. Si l'on obtient une valeur CRC autre que zéro, on peut exécuter l'algorithme à l'envers (en ignorant les bits de données) jusqu'à ce que la valeur CRC calculée soit égale à 1. C'est l'emplacement du bit incorrect. Notez que cette approche peut être adéquate pour la correction d'erreurs logicielles dans des choses comme le flash NAND. Pour l'employer utilement pour la correction d'erreur matérielle, il faudrait soit être en mesure de retarder les opérations de lecture jusqu'à ce que l'ECC puisse être traité, soit avoir besoin d'une table de valeurs 'syndrome' et de positions de bits.

Answer 2

J'ai récemment travaillé sur la détection d'erreur CRC16 et la correction d'erreur sur un seul bit.

est ici l'idée de base:

1. Supposons que vous avez une seule erreur binaire.
2. Si la donnée + crc n'inclut aucune erreur, le CRC sera 0, sinon ce n'est pas le cas.
3. Nous définissons le CRC envoyé comme CRC et le CRC reçu comme CRCr.
4. Ensuite, les bits d'erreur sont donnés par CRCox = CRCs^CRCr.
5. Le résultat englobe à la fois les erreurs CRC et les erreurs de données.
6. Regardez quelle est la relation entre CRCox et l'erreur binaire.

Est-ce clair? J'ai un article à ce sujet. Si vous voulez en savoir plus, faites le moi savoir.

Answer 3

Vous pouvez effectuer une correction d'erreur multi-bits avec des CRC. En regardant wikipedia, avec des références au travail de koopmans, un CRC peut détecter ses erreurs hamming_distance-1. La distance de hachage dépend de la longueur de la charge utile et du polynôme CRC utilisé. Ainsi, par exemple, le polynôme de Koopmans de 0xBA0DC66B peut détecter jusqu'à 5 bits d'erreur dans des messages d'une longueur maximale de 16360 bits. L'algorithme décrit dans les deux messages précédents peut être étendu à autant de bits que nécessaire, mais le temps augmente exponentiellement avec le nombre de bits à réparer.

1. Calculer l'erreur CRC = CRC_gotten^CRC_expected.
2. Examinez tous les messages de 1 bit possibles (c'est-à-dire tous les 0, 1 et tous les 0) (notez BITS non BYTES) et le bit d'erreur est le message qui génère l'erreur CRC.
3. Inverser le bit détecté pour corriger l'erreur.

Si vous ne trouvez pas 1 bit correspondant à l'erreur CRC, regardez à travers tous les 2 bits, 3 bits jusqu'à votre hamming_distance-1.Notez que cela devient lent, message_length au carré pour 2 bits, cubed pour 3 bits jusqu'à la cinquième puissance pour cinq bits.