Lors d'une transmission de données (clé USB, câble Ethernet, ...), des erreurs de transmission peuvent se produire (par exemple à cause d'une baisse de tension, ...). Une branche de l'informatique consiste donc à rechercher des algorithmes permettant de déceler et corriger ces erreurs, si elles ne sont pas trop nombreuses. Ces algorithmes trouvent aussi une application dans les lecteurs de CD car ils permettent de corriger des erreurs dues à la présence de poussières, rayures, ...
Le but de cet exercice est de programmer une méthode simple de correction d'erreurs, qui porte sur des matrices de 64 bits. Un bit sera représenté par un entier : 0 ou 1. Une matrice, type inexistant en Caml, sera représentée par un tableau de tableaux d'entiers. Ainsi, on pourra effectuer les opérations suivantes :
   - création d'une matrice contenant l'élément a : Array.make_matrix 8 8 a
   - accès à l'élément d'une matrice m en ligne i et en colonne j : m.(i).(j)
   - modification de cet élément pour lui affecter la valeur a : m.(i).(j) <- a
   Attention ! L'indexation des tableaux commence à 0. Les lignes et colonnes sont donc numérotées de 0 à 7.

1) Ecrivez une fonction ligne qui prend une matrice m et un entier a (entre 0 et 7) et qui rend la somme des éléments de la ligne a de m, en modulo 2 (si la ligne a de m est [|0;1;0;1;1;1;0;1|], on rend 1). Ecrivez ensuite la fonction colonne qui fait la somme modulo 2 de la colonne b.
Ici, il semble beaucoup plus simple de faire une fonction impérative :
let ligne m a =
let somme = ref 0 in
for j = 0 to 7 do somme := !somme + m.(a).(j) done;
!somme mod 2;;
Mais on peut aussi faire une récurrence (je ne la ferai qu'une fois dans l'exercice) :
let ligne m a =
let rec aux indice somme = if indice = 8 then somme else aux (indice+1) (somme + m.(a).(indice))
in (aux 0 0) mod 2;;
Et la fonction colonne :
let colonne m b =
let somme = ref 0 in
for i = 0 to 7 do somme := !somme + m.(i).(b) done;
!somme mod 2;;

2) Déduisez-en la fonction sommes_lignes qui prend une matrice m et rend le tableau à 8 éléments tel que son i-ème élément soit la somme modulo 2 de la i-ème ligne de m. Faites ensuite la fonction sommes_colonnes qui fait de même avec les colonnes de m.
Là aussi, on pourrait faire des fonctions récursives, mais je me contenterai d'impératives. On n'a qu'à appliquer les fonctions précédentes :
let sommes_lignes m = let resu = Array.make 8 0 in
for i = 0 to 7 do resu.(i) <- ligne m i done; resu;;
let sommes_colonnes m = let resu = Array.make 8 0 in
for i = 0 to 7 do resu.(i) <- colonne m i done; resu;;

3) L'algorithme qu'on va utiliser est en fait peu puissant : il ne peut corriger qu'au plus une erreur.
L'émetteur veut transmettre une matrice M. Il calcule d'abord L = sommes_lignes (M) et C = sommes_colonnes (M). Il transmet alors le triplet (M,L,C) au destinataire. On suppose qu'au cours de la transmission, se produit au plus une erreur (mais peut-être aucune).
Le destinataire reçoit alors (M2,L2,C2). Il calcule L3 = sommes_lignes (M2) et C3 = sommes_colonnes (M2).
Comment, à partir de M2, L2, C2, L3 et C3, peut-on reconstituer la matrice M d'origine ?
Examinons les cas :
   - s'il n'y a eu aucune erreur, M2 correspond à M. Alors L3 = L2 et C3 = C2.
   - s'il y a eu une erreur portant sur la transmission de M2 (M2 différent de M) alors la somme des lignes et des colonnes de M2 et M vont être égales sauf pour une ligne et une colonne. Donc L2 et L3 diffèrent par un seul élément a, C2 et C3 diffèrent par un seul élément b et l'élément en ligne a et colonne b de M2 est l'erreur cherchée.
   - s'il y a eu une erreur sur L2 ou C2 alors soit C3 = C2 et L3 différent de L2 soit l'inverse. La matrice M2 est correcte.
Comme on a envisagé tous les cas, on peut inverser le raisonnement :
   - soit L3 est différent de L2 et C3 est différent de C2. Alors il y a bien une erreur dans M2 qu'on retrouve en cherchant les éléments différents de L2/L3 et C2/C3
   - soit L3 est différent de L2 et C3 = C2, soit l'inverse, soit C3 = C2 et L3 = L2. Dans ces cas, il y a soit aucune erreur, soit une erreur mais pas sur M2. Donc M = M2.

4) On suppose qu'il y a eu une erreur de transmission sur M (donc M2 différente de M). Ecrivez alors une fonction corrige2 qui reçoit M2 L2 C2 et qui rend M.
Solution

> Haut de la page