Canal-U

Mon compte
Inria

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
Auteur(s) :
FINIASZ Matthieu
MARQUEZ-CORBELLA Irene
SENDRIER Nicolas

Producteur Canal-U :
Inria
Contacter le contributeur
J’aime
Imprimer
partager facebook twitter Google +

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)
 

Dans la même collection

FMSH
 
Facebook Twitter Google+
Mon Compte