/* * info528, TP1 : code de Gollay * Harry Potter */ #include "tp1.h" /* * macro pour récupérer le bit numéro 'i' dans un mot 'm' * question 1 */ #define BIT(i,m) ((m) & 1) /* * affiche les n bit de poids faible d'un mot * question 1 */ void print_bin(mot m,int n) { // ... } /* * compte le nombre de 1 dans un mot * question 2 */ int poids(mot m) { // ... return 0; } /* * renvoie le décalage circulaire (à droite) des n bit de poids faible d'un mot * question 7 */ unsigned decalage_circulaire(mot m, int n) { // ... return 0; } /********************************************************************** * Code de Golay avec parité * matrice generatrice: I | G avec G 10101110001 11111001001 11010010101 11000111011 11001101100 01100110110 00110011011 10110111100 01011011110 00101101111 10111000110 01011100011 *********************************************************************/ /* * matrice génératrice pour les bits de redondance * question 3 */ mot golay_A[12] = { 0x571, 0x7c9, 0x695, 0x63b, 0x66c, 0x336, 0,0,0,0,0,0}; /* * code une suite de 12 bits (bits de poids faible d'un mot) en ajoutant la * redondance donnée par la matrice A * Le résultat (23 bits) est stocké dans les 23 bits de poid faible du mot * renvoyé. * question 4 */ mot code_golay(mot entree) { // ... return 0; } /* * code de Golay étendu: 23 bit du code de Golay, avec un bit de parité * question 5 */ mot code_golay_etendu(mot entree) { // ... return 0; } /* * matrice de parité pour le code de Golay * question 6 */ unsigned golay_H[23] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }; /* * syndrome d'un mot du code de Golay (sans bit de parité) * question 6 */ mot syndrome_golay(mot m) { // ... return 0; } /* * correction d'erreur pour le code de Golay en utilisant la méthode "error * trapping" + cyclicité * question 8 * question 11 */ mot correction_golay(mot m) { // ... return 0; } /* * décode un mot du code de Golay en supprimant les bits de redondance * question 12 */ mot decode_golay(mot m) { return (m>>11) & ((1<<12)-1); } /* * fonction de test exécutée avec l'argument "-T" depuis la ligne de commande */ void test_cmd(void) { // test pour la question 1 mot m = 0x555; /* càd 00...000010101010101 en binaire */ int n = 3; printf("Le bit numéro %d de %x est %u et le bit %d est %u.\n", n, m, BIT(n,m), n+1, BIT(n+1,m)); // ... // test pour la question 2 m = 0xace; printf("le mot '%x' est en fait ",m); print_bin(m,12); printf("\n"); // ... // ... // ... } /**************************************************************************** * NE PAS MODIFIER LA SUITE DU FICHIER ************************************** ****************************************************************************/ /* * ajoute des erreurs sur un mot * chaque bit a une probabilité p d'étre modifié */ mot bruite_mot(mot m, double p) { mot err=0; for (int i=0;i<32;i++) { err = err<<1; if (rand()/(double)RAND_MAX < p) { err |= 1; } } return err^m; } /* * fait des tests et quelques statistiques */ void statistiques(int nb_tests, double proba) { mot m,err,c,C; int nb_mots_incorrects = 0; int nb_bits_incorrects = 0; int nb_bits_modifies = 0; int w; for (int i=0;i>11; err = C ^ m; w = poids(err); if (w != 0) { nb_mots_incorrects++; nb_bits_incorrects += w; } } printf("%d mots ont été codés, %d bits ont étés modifiés\n", nb_tests, nb_bits_modifies); printf("%d mots n'ont pas étés corrigés correctement (%.2f%%)\n", nb_mots_incorrects, (100.0*nb_mots_incorrects)/nb_tests); printf("%d bits n'ont pas étés corrigés correctement (%.2f%%)\n", nb_bits_incorrects, (100.0*nb_bits_incorrects)/(12.0*nb_tests)); } void print_usage(char *name) { printf("Utilisation :\n"); printf(" %s options\n", name); printf(" -T lance la fonction de test\n"); printf(" -h ce message\n"); printf(" -c mot code le mot de 12 bits sur 23 bits\n"); printf(" -s mot calcule le syndrome du mot 23 bits\n"); printf(" -d mot décode (avec correction d'erreurs) le mot de 23 bits sur 12 bits\n"); printf(" -C mot code le mot de 12 bits sur 24 bits\n"); printf(" -D mot décode (avec correction d'erreurs) le mot de 24 bits sur 12 bits\n"); printf(" -n nb nombre de mots à tester\n"); printf(" -p x probabilité d'erreur sur chaque bit\n"); printf(" -x utilise la base hexadécimal plutôt que la base 2\n"); } int main (int argc, char** argv) { // si les unsigned int ne font pas 4 octets, il faut les remplacer par des // unsigned long int... if (sizeof(mot) < 4) { printf("ATTENTION, les entiers sont stockés sur %lu octets !\n", sizeof(mot)); printf("Il faut au moins 4 octets pour pouvoir utiliser cette implémentation...\n"); exit(-1); } // initialisation pour l'aléatoire... time_t graine; time(&graine); srand(graine); int opt; if (argc == 1) { print_usage(argv[0]); exit(-1); } mot m = 0; int nb_tests = 1000; double proba = 1.0 / 10; int test = 0; int base = 2; mot c; while ((opt = getopt(argc, argv, "hTc:d:C:D:s:n:p:x")) != -1) { switch (opt) { case 'h': print_usage(argv[0]); exit(0); break; case 'x': base = 16; break; case 'T': test_cmd(); exit(0); break; case 'c': if (base == 16) { m = strtol(optarg,NULL,16); } else { m = strtol(optarg,NULL,2); } c = code_golay(m); printf("code_golay: "); if (base == 16) { printf("%03x => %06x\n",m,c); } else { print_bin(m,12);printf(" => "); print_bin(c,23);printf("\n"); } break; case 'C': if (base == 16) { m = strtol(optarg,NULL,16); } else { m = strtol(optarg,NULL,2); } c = code_golay_etendu(m); printf("code_golay_etendu: "); if (base == 16) { printf("%03x => %06x\n",m,c); } else { print_bin(m,12);printf(" => "); print_bin(c,24);printf("\n"); } break; case 's': if (base == 16) { m = strtol(optarg,NULL,16); } else { m = strtol(optarg,NULL,2); } c = syndrome_golay(m); printf("syndrome_golay: "); if (base == 16) { printf("%06x => %03x\n",m,c); } else { print_bin(m,23);printf(" => "); print_bin(c,11);printf("\n"); } break; case 'd': if (base == 16) { m = strtol(optarg,NULL,16); } else { m = strtol(optarg,NULL,2); } c = correction_golay(m); c = c>>11; printf("correction_golay: "); if (base == 16) { printf("%06x => %03x\n",m,c); } else { print_bin(m,23);printf(" => "); print_bin(c,12);printf("\n"); } break; case 'D': if (base == 16) { m = strtol(optarg,NULL,16); } else { m = strtol(optarg,NULL,2); } m = m>>1; c = correction_golay(m); c = c>>11; printf("correction_golay (étendu): "); if (base == 16) { printf("%06x => %03x\n",m,c); } else { print_bin(m,23);printf(" => "); print_bin(c,12);printf("\n"); } break; case 'n': nb_tests = atoi(optarg); test = 1; break; case 'p': proba = atof(optarg); test = 1; break; default: /* '?' */ printf("%s -h pour avoir la liste des options\n", argv[0]); exit(-1); } } if (test == 1) statistiques(nb_tests,proba); return 0; }