\section{Transformée de Walsh}

Dans cette section,  $m$ désigne un entier positif. 
On note $X$ l'ensemble des $m$-pulets binaires qui
est muni des opérations usuelles :
disjonction exclusive bit à bit,
conjonction bit à bit 
et produit scalaire.
$$
(x\oplus y)_i  = ( x_i + y_i) \mod 2
\quad
(x \ast y )_i = x_i y_i
$$

et 
$$
  x.y = \sum_{i=1}^m x_i y_i \pmod 2.
$$


\subsection{fonction booléenne}

Une fonction booléenne $f$ est une application de $X$
dans $\B$, elle est représentée par un tableau de
longueur $2^m$, la cellule d'index $x$ contient
$f(x)$.

Il s'agit d'une algèbre engendrée par
les fonctions coordonnées $X_i$.

\begin{exercice}
Exprimer $\delta_0$ en fonction des $X_i$.
\end{exercice}


Pour un élément $a\in B^m$ et un scalaire $b\in\B$,
on note $\wt(a,b)$ le poids de Hamming de l'application
$\phi_{a,b}$.

\begin{exercice}
Montrer que $\wt(a,0) + \wt(a,1) = 2^m$.
\end{exercice}

\begin{exercice}
Soit $a\not=0$. Montrer qu'il existe un élément
$y$ tel que $a.y=1$, puis établir une bijection
entre $\{ x \mid ax=0\}$ et  $\{ x \mid ax=1 \}$.
\end{exercice}

$$
\wt(a,b) = \begin{cases}
0,    & $a=0$ \ \text{et}\  $b=0$;\\
2^m,  & $a=0$ \ \text{et}\  $b=1$;\\
2^{m-1} & \text{autre}.
\end{cases}
$$

\subsection{code de Reed-Müller}

Une application de degré $1$ est une forme
affine, elle s'écrit :
$$
      \phi_{a,b}\colon x\mapsto ax+b
$$
avec $a\in\B^m$, et $b\in\B$.

L'ensemble des formes affines sur $X$ 
forme un code de paramètres :
\begin{itemize}
\item longueur $2^m$,
\item dimension $m+1$,
\item distance $2^{m-1}$. 
\end{itemize}

Pour la longueur c'est évident. Pour la
dimension, il suffit de vérifier que $\phi_{a,b}=\phi_{a',b'}$
si et seulement si $a=a'$ et $b=b'$. La distance de Hamming
entre  $\phi_{a,b}$ et $\phi_{a',b'}$ n'est autre que le
poids de Hamming de $\phi_{a+a'}{b+b'}$.


\subsection{transformée de Walsh}

Le coefficient de Walsh d'une application
booléenne $f$ en un point $a$ de $\B^m$ est
par définition :
$$
      \walsh f(a) =\sum_{x\in\B^m} (-1)^{f(x) + a.x}
$$

Il s'agit d'un cas particulier transformation de Fourier.
Le coefficient de Fourier-Hadamad d'une application
intégrale $F$ en un point $a$ de $\B^m$ est
par définition :
$$
      \hat f(a) =\sum_{x\in\B^m} F(x) (-1)^{a.x}
$$

On peut clairement calculer tous les coefficients de Walsh
d'une application intégrale en un temps quadratique.
Une manipulation classique permet de ramener ce
temps de calcul à $n\log_2n$.

Convenons de noter $x=(y, t)\in\B^{m-1}\times \B$,
$a=(\alpha, \gamma)\in\B^{m-1}\times \B$ :

\begin{align*}
      \hat F(a) &=\sum_{x\in\B^m} F(x) (-1)^{+a.x}\\
                  &=\sum_{y\in\B^{m-1}} F(y,0)(-1)^{\alpha.y}+
(-1)^{\gamma}\sum_{y\in\B^{m-1}} F(y,1) (-1)^{\alpha.y}\\
                  &=\walsh {F_0}(\alpha) +(-1)^\gamma \walsh {F_1}(\alpha)
\end{align*}
où $F_0( y ) = F(y, 0)$
et $F_1( y ) = F(y, 1)$.

\begin{figure}
\begin{lstlisting}[style=gcc]
void Fourier_Hadamard( int * f, int n )
{
int x, tmp;
  if ( n == 1 ) return;
  n = n / 2;
  Fourier_Hadamard( f, n  );
  Fourier_Hadamard( f + n , n );
  for( x = 0, x < n  ; x++ ){
     tmp = f[ x ];
     f[ x ] = tmp + f[ x + n ];
     f[ x + n ] = tmp - f[ x + n ];  
  }
}
\end{lstlisting}
\caption{\label{WALSH} Transformation de Fourier-Hadamard  récursive}
\end{figure}

Une analyse du butinage dans la fonction de \gcc{walsh}
montre qu'il est possible de supprimer la récursion pour
obtenir une version rapide \gcc{FWT}.
\begin{figure}
\includegraphics[scale=0.5]{img/walsh.png}
\caption{\label{BUTIN} Le butinage des cellules d'une
table par les papillons de la transformée de Walsh}
\end{figure}

\begin{figure}
\lstinputlisting[style=gcc, firstline=3, lastline=20]{walsh/walsh.c}
\caption{\label{FWT} Transformation rapide de Fourier Hadamard}
\end{figure}

\subsection{décodage}

Soit un mot $f$ du code de Reed-Müller, $\epsilon$ un mot erreur,
le coefficicient de Walsh de la fonction booléenne $g=f+\epsilon$
vaut :

\begin{align*}
\walsh g(a) &= \sum_{x\in\B^m} (-1)^{f(x)+\epsilon(x)+a.x}\\
          &= \sum_{\epsilon(x)=0}(-1)^{f(x)+a.x} -
             \sum_{\epsilon(x)=1}(-1)^{f(x)+a.x}
	  &= \hat f(a) - 2\sum_{\epsilon(x)=1}(-1)^{f(x)+a.x} 
\end{align*}

Soit $w$ le poids de $\epsilon$. Si $\walsh f(a) = 0$ alors
est de valeur absolue moindre que $2w$. Si $\walsh f(a) = 2^m$ alors
est de valeur absolue supérieure à  $2^m- 2w$. On déduit de ces
petits calculs une méthode de décodage valide dès que :
$$
        2^m - 2 w > 2w \Longrightarrow w<2^{m-2}
$$ 
\begin{exercice}
Laquelle ?
\end{exercice}

\begin{exercice}
La transformation de Fourier-Hadamard est
involutive. Pour le vérifier, établir :
$$
        \hat{\hat F} (a) = 2^m F(a)
$$
\end{exercice}
 
