\chapterimage{lena_couleur}
\chaptertext{%{\small 
Aujourd'hui,  des  mathématiques  concrètes  vont  nous  permettre  de
réduire,   agrandir,   assombrir,  éclaircir,   compresser,   bruiter,
quantifier,... une photo. Pour cela,  il existe des méthodes provenant
de  la théorie  du signal  et des  mathématiques continues.  Nous nous
pencherons plutôt sur  des méthodes plus légères  basées sur l'algèbre
linéaire  et l'analyse  matricielle.   Une image  sera  pour nous  une
matrice  carrée de  taille $2^9$  à coefficients  dans $\llbracket  0,
2^9-1\rrbracket$.  Cela manque de charme?  C'est sans compter sur Lena
qui depuis quarante ans rend les maths sexy (la population hantant les
laboratoires  mathématiques   et  surtout  informatiques   est  plutôt
masculine ...).

Nous   étudierons  pour   cela   la  \og   Décomposition  en   Valeurs
Singulières\fg{} qui apparaît de nos jours comme un couteau suisse des
problèmes linéaires:  en traitement  de l'image et  de tout  signal en
général, en  reconnaissance des formes, en  robotique, en statistique,
en  étude  du  langage  naturel,  en  géologie,  en  météorologie,  en
dynamique des structures, en....

Dans  quel domaine  travaille-t-on alors:  algèbre linéaire,  analyse,
probabilités, topologie,...?  Un  peu de tout cela  et d'autres choses
encore: cela s'appelle la mathématique.%}
}


\chapter{Dessine-moi une matrice...}





\section{Lena}

\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{kahan}
\caption{W. \bsc{Kahan (né en 1933)}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-6.35cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}


Nous  allons travailler  avec  des  images qui  sont  des matrices  de
niveaux de gris.  Notre belle amie Léna sera représentée par une matrice
carrée de  taille $2^9$ ce qui  permet de reproduire Léna  à l'aide de
$2^{18}=262\,144$  pixels. Léna  prend alors  beaucoup de  place. Nous
allons tenter de  compresser la pauvre Léna sans pour  cela qu'elle ne
perde sa qualité  graphique. Une des méthodes les  plus abordables est
d'utiliser la décomposition d'une matrice en valeurs singulières.

C'est   un    sujet   extrêmement   riche   qui    a   de   nombreuses
applications.  L'algorithme que  nous  utiliserons (mais  que nous  ne
détaillerons pas) a été mis au point par deux très éminents chercheurs en 1965
(Gene   \textsc{Golub},   états-unien   et   William   \textsc{Kahan},
canadien, père de la norme  IEEE-754). Il s'agit donc de mathématiques
assez récentes, au moins en comparaison avec votre programme...


La petite histoire  dit que des chercheurs  américains de l'University
of Southern California étaient pressés de trouver une image de taille
$2^{18}$ pixels pour leur conférence.  Passe alors un de leurs
collègues avec, en bon informaticien, le dernier Playboy sous le bras.
Ils décidèrent alors 
d'utiliser le poster central de la Playmate comme support...

 La photo originale est ici:
 \href{http://www.lenna.org/full/len\_full.html}{http://www.lenna.org/full/len\_full.html}
 mais nous n'utiliserons  que la partie scannée par  les chercheurs, de
 taille $5.12 \mathrm{in}\times 5.12 \mathrm{in}$...




\section{La SVD}

\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{eckart}
\caption{C. \bsc{Eckart (1902-1973)}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-6.35cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}


\subsection{Le théorème}

Un théorème démontré officiellement en 1936 par Carl \textsc{Eckart}
et Gale \textsc{Young} affirme alors que toute matrice rectangulaire A se
décompose sous la forme:

$$A = U \times S \times \tr V$$

avec U et  V des matrices orthogonales et S  une matrice nulle partout
sauf sur sa diagonale principale  qui contient les valeurs singulières
de A  rangées dans  l'ordre décroissant. \textsc{Sylvester}  s'y était
déjà  intéressé pour  des matrices  carrées  réelles en  1889 mais  ce
résultat a semblé n'intéresser personne pendant des années. 


Le court article de \textsc{Eckart} et \textsc{Young} est disponible à
l'adresse suivante: 

{\small
\href{http://projecteuclid.org/DPubS?service=UI\&version=1.0\&verb=Display\&handle=euclid.bams/1183501633}{http://projecteuclid.org/DPubS?service=UI\&version=1.0\&verb=Display\&handle=euclid.bams/1183501633}.
}
Ce qui est  remarquable, c'est que n'importe quelle  matrice admet une
telle  décomposition, alors  que la  décomposition en  valeurs propres
(la  diagonalisation d'une  matrice) n'est  pas toujours  possible. Et
quand  on  dit n'importe  quelle  matrice,  on  ne rigole  pas:  toute
matrice, même rectangulaire. C'est vraiment très puissant et à la fois
simple mais cette décomposition  n'a trouvé d'applications importantes
qu'assez récemment (ce  qui veut dire après 1899 à  l'échelle de votre
programme de prépa...) ce qui explique peut-être qu'on en parle si peu
en premier cycle.


Cependant,  la   décomposition  en  éléments  singuliers   utilise  la
décomposition en éléments propres.



Notons $r$ le rang  de A et $U_i$ et $V_i$ les  vecteurs colonnes de U
et V. La décomposition s'écrit:


$$A=
\begin{pmatrix}
  U_1&U_2&\cdots &U_r&\cdots & U_m
\end{pmatrix}
\times
\begin{pmatrix}
  \sigma_1& & & &\\
    &\ddots & & & \\
   & &\sigma_r & &\\
   & & &\ddots &\\
   & & & & 0
\end{pmatrix}
\times
\begin{pmatrix}
  \tr V_1\\
  \vdots\\
  \tr V_r\\
  \vdots\\
  \tr V_n
\end{pmatrix}
$$

ou formulé autrement:



\begin{eqnarray*}
A  &=&  \sigma_1\cdot  U_1\times  \tr  V_1+\sigma_2\cdot  U_2\times  \tr
V_2+\cdots+\sigma_r\cdot  U_r\times \tr  V_r+0\cdot U_{r+1}\times  \tr
V_{r+1}+\cdots\\
&=&\sigma_1\cdot  U_1\times  \tr  V_1+\sigma_2\cdot  U_2\times  \tr
V_2+\cdots+\sigma_r\cdot  U_r\times \tr  V_r
\end{eqnarray*}


Il  faut ensuite  se souvenir  que  les $\sigma_i$  sont classés  dans
l'ordre  décroissant ce  qui va  avoir des  applications importantes  en
informatique.


\subsection{Interprétation géométrique}


Comment interpréter géométriquement ce résultat? Considérez une sphère
de rayon 1:  que devient-elle transformée par A, i.e.  par $U \times S
\times \tr V$? Faites un petit dessin en dimension 2.
Que vaut $\Vert A\Vert_2 =\displaystyle \max_{\Vert x\Vert =1}\Vert Ax\Vert_2$?

Afin de répondre, un peu de vocabulaire d'abord.  On a $AV_i=\sigma_i U_i$: on dit alors
que $U_i$ est un vecteur singulier  à gauche pour la valeur singulière
$\sigma_i$.

De même $\tr A U_i =\sigma_i V_i$  et $V_i$ est un vecteur singulier à
droite  pour la  valeur singulière  $\sigma_i$. Les  bases $(u_i)$  et
$(V_i)$ sont orthonormées: si l'on exprime la matrice de l'application
linéaire  associée   à  A  dans   ces  bases,  que   pouvez-vous  dire
géométriquement?




\subsection{Un exemple simple}


On suppose  que la SVD d'une  matrice A de taille  $m\times n$ s'écrit
$U\times S \times \tr V$.

\begin{enumerate}
\item  Quelles sont  les  dimensions de  U et  V?  Que pensez-vous  de
  $A\times \tr A$?  Que représentent les
  colonnes de U pour $A\times \tr A$?. Et les colonnes de V pour $\tr A\times A$.
\item Calculez (à la main...) la SVD de $A=
  \begin{pmatrix}
    2&-2\\
    1&1
  \end{pmatrix}
$.

\item Shoot again avec $
  \begin{pmatrix}
    3&1&1\\
    -1&3&1
  \end{pmatrix}
$
\end{enumerate}


Quels liens existent entre la SVD et la recherche des éléments propres
d'une  matrice?  Avec le  théorème  spectral?  Vaut-il mieux  utiliser
$A\times \tr A$ ou $\tr A\times A$?


\subsection{Approximation de rang minimum d'une matrice}


Dans  de  nombreux  domaines,  on  doit  travailler  avec  de  grosses
matrices. Il est alors très important de déterminer une matrice $\widetilde{A_s}$ de
même taille qu'une matrice A mais de rang $s$ inférieur au rang $r$ de
A et qui minimise
l'erreur commise pour  une certaine norme (qui est le  plus souvent la
norme de  \textsc{Frobenius}, i.e.  la racine carrée  de la  somme des
carrés des  coefficients). Le théorème  d'\textsc{Eckart-Young} permet
alors de dire que:

$$\min_{{\rm   rg}(X)\leqslant  s}\Vert   A-X\Vert_F=\Vert
A-\widetilde{A_s}\Vert_F= \sqrt{\sum_{j=s+1}^r \sigma_j^2(A)}$$


avec $\widetilde{A_s}=\sigma_1\cdot  U_1\times  \tr  V_1+\sigma_2\cdot  U_2\times  \tr
V_2+\cdots+\sigma_s\cdot  U_s\times \tr  V_s$:  on  considère que  les
éléments diagonaux de A sont  nuls en-dessous d'un certain seuil. Nous
allons l'illustrer informatiquement  à défaut de le  démonter. On voit
tout de  suite des conséquences  pratiques, que nous  allons également
illustrer informatiquement dans le cas de la compression des images.



\section{Manipulation d'images}

\subsection{Quelques fonctions Python}

Python contient une  matrice carrée de taille 512 contenant  les niveaux de gris
représentant Lena. Il suffit de cherger les bonnes bibliothèques:
\pythonc

\begin{lstlisting}
from pylab import *
from scipy import misc

l = misc.lena()
imshow(l,cmap=cm.gray)
\end{lstlisting}

Lena est bien une matrice:


\begin{lstlisting}
In [8]: type(l)
Out[8]: numpy.ndarray

In [9]: shape(l)
Out[9]: (512, 512)
\end{lstlisting}

On peut préférer travailler sur une photo de format jpg (qui sera à l’envers) ou
png (qui  sera à l’endroit).  Python la transforme  en matrice avec  la fonction
imread.  La matrice  obtenue est  en  RVB :  chaque coefficient  est un  vecteur
(R,V,B). On la convertit  en niveau de gris par exemple  en calculant la moyenne
des trois couleurs.

On récupère d'abord une image:

\begin{lstlisting}
In [4]: from urllib.request import urlretrieve

In [5]: urlretrieve('http://download.tuxfamily.org/tehessinmath/les_images/marty.png','marty.png')
Out[5]: ('marty.png', <http.client.HTTPMessage at 0x7f3aeeb5fa20>)
\end{lstlisting}

et on la transforme en matrice:

\begin{lstlisting}
tm = imread('marty.png')

def rvb_to_gray(m):
    r = len(m)
    c = len(m[0])
    return(array([[m[i,j][0] for j in range(c)] for i in range(r)]))

marty = rvb_to_gray(tm)
\end{lstlisting}


\subsection{Manipulations basiques}

Comment obtenir les images suivantes:

\begin{multicols}{2}
  \begin{center}
  \includegraphics[height=3cm]{lena_miroir}
\end{center}
\begin{center}
  \includegraphics[height=3cm]{lena_retourne}
\end{center}
\end{multicols}

Sachant que l'échelle de gris est celle-ci:


%\begin{figure}
\begin{center}
  \includegraphics[width=0.8\linewidth]{grayscale}
\end{center}
%\end{figure}

comment obtenir les images suivantes:

\begin{multicols}{3}
   \begin{center}
  \includegraphics[height=4cm]{lena_foncee}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_claire}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_neg}
\end{center}

\end{multicols}


\subsection{Gagner de la place}


Une matrice de taille $2^9$ contient $2^{18}$ entiers codés entre 0 et
$2^8-1$ ce  qui prend pas mal  de place en mémoire.  Peut-on être plus
économique sans pour cela diminuer la qualité esthétique de la photo?

\subsubsection{Résolution}

La première idée est de prendre  de plus gros pixels, c'est-à-dire une
matrice plus petite: on extrait par exemple régulièrement un pixel sur
$k$ (en choisissant $k$ parmi une puissance de 2 inférieure à $2^9$).

Comment obtenir par exemple ces images?

\begin{multicols}{3}
%\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{lena_64}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_128}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_256}
\end{center}
%\end{figure}
\end{multicols}



\subsubsection{Quantification}

On peut également  réduire le nombre de niveaux de  gris en regroupant
par exemple tous les niveaux entre 0 et 63 en un seul niveau 0, puis 64
à 127 en 64, 128 à 191 en 128, 192 à 256 en 192.

Par exemple, avec 4, 8 puis 16 niveaux:





\begin{multicols}{3}
%\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{lena_q4}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_q8}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_q16}
\end{center}
%\end{figure}
\end{multicols}







\subsubsection{Compression et SVD}

Tout  langage  orienté  calcul  comprend  des  fonctions  liées  à  la
décomposition en éléments simples.  

Python a  sa fonction  \lstinline+linalg.svd(mat)+ qui renvoie la décomposition en
valeurs singulières sous la forme du triplet U, S et V.


En  vous  inspirant  des   commentaires  faits  dans  les  paragraphes
précédents sur la SVD, expliquez comment cette décomposition permet de
compresser une image. Quantifiez également le niveau de compression.

Voici trois niveaux de compression:


\begin{multicols}{3}
%\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{lena_svd10}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_svd25}
\end{center}
\begin{center}
  \includegraphics[height=4cm]{lena_svd50}
\end{center}
%\end{figure}
\end{multicols}



\subsection{Enlever le bruit}


\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{shannon}
\caption{C.E. \bsc{Shannon (1916-2001)}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5.9cm}
\begin{minipage}[t]{\linewidth}

La transmission  d'informations a toujours posé  des problèmes: voleurs
de grands  chemins, poteaux télégraphiques sciés,  attaques d'indiens,
etc.

Claude    Elwood    \textsc{Shannon}    (1916    -    2001)    est    un
mathématicien-inventeur-jongleur américain qui,  suite à son article \og
\textit{A mathematical theory of communications}\fg{} paru en 1948, est
considéré comme le fondateur de la
\textit{théorie  de  l'information}  qui  est  bien sûr  une  des  bases
de...l'\textit{informatique}.
\end{minipage}

L'idée est d'étudier et de quantifier l'\og information\fg{} émise et
reçue:  quelle est la  compression maximale  de données  digitales? Quel
débit choisir pour transmettre un message dans un canal \og bruité\fg{}?
Quel est le niveau de sûreté d'un chiffrement?...

La  théorie de  l'information  de \textsc{Shannon}  est  fondée sur  des
modèles probabilistes:  leur étude  est donc un  préalable à  l'étude de
problèmes   de  réseaux,   d'intelligence   artificielle,  de   systèmes
complexes. 

Par   exemple,   dans   le   schéma  de   communication   présenté   par
\textsc{Shannon}, la  source et le destinataire  d'une information étant
séparés, des perturbations peuvent créer une différence entre le message
émis et le message reçu.   Ces perturbations (bruit de fond thermique ou
accoustique, erreurs d'écriture ou de lecture, etc.) sont de nature
\textit{aléatoire}:  il n'est  pas possible  de prévoir  leur  effet. De
plus, le message  source est par nature \textit{imprévisible} du  point de vue du
destinataire (sinon, à quoi bon le transmettre). 

\textsc{Shannon}  a  également  emprunté   à  la  physique  la  notion
d'entropie   pour   mesurer   le  désordre   de   cette   transmission
d'information, cette même notion d'entropie  qui a inspiré notre héros
national, Cédric \textsc{Villani}... 


Mais revenons à Lena. Nous allons simuler une Lena bruitée:

\begin{lstlisting}
from random import *
def ber(p):
    if random() < p:
        return 1
    else:
        return 0
    
def bruit(m,p):
    r = len(m)
    c = len(m[0]) 
    return(array([[(m[i,j] + randint(0,255)*ber(p))%256 for j in range(c)] for i in range(r)]))
\end{lstlisting}


Il existe de nombreuses méthodes, certaines très élaborées, permettant
de minimiser  ce bruit. Une des  plus simples est de  remplacer chaque
pixel par la  moyenne de lui-même et de ses  8 autres voisins directs,
voire aussi ses  24 voisins directs et indirect, voire  plus, ou de la
médiane de  ces séries  de \og  cercles\fg{} concentriques  de pixels,
comme on  le voit  sur cette figure  (extraite du  site \texttt{Images
  des mathématiques}):



%\begin{figure}
\begin{center}
  \includegraphics[height=2.25cm]{mean_pix}
\end{center}
%\end{figure}

Créez  des fonctions    qui feront  le  boulot. Vous  utiliserez
\texttt{mean} et \texttt{median} pour obtenir par exemple:





\setindent{1cm}
\begin{multicols}{3}
%\begin{figure}
\begin{center}
  \includegraphics[height=3.8cm]{lena_bruit}
\end{center}
\begin{center}
  \includegraphics[height=3.8cm]{lena_mean}
\end{center}
\begin{center}
  \includegraphics[height=3.8cm]{lena_median}
\end{center}
%\end{figure}
\end{multicols}
\setindent{\indentationcours}

où l'on  trouve de gauche à  droite l'image bruitée originale  puis sa
correction par moyenne sur 25 pixels et par médiane sur 9 pixels.


\subsection{Détection de bords}


Pour  sélectionner  des objets  sur  une  image,  on peut  essayer  de
détecter leurs bords, i.e. des  zones de brusque changement de niveaux
de gris.

On  remplace alors  un pixel  par une  mesure des  écarts des  voisins
immédiats donnée par exemple par:

$$\sqrt{ \left(m_{i,j+1}-m_{i,j-1}\right)^2+ \left(m_{i+1,j}-m_{i-1,j}\right)^2
}$$

On obtient alors au choix:


\begin{multicols}{2}
%\begin{figure}
\begin{center}
  \includegraphics[height=4.5cm]{lena_contour}
\end{center}
\begin{center}
  \includegraphics[height=4.5cm]{lena_contour_blanc}
\end{center}
%\end{figure}
\end{multicols}




\section{Chiffrement de Hill}



Nous  allons  à présent  utiliser  nos  outils  de calcul  matriciel  en
cryptographie. En  1929, Lester \textsc{Hill} (1891 - 1961) proposa une
méthode  de chiffrement  par blocs  de lettres  en travaillant  avec des
matrices à  coefficients dans $\bbz/26\bbz$  (combien y a-t-il  de lettres
dans notre alphabet?).  Par la suite nous noterons $\bbz_{n}$ l'ensemble
$\bbz/n\bbz$. Cela a ouvert le domaine de la cryptographie algébrique et
de   nos  jours,   c'est   l'\textsc{Aes}  (\textit{Advanced   Encrypting
  Standard}),  né  en  2000,  qui  assure la  majorité  de  la  sécurité
informatique.


Nous allons explorer cette
méthode en travaillant sur tous les caractères affichables en ASCII.

\subsubsection{Codage}\label{code_ascii}



Chaque caractère est  associé à un codage binaire, en général
sur 8 bits (un octet) ce qui donne $2^8=256$ caractères possibles.

En fait,  un américain a mis au  point en 1961 l'ASCII  (on prononce \og
aski\fg{})   pour   \og   American   Standard   Code   for   Information
Interchange\fg{}  qui  codait 128  caractères  sur  7  bits ce  qui  est
suffisant pour les américains qui n'ont pas de lettres accentuées.

Il  a ensuite  fallu étendre  ce code  pour les  langues  comportant des
caractères  spéciaux  et là,  les  normes  diffèrent,  ce qui  crée  des
problèmes de compatibilité.

Depuis quelques années, le codage  \emph{Unicode} tente de remédier à ce
problème  en codant  tous  les caractères  existants. %  C'est le  standard
% utilisé sur les systèmes Linux par exemple.

La plupart des langages de programmation, et bien sûr \py, ont une commande qui associe le
code  ASCII  (éventuellement étendu)  à  un  caractère.  On pourra  donc
l'utiliser pour résoudre notre problème. Il s'agit de  la
commande \lstinline+ord(caratère)+ qui  renvoie le code ASCII\index{ASCII} du
caractère \lstinline+caractère+.



\begin{table}[h!]
\begin{center}
{\scriptsize
\begin{tabularx}{0.99\linewidth}{Il*{19}{|Z}I}
\whline
Caractère&  & ! & " & \# & \$ & \% & \& & ' & (  & ) & * & + & , & - & . & / & 0 & 1 & 2 \\
\hline
Code & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 & 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 \\
\hline
\end{tabularx}

\begin{tabularx}{0.99\linewidth}{Il*{19}{|Z}I}
\hline
Caractère&3 & 4 & 5 & 6 & 7 & 8 & 9 & : & ; & < & = & > & ? & @ & A & B & C & D & E \\
\hline
Code &51 & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60 & 61 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69\\
\hline
\end{tabularx}



\begin{tabularx}{0.99\linewidth}{Il*{19}{|Z}I}
\hline
Caractère&F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X \\
\hline
Code &70 & 71 & 72 & 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80 & 81 & 82 & 83 & 84 & 85 & 86 & 87 & 88\\
\hline
\end{tabularx}





\begin{tabularx}{0.99\linewidth}{Il*{19}{|Z}I}
\hline
Caractère& Y & Z & [ & \verb+ \ + & ] & \verb+ ^ + & \verb+ _ + & \verb+ ` + & a & b & c & d & e & f & g & h & i & j & k \\
\hline
Code & 89 & 90 & 91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100 & 101 & 102 & 103 & 104 & 105 & 106 & 107 \\
\hline
\end{tabularx}



\begin{tabularx}{0.99\linewidth}{Il*{19}{|Z}I}

\hline
Caractère& l & m & n & o & p & q & r & s & t & u & v & w & x & y & z & \{ & | & \} & \verb+~+ \\
\hline
Code & 108 & 109 & 110 & 111 & 112 & 113 & 114 & 115 & 116 & 117 & 118 & 119 & 120 & 121 & 122 & 123 & 124 & 125 & 126\\
\whline
\end{tabularx}
}
\caption{Table des caractères ASCII affichables}
\end{center}
\end{table}



Par exemple:

\begin{pythoncode}
>>> ord('@')
64
\end{pythoncode}

Mais   attention!  Cela   ne  fonctionne   par  pour   les   chaînes  de
caractères\index{chaîne de caractères}:

\begin{pythoncode}
>>> ord('AB')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: ord() expected a character, but string of length 2 found
\end{pythoncode}

Il faudra donc considérer les caractères d'une chaîne un par un:


\begin{pythoncode}
def ascii(chaine):
    return [ord(c)-ord((' ')) for c in chaine]
\end{pythoncode}

Le \lstinline+-ord((' ')+ permet d'obtenir des caractères codés entre 0 et
95.

\begin{pythoncode}
>>> ascii("3h de retard !!#@!")
[19, 72, 0, 68, 69, 0, 82, 69, 84, 65, 82, 68, 0, 1, 1, 3, 32, 1]
\end{pythoncode}




Tant  qu'on y  est,  créons une  fonction  \lstinline+deascii+ qui  effectuera
l'opération inverse.  On utilisera alors  la commande \Com{chr}
qui renvoie le caractère associé à un code ASCII.  On utilise
\Com{join} pour concaténer plus vite des chaînes.


\begin{pythoncode}
def deascii(chaine):
    return ''.join(chr(x + ord((' '))) for x in chaine)
\end{pythoncode}

Par exemple:

\begin{pythoncode}
>>> deascii([19, 72, 0, 68, 69, 0, 82, 69, 84, 65, 82, 68, 0, 1, 1, 3, 32, 1])
'3h de retard !!#@!'
\end{pythoncode}


Choisissons à présent un message à coder, assez long:

\begin{center}
Arghh !! Ce 1000 pattes aurait 314 pattes ??
\end{center}


\begin{pythoncode}
>>> m = "Arghh !! Ce 1000 pattes aurait 314 pattes ??"
\end{pythoncode}

Le  principe consiste  alors  à  regrouper les  nombres  par paquets  de
longueur constante $p$ et donc à construire à partir de la liste \lstinline+L+ une
matrice de $p$ lignes complétée éventuellement de zéros.

Nous allons  pour cela  créer une fonction  \lstinline+to_Hill(liste,p)+ qui
transforme une liste en une matrice de  $p$ colonnes en complétant par des zéros
si nécessaire:

\begin{pythoncode}[Python3]
def to_Hill(m,p):
  ???
\end{pythoncode}



Le message  en clair devient une matrice.  Choisissons par exemple
un 3-chiffrement de Hill; la matrice \lstinline+clair+ aura donc 3 lignes:


\begin{pythoncode}[Python3]
>>> clair = to_Hill(m,3)
>>> clair
 33  72   1  35  17  16  65  69  65  65   0  20  65  69  31
 82  72   1  69  16   0  84  83  85  73  19   0  84  83  31
 71   0   0   0  16  80  84   0  82  84  17  80  84   0   0
\end{pythoncode}


Il faut  choisir à présent une  clé de chiffrement: ce  sera une matrice
carrée de taille  3, à coefficients dans $\bbz_{95}$  et inversible dans
$\bbz_{95}$.
Nous allons vérifier que la matrice $
\left(\begin{smallmatrix}
1&23&29\\
0&31&1\\
47&3&1
\end{smallmatrix}\right)
$ convient.

Nous voudrions utiliser \lstinline{inverse}
mais on y effectue une division réelle ce qui n'est pas autorisée
dans $\bbz_{95}$.  Nous allons donc un  peu transformer \lstinline{inverse}
pour donner la méthode d'inversion des nombres comme argument.  Seule la dernière ligne de
\lstinline{diago_triangle} change en fait: 



\begin{pythoncode}[matrice.py]
    def diago_triangle(self,inv):
        .
        .
        .
            T = T.mult_ligne(inv(T[k,r-1]),k)
        return T

\end{pythoncode}


puis:

\begin{pythoncode}[matrice.py]
def inverse(self,inv):
    return self.cat_carre_droite().triangle().diago_triangle(inv).extrait_carre_droite()
\end{pythoncode}


Oui mais quel est l'inverse d'un nombre dans $\bbz_{95}$?

C'est un problème d'arithmétique qui  se résout à l'aide de l'algorithme
d'Euclide étendu:



Petit rappel sur cet algorithme qui permet de prouver le théorème de
Bézout et d'obtenir des coefficients vérifiant $au+bv=a\wedge b$~:
\index{\textsc{Bézout} (coefficients de)}
\begin{center}
\begin{tabular}{|c||c|c|c||c|}
\hline $k$ & $u_k$ & $v_k$ & $r_k$ & $q_k$ \\ 
\hhline{=====} 0 & 1 & 0 &$r_0=a$& /  \\ 
\hline 1 & 0 & 1 &$r_1=b$& $q_1$  \\
\hline 2 & $u_0-u_1q_1$ & $v_0-v_1q_1$ &$r_2=r_0-r_1q_1$& $q_2$  \\ 
\hline 3 & $u_1-u_2q_2$ & $v_1-v_2q_2$ & $r_3=r_1-r_2q_2$&$q_3$  \\ 
\hline $\vdots$ &  &  & $\vdots$ & $\vdots$ \\ 
\hline $p-1$ &  &  & $r_{p-1}=a\wedge b$ & $q_{p-1}$ \\ 
\hline $p$ &  &  &   $r_p=0$ &\\
\hline 
\end{tabular} 
\end{center}

La démonstration de l'algorithme découle de la relation:

\begin{center}
\begin{tabular}{ccccc}
 & \fcolorbox{black!90}{black!20}{$u_k$} & {\Large{\textbf{$-$}}} &  &    \\
 & & & &  \\ 
{\Large\bfseries  (   }  &  \fcolorbox{black!90}{black!20}{$u_{k+1}$}  &
{\Large $\mathbf\times$ } & \fcolorbox{black}{black!40}{$q_{k+1}$} &
{\Large\bfseries )} \\
 & & & &  \\ 
{\Large{\textbf{$=$}}} & \fbox{$u_{k+2}$} &  &  &    \\ 
\end{tabular} 
\end{center}


et de la relation similaire pour les $v_k$ et les $r_k$.


Par exemple, pour 19 et 15~:



\begin{center}
\begin{tabular}{|c||c|c|c||c|l}
\hhline{-----} $k$ & $u_k$ & $v_k$ & $r_k$ & $q_k$ &  \\ 
\hhline{=====} 0 & \fcolorbox{black!90}{black!20}{ 1} & \fcolorbox{black!90}{black!20}{ 0} & \fcolorbox{black!90}{black!20}{ 19} & / & $L_0$ \\ 
\hhline{-----} 1 & \fcolorbox{black!90}{black!20}{ 0} & \fcolorbox{black!90}{black!20}{ 1} & \fcolorbox{black!90}{black!20}{ 15} & \fcolorbox{black}{black!40}{1} & $L_1$ \\ 
\hhline{-----} 2 & 1 & $-1$ & 4 & 3 & $L_2\leftarrow L_0-\fcolorbox{black}{black!40}{1}\times L_1$ \\ 
\hhline{-----} 3 & $-3$ & 4 & 3 & 1 & $L_3\leftarrow L_1-3\times L_2$ \\ 
\hhline{-----} 4 & 4 & $-5$ & 1 & 3 & $L_4\leftarrow L_2-1\times L_3$ \\ 
\hhline{-----} 5 &  &  & 0 &  & $L_5\leftarrow L_3-3\times L_4$ \\ 
\hhline{-----} 
\end{tabular} 
\end{center}

C'est-à-dire $4\times 19-5\times 15=1$ et  $19\wedge 15=1$.

En  version récursive, on  peut procéder  en deux  étapes en  suivant la
méthode rappelée ci-dessus:


\begin{pythoncode}[Python3]
def aee(u,v,r,U,V,R):
    if R == 0: return [u,v,r]
    else:
        q = r // R
        return ???

def AEE(a,b): 
    return aee(1,0,a,0,1,b)
\end{pythoncode}


Soit $\dot{a}$ la classe de l'entier $a$ modulo $n$.
Démontrons que $\dot{a}$ est inversible dans $\bbz_n$ si et
seulement si $a$ et $n$ sont premiers entre eux:



$\dot{a}\times\dot{b}=\dot{1}\Leftrightarrow ab\equiv 1[n]\Leftrightarrow  \exists k\in\bbz \ 
ab=1+kn\Leftrightarrow \exists k\in\bbz \ ba-kn=1 \Leftrightarrow a\wedge n=1$, la dernière équivalence 
étant obtenue grâce au théorème de Bézout.

Comme 11 et 13 sont premiers, chaque élément non nul de $\bbz_{11}$ et $\bbz_{13}$ 
est inversible. Mais par 
exemple 6 n'est pas premier avec 9, donc $\dot{6}$ n'est pas inversible dans 
$\bbz_9$,  c'est pourquoi  la résolution  de l'équation  $6x\equiv b[9]$
pose problème.


Nous allons  donc utiliser la fonction  \verb+AEE+ créée précédemment
 pour déterminer l'inverse d'un nombre dans
$\bbz_{n}$:\label{inv_modulaire}


\begin{pythoncode}[Python3]
def inv_mod(p,n):
    B = AEE(p,n)
    assert B[2] == 1, str(p) + ' non iversible modulo ' + str(n)
    return ???
\end{pythoncode}





On peut alors obtenir directement l'inverse de la matrice \lstinline+cle+:



\begin{pythoncode}[python3]
>>> cle = list2mat([[1,23,29],[0,31,1],[47,3,1]])
>>> inv_cle = cle.inverse(lambda x: inv_mod(x, 95))
>>> inv_cle
-1.82136E+09 -4.16311E+09  5.69826E+10
       23312      -675552         -496
      -30597        22638          651
\end{pythoncode}

Oups!  Il  serait  plus  lisible   d'obtenir  les  représentants  canoniques  de
$\bbz_{95}$. Il suffit  donc de calculer le reste de  chaque coefficient dans la
division par 95 donc d'appliquer la fonction \lstinline{lambda coeff : coeff % 95}.

Comme ce genre d'action est standard, on créer une méthode \lstinline{map} dans notre classe
\lstinline{Mat}   (on  parle   alors  de   \textit{foncteur}  en   programmation
fonctionnelle qui rejoint la notion homonyme en théorie des catégories).

\begin{pythoncode}[matrice.py]
    def map(self,f):
        return Mat(self.D, lambda i,j: f(self.F(i,j)))
\end{pythoncode}


Alors:

\begin{pythoncode}[Python3]
>>> inv_cle = cle.inverse(lambda x: inv_mod(x, 95)).map(lambda coeff : coeff % 95)
>>> inv_cle
 18  14  34
 37  88  74
 88  28  81
\end{pythoncode}

On vérifie:

\begin{pythoncode}[Python3]
>>> (cle * inv_cle).map(lambda coeff : coeff % 95)
 1  0  0
 0  1  0
 0  0  1
\end{pythoncode}


Nous  pouvons multiplier  \lstinline+cle+ par  \lstinline+clair+ pour  coder notre
message. Pour le  décoder, il suffira de multiplier  le message codé par
\lstinline+inv_cle+.

La   matrice  \lstinline+cle+$\times$\lstinline+clair+  est   une  matrice   de  3
lignes. Il  faudra la  transformer ensuite en  liste pour  lui appliquer
\lstinline+decode+. On utilise la fonction  \Com{iter} définie dans notre classe
\lstinline{Mat}.



\begin{pythoncode}[python3]
>>> crypte = deascii(iter((cle * clair).map(lambda n : n % 95)))

>>> crypte
"sP_2Ou8?R'QOyE(Xph_<bn(h<Yc cAkDj\\pf_<bn(ho+>"
\end{pythoncode}

Si on le compare au message initial:

\lstinline{"Arghh !! Ce 1000 pattes aurait 314 pattes ??"}

on remarque  que le premier \og pattes\fg{}  est codé par  \lstinline{h_<be(} alors que le  second est
codé par \lstinline{pf_<bn}: ce n'est donc pas un codage lettre par lettre et il est donc
apparemment plus compliqué que le chiffrement de César.



\subsubsection{Décodage}



Celui  qui  reçoit ce  message  (l'éternel  Bob...)  possède la  clé  de
décodage qui est \lstinline+inv_cle+.


\begin{pythoncode}[Python3]
>>> decrypte = deascii(???)
>>> decrypte
'Arghh !! Ce 1000 pattes aurait 314 pattes ?? '
\end{pythoncode}

Ça marche! On remarque les deux espaces (neutres) rajoutés à la fin pour obtenir
une chaîne de longueur un multiple de 3.

% \subsubsection{Casser le chiffrement de \textsc{Hill}}

% \subsubsection{Exercices}


\section{Codes correcteurs d'erreurs linéaires}

Un très rapide tour d'horizon...Vous utiliserez la classe Mat pour illustrer les
notions suivantes...


\subsection{Quelques rappels}

On  veut transmettre  $2^r$ messages  distincts: on  les code  sur $r$  bits. On
rajoute des bits de contrôle pour vérifier que le message a été bien transmis.

Le message tient donc en fait sur $n$ bits.

Si une transformation linéaire permet de  passer du code initial de $\bbf_2^r$ au
code émis de $\bbf_2^n$, on dit que le code est linéaire.

\begin{exercice}
Par exemple, on veut transmettre des mots de 1 bit. On émet le message en le
triplant (1 est émis en 111). Le code est-il linéaire? Quelle est sa matrice $G$ de codage?
\end{exercice}


Notons $G$ la matrice du code linéaire. 

\begin{exercice}
  Il doit y avoir au moins autant de  mots codés que de mots au départ: comment
  cela se traduit-il quant au rang de $G$?
\end{exercice}


Notons $C$ la matrice de contrôle telle  que $C\cdot m_r=0$ si, et seulement si,
$m_r$ (le message reçu) est un mot de code (qui a donc été transmis sans erreur).


\begin{exercice}
  Que dire du rang de C?
\end{exercice}


On notera \textit{syndrome} la fonction associée à $s$.

On appellera matrice de décodage la  matrice $D$ telle que $x=Dy \Leftrightarrow
y = Gx$.

Par la  méthode de  la $\ell$-réduite échelonnée  de \textsc{Gau\ss  -Jordan} on
peut  déterminer $D$  et $C$:  suivez  les explications  de votre  chargé de  TD
préféré...

\begin{exercice}
  Que donne $R\times (G|m_r)$?
\end{exercice}

Notons $ε$ l'erreur commise que le message codé émis $m_c$. Alors $m_c=m_r+ε$.

\begin{exercice}
  Montrez que $s(m_r)=s(ε)$ et que l'on peut répartir les vecteurs de $\bbf_2^n$
  selon des classes d'équivalences par syndromes.

Montrez que si $u$ est un  message reçu quelconque, ${\rm classe}(u)=u+\CR$ avec
$\CR$ l'ensemble des mots codés.
\end{exercice}

Un  code  de  \textsc{Hamming}  est  un  code  tel  que  tous  les  vecteurs  de
$\bbf_2^{n-r}$, sauf le vecteur nul, apparaissent dans C.


\subsection{Exemples}

\begin{exercice}
  Déterminez une matrice de contrôle du code défini par la matrice génératrice:


$$G=
\left(
\begin{smallmatrix}
  1&0&0&1\\
  1&1&1&1\\
  0&1&1&0\\
  1&0&0&0\\
  0&1&0&0\\
  0&0&1&0\\
  0&0&0&1\\
\end{smallmatrix}
\right)
$$

Après contrôle d'erreur, décodez les  messages reçus suivants: 0111101, 0100110,
1010010.

Quel est le défaut de ce code?


\end{exercice}



\begin{exercice}
  Même style de questions avec:


$$
G=\left(
\begin{smallmatrix}
  1&1&0&1\\
  1&0&1&1&\\
  1&0&0&0\\
  0&1&1&1\\
  0&1&0&0\\
  0&0&1&0\\
  0&0&0&1\\
\end{smallmatrix}
\right)
$$
On reçoit 1010110, 1100110, 0100001, 0010001.
Quelle est la nature du code? Quelle est la matrice de décodage $D$?




\end{exercice}




\begin{exercice}
  Même style de questions avec:


$$
G=
\left(
\begin{smallmatrix}
1&0&0&0\\
0&1&0&0\\
1&0&1&0\\
1&1&0&1\\
0&1&1&0\\
0&0&1&1\\
0&0&0&1\\
\end{smallmatrix}
\right)
$$
On reçoit 1100101.
Quelle est la nature du code? Quelle est la matrice de décodage $D$?




\end{exercice}


\begin{exercice}
  Si $p$ est la  probabilité d'erreur sur un bit et si les  erreurs par bit sont
  indépendantes, exprimez la  probabilité en fnctin de $p$  qu'un message erroné
  devienne   un  mot   différent   du  mot   émis  lorsque   le   code  est   de
  \textsc{Hamming}.  Donnez  une valeur  approchée  pour  $p=0,1$. (On  rappelle
  que 
le code de \textsc{Hamming} ne corrige que les erreurs de poids 1).
\end{exercice}






%%% Local Variables: 
%%% TeX-master: "PolyIPT2014_15"
%%% End: 
