X Informatique MP 2007

Thème de l'épreuve Codage de Reed-Solomon
Principaux outils utilisés polynômes, arbres, listes, récursivité
Mots clefs codage de Reed-Solomon, polynôme, arbre, division euclidienne, quotient, modulo, liste

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                       

Rapport du jury

(télécharger le PDF)
           

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE POLYTECHNIQUE FILIÈRE MP OPTION INFORMATIQUE CONCOURS D'ADMISSION 2007 COMPOSITION D'INFORMATIQUE (Durée : 4 heures) L'utilisation des calculatrices n'est pas autorisée pour cette épreuve. On attachera une grande importance a la concision, a la clarté, et a la précision de la rédaction. *** Codage Reed-Solomon Ce problème s'intéresse aux codes de correction d'erreurs de Reed-Solomon. On souhaite trans-- mettre un message au travers d'un canal de communication bruite" : les données émises sont modi-- fiées par quelques erreurs lorsqu'elles sont reçues. Pour permettre néanmoins la transmission fiable d'un message, la donnée émise est un codage du message, plus long que le message lui-même. La redondance ainsi ajoutée permet de corriger ensuite des erreurs qui peuvent apparaître lors de la transmission. Les codes appelés codes de Reed-Solomon ont de nombreuses applications : les CDs, DVDs, les systèmes ADSL, ou encore de nombreuses sondes spatiales utilisent des codes bâtis autour des codes de Reed--Solomon. Le préambule donne les définitions communes a l'ensemble de l'énoncé, et introduit les codes de Reed-Solomon. La partie I s'attache au calcul du codage d'un message. La partie Il définit quelques fonctions de manipulation de polynômes. La partie III poursuit cette étude par la mise en oeuvre d'algorithmes de meilleure complexité. Enfin, la partie IV permet d'améliorer la complexité du codage. On notera que le problème du décodage {retrouver un message original a partir d'une transmission bruitée) n'est pas traité dans ce problème. Les parties 1 a Ill peuvent être traitées indépendamment. La partie IV repose sur les résultats de la partie III. Préambule : Définitions et notations Dans l'ensemble de l'énoncé, on fixe un nombre premier }) inférieur a 215 (de telle sorte que le produit de deux entiers modulo }) soit toujours représentable par un simple entier positif en Caml ou en Pascal). Les calculs liés aux codes de Reed--Solomon seront réalisés dans le corps le : Z/pZ des entiers modulo p. On rappelle que l'opération << modulo >> est réalisée par l'opérateur mod en Caml et en Pascal, où on suppose également disposer de la fonction inv suivante pour calculer l'inverse modulo }) de tout entier a vérifiant 0 < a < p : (* Caml *) { Pascal } (donné) inv : int --> int (donné) function inv(azinteger) : integer Toutes les questions ayant trait a la complexité des programmes écrits demandent comme réponse une borne supérieure (raisonnable) du type O() sur le nombre d'opérations dans le : chacune des opérations dans le (addition, multiplication, inversion) est considérée de complexité 1. 1 On manipulera des listes d'entiers modulo p en les identifiant avec des polynômes. Ainsi la liste de (d + 1) entiers  correspond au polynôme A(X ) : ZÎ=0 a.;Xi de degré inférieur ou égal a d, a coefficients dans E,. On notera couramment degA le degré d'un polynôme A(X ) Les listes d'entiers modulo p sont des valeurs du type poly, défini comme suit : (* Caml *) { Pascal } type poly = int list;; type poly = "polycoeff; polycoeff = record coeff: integer; suivant: poly; end; En Pascal la liste vide est nil, et l'on pourra utiliser la fonction suivante pour construire des listes : { Pascal } function nouveauPolynome(a : integer ; (Q : poly) : poly; var r : poly; begin new(r); r".coeff := a. ; r".suivant := Q; nouveauPolynome := r; end; Pour définir le codage de Reed--Solomon, on fixe deux constantes entières k et 77. qui vérifient O de k entiers modulo p, tandis que le codage est une liste B :  de n entiers modulo p. On peut aussi voir le message comme un polynôme A(X ) de degré inférieur ou égal a le -- 1. Le codage utilise comme paramètre une liste oz : {cm, . . . ,dn_1> de n entiers modulo p, et est calculé comme suit : k--1 |A :  | -->|B :  | , avec b; : A(oz;) : Zou--cd modp. message codage j =O Dans les programmes qu'on écrira, on considérera les entiers k, 77. et p comme des constantes globales. Partie I. Codage de Reed-Solomon, première version Question 1 Écrire la fonction valeur qui prend comme arguments un polynôme U a coefficients dans E, et un entier a:; et qui retourne la valeur U (513) dans E, de ce polynôme en cet entier a:. (* Caml *) valeur : poly --> int --> int { Pascal } function valeur(U : poly ; a: : integer) : integer Question 2 Écrire la fonction codage qui prend comme arguments la liste 04 : (cm, . . . ,an_1> et le polynôme A(a:) ; et qui retourne le codage de Reed--Solomon du message A. (* Caml *) codage : poly --> poly --> poly { Pascal } function codage(a : poly ; A : poly) : poly Question 3 Quelles sont les complexités des fonctions valeur et codage en fonction de n et k ? Partie II. Polynômes Dans cette partie) toutes les opérations retournent des polynômes a coefficients dans le. Question 4 Écrire la fonction addition qui prend comme arguments deux polynômes U (X ) et V(X ) a coefficients dans le, représentés par des listes de ÆU et EURV coefficients; et qui retourne la somme de ces deux polynômes. Les coefficients du résultat sont aussi dans le. Déterminer la complexité de cette fonction en fonction de ÆU et (V- (* Caml *) addition : poly --> poly --> poly { Pascal } function addition(U : poly ; V : poly) : poly Question 5 Écrire de même la fonction soustraction qui prend comme arguments deux poly-- nômes U (X ) et V(X ) a coefficients dans le, représentés par des listes de ÆU et EURV coefficients; et qui retourne la différence U (X ) -- V(X ) Déterminer la complexité de cette fonction en fonction de ËU et Ëv. (* Caml *) soustraction : poly --> poly --> poly { Pascal } function soustraction(U : poly ; V : poly) : poly Question 6 Écrire la fonction produitParScalaire qui prend comme arguments un polynôme U (X )) représenté par la liste de ÆU coefficients7 et un entier 5 dans &; et qui retourne s >< U (X ) Donner la complexité de cette fonction en fonction de EURU. (* Caml *) produitParScalaire : poly --> int --> poly { Pascal } function produitParScalaire(U : poly ; s : integer) : poly Question 7 Écrire la fonction produit qui prend comme arguments deux polynômes U (X ) et V(X), représentés par des listes de ÆU et EURV coefficients; et qui retourne le produit de ces deux polynômes. Déterminer la complexité de cette fonction en fonction de ÆU et (V- (* Caml *) produit : poly --> poly --> poly { Pascal } function produit(U : poly ; V : poly) : poly 3 Question 8 Soit un polynôme U (X ) de degré inférieur ou égal a dU représenté par une liste de ÆU : (dU + 1) entiers, et un polynôme non nul V(X ) de degré exactement égal a dv, représenté par une liste de EURV : (dv + 1) entiers. Écrire la fonction division qui calcule le quotient de la division euclidienne de U (X ) par V(X), noté U div V. On rappelle que le résultat de la division euclidienne d'un polynôme U (X ) par un polynôme non nul V(X ) est l'unique couple (Q(X ), R(X )) (quotient et reste) vérifiant : U(X) =Q(X)V(X)+R(X), degR < dv. Déterminer la complexité de la fonction division en fonction de ÆU et ËV- (* Caml *) division : poly --> poly --> poly { Pascal } function division(U : poly ; V : poly) : poly Question 9 Écrire la fonction modulo qui prend comme arguments deux polynômes U (X ) et V(X ) ; et qui calcule le reste de la division euclidienne de U (X ) par V(X ) Quelle est la complexité de cette fonction ? (* Caml *) modulo : poly --> poly --> poly { Pascal } function modulo(U : poly ; V : poly) : poly Dans la suite du problème) le reste de la division euclidienne de U (X ) par V(X ) est noté U mod V. Partie III. Multiplication et division rapide Cette partie s'attache a l'amélioration de la complexité des algorithmes de multiplication et de division de polynômes. La notation La:l (respectivement loel) désigne la partie entière inférieure (respectivement la partie entière supérieure) d'un nombre réel a:. On remarque qu'on a, pour tout - w ° d d _ nombre ent1er d, lequat10n (fl + bl -- d. Multiplication Soient deux polynômes U (X ) et V(X ) représentés par les listes (uO7 . . . ,ug_1> et (co, . .. ,Ug_1> ayant EUR coefficients (le degré de U et V est donc au plus EUR -- 1). On pose 6 : (% puis Ub : (u0, . .. ,u6_1> et Uh : (ue, . .. ,ug_1>, de sorte que U : Ub +X6Uh. On définit de même Vb et Vh. Lorsqu'on écrit le produit U (X )V(X )) on fait apparaitre quatre produits impliquant les polynômes Uh, Ub, Vh, % : U(X)V(X) = (UbX6 + Ub) (VhX6 + Vb), = Uhth2EUR + (Ubi/}) + Uth) X6 + Ubi/b. Question 10 Donner une formule par laquelle le produit U (X )V(X ) s'exprime sous la forme VVsz26 + VV...XEUR + W5, où les polynômes W... W... et Wb se calculent avec seulement trois produits impliquant les polynômes U... V... Ub, V},, Uh + Ub et Vh + V5. 4 Question 11 Écrire la fonction produitRapide qui prend comme arguments deux polynômes U (X ) et V(X ) représentés par des listes de EUR coefficients; et qui calcule leur produit, avec une complexité O (EUR10g2 3) dans le cas où EUR est une puissance de 2. Justifier cette formule de complexité. (* Caml *) produitRapide : poly --> poly --> poly { Pascal } function produitRapide(U : poly ; V : poly) : poly Division Il est possible d'obtenir une amélioration similaire de la division de polynômes. Soit un dividende U (X ) et un diviseur non nul V(X ), respectivement représentés par les listes  et  d'entiers. On suppose que vg_1 est non nul, de telle sorte que deg V est exactement égal a d = EUR -- 1. Le degré de U est au plus égal a 2d : 2EUR -- 2. Comme pour la multiplication, on sépare les entrées en << partie haute >> et << partie basse >>. On pose 6 : L%J : l%l, puis Uh : , U;, : , Vh : , Vb : . Le découpage est représenté par la figure 1. Attention, selon la parité de d, on a2<9=dou2<æ=d+l. On recherche le quotient Q, écrit sous la forme Q : X6Qh+Qb avec deg Qh S d--e et deg Qb < 6. Les formules suivantes donnent la valeur de Q}, et Qb. -- Q,, est le quotient de la division de U ;, par V;,. -- R,, est le reste de cette même division. -- Qb est le quotient de la division de S : <80, . .. 782(d--e)> par Vh, où : S = X6R.. + uge_1XEUR--l -- thb. Ub = <%. - -- ,U2e_1> U}. =  A A U : Ub + X26Uh |...,| ................. r..26| ................. |...| V=Vb+Xth IUÜI °°°°°° |%l °°°°°°° lUdl % %. degU;,£2(d--e), degUb<26, deth=d--e, degV}, poly --> poly { Pascal } function divisionRapide(U : poly ; V : poly) : poly Question 13 Écrire la fonction moduloRapide qui prend comme arguments deux polynômes U (X ) et V(X ) (toujours soumis a la contrainte degU S 2deg V); et qui calcule le reste de la division euclidienne de U (X ) par V(X), plus rapidement qu'avec la fonction modulo de la question 11.9. Quelle est la complexité de la fonction moduloRapide ? (* Caml *) moduloRapide : poly --> poly --> poly { Pascal } function moduloRapide(U : poly ; V : poly) : poly Partie IV. Codage par évaluation multi--points L'objectif de cette partie est de proposer un autre algorithme pour calculer le codage de Reed-- Solomon par une stratégie de type << diviser pour régner >>. On commence par construire un arbre binaire dont les noeuds sont étiquetés par des polynômes. Un arbre de sous-produits pour les polynômes X -- dg, X -- cn, . . . X -- dn_1 est défini comme suit : les X -- a; sont les étiquettes des feuilles de l'arbre (par ordre des indices i croissants dans l'ordre de lecture des feuilles de la gauche vers la droite)) chaque noeud interne est étiqueté par le produit des polynômes étiquetant ses noeuds fils. Un arbre de sous--produits est dit optimal s'il est de hauteur h minimale (2h_1 < 77. S 2h), et si les degrés des polynômes étiquetant deux fils d'un même noeud diffèrent d'au plus un. La figure 2 représente un tel arbre de sous--produits de hauteur h = 3 pour une famille de 6 polynômes X -- dg, . . . ,X -- a5. m0mlm2m3m4m5 /\ m0m1m2 m3m4m5 /\ /\ m0m1 m2 m3m4 m5 ...! \... ...! \... FIG. 2: Un arbre de sous--produits optimal pour (mo, . . . ,m5), avec la notation m; = X -- cri. Un arbre de sous--produits est représenté par une valeur de type arbre, défini comme suit : (* Caml *) { Pascal } type arbre = Vide type arbre = "noeud; l Noeud of poly * arbre * arbre noeud = record etiquette: poly; filsG: arbre; filsD: arbre; end; L'arbre vide (sans aucun noeud) est représenté par Vide en Caml et par nil en Pascal. Question 14 Écrire la fonction arbreSousProduits qui prend comme argument la liste  arbre { Pascal } function arbreSousProduits(a: poly) : arbre On souhaite maintenant calculer un second arbre, appelé arbre des restes de A(X ) Il est similaire a l'arbre de sous--produits calculé a la question précédente) mais les étiquettes des noeuds diffèrent : a un noeud d'étiquette m dans l'arbre des sous--produits) correspond un noeud d'étiquette A(X ) mod m dans l'arbre des restes. La figure 3 donne l'arbre des restes de A(X ) qui correspond a l'arbre de la figure 2. A(X) mod m0m1mgmgm4m5 A(X )mod mom1m2 A(X )mod m3m4m5 A(X) mod m0m1 A(X) mod m2 A(X) mod m3m4 A(X) mod 7715 / \ / \ A(X) mod m0 A(X) mod m1 A(X) mod 7713 A(X) mod 7714 FIG. 3: Arbres des restes de A(X ) correspondant a la figure 2. On fait l'observation suivante. Soient (Q(X ), R1 (X ), R2 (X )) trois polynômes a coefficients dans le. Si on connait @ mod R1R2, on peut calculer @ mod R1 par l'opération : @ mod R1 = (@ mod R1R2) mod R1. Question 15 Écrire la fonction arbreRestes qui prend comme arguments l'arbre des sous-- produits et un polynôme A(X ) ; et qui retourne comme résultat l'arbre des restes de A(X ) Quelle est la complexité de la fonction arbreRestes lorsqu'on utilise les fonctions de la partie III ? Quelle est la complexité lorsqu'on ne les utilise pas ? (* Caml *) arbreRestes : arbre --> poly --> arbre { Pascal } function arbreRestes(T : arbre ; A : poly) : arbre À présent) on se sert de l'arbre des sous--produits pour factoriser les évaluations du même poly-- nôme A(X) aux nombreux points cm, cm, . . . an_1. On remarque qu'on a pour tout i (0 S i < 77.) : A(CQ) : A(X) mod (X -- ozi) Et on calcule ces valeurs a partir de A(X) mod (X -- dg)(X -- 041) - - - (X -- ozn_1) a l'aide de l'arbre des restes. Question 16 Écrire la fonction codageArbre qui prend comme arguments la liste 04 : (cm, . .. ,dn_1> et le polynôme A(a:) ; et qui retourne le codage de Reed-Solomon du message A en utilisant l'arbre de sous--produits correspondant a la suite des polynômes X -- cri. Déterminer sa complexité. (* Caml *) codageArbre : poly --> poly --> poly { Pascal } function codageArbre(oz : poly ; A : poly) : poly

Extrait du corrigé obtenu par reconnaissance optique des caractères


 X Informatique MP 2007 -- Corrigé Ce corrigé est proposé par Samuel Mimram (ENS Lyon) ; il a été relu par JeanBaptiste Rouquier (ENS Lyon) et Vincent Puyhaubert (Professeur en CPGE). Le sujet traite des codes de correction d'erreurs de Reed-Solomon, qui sont une méthode pour coder un message de façon redondante, donnant la possibilité de corriger certaines erreurs pouvant apparaître durant la transmission du message. Les polynômes sont un outil qui joue un rôle essentiel dans ce codage car il consiste à évaluer un polynôme en plusieurs points. Quatre parties relativement indépendantes sont proposées. Les trois premières invitent à programmer des fonctions usuelles de manipulation de polynômes (addition, multiplication, etc.), de deux façons différentes : une première méthode naïve et une seconde, de meilleure complexité, utilisant la stratégie « diviser pour régner ». La dernière partie demande l'écriture de fonctions pour créer des arbres étiquetés par des polynômes afin de réaliser une implémentation efficace du codage de ReedSolomon. Les questions sont de difficulté progressive. Ce sujet constitue une très bonne révision pour se préparer aux questions de programmation et de calcul de complexité aux concours, notamment pour les calculs de complexité de fonctions récursives. Indications 1 Écrire U(x) sous la forme u0 + x(u1 + x(· · · + x(un-2 + xun-1 ) · · · )). 2 Utiliser la fonction valeur pour évaluer le polynôme A en chaque i . 3 Montrer que valeur est en O(n) et codage en O(kn). 4 Additionner les coefficients de même degré des polynômes. 5 Proposer un programme similaire à celui de la question précédente. 7 Écrire U sous la forme U(X) = u0 + XU (X) et en déduire un algorithme récursif pour calculer le produit. 8 Adapter aux polynômes la méthode de division habituelle sur les entiers. 9 Utiliser la fonction division de la question précédente. 11 Utiliser l'écriture donnée à la question 10 pour implémenter de façon récursive la fonction. 13 Procéder comme à la question 9. 14 Diviser la liste h0 , . . . , n-1 i en deux et procéder récursivement. 16 Le codage du message peut se lire dans les feuilles de l'arbre des sous-produits. I. Codage de Reed-Solomon, première version Supposer p premier permet de s'assurer de l'existence systématique de l'inverse modulo p d'un entier non nul. En effet, pour tout entier a vérifiant 0 < a < p, le théorème de Bézout nous assure l'existence d'entiers x et y tels que ax + py = 1. L'entier ax est alors congru à 1 modulo p et x est donc un inverse de a modulo p. Les entiers x et y peuvent être calculés à l'aide de l'algorithme d'Euclide de la façon suivante : let rec euclide a b = if a mod b = 0 then 0, 1 else let x, y = euclide b (a mod b) in y, x - y * (a / b) ;; Une implémentation possible de la fonction inv qui calcule l'inverse d'un entier modulo p est donc let inv a = (p + fst (euclide a p)) mod p ;; Cette dernière fonction calcule l'entier x à l'aide de l'algorithme d'Euclide et renvoie son représentant canonique compris entre 0 et p (on rappelle que l'opération modulo en caml renvoie des valeurs négatives pour des entrées négatives). Pour tester les programmes, il faudra s'assurer d'avoir préalablement défini p comme un entier premier. La syntaxe correcte en caml-light pour définir le type poly nécessite deux signes d'égalité : type poly == int list;; 1 La fonction valeur peut être implémentée en utilisant l'algorithme de Horner : n-1 P la valeur U(x) du polynôme U(X) = ui Xi donné en entrée, en un entier x, peut i=0 être écrite sous la forme U(x) = u0 + x(u1 + x(· · · + x(un-2 + xun-1 ) · · · )) On en déduit l'implémentation récursive suivante : let rec valeur u x = match u with | ui::u' -> (ui + x * (valeur u' x)) mod p | [] -> 0 ;; Le calcul du modulo permet de s'assurer que les valeurs manipulées restent comprises entre 0 et p. On pouvait donner une implémentation de la fonction valeur encore plus courte : let valeur u x = list_it (fun ui accu -> (ui + x * accu) mod p) u 0 ;; On rappelle que la fonction list_it utilisée ici prend trois arguments : une fonction f , une liste hu0 , . . . , un-1 i et une valeur s. Elle renvoie f u0 (f u1 (...(f un-1 s)...)) On peut par exemple l'utiliser pour définir une fonction qui calcule la somme des éléments d'une liste d'entiers de la façon suivante let somme_list l = list_it (prefix +) l 0;; 2 La fonction codage associe à une liste = h0 , . . . , n-1 i et à un polynôme A, une liste B = hb0 , . . . , bn-1 i, où pour tout i, bi est la valeur du polynôme A en i . Une implémentation de cette fonction est donc let rec codage alpha a = match alpha with | ai::alpha' -> (valeur a ai)::(codage alpha' a) | [] -> [] ;; 3 La fonction valeur effectue une addition, une multiplication et un modulo pour chacun des n coefficients du polynôme A donné en argument. Ces opérations étant supposées s'effectuer en temps constant, on en déduit que La fonction valeur renvoie A() en O(n) opérations. La fonction codage effectue un modulo et un appel à la fonction valeur avec le polynôme A de degré k - 1 en argument pour chacun des n éléments de la liste . La fonction codage renvoie A() en O(kn) opérations. II. Polynômes 4 Le coefficient de degré i de la somme de deux polynômes U et V est la somme des coefficients de degré i de ces polynômes. Une implémentation de la fonction addition est alors : let rec addition u v = match u, v with | ui::u', vi::v' -> ((ui + vi) mod p)::(addition u' v') | _, [] -> u | [], _ -> v ;; On a pris soin de gérer les cas où les listes représentant les polynômes ne sont pas de même longueur. La fonction fait au plus une addition et un modulo pour chacun des coefficients de la plus longue des deux listes qu'elle parcourt. La fonction addition est en O(max(U , V )).