高速ウォルシュ・アダマール変換

計算数学において、アダマール順序付き高速ウォルシュ・アダマール変換（FWHT _h）は、ウォルシュ・アダマール変換（WHT）を計算するための効率的なアルゴリズムである。次数 のWHTの単純な実装${\displaystyle n=2^{m}}$計算複雑度はO (${\displaystyle n^{2}}$）。FWHT _hは、${\displaystyle n\log n}$足し算または引き算。

FWHT _{h は}、サイズ WHT を再帰的に分割する分割統治アルゴリズムです。${\displaystyle n}$2 つの小さな WHT のサイズに${\displaystyle n/2}$[ ^{1 ]} この実装は^、$2m × 2m$アダマール行列${\displaystyle H_{m}}$:

${\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}.}$

の${\displaystyle 1/{\sqrt {2}}}$各段階の正規化係数は、まとめて適用することも、省略することも可能です。

シーケンス順序付けされた、またはウォルシュ順序付けされた高速ウォルシュ・アダマール変換 FWHT _wは、上記のように FWHT _hを計算し、出力を並べ替えることによって得られます。

ウォルシュ・アダマール変換の単純で高速な非再帰的実装は、アダマール変換行列の分解から導かれる。${\displaystyle H_{m}=A^{m}}$ここで、Aはm乗根である。${\displaystyle H_{m}}$[ ^{2 ]​}

• 高速フーリエ変換
• 高速ウェーブレット変換

• チャールズ・コンスタンティン・グマス著「100年前の高速アダマール変換はデジタル通信で有用であることが証明された」