Informations pratiques

Description de la ressource

Résumé

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.

"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)

• Cette ressource fait partie de
  • 2: McEliece Cryptosystem