Canal-U

Mon compte
Inria

2.7. Reducing the Key Size - LDPC codes


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/2_7_reducing_the_key_size_ldpc_codes.32847?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) :
MARQUEZ-CORBELLA Irene
SENDRIER Nicolas
FINIASZ Matthieu

Producteur Canal-U :
Inria
Contacter la chaine
J’aime
Imprimer
partager facebook twitter

2.7. Reducing the Key Size - LDPC codes

LDPC codes have an interesting feature: they are free of algebraic structure. We will study in detail this proposal for the McEliece cryptosystem in this session. LDPC codes were originally introduced by Gallager, in his doctoral thesis, in 1963. One of the characteristic of LDPC codes is the existence of several iterative decoding algorithms which achieve excellent performances. Tanner, later, in the 1981, introduced a graphical representation to these codes as bipartite graph. However, they remained almost forgotten by the coding theory community until 1996 when MacKay and Neal re-discovered these codes, promoting them to the select group of good linear codes for telecommunication applications. LDPC codes admit two different representations: on one hand, we have the matrix representation. LDPC codes admit a sparse parity-check matrix, that is, it contains few non-zero entries in comparison to the amount of zeros. And we have also a graphical representation. LDPC codes could be represented with a graph which is also known as the Tanner graph. First of all, recall the definition of a bipartite graph which is a graph that we can partition the set of vertices into two nonempty disjoint sets such that no two vertices within the same set are adjacent. Now, let H be a sparse matrix. We will denote the set of variable nodes
to the column of the parity-check matrix and the check nodes to the rows of the parity-check matrix. And we define an edge between the j check nodes and the i variable nodes if the entry (i,j) at the matrix H is non-zero. For example, if we have a binary LDPC codes with this parity-check matrix then we can associate the following Tanner graph. The first parity-check equation gives us this relation. The second parity-check equation gives us this other relation and the third one gives us the complete graph. We explain here an iterative decoding algorithm for LDPC codes which is called the Bit-Flipping algorithm, which was already introduced by Gallager.

  •  
    Label UNT : UNIT
  •  
    Date de réalisation : 5 Mai 2015
    Durée du programme : 5 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 : 2: McEliece Cryptosystem
    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, McEliece, LDPC, MDPC
    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
Mon Compte