# Canal-U

Mon compte

## 4.5. Error-Correcting Pairs

Copier le code pour partager la vidéo :
<div style="position:relative;padding-bottom:56.25%;padding-top:10px;height:0;overflow:hidden;"><iframe src="https://www.canal-u.tv/video/inria/embed.1/4_5_error_correcting_pairs.32943?width=100%&amp;height=100%" style="position:absolute;top:0;left:0;width:100%;height: 100%;" width="550" height="306" frameborder="0" allowfullscreen scrolling="no"></iframe></div> Si vous souhaitez partager une séquence, indiquez le début de celle-ci , et copiez le code : h m s
Contacter le contributeur
J’aime
Imprimer
partager

### 4.5. Error-Correcting Pairs

We present in this session a general decoding method for linear codes. And we will see it in an example. Let C be a generalized Reed-Solomon code of dimension k associated to the pair (c, d). Then, its dual is again a generalized Reed-Solomon code with the same locator and another column multiplier we will denote by d^ (d dual). Now, consider the codes A and B.  These codes have not been chosen at random. First, notice that the star product of these two codes is the dual of C. Suppose that these codes are known. We will present here an efficient decoding algorithm for C. So, let y be the received word, that is, it is a sum of  a valid codeword and an error vector, and suppose that there have been at most t errors. We define the following kernel that is the set of elements of the code A which are the solutions of this equation. We will see that the kernel associated to the received vector is equivalent to the kernel associated to the error vector. And the reason is very simple. First, notice that the star product of the codes A and B, as we have already said, is the dual of C. Moreover, by definition, the inner product of the code with its dual is 0.  So, the codeword would not affect this system. So, what do we have?  We have that the kernel associated to the received vector is equivalent to the kernel of the received vector. This is because the star product of A and B is the dual code. So, now, we look for a nontrivial element on this kernel, that is, a nontrivial solution of this system, where e is the error vector. Let us define, first, the error locator polynomial associated to the vector c, that is, the root of this polynomial indicate the error position. The evaluation of this element belongs to the code A if, and only if, the dimension of A is greater than t.

•
Label UNT : UNIT
•
Date de réalisation : 5 Mai 2015
Durée du programme : 6 min
Classification Dewey : Analyse numérique, Théorie de l'information, données dans les systèmes informatiques, cryptographie, Mathématiques
•
Catégorie : Vidéocours
Niveau : niveau Master (LMD), niveau Doctorat (LMD), Recherche
Disciplines : Mathématiques, Informatique, Informatique, Mathématiques et informatique
Collections : 4: Key Attacks
ficheLom : Voir la fiche LOM
•
Auteur(s) : MARQUEZ-CORBELLA Irene, SENDRIER Nicolas, FINIASZ Matthieu
•
Langue : Anglais
Mots-clés : algèbre linéaire, chiffrement à clé publique, cryptage des données, cryptographie, code correcteur, algorithmes, GRS code
Conditions d’utilisation / Copyright : 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.

## commentaires

Ajouter un commentaire Lire les commentaires
*Les champs suivis d’un astérisque sont obligatoires.
Aucun commentaire sur cette vidéo pour le moment (les commentaires font l’objet d’une modération)