\documentclass[a4paper,12pt,fleqn]{article} 
\usepackage[]{claire,french,fullpage,euler}
\catcode`\à=\active \def à{\`a}
\catcode`\â=\active \def â{\^a}
\catcode`\é=\active \def é{\'e}
\catcode`\è=\active \def è{\`e}
\catcode`\ê=\active \def ê{\^e}
\catcode`\ù=\active \def ù{\`u}
\catcode`\ô=\active \def ô{\^o}
\catcode`\û=\active \def û{\^u}
\catcode`\ç=\active \def ç{\c c}
\catcode`\î=\active \def î{\^\i}
% Mon \F est pour \F_2
\renewcommand{\F}{\ifcase\BoldMath\ensuremath{\mathbb{F}}\or%
\ensuremath{\pmb{\mathbb{F}}}\fi}%
%
% Le joli F est pour l'espace des fonctions
\newcommand{\varF}{\ensuremath{\matheu{F}}}
%
% Pour des jolies bases
\newcommand{\B}{\ensuremath{\matheu{B}}}
%
\hoffset=-1cm
\voffset=-2.9cm
\topmargin=0cm
\oddsidemargin=0cm
\evensidemargin=0cm
\marginparsep=0pt
\marginparwidth=0pt
\marginparpush=0pt
\headheight=14pt
\textwidth=520pt
\textheight=790pt
\footskip=0pt
\begin{document}
\pagestyle{empty}

\section{Transformation d'Hadamard}
  \subsection{Présentation}

\begin{gather*}
\F_2 = \{0,1\}\\
m\geq1,\ {\F_2}^m\\
\omega=(\omega_1,\ ...\ ,\ \omega_m),\ \tau=(\tau_1,\ ...\ ,\ \tau_m)\\
<{} \omega, \ \tau>{} = \sum_{k=1}^m \omega_k \tau_k \in \F_2\\
\varF(m) = \varF({\F_2}^m,\C)\\
\B = (\varphi_\omega)_{\omega \in {\F_2}^m} \text{ (trié par l'ordre lexicographique)}\\
\varphi_\omega(\tau)=
\left\{
\begin{array}{cc}
1\text{ si }\tau=\omega\\
0\text{ si }\tau\neq\omega
\end{array}
\right.\\
f\in\varF(m),\ \tau\in{\F_2}^m,\ h_{2^m}(f)(\tau) = \sum_{\omega\in{\F_2}^m} {(-1)}^{<\ \omega,\ \tau>\ } f(\omega)\\
h_{2^m} \circ h_{2^m} = 2^m Id\\
O(2^m * 2^m)
\end{gather*}

  \subsection{Calcul rapide}

\begin{gather*}
H_{2^m}=M_\B(h_{2^m})\\
H_2 =
\begin{pmatrix}
1& 1\\
1&-1
\end{pmatrix},\ 
H_4 =
\begin{pmatrix}
1& 1& 1& 1\\
1&-1& 1&-1\\
1& 1&-1&-1\\
1&-1&-1& 1
\end{pmatrix} =
\begin{pmatrix}
H_2& H_2\\
H_2&-H_2
\end{pmatrix}\\
H_{2^{m+1}} =
\begin{pmatrix}
H_{2^m}& H_{2^m}\\
H_{2^m}&-H_{2^m}
\end{pmatrix}\\
O(m * 2^m)
\end{gather*}

\newpage

\section{Codes correcteurs}

\subsection{Définition}

$C$ de longueur $m$, de dimension $k$ :\\
sous-espace vectoriel de ${\F_2}^m$, de dimension k

\subsection{Distance minimale}

\begin{gather*}
d(\omega,\ \omega') = \text{card} \{i / \omega_i \neq {\omega'}_i \}\\
d(\omega,\ C) = \inf \{ d(\omega,\ \tau),\ \tau\in C\}\\
d_C = \inf \{ d(\tau,\ \tau'),\ (\tau,\ \tau') \in C^2,\ \tau \neq \tau' \}
\end{gather*}

\subsection{Pouvoir correcteur}

soit $t = \lfloor\frac{d-1}{2}\rfloor$,\\
si $d(\omega,\ C) \leq t$, il existe un unique mot de $C$ à distance minimale de $\omega$\\
on dit alors que $C$ corrige $t$ erreurs.

\newpage

\section{Codes de Reed Muller}

\subsection{Codage}

\begin{gather*}
\begin{split}
E=\{u & = u_0+u_1 X_1 + ... + u_m X_m,\ u_0,\ ...\ ,\ u_m \in \F_2 \}\\
      & = (u_0,\ ...\ ,\ u_m )
\end{split}\\
\begin{split}
\psi :\ & E\ \rightarrow\ {\F_2}^{2^m}\\
        & u\ \mapsto\     {(u(\omega))}_{\omega\in{\F_2}^m}
\end{split}\\
C = \text{Im }\psi\\
C\text{ de longueur }2^m,\text{ de dimension }m+1\\
d_C = 2^{m-1},\ t = 2^{m-2}-1
\end{gather*}

\subsection{Décodage}

\begin{gather*}
f \in {\F_2}^{2^m},\ f={(f_\omega)}_{\omega\in{\F_2}^m}\\
\begin{split}
\tau=(u_1,\ ...\ ,\ u_m),\ & g_0=\psi(  \sum_{i=1}^m u_i X_i)\\
                     & g_1=\psi(1+\sum_{i=1}^m u_i X_i)
\end{split}\\
F(\omega)={(-1)}^{f_\omega}\\
d(f,\ g_0) = \frac{1}{2} (2^m-h_{2^m}(F)(\tau))\\
d(f,\ g_1) = \frac{1}{2} (2^m+h_{2^m}(F)(\tau))
\end{gather*}

\subsection{Algorithme}

\begin{itemize}
\item{calculer $F$}
\item{calculer $h_{2^m}(F)$}
\item{chercher $\tau$ tel que $|h_{2^m}(F)(\tau)|$ est maximal}
\item{si $h_{2^m}(F)(\tau)\geq 0$, renvoyer $(0,\ \tau_1,\ ...\ ,\ \tau_m)$\\
      si $h_{2^m}(F)(\tau)  <  0$, renvoyer $(1,\ \tau_1,\ ...\ ,\ \tau_m)$}
\end{itemize}

$O(m * 2^{m})$\\

Exemple:

$f=(0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1)$

\begin{itemize}
\item{$F=(1, -1, 1, 1, -1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, 1, -1, -1)$}
\item{$h_{2^m}(F)=(2, 6, 6, -6, 2, -2, -2, 10, -2, 2, -6, -2, -2, -6, 2, -2, 6, 2, 2, -2, -2, 2, 2, 6, 2, -2, -10, 2, 10, 14, -10, 10)$}
\item{$i=29$, c'est-à-dire $\tau = (1,0,1,1,1)$}
\item{$29>0$, donc $u=(0,1,0,1,1,1)$}
\end{itemize}

et $\psi(u)=(0, 1, 0, \bold{1}, 1, 0, \bold{1}, \bold{0}, \bold{1}, 0, 1, \bold{0}, 0, \bold{1}, 0, 1, 1, 0, 1, \bold{0}, 0, 1, 0, 1, 0, 1, 0, \bold{1}, 1, 0, 1, \bold{0})$

\newpage

\begin{verbatim}
let hadamard f=
  let g=copy_vect f in
  let rec hadam j n=
    for k=0 to n-1 do
      let aux=g.(j+k) in
      g.(j+ k )<-aux + g.(j+k+n);
      g.(j+k+n)<-aux - g.(j+k+n)
    done;
    if n>=2 then (
      hadam   j   (n/2);
      hadam (j+n) (n/2)
    ) in 
  hadam 0 (vect_length f / 2);
  g;;
\end{verbatim}

\begin{verbatim}
let decode f=
  let F=F_of_f f in
  let h2mF=hadamard F in
  let i=cherche_max h2mF
  and m=lg (vect_length h2mF) in
  let u=vect_of_int2 i m in
  if h2mF.(i)<0 then u.(0)<-1;
  u;;
\end{verbatim}


\end{document}