Si je veux envoyer un paquet de bits d et ajouter un autre r bits pour le code de correction d'erreur (d> r)
combien d'erreurs je peux trouver et corriger au maximum?code de correction d'erreur limite supérieure
Vous devriez probablement lire la page de wikipedia sur ce point:
http://en.wikipedia.org/wiki/Error_detection_and_correction
On dirait que vous voulez spécifiquement un code Hamming:
http://en.wikipedia.org/wiki/Hamming_code#General_algorithm
En utilisant ce système, vous pouvez rechercher quelques exemples de valeurs de la table liée.
Vous avez 2^d différents types de paquets de longueur d bits que vous souhaitez envoyer. L'ajout de vos r bits les transforme en mots de code de longueur d + r, donc vous avez maintenant 2^d mots de code possibles que vous pourriez envoyer. Le récepteur pourrait obtenir 2^(d + r) différents mots reçus (mots de code avec erreurs possibles). La question devient alors, comment mappez-vous ces 2^(d + r) mots reçus aux mots de code 2^d? Ceci est le minimum distance du code. C'est-à-dire, pour chaque paire de mots de code, trouvez le nombre de bits où ils diffèrent, puis prenez la plus petite de ces valeurs. Disons que vous aviez une distance minimale de 3. Vous avez reçu un mot et vous remarquez que ce n'est pas l'un des mots de passe. Autrement dit, il y a une erreur. Donc, en l'absence d'un meilleur algorithme de décodage, vous retournez le premier bit, et voyez si c'est un mot de code. Si ce n'est pas vous retournez et retournez le suivant. Finalement, vous obtenez un mot de passe. Puisque tous les mots de code diffèrent dans 3 positions, vous savez que ce mot de code est le "plus proche" du mot reçu, puisque vous auriez à retourner 2 bits dans le mot reçu pour arriver à un autre mot de code. Si vous n'obtenez pas un mot de passe en retournant juste un bit à la fois, vous ne pouvez pas savoir où sont les erreurs, car vous pouvez obtenir plusieurs mots de code en retournant deux bits, mais vous savez qu'il y en a au moins deux les erreurs. Cela conduit au principe général selon lequel, pour une distance minimale md, vous pouvez détecter les erreurs md-1 et corriger les erreurs floor ((md-1)/2). Le calcul de la distance minimale dépend des détails de la génération des mots de code, autrement dit du code. Il existe différentes limites que vous pouvez utiliser pour déterminer une limite supérieure sur md en fonction de d et (d + r). Paul mentionne le code de Hamming, qui est un bon exemple. Il atteint le Hamming bound. Pour le code Hamming (7,4), vous disposez de 4 bits et de 7 mots de code, et vous atteignez une distance minimum de 3. Evidemment *, vous n'allez jamais obtenir une distance minimale supérieure au nombre de bits que vous ajoutez c'est donc le meilleur que vous puissiez faire. Ne soyez pas trop habitués à cela. Le code Hamming est l'un des rares exemples d'un non-trivial perfect code, et la plupart d'entre eux ont une distance minimale inférieure au nombre de bits que vous ajoutez.
* Ce n'est pas vraiment évident, mais je suis à peu près certain que c'est vrai pour les codes de correction d'erreur non triviaux. L'ajout d'un bit de parité vous permet d'obtenir une distance minimale de deux, ce qui vous permet de détecter une erreur. Le code composé de {000,111} vous donne une distance minimale de 3 en ajoutant seulement 2 bits, mais c'est trivial.
Pourquoi la downvote? C'est la bonne réponse. –