\section{Codages}

\subsection{ascii}

Le code ASCII est un code assez ancien. Il normalise
les caractères correspondant aux nombres de 7-bits. En
effet, lors d'une transmission d'un caractère le 8ième
bit est utilisé pour un contrôle de parité par le
récepteur. 

$$
     'C' \mapsto 67 = 0x43 = 0100 0011 \leadsto 11000011
$$

\begin{lstlisting}[style=man]
ASCII(7)                   Linux Programmer's Manual

NAME
       ascii - ASCII character set encoded in octal, 
       decimal, and hexadecimal
DESCRIPTION
  ASCII is the American Standard Code for Information
  Interchange.  It is a 7-bit code.  Many 8-bit codes 
(such as ISO 8859-1, the Linux defaultcharacter  set)
contain  ASCII as their lower half.  The international
counterpart of ASCII is known as ISO 646.

The following table contains the 128 ASCII characters.

       Oct   Dec   Hex   Char
       000   0     00    NUL  \0
       101   65    41    A
       006   6     06    ACK  (acknowledge)    
       007   7     07    BEL  \a (bell)       
       012   10    0A    LF   \n (new line)    
       015   13    0D    CR   \r (carriage ret) 
\end{lstlisting}

Une fois n'est pas coutume, 
le système \SE{MSDOS} et toute sa 
descendance, contrairement \`a \SE{unix},
à conserver
le saut de ligne ancestral.

\begin{lstlisting}[style=term]
$ echo 'ascii' | unix2dos  | hexdump -c
0000000   a   s   c   i   i  \r  \n  
\end{lstlisting}

\subsection{format}

La troisième partie du match Viswanathan Anand, Magnus Carlsen,
joué le 12 Novembre 2013 à Chenai, a commencé par les coups : 
1. Nf3 d5, 2. g3 g6, 3. c4 dc4. Voilà
un codage pour les humains. Il correspond au format algébrique :
g1f3 d7d5 g2g3 g7g6 c2c4 d5c4 utilisé dans les moteur d'analyse
comme \shell{stockfish}. La suite de coups en base octale 60, 52, 36, 
34, 61, 62, 66, 65, 21, 23, 34, 23,  et le flux binaire correspondant:
$$
011 100 110 001 110 110 110 101 010 001 010 011 011 100 010 011
$$


\subsection{canal bruité}

Dans un canal binaire bruité symétrique, les bits
transmis diffèrent des bits reçus, la probabilité
de transition est $p$. Pour traverser un tel
canal de communication, il faut introduire de la
redondance, par exemple en répétant trois fois 
chacun des bits. Le récepteur décode l'information
par une décision majoritaire, la probabilité 
de recouvrer chacun des bits transmis est $q^3+3q^2p$,
au final la probabilité de retrouver un symbole est 
$(q^3+3q^2p)^3$, ou un coup est $(q^3+3q^2p)^{12}$.  

\begin{figure}
\includegraphics[scale=0.5]{perr.png}
\caption{\label{PERR} Probabilité d'un bon décodage}
\end{figure}

D'une manière générale, pour un système de codage
cappable de corriger $e$ erreur, la probabilité 
d'erreur sur un symboles aprés décodage est majorée
par :
$$
\sum_{k=e+1}^n \binomial kn q^{n-k} p^k,\quad p+q = 1.
$$

\subsection{codage de Hamming}

L'encodage de Hamming consiste à introduire la
redondance comme suit
$$
       (x,y,z,t ) \mapsto (x, y, z, t, x+y+t, y+z+t, x+y+t )
$$


\begin{figure}
\includegraphics[scale=0.5]{img/hamming.png}
\caption{\label{CH} Codage de Hamming utilise 3 symboles de
parités et 4 symboles d'information.}
\end{figure}


Le code de Hamming corrige moins bien que le
code à répétition mais il permet un débit de
de transmission est 1.71 plus important.

\subsection{distance}

On rappelle que le poids d'un $n$-uplet binaire
est égal au nombre de 1 qui le compose. 

\begin{figure}
\begin{lstlisting}[style=gcc]
int wt( ullong z )
{
int r = 0;
while ( z ) {
   z &= (z-1);
   r++;
}
return r;
}
\end{lstlisting}
\caption{\label{WT}Une fonction bien utile}
\end{figure}
\begin{exercice}
Que retourne la fonction \gcc{wt} ?
\end{exercice}

L'ensemble $\B^n$ est muni d'une métrique, la
distance de Hamming :
$$
\dh(x, y ) = \wt( y - x ) = \sharp\{ i\mid x_i\not=y_i\} 
$$ 

\begin{exercice}
Montrer que la distance de Hamming est bien une
distance au sens topologique.
\end{exercice}


Un code de paramètre $[n,k,d]$ est une partie $C$
de cardinal $2^k$ dans $\B^n$ telle que 
$$
\forall x, y \in C,\quad x\not=y \imp \dh(x,y) \geq d.
$$
Une telle partie permet d'encoder les messages de longueurs
$k$ dans des mots de longueurs $n$ de sorte à pouvoir corriger
jusqu'à $e=(d-1)/2$ erreurs.
\begin{proof}
Il suffit de vérifier que tout mot de code $c$ entaché de
moins de $e$ erreurs est à distance au plus $e$ d'un et un
seul mot de code.  
\end{proof}

L'opération de décodage qui consiste à retrouver $c$ à
partir d'un mot $c+x$ avec $\wt(x)\leq e$ est une opération
algorithmiquement complexe en générale.

\subsection{linéarité}

Un code stable par addition est dit linéaire. Dans ce cas, il
s'agit d'un groupe commutatif. Tout système générateur minimal
est une base, il existe des matrices génératrices $G$ permettant 
un encodage linéaire :

$$
   (x_m,\ldots,x_2,x_1) \mapsto (x_m,\ldots,x_2,x_1) G 
$$

Dans le cas d'un code linéaire, la distance minimale coincide 
avec le plus petit poids non nul. L'énumérateur de poids du
code est la séquence 
$$
	A_w(C) = \sharp\{ c\in C\mid \wt(c) = w\}.
$$

\begin{exercice}
Prouver l'existence de système générateur.
\end{exercice}

\begin{exercice}
Ecrire \gcc{int* enum( ullong *G, int k )} pour calculer
l'énumérateur de poids des mots du code engendré par $G$.
Préciser le temps de calcul. Plusieurs solutions possibles :
naïve, récursive et basée sur le code de Gray.
\end{exercice}

\begin{exercice}
Montrer que le code de Hamming est linéaire. Montrer que
sa distance minimame est supérieur à 2. Montrer qu'il existe
pas de $[7,4,4]$-code. Montrer que les boules de rayon 1
centrées sur les mots d'un $[7,4,3]$ forment une partition
de $\B^7$.
\end{exercice}


