Consignes

Le TP est à rendre, avant le mercredi 28 novembre à 23h59...

Le rendu de TP se fera uniquement à travers l'interface web TPLab. Vous devrez fournir un unique fichier .c contenant le code des fonctions demandées.

Vous pouvez utiliser le fichier Makefile fournit pour faciliter la compilation.

Certaines questions appellent à une réponse que vous pouvez mettre en commentaire dans votre fichier principal.

Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :

vous devrez essayer de réutiliser votre code du TP1 en copiant le fichier "tp1-nom.c" dans le répertoire "info-528-TP2",
votre fichier devra s'appeler "tp2-nom.c",
chaque fichier devra comporter un commentaire au début avec vos nom, prénom, filière et numéro du TP,
votre code doit compiler avec les options -Wall -Werror -Wextra -pedantic -std=c99,
une exécution des fonctions de test et de décodage / information du programme principal ne devra pas provoquer d'erreur sur les fichiers de test fournis.

Le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront pris en compte :

l'architecture de votre programme (code découpé en fonctions etc.),
la lisibilité de votre programme (choix pertinent pour les noms de variables etc.),
la présence de commentaires aux endroits appropriés,
la présence de documentation pour vos fonctions.

Liens utiles

QR codes - partie 2 : correction d'erreurs

Préliminaires

Nous avons vu dans le TP1 que les QR codes (version 1) contenait 26 octets de données. Parmi ces 26 octets, certains sont réservés à de la redondance d'information permettant de corriger certaines erreurs qui auraient pu survenir lors de la lecture du code : zones d'ombres, parties manquantes, déformation de l'image, etc.

Cette correction est souvent détournée à des fins commerciales ou artistiques en modifiant un QR code existant pour incorporer messages, logos, etc. (exemples du QR codes personnalisés sur Google images).

La norme des QR codes propose 4 niveaux de correction d'erreurs :

niveau L, qui permet en général de corriger 7% d'erreurs,
niveau M, qui permet en général de corriger 15% d'erreurs,
niveau Q, qui permet en général de corriger 25% d'erreurs,
niveau H, qui permet en général de corriger 30% d'erreurs.

Le taux de correction utilisé est codé dans 2 des bits du format (cf TP1) :

01 pour le niveau L,
00 pour le niveau M,
11 pour le niveau Q,
10 pour le niveau H.

correction d'erreurs dans le format

Le format est codé sur 15 bits, répétés à deux endroit dans le code. Sur ces 15 bits, seulement 5 sont des bits de données, et les 10 autres sont des bits de redondances. Les bits de redondances sont calculés grâce à un code « BCH » qui peut corriger 3 bits arbitraires du format.

Comme il n'y a que 2⁵ = 32 possibilités de format, le plus simple en cas d'erreurs détectées sur les 15 bits du format est simplement d'essayer chacun des 32 formats corrects et de garder celui qui diffère le moins du format erroné.

Écrivez la fonction

int correct_format(bit F[15]);

qui essaie de corriger un format (récupéré avec votre fonction get_format_bits du TP1) de 15 bits.

Vous devrez :

coder les 32 formats possibles (avec la fonction encode_format(const bit format_data[5], bit F[15]))
comparer chacun des formats possible avec le format (erroné) passé en argument (avec la fonction int hamming_format(bit *F1, bit *F2, int n)
garder le format valide le plus proche du format passé en argument.

Attention, s'il y a deux formats valides distincts à distance minimale du format donné en argument, vous ne pourrez donc pas choisir le format valide adéquat. La fonction devra donc renvoyer -1.

Pour tester:


fichier	`exemple-TP2-1.pbm`	`exemple-TP2-2.pbm`	`exemple-TP2-3.pbm`
format initial 1	`101010000101101`	`110111000011100`	`110001001000111`
format corrigé 1	`101110000101001`	`110111000010100`	`101011001000111`
nombre d'erreurs 1	2	1	3
format initial 2	`101110000101001`	`111111000010101`	`101011000010111`
format corrigé 2	`101110000101001`	`110111000010100`	`101011001000111`
nombre d'erreurs 2	0	2	2

Modifiez la fonction get_format du fichier tp1-nom.c (ou decode.c) pour qu'elle applique la correction du format quand elle détecte des erreurs dans le format.

correction d'erreurs dans les données

Pour les QR codes de version 1, sur les 26 octets de données :

dans le mode L, 7 sont des octets de redondance, permettant de corriger 3 octets erronés,
dans le mode M, 10 sont des octets de redondance, permettant de corriger 5 octets erronés,
dans le mode Q, 13 sont des octets de redondance, permettant de corriger 6 octets erronés,
dans le mode H, 17 sont des octets de redondance, permettant de corriger 8 octets erronés.

Ces données contiennent suffisamment d'information pour coder :

17, 14, 11 ou 7 caractères ASCII,
25, 20, 16 ou 10 caractères alphanumériques,
41,34, 27 ou 17 chiffres.

Syndromes et détection d'erreurs

Les 26 octets de données sont considérés comme les coefficients d'un polynôme de degré 25. La case 0 correspond au coefficient du monôme de degré 25, la case 1 au coefficient du monôme de degré 24, etc.

Les syndromes de ce polynôme sont les valeurs qu'il prend sur les octets 0x02ⁱ pour les valeurs de i entre 0 (compris) et le nombre d'octets de redondance (pas compris). Il y a donc autant de syndromes que d'octets de redondance.

Si les octets de donnés sont corrects, alors tous les syndromes sont égaux à 0x00.

Les opérations sur les octets se font grace à :

l'addition « ⊕ » qui est le XOR bit à bit ("^" en C),
la multiplication donnée par la fonction mult_coeff,
la division donnée par la fonction div_coeff,
la puissance est calculé avec la fonction pow_coeff.

Notez bien que la soustraction est identique à l'addition, c'est à dire au XOR bit à bit.

Programmez la fonction

byte eval_poly(const byte *P, int d, byte x);

qui évalue un polynôme (donné par le tableau P) de degré d sur une valeur x en utilisant les opération sur les octets.

Programmez ensuite la fonction

void data_syndrome(const byte *data, int n, byte *S);

qui calcule les n syndromes correspondants aux données contenues dans data (polynome de degré 25).

Pour tester :


fichier	`exemple-TP2-1.pbm`	`exemple-TP2-2.pbm`	`exemple-TP2-3.pbm`
nombre de syndromes	17	13	17
syndromes	`96, 74, cb, 2d, 79, 4d, ca, 07, c8, bc, 3a, ca, 7d, b1, 86, bd, 36`	`69, 73, a6, 55, 8f, 53, 0e, 49, c2, db, 7a, 36, 22`	`6a, 23, 9b, e3, b8, b8, ce, 7a, 01, 7a, f0, 75, 93, a9, dd, c5, 7c`

Et un exemple du TP1 :


fichier	`exemple-ASCII.pbm`
nombre de syndromes	7
syndromes	`00, 00, 00, 00, 00, 00, 00`

Note : pour obtenir le nombre d'octets de redondances (et donc le nombre de syndromes à calculer), il faut récupérer le taux de correction (fonction get_format) et prendre la valeur correspondante dans le tableau NB_DATA_BYTES.

pivot de Gauss

Le pivot de Gauss est une méthode pour résoudre les systèmes d'équations linéaires. L'idée est de transformer la matrice des coefficients du système d'équations par une suite d'étapes élémentaires pour obtenir une matrice où l'on peut directement lire les solutions.

Les opérations élémentaires sont :

intervertir deux lignes,
diviser une ligne par une valeur connue,
ajouter deux lignes et stocker le résultat dans la seconde.

Si on souhaite résoudre le système

    20 x ⊕ 31 y ⊕ 07 z  ==  36
    12 x ⊕ fa y ⊕ ff z  ==  88
    a5 x ⊕ 00 y ⊕ 76 z  ==  a8

on considère la matrice

  byte M[3][4] = {
    { 0x20, 0x31, 0x07, 0x36},
    { 0x12, 0xfa, 0xff, 0x88},
    { 0xa5, 0x00, 0x76, 0xa8}
  };

et on peut procéder comme suit :

matrice initiale :
20  31  07  36  
12  fa  ff  88  
a5  00  76  a8  
00  00  00  00  

===== On élimine la colonne 0 =====
20  31  07  36  
12  fa  ff  88  
a5  00  76  a8  
00  00  00  00  

>>> on passe la colonne 0 à 01 <<<

on divise la ligne 0 par 20
01  e3  19  fa  
12  fa  ff  88  
a5  00  76  a8  
00  00  00  00  

on divise la ligne 1 par 12
01  e3  19  fa  
01  b4  53  da  
a5  00  76  a8  
00  00  00  00  

on divise la ligne 2 par a5
01  e3  19  fa  
01  b4  53  da  
01  00  a5  b2  
00  00  00  00  

>>> on élimine les 01s de la colonne 0 <<<

on remplace la ligne 1 par la somme des lignes 0 et 1.
01  e3  19  fa  
00  57  4a  20  
01  00  a5  b2  
00  00  00  00  

on remplace la ligne 2 par la somme des lignes 0 et 2.
01  e3  19  fa  
00  57  4a  20  
00  e3  bc  48  
00  00  00  00  

===== On élimine la colonne 1 =====
01  e3  19  fa  
00  57  4a  20  
00  e3  bc  48  
00  00  00  00  

>>> on passe la colonne 1 à 01 <<<

on divise la ligne 0 par e3
f0  01  98  99  
00  57  4a  20  
00  e3  bc  48  
00  00  00  00  


on divise la ligne 1 par 57
f0  01  98  99  
00  01  88  bc  
00  e3  bc  48  
00  00  00  00  

on divise la ligne 2 par e3
f0  01  98  99  
00  01  88  bc  
00  01  55  05  
00  00  00  00  

>>> on élimine les 01s de la colonne 1 <<<

on remplace la ligne 0 par la somme des lignes 1 et 0.
f0  00  10  25  
00  01  88  bc  
00  01  55  05  
00  00  00  00  

on remplace la ligne 2 par la somme des lignes 1 et 2.
f0  00  10  25  
00  01  88  bc  
00  00  dd  b9  
00  00  00  00  

===== On élimine la colonne 2 =====
f0  00  10  25  
00  01  88  bc  
00  00  dd  b9  
00  00  00  00  

>>> on passe la colonne 2 à 01 <<<

on divise la ligne 0 par 10
0f  00  01  9d  
00  01  88  bc  
00  00  dd  b9  
00  00  00  00  

on divise la ligne 1 par 88
0f  00  01  9d  
00  49  01  09  
00  00  dd  b9  
00  00  00  00  

on divise la ligne 2 par dd
0f  00  01  9d  
00  49  01  09  
00  00  01  ce  
00  00  00  00  

>>> on élimine les 01s de la colonne 2 <<<

on remplace la ligne 0 par la somme des lignes 2 et 0.
0f  00  00  53  
00  49  01  09  
00  00  01  ce  
00  00  00  00  

on remplace la ligne 1 par la somme des lignes 2 et 1.
0f  00  00  53  
00  49  00  c7  
00  00  01  ce  
00  00  00  00  

matrice finale :
0f  00  00  53  
00  49  00  c7  
00  00  01  ce  
00  00  00  00

La matrice finale nous dit que le système est équivalent à

0f x  ==  53
49 y  ==  c7
01 z  ==  ce

et on peut donc obtenir la solution par divisions.

Programmez la fonction

int solve_linear_system(int height, int width, byte **M, byte *X);

qui résout un système de height équations linéaires à width inconnues en utilisant le pivot de Gauss.

Vous pouvez programmez les manipulation élémentaires

/* divise une ligne par une valeur */
void divide_row(int width, byte *R, byte c);

/* additionne deux lignes et met le résultat dans la seconde */
void add_row(int width, const byte *R1, byte *R2);

Attention, il est possible qu'il faille échanger des lignes pour positionner un coefficient non nul dans une colonne précise. Il faudra donc probablement programmer une manipulation élémentaire supplémentaire...

si la colonne correspondant à une inconnue ne contient que des 0x00, c'est que le système d'équations est sous spécifié : il risque d'avoir un nombre de solution infini. La fonction devra renvoyer -1 dans ce cas.
s'il y a n+1 colonnes, c'est à dire n inconnues, il doit y avoir au moins n lignes :
- s'il y a moins de lignes, le système risque d'avoir une infinité de solutions,
- s'il y a plus de lignes, le système risque d'avoir 0 solution. Il faut donc vérifier que les lignes en trop s'annulent lors du pivot de Gauss.

Pour tester :

vous pouvez utiliser la matrice ci-dessus et trouver
```
X[0] = 0x5c
X[1] = 0x45
X[2] = 0xce
```

pour

  byte M[3][4] = {
    { 0x00, 0x00, 0x01, 0xaa},
    { 0x00, 0x01, 0x00, 0xbb},
    { 0x01, 0x00, 0x00, 0xcc}
  };

vous devriez trouver

X[0] = 0xcc
X[1] = 0xbb
X[2] = 0xaa

pour

  byte M[4][4] = {
    { 0x00, 0x57, 0x4a, 0x20},
    { 0x20, 0x31, 0x07, 0x36},
    { 0x12, 0xfa, 0xff, 0x88},
    { 0xa5, 0x00, 0x76, 0xa8},
  };

vous devriez trouver

X[0] = 0x5c
X[1] = 0x45
X[2] = 0xce

mais pour

  byte M[4][4] = {
    { 0x01, 0x57, 0x4a, 0x20},
    { 0x20, 0x31, 0x07, 0x36},
    { 0x12, 0xfa, 0xff, 0x88},
    { 0xa5, 0x00, 0x76, 0xa8},
  };

il n'y a pas de solution...

Trouver le nombre d'erreurs et les coefficients du polynôme localisateur

S'il y a des erreurs en nombre raisonnable, il est possible de construire un polynôme localisateur d'erreurs. Son degré est exactement le nombre d'erreurs. Si le taux de correction permet de corriger au plus t erreurs, c'est à dire que le nombre d'octets de redondances est des 2t ou 2t+1, on construit la matrice suivante :

  S[0]    S[1]  ...  S[t-1]     S[t]
  S[1]    S[2]  ...  S[t]       S[t+1]
  ...           ...             ...
  ...           ...             ...
  S[t-1]  S[t]  ...  S[2t-2]    S[2t-1]

Cette matrice est construite à partir des syndromes et a t lignes et t+1 colonnes.

Pour trouver le nombre d'erreurs ainsi que les coefficients du polynôme localisateur, il faut trouver le plus gros système de cette forme qui a une unique solution :

si le système a lui même une solution, il y a t erreurs et la solution donne les coefficients du polynôme localisateur
sinon, on fait t = t-1 et on recommence...

Attention : s'il y a e erreurs, le polynôme localisateur est de degré e. La procédure décrite plus haut donne seulement les coefficients des monômes de degrés strictement positif. Le coefficient constant vaut toujours 1.

Programmez la fonction

int error_locator(int nb_correction_bytes, const byte *S, byte *L);

qui cherche le nombre d'erreurs en utilisant la méthode décrite plus haut.

nb_correction_bytes est le nombre d'octets de redondances,
S est le tableau des syndromes (de taille nb_correction_bytes),
L est un tableau (déjà alloué) qui contiendra les coefficients du polynôme localisateur.

La fonction renvoie le nombre d'erreurs.

Pour tester :


fichier	`exemple-TP2-1.pbm`	`exemple-TP2-2.pbm`	`exemple-TP2-3.pbm`
nombre d'erreurs	6	5	7
solutions du système	`0a, 03, be, 0a, 04, b8`	`8c, 09, 7e, 8b, 63`	`6d, 5c, db, cb, 94, d7, cf`
polynôme localisateur	`a X^6 + 3 X^5 + be X^4 + a X^3 + 4 X^2 + b8 X^1 + 1`	`8c X^5 + 9 X^4 + 7e X^3 + 8b X^2 + 63 X^1 + 1`	`6d X^7 + 5c X^6 + db X^5 + cb X^4 + 94 X^3 + d7 X^2 + cf X^1 + 1`

Trouver la localisation des erreurs

Le polynôme localisateur L a la propriété surprenante que L(2^-i) == 0 si et seulement si le coefficient de degré i du message (c'est à dire l'octet 25-i) est erroné.

Pour trouver les endroits où L s'annule, il suffit donc de calculer (avec la fonction eval_poly) le polynôme L sur 2⁰, 2^-1, ..., 2^-25.

Programmez la fonction qui calcule les positions des erreurs :

int find_locations(int nb_errors, const byte *L, byte *X);

nb_errors est le nombre d'erreurs détectées (question précédente),
L contient les coefficients du polynôme localisateur,
X est un tableau (alloué précédemment) qui contiendra les position des erreurs.

Note : la fonction inv_coeff vous permet de calculer l'inverse d'un octet ; 2^-i est donc simplement inv_coeff(pow_coeff(2,i)).

Pour tester :


fichier	`exemple-TP2-1.pbm`	`exemple-TP2-2.pbm`	`exemple-TP2-3.pbm`
tableau `X`	`{ 0, 1, 2, 3, 20, 25 }`	`{ 5, 6, 11, 12, 15 }`	`{ 15, 16, 17, 18, 21, 22, 24 }`
positions des erreurs dans `data`	0, 5, 22, 23, 24, 25	10, 13, 14, 19, 20	1, 3, 4, 7, 8, 9, 10

Trouver les valeurs des erreurs

Maintenant que l'on connait la position des erreurs, on peut chercher la valeur des erreurs. Pour ça, il suffit de résoudre le système donné par la matrice

1         1         ...  1           S[0]
x0        x1        ...  xe          S[1]
x0^2      x1^2      ...  xe^2        S[2]
x0^3      x1^3      ...  xe^3        S[3]
...                 ...              ...
...                 ...              ...
x0^(n-1)  x1^(n-1)  ...  xe^(n-1)    S[n-1]

où

x0, x1, ... xe sont les inverses des zéros du polynôme localisateur (autrement dit, x0 = pow_coeff(2,X[0]), etc.)
n est le nombre d'octets de redondance.

Programmez la fonction qui calcule les valeurs des erreurs

int error_values(int nb_correction_bytes, int nb_errors, const byte *S, const byte *X, byte *V);

avec

nb_correction_bytes est le nombre d'octets de redondance,
nb_errors est le nombre d'erreurs détectées,
S est le tableau des syndromes (de taille nb_correction_bytes),
X est le tableau de position des erreurs (de taille nb_errors),
V est le tableau (déjà alloué) qui contiendra les valeurs des erreurs.

La fonction renvoie 0 si elle a trouvée une unique solution au système (normal) et -1 sinon (c'est qu'il y a un problème).

Pour tester :


fichier	`exemple-TP2-1.pbm`	`exemple-TP2-2.pbm`	`exemple-TP2-3.pbm`
valeurs des erreurs	`24, 46, 93, 05, c2, a0`	`87, 08, 52, 04, b0`	`80, d0, 16, 50, f0, c9, 45`

Corriger les erreurs

Pour corriger, il suffit maintenant de soustraire (avec le XOR bit à bit) chacune des valeurs au coefficient du polynôme des données correspondant (le tableau data du TP1).

Programmer la fonction

int correct_data(byte *data, int correction_level);

qui utilisent toutes les fonctions précédentes pour corriger le tableau data.

Pour tester :


fichier	`exemple-TP2-1.pbm`	`exemple-TP2-2.pbm`	`exemple-TP2-3.pbm`
`data`	`40 74 f7 57 07 32 e2 e2 e0 90 b1 f3 5a 7f e6 54 f9 37 13 ef c1 58 10 12 30 9d`	`40 a5 36 16 c7 57 42 04 26 f6 22 e0 ec 65 d2 d8 e1 15 9f 4c a3 0e 6a 42 67 47`	`40 65 06 66 66 62 02 10 ec 7b 0c a3 81 3c 0f b2 30 60 15 8e f3 54 8a 53 33 ed`
contenu final (ASCII)	`Oups...`	`Salut Bob.`	`Pfff !`

Modifier les fonctions

void info_file(const char *filename, int margin_size, int module_size);
void decode_file(const char *filename, int margin_size, int module_size);

du TP1 pour utiliser la correction d'erreurs.

TP2 : correction d'erreurs dans les QR code (version 1)

info-528 : mathématiques pour l'informatique

Hivers 2012

Consignes

Liens utiles

QR codes - partie 2 : correction d'erreurs

Préliminaires

correction d'erreurs dans le format

correction d'erreurs dans les données

Syndromes et détection d'erreurs

pivot de Gauss

Trouver le nombre d'erreurs et les coefficients du polynôme localisateur

Trouver la localisation des erreurs

Trouver les valeurs des erreurs

Corriger les erreurs