Vidéo pédagogique

4.7. Attack against Reed-Muller codes

Durée : 00:05:47 -Réalisation : 5 mai 2015 -Mise en ligne : 5 mai 2015
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3

In this session, we willintroduce an attack against binary Reed-Muller codes. Reed-Muller codes wereintroduced by Muller in 1954 and, later, Reed provided thefirst efficient decoding algorithm for these codes. Reed-Muller are just ageneralization of generalized Reed-Solomon codes. Generalized Reed-Solomoncodes are evaluation of univariate polynomials,and Reed-Muller codes are evaluation ofmultivariate polynomials. We will study binary Reed-Muller codes. The binary Reed-Mullerconsists of the set of codewords obtained by evaluating all theBoolean functions of degree r with m variables. Thus, theblock length of this code is 2^m. The dimension is anumber of polynomials of degree r with binary coefficient, andthe minimum distance is 2^m - r. Let us study two examples. The first example is aReed-Muller associated to the evaluation of all monomialsof degree 1 in three variables. The vectors associatedto these monomials are the following ones, which gives agenerator matrix of the code. This code has parameters:length 8, dimension 4, and minimum distance 4, thatis, it detects two errors and correct just one error.Take notice that the matrix of a Reed-Muller code withdegree bound 1 has a particular form. If we remove the firstrow, then we have at  the i-th column just the number i-1read as a binary number. And this property willbe the key of the attack. Now, we have another example. We have the binaryReed-Muller code associated to the evaluation of monomialsof degree up to 2 in four variables. The vectorsassociated to this monomial are the following ones, which givea generator matrix of the code. This code has length 16,dimension 11, and minimum distance 4. Let us see someproperties of Reed-Muller code. First of all, we have thefollowing decreasing sequence. The code with the same degreebound as variables is the whole space. And moreover, the dual of aReed-Muller code is again a Reed-Muller code. And the proof is very easy.Just note that the dimension of the sum of these twocodes is 2^n, that is, the whole space. Moreover, the starproduct of these two codes is - this special code, which isthe code with all even weight vectors.

Langue :
Irene Marquez-Corbella (Intervenant), Nicolas Sendrier (Intervenant), Matthieu Finiasz (Intervenant)
Conditions d'utilisation
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.
Citer cette ressource :
Irene Marquez-Corbella, Nicolas Sendrier, Matthieu Finiasz. Inria. (2015, 5 mai). 4.7. Attack against Reed-Muller codes. [Vidéo]. Canal-U. (Consultée le 29 septembre 2023)

Dans la même collection

Avec les mêmes intervenants

Sur le même thème