Algorithme

L'algorithme est alors très simple :

• calculer F, à l'aide d'une fonction F_of_f ;
• calculer sa transformée d'HADAMARD h2mF ;
• chercher l'indice i de l'élément du tableau h2mF de valeur absolue maximale (cherche_max) et le convertir en sa représentation binaire, en laissant une case supplémentaire (vect_of_int) ;
• si l'élément ainsi trouvé est négatif, mettre un 1 dans la case supplémentaire.

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;;

La complexité de cet algorithme est donc ramenée à celle du calcul de la transformée d'HADAMARD de F, c'est-à-dire $O(m \times 2^m)$, ce qui est largement mieux qu'avec une méthode brutale, dont la complexité serait en $O(2^m \times 2^m)$.