Consignes

Le TP est à rendre, avant le mercredi 19 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) contenaient 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 pour qu'elle applique la correction du format tout de suite après l'appel à la fonction get_format_bits. (Il est important de faire cette correction avant de récupérer les valeurs du taux de correction et le numéro du masque !)

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 (correction_level à 1), 7 sont des octets de redondance, permettant de corriger 3 octets erronés,
dans le mode M (correction_level à 0), 10 sont des octets de redondance, permettant de corriger 5 octets erronés,
dans le mode Q (correction_level à 3), 13 sont des octets de redondance, permettant de corriger 6 octets erronés,
dans le mode H (correction_level à 2), 17 sont des octets de redondance, permettant de corriger 8 octets erronés.

Ce nombre est accessible à travers le tableau NB_DATA_BYTES qui donne le nombre d'octets de données pour une valeur de correction_level. (Attention, le nombre d'octets de redondances est égal à 26 moins le nombre de d'octets de données...)

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.

La fonction

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

est déjà programmée dans le fichier fourni. Elle utilise trois fonctions auxiliaires, dont

static void divide_row(int width, byte *R, byte c);

static void add_row(int width, const byte *R1, byte *R2);

Complétez ses fonctions pour que solve_linear_system fonctionne correctement.

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 renvoie -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

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

et le résultat trouver

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

Pour des raisons techniques, il faut appeler la fonction solve_linear_system avec une matrice allouée avec malloc car tmp n'est pas un pointeur de pointeurs. Le plus simple est de déclarer ensuite la matrice M en recopiant tmp dedans de la manière suivante :

int width = 4;
int height = 3;
byte **M = malloc(height*sizeof(byte*));
for (i=0; i<height; i++) M[i] = malloc(width*sizeof(byte));
for (i=0; i<taille+1; i++)
  for (j=0; j<taille+1; j++)
    M[i][j] = tmp[i][j];      

byte *result = malloc(sizeof(byte)*(height));
int r = solve_linear_system(height, width, M, result);

pour

byte tmp[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 tmp[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

(n'oubliez pas de changer la valeur de height)

mais pour

byte tmp[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 !`

Modifiez 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 codes (version 1)

info-528 : mathématiques pour l'informatique

Hivers 2014

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