Encodage / erreur Défi de correction

StackOverflow https://stackoverflow.com/questions/2393362

Question

Est-il mathématiquement possible de coder et message initial de 4 octets en 8 octets et si l'un des 8 octets est complètement retiré et un autre est faux de reconstruire le message initial de 4 octets? Il n'y aurait aucun moyen de réémettre ne serait connu l'emplacement de l'octet abandonné.

Si l'on utilise la correction d'erreur Reed Solomon avec 4 « parité » octets cloués à la fin des 4 « données » octets, tels que DDDDPPPP, et vous vous retrouvez avec DDDEPPP (où E est une erreur) et un octet de parité a été abandonné, je ne crois pas qu'il y ait un moyen de reconstruire le message initial (bien que moi si je me trompe) ...

Que dire en multipliant (ou effectuer une autre opération mathématique) le message initial de 4 octets par un propriétés, puis en utilisant des constantes d'une opération mathématique inverse pour déterminer quel octet a été abandonné. Ou, imposer quelques contraintes sur la structure du message afin qu'un octet doit être bizarre et les autres ont besoin d'être encore.

Au lieu d'octets, il pourrait aussi être de 4 chiffres décimaux codés d'une certaine façon en 8 chiffres décimaux où les erreurs peuvent être détectées et corrigées dans les mêmes circonstances mentionnées ci-dessus - pas de retransmission et l'emplacement de l'octet tombé ne sait pas .

Je cherche des idées folles tout le monde pourrait avoir ... Des idées là-bas?

EDIT:

Il est peut-être un peu artificiel, mais la situation que je suis en train de résoudre est celui où vous avez, disons, une imprimante défectueuse qui imprime les numéros importants sur un formulaire, qui sont ensuite envoyé par la poste au large à une entreprise de traitement qui utilise OCR pour lire les formulaires. L'OCR ne va pas être parfait, mais il devrait se rapprocher avec seulement des chiffres à lire. pourrait être un problème plus grand, où il peut déposer un nombre entier, mais il n'y a aucun moyen de savoir de quoi il se laissera tomber, mais ils seront toujours sortir dans le bon ordre, il n'y aura pas de chiffres permutées L'imprimante défectueuse.

La forme peut être modifiée de façon qu'il imprime toujours un espace entre les quatre premiers numéros et les numéros de correction d'erreur, soit 1234 5678, de sorte que l'on pourrait savoir si un 1234 chiffre initial a été abandonné ou un chiffre de correction d'erreur 5678 a été abandonnée , si cela rend le problème plus facile à résoudre. Je pense un peu similaire à la façon dont ils vérifient les numéros de carte de crédit via l'algorithme, mais en quatre morceaux de chiffres.

Si tout va bien, qui fournit des précisions quant à ce que je cherche ...

Était-ce utile?

La solution

En l'absence de structure algébrique « agréable », je pense que ça va être difficile de trouver un schéma concis qui vous fait tout le chemin à 10 ** 4 mots de code, puisque l'information-théoriquement, il n'y a pas beaucoup de mou. (Celui ci-dessous peut utiliser GF (5) pour 5 ** 5 = 3125.) Heureusement, le problème est assez petit pour que vous pourriez essayer avide méthode de construction de code de Shannon (trouver un mot de code qui ne pas en conflit avec l'un déjà choisi, ajouter à l'ensemble).

Coder jusqu'à 35 bits que un polynôme quartique f sur GF (128). Évaluer le polynôme à huit points prédéterminés x0, ..., x7 et encoder en tant que 0f (x0) 1f (x1) 0f (x2) 1f (x3) 0f (x4) 1f (x5) 0f (x6) 1f (X7), où les zéros en alternance et sont ceux qui sont stockés dans le MSB.

Lors du décodage, d'abord regarder le MSB. Si le MSB ne correspond pas au mod index 2, alors que l'octet est corrompu et / ou il a été décalé vers la gauche par une suppression. On suppose qu'il est bon et le déplacer vers la droite (éventuellement accumuler plusieurs différentes valeurs possibles à un point). Maintenant, nous avons au moins sept évaluations d'un polynôme quartique f à des points connus, dont au plus un est corrompu. Nous pouvons maintenant essayer toutes les possibilités de la corruption.

EDIT: bmm6o a avancé la thèse selon laquelle la deuxième partie de ma solution est incorrecte. Je suis en désaccord.

Revoyons les possibilités pour le cas où les MSB sont 0101101. On suppose que X est le tableau d'octets envoyés et Y est le tableau d'octets reçus. D'une part, Y [0], Y [1], Y [2], Y [3] ont MSB correctes et sont présumés être X [0], X [1], X [2], X [3] . D'un autre côté, Y [4], Y [5], Y [6] ont MSB incorrectes et sont présumés être X [5], X [6], X [7].

Si X [4] est tombé, nous avons sept évaluations correctes de f.

Si X [3] est tombé et X [4] est corrompu, alors nous avons une évaluation erronée à 3 et six évaluations correctes.

Si X [5] est tombé et X [4] est corrompu, alors nous avons une mauvaise évaluation à 5, et six évaluations correctes.

Il y a plus de possibilités en dehors de ceux-ci, mais nous avons jamais moins de six évaluations correctes, ce qui suffit à récupérer f.

Autres conseils

Je pense que vous auriez besoin d'étudier ce que codes effacement peut vous offrir. Je ne sais pas de bornes moi-même, mais peut-être une sorte de code MDS peut-être y parvenir.

EDIT: Après une recherche rapide je l'ai trouvé RSCode bibliothèque et dans la section exemple il est dit que 

In general, with E errors, and K erasures, you will need
* 2E + K bytes of parity to be able to correct the codeword
* back to recover the original message data.

ressemble donc comme le code Reed-Solomon est en effet la réponse et vous pouvez réellement obtenir la récupération d'un effacement et une erreur dans le code 8,4.

codes de parité fonctionnent aussi longtemps que deux octets de données différentes ne sont pas affectés par l'erreur ou de la perte et aussi longtemps que l'erreur ne correspond pas à un octet de données alors qu'un octet de parité est perdu, IMHO.

codes correcteurs d'erreurs peuvent en général ratures manche, mais dans la littérature la position de l'effacement est supposé connu. Dans la plupart des cas, l'effacement sera introduit par le démodulateur quand il est faible confiance que les données correctes peuvent être récupérées à partir du canal. Par exemple, si le signal est pas clairement 0 ou 1, le dispositif peut indiquer que les données ont été perdues, plutôt que de risquer l'introduction d'une erreur. Depuis un effacement est essentiellement une erreur avec une position connue, ils sont beaucoup plus faciles à corriger.

Je ne sais pas ce que votre situation est où vous pouvez perdre une seule valeur et vous pouvez être certain que les valeurs restantes sont livrées dans l'ordre correct, mais ce n'est pas une situation adresses de la théorie de codage classique.

Qu'est-ce que algorithmist suggère-dessus est la suivante: Si vous pouvez vous limiter à seulement 7 bits d'information, vous pouvez remplir le 8 bit de chaque octet avec une alternance de 0 et 1, ce qui vous permettra de connaître l'emplacement de l'octet manquant . Qui est, mettre un 0 dans le bit de poids fort des octets 0, 2, 4, 6 et un 1 dans les bits de poids fort des autres. Sur la réception, si vous ne recevez que 7 octets, disparus on aura été passé de entre octets dont correspondance bits de poids fort. Malheureusement, ce n'est pas tout à fait raison: si l'effacement et l'erreur sont adjacents, vous ne pouvez pas savoir immédiatement quel octet a été abandonné. Par exemple, les bits élevés 0101101 pourraient résulter d'une chute du 4ème octet, ou d'une erreur dans le 4ème octet et laissant tomber le 3ème, ou d'une erreur dans le 4ème octet et laissant tomber le 5ème.

Vous pouvez utiliser le code linéaire: 

1 0 0 0  0 1 1 1
0 1 0 0  1 0 1 1
0 0 1 0  1 1 0 1
0 0 0 1  1 1 1 0

(c.-à-vous envoyer des données comme (a, b, c, d, b + c + d, a + c + d, a + b + d, a + b + c) (où l'addition est mis en œuvre avec XOR, étant donné que a, b, c, d sont des éléments de GF (128))). Il est un code linéaire avec la distance 4, il peut corriger une erreur sur un seul octet. Vous pouvez décoder avec le décodage du syndrome noreferrer"> , et puisque le code est auto-dual, la matrice H sera le même que ci-dessus.

Dans le cas où il y a un octet tombé, vous pouvez utiliser la technique ci-dessus pour déterminer lequel il est. Une fois que vous avez déterminé que, vous essentiellement un code de décodage différent - le code « crevé » créé en laissant tomber cet octet donné. Étant donné que le code poinçonné est toujours linéaire, vous pouvez utiliser le décodage de syndrome pour déterminer l'erreur. Vous devez calculer la

Dans le cas des chiffres décimaux, en supposant un va de pair avec le premier chiffre impair, deuxième chiffre même, troisième chiffre impair, etc - avec deux chiffres, vous obtenez 00-99, qui peut être représenté en 3 paires / impaires / chiffres impairs (125 combinaisons au total) - 00 = 101, 01 = 103, 20 = 181, 99 = 789, etc. donc, on encode deux séries de chiffres décimaux en 6 chiffres au total, les deux derniers chiffres signifient des choses sur les premiers ensembles de 2 des chiffres ou une somme de contrôle de quelque sorte ... Le dernier chiffre à côté, je suppose, pourrait être une sorte d'indicateur impair / même sur chacun des messages initiaux 2 chiffres initiaux (1 = même 2 premiers chiffres, 3 = premier impair deux chiffres) et suivre le modèle d'être impair. Ensuite, le dernier chiffre pourrait être la place de celui d'une somme des chiffres individuels, de cette façon, si un chiffre manquait, il serait immédiatement apparente et pourrait être corrigée en supposant que le dernier chiffre était correct. Bien, il jeter des choses hors si l'un des deux derniers chiffres ont été abandonnées ...

Il semble être théoriquement possible si nous supposons 1 erreur binaire dans un mauvais octet. Nous avons besoin de 3 bits pour identifier les octets tombé et 3 bits pour identifier mauvais octet et 3 bits pour identifier peu mal. Nous avons 3 fois que le nombre de bits supplémentaires.

Mais si nous avons besoin d'identifier un certain nombre d'erreurs de bits dans un mauvais octet, il est à 30 bits. Même qui semble être possible avec 32 bits, bien que 32 est un peu trop près pour mon confort.

Mais je ne sais pas chaud pour encoder pour obtenir cela. Essayez turbocode?

En fait, comme Krystian dit, lorsque vous corrigez un code RS, le message et les octets « de parité » seront corrigées, aussi longtemps que vous avez v + 2e <(nk) où v est le nombre d'effacements (vous connaître la position) et e est le nombre d'erreurs. Cela signifie que si vous n'avez des erreurs, vous pouvez corriger jusqu'à (nk) / 2 erreurs ou (nk-1) effacements (environ le double du nombre d'erreurs), ou un mélange des deux (voir article de Blahut: Transformer les techniques de codes de contrôle d'erreur et < a href = "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.2084&rep=rep1&type=pdf" rel = "nofollow"> un décodeur universel Reed-Solomon ).

Ce qui est encore plus agréable est que vous pouvez vérifier que la correction a été un succès: en vérifiant que le polynôme de syndrome ne contient que 0 coefficients, vous savez que le message + parité octets sont tous les deux corrects. Vous pouvez le faire avant de vérifier si le message a besoin d'une correction, et vous pouvez également faire le contrôle après le décodage pour vérifier que le message et les octets de parité ont été complètement réparés.

La limite v + 2e- <(n-k) est optimale, vous ne pouvez pas faire mieux (c'est pourquoi Reed-Solomon est appelé un code de correction d'erreur optimale). En fait, il est possible d'aller au-delà de cette limite en utilisant des approches bruteforce, jusqu'à un certain point (vous pouvez gagner 1 ou 2 autres symboles pour chaque 8 symboles) en utilisant

Non affilié à StackOverflow
scroll top