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