Ressource pédagogique : 1.6. Decoding (A Difficult Problem)

Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (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)

Thème(s)