Fast Walsh–Hadamard transform とは

計算上の数学では、アダマール命令の高速Walsh-Hadamard変換(FWHTh)は、Walsh-Hadamard変換(WHT)を計算する効率的なアルゴリズムです。順序 n = 2 m {\displaystyle n=2^{m}} のWHTの素朴な実装は、計算量がO( n 2 {\displaystyle n^{2}} )になります。 FWHThは n log n {\displaystyle n\log n} の加算または減算しか必要としない。
FWHThは、サイズ n {\displaystyle n} のWHTをサイズ n / 2 {\displaystyle n/2} の2つのより小さいWHTに再帰的に分解する分割征服アルゴリズムです。この実装は、 2 m × 2 m {\displaystyle 2^{m}\times 2^{m}} アダマール行列 H m {\displaystyle H_{m}} の再帰的定義に従います。
H m = 1 2 ( H m 1 H m 1 H m 1 H m 1 ) . {\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}.}
各段階の 1 / 2 {\displaystyle 1/{\sqrt {2}}} 正規化係数は、グループ化されていても、省略されていてもよい。
上記のFWHThを計算し、出力を並べ替えることによって、順序付けられたシーケンス、ウォルシュオーダー、高速ウォルシュ – アダマール変換、FWHTwが得られます。
Walsh-Hadamard変換の単純で高速な非再帰的実装は、Aが H m {\displaystyle H_{m}} のm乗根であるようなアダマール変換行列の分解から得られる H m = A m {\displaystyle H_{m}=A^{m}}