Worldlex Wiki théorie du codage , le décodage est le processus de traduction des messages reçus en mots de code d'un code donné . Il existe de nombreuses méthodes courantes de conversion des messages en mots de code. Celles-ci sont souvent utilisées pour récupérer des messages transmis sur un canal bruité , tel qu'un canal binaire symétrique .
est considéré comme un code binaire de longueur ; doivent être des éléments de ; et est la distance entre ces éléments.décodage par un observateur idéal
On peut donner le message , puis le décodage par un observateur idéal génère le mot de code . Le processus aboutit à la solution suivante :
Par exemple, une personne peut choisir le mot de code le plus susceptible d'être reçu comme message après transmission.
Conventions de décodage
Chaque mot de code n'a pas une probabilité d'apparition fixe : plusieurs mots de code peuvent avoir une probabilité égale de se transformer en message reçu. Dans ce cas, l'expéditeur et le(s) destinataire(s) doivent convenir au préalable d'une convention de décodage. Voici quelques conventions courantes :
- Demande de renvoi du mot de passe – requête de répétition automatique .
- Choisissez un mot de code aléatoire parmi l'ensemble des mots de code les plus probables qui s'en rapproche le plus.
- Si un autre code suit , marquez les parties ambiguës du mot de code comme des effacements et espérez que le code externe les lèvera.
- Signalez au système toute erreur de décodage.
Décodage par maximum de vraisemblance
Décodage à distance minimale
Étant donné un vecteur reçu , le décodage à distance minimale choisit un mot de code pour minimiser la distance de Hamming :
c'est-à-dire choisir le mot de code qui est le plus proche possible de .
Notez que si la probabilité d'erreur sur un
alors:
qui (puisque p est inférieur à la moitié) est maximisé en minimisant d .
Le décodage par distance minimale, également appelé décodage au plus proche voisin , peut être assisté ou automatisé à l'aide d'un tableau standard . Cette méthode est pertinente lorsque les conditions suivantes sont réunies :
- La probabilité qu'une erreur se produise est indépendante de la position du symbole.
- Les erreurs sont des événements indépendants – une erreur à un endroit du message n'affecte pas les autres endroits.canal binaire symétrique . Elles peuvent s'avérer déraisonnables pour d'autres supports, comme un DVD , où une simple rayure sur le disque peut entraîner une erreur dans de nombreux symboles ou mots de code voisins.
Comme pour les autres méthodes de décodage, une convention doit être convenue pour le décodage non unique.
Décodage des syndromes
Le décodage par syndrome est une méthode très efficace pour décoder un code linéaire sur un canal bruité , c'est-à-dire un canal sujet à des erreurs. En substance, le décodage par syndrome est un décodage à distance minimale utilisant une table de consultation réduite . Ceci est rendu possible par la linéarité du code.
Supposons que soit un code linéaire de longueur et de distance minimale avec une matrice de contrôle de parité . Alors, il est clair que est capable de corriger jusqu'à .
erreurs commises par le canal (car s'il n'y a pas plus d' erreurs, le décodage à distance minimale décodera correctement le mot de code transmis incorrectement).
Supposons maintenant qu'un mot de code soit envoyé sur le canal et qu'une erreur se produise. Le vecteur est alors reçu. Un décodage classique par distance minimale consisterait à rechercher dans une table de taille n la correspondance la plus proche, c'est-à-dire un élément (pas nécessairement unique) dont le vecteur correspond à la valeur de n.
pour tous . Le décodage par syndrome exploite la propriété de la matrice de parité selon laquelle :
pour tous . Le syndrome du patient est défini comme suit :
Pour effectuer un décodage ML dans un canal binaire symétrique , il faut consulter une table précalculée de taille , correspondant à .
Notez que cela est déjà d'une complexité nettement inférieure à celle d'un décodage de tableau standard .
Toutefois, en supposant qu'il n'y ait pas eu plus de 10 erreurs lors de la transmission, le récepteur peut rechercher la valeur dans une table encore plus réduite de taille 1.
Décodage de liste
La forme la plus simple est due à Prange : soit la matrice génératrice de utilisée pour le codage. Sélectionnons aléatoirement des colonnes de et notons la sous-matrice correspondante de . Avec une probabilité raisonnable , sera de rang maximal, ce qui signifie que si l'on note le sous-vecteur correspondant aux positions de tout mot de code de pour un message , on peut retrouver comme . Par conséquent, si nous avons la chance que ces positions du mot reçu ne contiennent aucune erreur, et correspondent donc aux positions du mot de code envoyé, alors nous pouvons décoder .
En cas d'erreurs, la probabilité d'une telle sélection de colonnes est donnée par .
Cette méthode a été améliorée de diverses manières, par exemple par Stern et Canteaut et Sendrier.
Réponse partielle, vraisemblance maximale
Décodeur Viterbi
Algorithme de décodage de décision optimal (ODDA)
Algorithme de décodage de décision optimal (ODDA) pour un système TWRC asymétrique.
Plus d articles de Worldlex Wiki
Revenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais.
Explorer l index