next up previous
Next: C Bouclage de phase Up: Comment faire son propre Previous: A Le bloc de

B Codage de Hamming

  Soit le message binaire $S=(s_1,s_2,\cdots ,s_m)$, dit message "source". On lui fait correspondre le message codé suivant: $V=(v_1,v_2,\cdots ,v_n)$,dit message "voie". V est déterminé par les relations suivantes (les sommes sont faites modulo 2 et les ai valent 0 ou 1):

\begin{displaymath}
\begin{array}
{rl}
\mbox{m équations } &
\left\{
\begin{arra...
 ...& = & k_1s_1+k_2s_2+\cdots +k_ms_m\end{array}\right.\end{array}\end{displaymath}

On peut aussi écrire matriciellement:

\begin{displaymath}
\left[ {\cal V} \right] = \left( {\cal G} \right) \, \left[ {\cal S} \right]\end{displaymath}

avec:

\begin{displaymath}
\left( {\cal G} \right) = \left(
\begin{array}
{cccc}
1 & 0 ...
 ...vdots & & & \vdots\ k_1 & k_2 & \cdots & k_m\end{array}\right)\end{displaymath}

Après transmission, on reçoit le message binaire $\left[ {\cal V} \right]$,auquel on va faire subir les équations de vérification suivantes:

\begin{displaymath}
\begin{array}
{rcl}
a_1v_1+a_2v_2+\cdots +a_mv_m+v_{m+1} & =...
 ... \vdots\ k_1v_1+k_2v_2+\cdots +k_mv_m+v_n & = & z_k\end{array}\end{displaymath}

Il est clair que si aucune erreur n'est apparue lors de la transmission, alors le vecteur $\left[ {\cal Z}
\right]$ est nul, avec:

\begin{displaymath}
\left[ {\cal Z} \right]=\left(
\begin{array}
{c}
z_1\ \vdots\ z_k\end{array}\right)\end{displaymath}

Sinon, en général, il est non nul; en tout cas, pour un nombre limité d'erreur (<k), il est systématiquement non nul. Le principe de la correction d'une erreur est d'établir une bijection entre l'ensemble des vecteurs $\left[ {\cal Z}
\right]$ non nuls (dits "syndromes d'erreurs") et l'ensemble des erreurs possibles sachant qu'il est supposé n'y en avoir qu'une.

Le vecteur$\left[ {\cal Z}
\right]$ ayant k composantes et le vecteur $\left[ {\cal V} \right]$ transmis ayant n composantes (n bits, donc n erreurs possibles), cela amène à la condition n=2k-1, ce qui dimensionne le système d'équations, si l'on se fixe n a priori (ou m). On a par ailleurs évidemment n=m+k.

Il reste à déterminer les valeurs des coefficients des k équations de départ. Pour cela écrivons la relation de vérification sans, puis avec une erreur:

L'opération $\left( {\cal H} \right)\left[ \varepsilon_i\right]$ est triviale vu la forme de $\left[ \varepsilon_i\right]$: le résultat est la $i^{\grave{e} me}$ colonne de $\left( {\cal H} \right)$. Ainsi, à chaque erreur différente est associée une colonne différente et une seule de $\left( {\cal H} \right)$.

La bijection est alors réalisée si toutes les colonnes de $\left( {\cal H} \right)$ sont différentes entre elles et bien sûr non nulles. D'où la construction de $\left( {\cal H} \right)$ et aussi celle de $\left( {\cal G} \right)$. Alors, une fois cette construction faite, une erreur sera localisée grâce à la valeur du syndrome $\left[ {\cal Z}
\right]$ trouvée grâce à une simple table de correspondance.

Exemple: $k=3\Rightarrow n=2^3-1=7\Rightarrow m=7-3=4$.

Construction de $\left( {\cal H} \right)$:

\begin{displaymath}
\left( {\cal H} \right)=\left(
\begin{array}
{ccccccc}
1&0&1&1&1&0&0\ 1&1&0&1&0&1&0\ 0&1&1&1&0&0&1\end{array}\right)\end{displaymath}

D'où:

\begin{displaymath}
\left( {\cal G} \right)=\left(
\begin{array}
{cccc}
1&0&0&0\...
 ...0&1&0\ 0&0&0&1\ 1&0&1&1\ 1&1&0&1\ 0&1&1&1\end{array}\right)\end{displaymath}


next up previous
Next: C Bouclage de phase Up: Comment faire son propre Previous: A Le bloc de
Denis Arnaud
11/25/1997