![Canal-U](https://www.enseignementsup-recherche.gouv.fr/ressources-pedagogiques/media/repositories/CANAL-U.png)
Sommaire
1.6. Decoding (A Difficult Problem)
Date de création :
05.05.2015Auteur(s) :
Irene MARQUEZ-CORBELLA, Nicolas SENDRIER, Matthieu FINIASZPrésentation
Informations pratiques
Droits réservés à l'éditeur et aux auteurs. Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.
Description de la ressource
Résumé
The process of correcting errors and obtaining back the message is called decoding. In this sequence, we will focus on this process, the decoding. We would like that the decoder of the received vector, which is the encoding of the original message plus a certain vector, is again the original message, for every message and every reasonable noisy pattern. The basis of decoding is the following principle, called Minimum Distance Decoding. Given a received vector, we look for a codeword that minimizes the Hamming distance with the received vector One of the most obvious decoding algorithms is Brute Force. What do we have to do? First of all, enumerate all codewords until we find one at distance t or less from the received vector. And we return such codeword. The complexity of this Brute Force is n*q^k since we have to compare the received vectors, and all the codewords; recall that we have q^k codewords. Thus, large parameters make any Brute Force method impractical. Let us explain a decoding method using parity check matrices. A vector is in the code if an only if this product is 0.
"Domaine(s)" et indice(s) Dewey
- Analyse numérique (518)
- Théorie de l'information (003.54)
- données dans les systèmes informatiques (005.7)
- cryptographie (652.8)
- Mathématiques (510)
Domaine(s)
- Analyse numérique
- Analyse numérique appliquée, calcul numérique, mathématiques numériques
- Programmation : Algorithmique, langages, conception objet, programmes
- Informatique
- Informatique
- Expression orale et écrite
- Cryptographie
- Généralités, philosophie, théorie des mathématiques
- Généralités
- Outils, méthodes et techniques scientifiques
- Didactique des mathématiques
- Histoire des mathématiques
- Mathématiques et physique
Document(s) annexe(s)
- Cette ressource fait partie de
Fiche technique
- LOMv1.0
- LOMFRv1.0
- Voir la fiche XML