Transformation rapide de Walsh-Hadamard

En mathématiques computationnelles, la transformée de Walsh-Hadamard rapide ordonnée par Hadamard ( FWHT _h ) est un algorithme efficace pour calculer la transformée de Walsh-Hadamard (WHT). Une implémentation naïve de la WHT d'ordre h est présentée. ${\displaystyle n=2^{m <semantics><mrow><mstyle><mi>n</mi><mo>=</mo><msup><mn>2</mn><mrow><mi>m</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle n=2^{m}}</annotation></semantics></math><img src=$ ${\displaystyle n^{2 <semantics><mrow><mstyle><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup></mstyle></mrow><annotation>{\displaystyle n^{2}}</annotation></semantics></math><img src=$ _h ne nécessite que ${\displaystyle n\log n <semantics><mrow><mstyle><mi>n</mi><mi>enregistrer</mi><mo>⁡</mo><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n\log n}</annotation></semantics></math><img src=$

L'algorithme FWHT _h est un algorithme de type diviser pour régner qui décompose récursivement un WHT de taille n. ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ${\displaystyle n/2 <semantics><mrow><mstyle><mi>n</mi><mrow><mo>/</mo></mrow><mn>2</mn></mstyle></mrow><annotation>{\displaystyle n/2}</annotation></semantics></math><img src=$ ${\displaystyle 2^{m} imes 2^{m <semantics><mrow><mstyle><msup><mn>2</mn><mrow><mi>m</mi></mrow></msup><mo>×</mo><msup><mn>2</mn><mrow><mi>m</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{m} imes 2^{m}}</annotation></semantics></math><img src=$ ${\displaystyle H_{m <semantics><mrow><mstyle><msub><mi>H</mi><mrow><mi>m</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle H_{m}}</annotation></semantics></math><img src=$

{\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}. <semantics><mrow><mstyle><msub><mi>H</mi><mrow><mi>m</mi></mrow></msub><mo>=</mo><mrow><mfrac><mn>1</mn><msqrt><mn>2</mn></msqrt></mfrac></mrow><mrow><mrow><mo>(</mo><mtable><mtr><mtd><msub><mi>H</mi><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msub></mtd><mtd><msub><mi>H</mi><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>H</mi><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msub></mtd><mtd><mo>−</mo><msub><mi>H</mi><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msub></mtd></mtr></mtable><mo>)</mo></mrow></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}.}</annotation></semantics></math></span><img src=

Le ${\displaystyle 1/{\sqrt {2 <semantics><mrow><mstyle><mn>1</mn><mrow><mo>/</mo></mrow><mrow><msqrt><mn>2</mn></msqrt></mrow></mstyle></mrow><annotation>{\displaystyle 1/{\sqrt {2}}}</annotation></semantics></math><img src=$

La transformée de Walsh-Hadamard rapide ordonnée en séquence , également connue sous le nom de transformée de Walsh ordonnée en séquence, FWHT _w , est obtenue en calculant la FWHT _h comme ci-dessus, puis en réorganisant les sorties.

Une implémentation simple, rapide et non récursive de la transformée de Walsh-Hadamard découle de la décomposition de la matrice de la transformée de Hadamard comme ${\displaystyle H_{m}=A^{m <semantics><mrow><mstyle><msub><mi>H</mi><mrow><mi>m</mi></mrow></msub><mo>=</mo><msup><mi>UN</mi><mrow><mi>m</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle H_{m}=A^{m}}</annotation></semantics></math><img src=$ A est la racine m -ième de ${\displaystyle H_{m <semantics><mrow><mstyle><msub><mi>H</mi><mrow><mi>m</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle H_{m}}</annotation></semantics></math><img src=$

Exemple de code Python

import math def fwht ( a ) -> None : Transformation rapide de Walsh-Hadamard en place du tableau a.""" assert math . log2 ( len ( a )) . is_integer (), "la longueur de a est une puissance de 2" h = 1 while h < len ( a ): # effectuer la FWHT for i in range ( 0 , len ( a ), h * 2 ): for j in range ( i , i + h ): x = a [ j ] y = a [ j + h ] a [ j ] = x + y a [ j + h ] = x - y # normaliser et incrémenter a /= math . sqrt ( 2 ) h *= 2