Transformée de Hadamard

La transformée de Hadamard (aussi connue sous le nom de « transformée de Walsh-Hadamard ») est un exemple d'une classe généralisée d'une transformée de Fourier. Elle est nommée d'après le mathématicien français Jacques Hadamard et effectue une opération linéaire et involutive avec une matrice orthogonale et symétrique sur 2m nombres réels (ou complexes, bien que les matrices utilisées possèdent des coefficients réels). Ces matrices sont des matrices de Hadamard.

La transformée de Hadamard peut être vue comme étant issue d'une transformée de Fourier discrète et s'avère être en fait l'équivalent d'une transformée de Fourier discrète multidimensionnelle d'une taille de 2×2×...×2×2. Elle décompose un vecteur arbitraire en entrée en une superposition de fonctions de Walsh[1].

Définition formelle modifier

La transformée de Hadamard Hm utilise une matrice 2m×2m (une matrice de Hadamard) multipliée par un facteur de normalisation, et transforme 2m nombres réels xn en 2m nombres réels Xk. La transformée peut être définie de deux manières : récursivement ou en utilisant une représentation binaire des indices n et k.

Définition récursive modifier

Récursivement, on définit une première transformation 1×1 via une matrice H0 qui est la matrice identité avec un seul élément (1). On définit ensuite Hm pour m > 0 grâce à la relation suivante :

 

1/2 est un facteur de normalisation qui est parfois omis. Ainsi, à l'exception de la normalisation, les coefficients de la matrice sont égaux à 1 ou -1.

Définition directe modifier

De manière équivalente, on peut définir l'élément (k,n) d'une matrice de Hadamard grâce à   et  , où kj et nj sont le bit j (0 ou 1) de respectivement k et n. Dans ce cas, on obtient

 .

Interprétation modifier

Il s'agit d'une transformée de Fourier discrète 2×2×...×2×2 normalisée de manière à être unitaire, si l'on considère les entrées et les sorties comme des tableaux multidimensionnels indexés par nj et kj.

Exemples modifier

Les premières matrices de Hadamard sont données par :

 
 
 
 

Les lignes d'une matrice de Hadamard forment des fonctions de Walsh.

Applications modifier

Dans le traitement de l'informatique quantique, la transformation de Hadamard, plus souvent appelée « porte de Hadamard » dans ce contexte, est une rotation d'un qubit. Elle permet de transformer les états   et   du qubit en deux états superposés avec un poids égal :   et  . En général, les phases sont choisies de telle manière que :

 

dans la notation de Dirac. Cela correspond à la matrice de transformation :

 

dans la base  ,  .

Un grand nombre d'algorithmes quantiques utilisent la transformation de Hadamard comme première étape, puisqu'elle[pas clair] transforme n qubits initialisés avec   en une superposition de tous les 2n états orthogonaux exprimés dans la base  ,   avec une pondération égale.

À titre d'exemple, l'algorithme de Shor fait appel à une telle transformation.

Autres applications modifier

La transformation est utilisée en cryptographie, on parle alors de pseudo-transformation de Hadamard. Elle est aussi utilisée pour générer des nombres aléatoires à partir d'une distribution gaussienne. On l'utilise aussi dans la compression de données comme dans l'algorithme H.264 et pour des opérations de traitement du signal.

La transformation de Hadamard est également utilisée pour étudier l'évolution de systèmes au cours du temps par des méthodes expérimentales telles que la cristallographie aux rayons X[2].

Notes et références modifier

  1. Kunz, « On the Equivalence Between One-Dimensional Discrete Walsh-Hadamard and Multidimensional Discrete Fourier Transforms », IEEE Transactions on Computers, vol. C-28, no 3,‎ , p. 267–268 (ISSN 0018-9340, DOI 10.1109/TC.1979.1675334, lire en ligne, consulté le )
  2. (en) Briony A Yorke, Godfrey S Beddard, Robin L Owen et Arwen R Pearson, « Time-resolved crystallography using the Hadamard transform », Nature Methods, vol. 11, no 11,‎ , p. 1131–1134 (ISSN 1548-7091 et 1548-7105, PMID 25282611, PMCID PMC4216935, DOI 10.1038/nmeth.3139, lire en ligne, consulté le )