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

> Haut de la page