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

Question

Je sais toute l'intention d'utiliser CRC est de faire la détection d'erreur, mais j'ai entendu l'état de quelqu'un qui peut être utilisé pour faire la correction d'erreurs de base en plus de la détection d'erreur. J'étais curieux de savoir si tel était le cas, et si oui, comment est-il puissant? Je veux dire, on se réfère généralement à CRC comme capable d'effectuer la détection x bits, mais je suis curieux de savoir si elle est capable d'effectuer une correction x bits. Si oui, comment cela fonctionne? Merci.

Answer 1

Il est possible de faire la correction d'erreurs 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 avant et en arrière un peu à 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;
}

Supposons une a un paquet qui est calculée de telle sorte que l'initialisation du CRC à une valeur en cours d'exécution et crc_forward pour chaque bit (MSB premier) devrait donner zéro. Si l'on obtient une valeur CRC autre que zéro, on peut exécuter l'algorithme en sens inverse (abstraction faite des bits de données) jusqu'à ce que la valeur CRC calculée est 1. C'est l'emplacement du bit incorrect.

Notez que cette approche peut être adéquate pour la correction d'erreur de logiciel dans les choses comme le flash NAND. Pour employer utilement pour la correction d'erreur matérielle, il faudrait soit en mesure de retarder les opérations de lecture jusqu'à ce que l'ECC pourrait être traitée, ou bien on aurait besoin d'une table des valeurs et des positions de bits « syndrome ».

Answer 2

Vous pouvez faire une correction d'erreur multi-bits avec CRCs. En regardant wikipedia, avec des références à koopmans travail, un CRC peut détecter ses erreurs hamming_distance-1. La distance de Hamming dépend de la longueur de la charge utile et le polynôme CRC en cours d'utilisation. Ainsi, par exemple polynôme Koopmans de 0xBA0DC66B peut détecter jusqu'à 5 bits d'erreur dans les messages jusqu'à 16360 bits. L'algorithme décrit dans les deux précédents messages peut être prolongée jusqu'à autant de bits que nécessaire, mais le temps monte de façon exponentielle avec le nombre de bits à corriger.

1. Calculer l'erreur CRC = CRC_gotten ^ CRC_expected.
2. Regardez à travers tous les possibles 1 messages de bits (ie tous les 0, un 1 et des 0) (il y a des cas MESSAGE_LENGTH à évaluer. Notez que c'est BITS pas 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 pouvez pas trouver 1 bit correspondant à l'erreur CRC, regardez à travers tous les 2 bits, 3 bits à votre hamming_distance-1. Notez que cela devient lent rapide, MESSAGE_LENGTH carré pour 2 bits, 3 bits pour cubed jusqu'à la cinquième puissance pour cinq bits.

Answer 3

J'ai récemment travaillé sur la détection d'erreur CRC16 et simple correction d'erreur binaire.

Voici l'idée de base:

1. Supposons que vous avez une seule erreur binaire.
2. Si les données + crc ne comporte aucune erreur, le CRC sera 0, sinon il n'est pas.
3. Nous définissons la CRC comme envoyé et CRC reçu CRC comme CRCR.
4. Ensuite, les bits d'erreur sont données par CRCox = CRCs ^ CRCr.
5. Le résultat comprend à la fois des erreurs CRC et les erreurs de données.
6. voir, donne à quel rapport entre CRCox et l'erreur binaire est.

Est-ce clair? J'ai un document à ce sujet. Si vous voulez en savoir plus, me le faire savoir.