home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 17 / CD_ASCQ_17_101194.iso / dos / prg / vidal / c / hamming.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-25  |  7.3 KB  |  265 lines
  1. /*
  2. codage et decodage permettant de détecter 3 erreurs et d'en corriger 2
  3. Le facteur de multiplication du code a coder est de 3.
  4. Ce Source donne des exemples comment faire des decalages.
  5. Des Masques avec des and '&',et offre des fonctions interresantes:
  6.  
  7. char get_bit(o,n)
  8. void put_bit(o,n,b)
  9. void inverse_bit(o,n)
  10. void aff_char  -> en binaire
  11.  
  12. Comment ca marche:
  13. Algo: on prend un octect , on le separe en deux :
  14.  octect:x1x2x3x4x5x6x7x8 octect1:x1x2x3x4 octect2:x5x6x7x8
  15.  on code par hamming octect1 et octect2 et on fait la somme bit a bit
  16.  par octect3 ( octect de parité);
  17.  c'est une operation xor : xor correspond a l'addition en base 2.
  18.  on insert des erreurs ( <=3 erreurs ) dans les octects que l'on veut
  19.  modifier.
  20.  resultat:par hamming , on sait que l'on peut corriger 1 erreur et en
  21.  detecte 2.
  22.  donc si 1 erreur vient des 2 premier octects: erreur octect1
  23.                            erreur octect2
  24.  par hamming on corrige.
  25.  si 2 erreur vient dans un octect: on corrige grace a l'octect non
  26.  affecté et par l'octect de parite.
  27.  Pour 3 erreur , on regarde l'octect de parite , 3 different avec les
  28.  autres, et voila;
  29.  Ce n'est pas un code de detection , et de correction extraordinaire.
  30.  Il faut savoir que hamming (dectecte 1 erreur sur 7 octect) est utilisé
  31.  par le minitel.
  32.  Sinon le code de detection d'erreur CRC, est equivalant a hamming.
  33.  MAis il y a de code plus performant comme celui de Reed-Muller.
  34.  auteur email:vidal@amertume.ufr-info-p7.ibp.fr
  35. */
  36. #include <stdio.h>
  37. typedef struct { int nb_error;
  38.      char error[2];
  39.        } ERREUR;
  40.  
  41. /* affiche un char en binaire */
  42. void aff_char(o)
  43. char o;
  44. {
  45. char i;
  46. for (i=0;i<8;i++)
  47.    if ((o>>i)&1)  printf("1"); else printf("0");
  48. }
  49. /* renvoie le n^eme bit de o */
  50. char get_bit(o,n)
  51. char o,n;
  52. {return  ((o>>n)&1);}
  53.  
  54. /* met le n^eme bit de o a b */
  55. void put_bit(o,n,b)
  56. char *o;
  57. char n,b;
  58. {if (b) {b=b<<n;*o=*o|b;}
  59.   else {b=1<<n;
  60.        b^=255;*o=*o&b;}
  61. }
  62.  
  63. void inverse_bit(o,n)
  64. char *o;
  65. char n;
  66. {
  67. put_bit(o,n,(get_bit(*o,n)^1));
  68. }
  69.  
  70. /* codage hamming : code o -> code_hamming */
  71. char code_hamming(o)
  72. char o;
  73. {char i=0,a=0;
  74. o=o<<3;
  75. put_bit(&o,2,get_bit(o,3));
  76. put_bit(&o,0,(get_bit(o,2)^get_bit(o,4)^get_bit(o,6)));
  77. put_bit(&o,1,(get_bit(o,2)^get_bit(o,5)^get_bit(o,6)));
  78. put_bit(&o,3,(get_bit(o,4)^get_bit(o,5)^get_bit(o,6)));
  79. for (i=0;i<7;i++)
  80.  a^=get_bit(o,i);
  81.  put_bit(&o,7,a);
  82. return(o);
  83. }
  84. /* decodage hamming : decode o (o etant codé)  -> decode_hamming */
  85. char decode_hamming(o)
  86. char *o;
  87. {
  88. char i=0,b,p=0;
  89. put_bit(&i,2,(get_bit(*o,3)^get_bit(*o,4)^get_bit(*o,5)^get_bit(*o,6)));
  90. put_bit(&i,1,(get_bit(*o,1)^get_bit(*o,2)^get_bit(*o,5)^get_bit(*o,6)));
  91. put_bit(&i,0,(get_bit(*o,0)^get_bit(*o,2)^get_bit(*o,4)^get_bit(*o,6)));
  92. p=get_bit(*o,7);
  93. if (!i) {put_bit(o,3,get_bit(*o,2));
  94.      *o=*o>>3;
  95.       *o=*o&0x0f;
  96.        for (b=0;b<8;b++)  p^=get_bit(*o,b);
  97. put_bit(&i,7,p);
  98.     }
  99. else {for (b=0;b<8;b++)  p^=get_bit(*o,b);
  100.       put_bit(&i,7,p);}
  101. return (i);
  102. }
  103.  
  104. void correction_hamming(o,i)
  105. char *o;
  106. char i;
  107. {
  108.  inverse_bit(o,(i-1));
  109. }
  110.  
  111. char somme_bit(e)
  112. char e;
  113. {char p=0,b;
  114. for (b=0;b<8;b++)  p^=get_bit(e,b);
  115. return (p);
  116. }
  117.  
  118. char nombre_erreur(e,a)
  119. char e;
  120. char *a;
  121. {
  122. *a=decode_hamming(&e);
  123. *a&=127;
  124. if (!*a) {
  125.       return(0);
  126.     }
  127.       else {if (!somme_bit(e)) return(2);
  128.            else return(1);
  129.   }
  130. }
  131. /* decoupe un char en deux char */
  132. void decoupe1en2(o,t)
  133. char o;
  134. char *t;
  135. { t[0]=o;
  136.   t[0]&=15;
  137.   t[1]=o>>4;
  138.   t[1]&=15;
  139. }
  140. /* inverse de   decoupe1en2 */
  141. void regroupe2en1(t,o)
  142. char *t;
  143. char *o;
  144. { *o=t[0];
  145.   t[1]<<=4;
  146.   *o|=t[1];
  147. }
  148.  
  149. char xor_bit_a_bit(a,b)
  150. char a,b;
  151. {
  152. char tempo;
  153. char i;
  154.  for (i=0;i<8;i++)
  155.   put_bit(&tempo,i,get_bit(a,i)^get_bit(b,i));
  156. return (tempo);
  157. }
  158.  
  159. char nombre_xor_dif(t)
  160. char *t;
  161. {char tempo=0,i;
  162.  for (i=0;i<8;i++)
  163.  tempo+=get_bit(t[0],i)^get_bit(t[1],i)^get_bit(t[2],i);
  164.  printf(" nombre xor dif %d\n",tempo);
  165.  return (tempo);
  166. }
  167. /* compte le nombre d'erreur */
  168. char compte_erreur(t,erreur)
  169. char *t;
  170. ERREUR *erreur;
  171. {char xor_dif;
  172.  erreur->nb_error=0;
  173.  erreur->error[0]=0;
  174.  erreur->error[1]=0;
  175.  erreur->nb_error+=nombre_erreur(t[0],erreur->error);
  176.  erreur->nb_error+=nombre_erreur(t[1],erreur->error+1);
  177.  printf(" nombre erreur pour 2 char %d\n",erreur->nb_error);
  178.  printf(" erreur 1 char %d\n",erreur->error[0]);
  179.  printf(" erreur 2 char %d\n",erreur->error[1]);
  180.  xor_dif=nombre_xor_dif(t);
  181.  if (xor_dif>=3) {erreur->nb_error=3;return(3);}
  182.  if (xor_dif==1 && erreur->nb_error==2) {erreur->nb_error=3;return(3);}
  183.  if (xor_dif<=erreur->nb_error) {printf("pas d'erreur dans octect de parite \n");return(erreur->nb_error);}
  184.  if (xor_dif<=2 && erreur->nb_error==0) return(0);
  185.  if (xor_dif==2 && erreur->nb_error==1) return(1);
  186.  if (xor_dif>erreur->nb_error) erreur->nb_error=3;
  187.  return(erreur->nb_error);
  188. }
  189. /* corrige 0 1 2 erreurs */
  190. void correction_2erreurs(t,erreur)
  191. char *t;
  192. ERREUR erreur;
  193. {char e,i;
  194. switch (erreur.nb_error)
  195.  { case 0:break;
  196.    case 1: for (i=0;i<2;i++)
  197.        {
  198.         if (erreur.error[i]) {printf(" erreur dans %d ere char a %d \n",i,erreur.error[i]);correction_hamming(&t[i],erreur.error[i]);
  199.         break;}
  200.        }
  201.        break;
  202.     case 2:if (erreur.error[0] && erreur.error[1] && erreur.nb_error==2)
  203.          {  for (i=0;i<2;i++)
  204.            {
  205.              if (erreur.error[i]) {printf(" erreur dans %d ere char a %d \n",i,erreur.error[i]);correction_hamming(&t[i],erreur.error[i]);}
  206.            }
  207.          }
  208.            else { if ((erreur.error[0] || erreur.error[1]) && (!erreur.error[0] || !erreur.error[1]) && erreur.nb_error==2)
  209.             {printf(" le paquet d'erreur est regrouper dans un seul octet \n");
  210.              if (erreur.error[0]) t[0]=xor_bit_a_bit(t[1],t[2]);
  211.               else t[1]=xor_bit_a_bit(t[0],t[2]);
  212.             }
  213.             }
  214.        break;
  215.    default:break;
  216.  }
  217. printf("decodagec");aff_char(t[0]);printf("   ");aff_char(t[1]);printf("   ");aff_char(t[2]);printf("\n");
  218. }
  219. void decodage_2char(t)
  220. char *t;
  221. {
  222.  decode_hamming(t);t++;decode_hamming(t);
  223. }
  224. main ()
  225. {
  226. unsigned char i,o,whereerreur[10],quelbit[10],nb_inversion,cas,b;
  227.  char t[3];
  228.  ERREUR erreur;
  229.  int in;
  230.  printf(" entrez un nombre 0 255 ");
  231.  scanf("%d",&in);
  232.  i=(char ) in;
  233.  printf(" nombre d'erreur 0 3 ");
  234.  scanf("%d",&in);
  235.  nb_inversion=(char) in;
  236.  for (b=0;b<nb_inversion;b++)
  237.  {
  238.  printf(" entrez position erreur 0 2 ");
  239.  scanf("%d",&in);
  240.  whereerreur[b]=(char) in;
  241.  printf(" entrez position bit erreur 0 7 ");
  242.  scanf("%d",&in);
  243.  quelbit[b]=(char) in;
  244.  }
  245.   decoupe1en2(i,t);
  246.   printf("decoupage ");aff_char(i);printf("   ");aff_char(t[0]);printf("   ");aff_char(t[1]);printf("\n");
  247.   t[0]=code_hamming(t[0]);
  248.   t[1]=code_hamming(t[1]);
  249.   t[2]=xor_bit_a_bit(t[0],t[1]);
  250.   printf(" codage   ");aff_char(t[0]);printf("   ");aff_char(t[1]);printf("   ");aff_char(t[2]);printf("\n");
  251.   for (b=0;b<nb_inversion;b++)
  252.   inverse_bit(&(t[whereerreur[b]]),quelbit[b]);
  253.   printf(" erreur   ");aff_char(t[0]);printf("   ");aff_char(t[1]);printf("   ");aff_char(t[2]);printf("\n");
  254.   if (compte_erreur(t,&erreur)<3)
  255.    {
  256.   printf(" nb erreur %d \n",erreur.nb_error);
  257.    correction_2erreurs(t,erreur);
  258.    decodage_2char(t);
  259.    printf("decodage ");aff_char(t[0]);printf("   ");aff_char(t[1]);printf("   ");aff_char(t[2]);printf("\n");
  260.   printf(" regroupement ");regroupe2en1(t,&o);aff_char(o);printf("\n nombre %d\n",o);
  261.   if (o!=i) fprintf(stderr," erreur programmation \n");
  262.   }
  263.   else printf(" nb erreur %d \n",erreur.nb_error);
  264. }
  265.