蝶の図

高速フーリエ変換アルゴリズムの文脈では、バタフライとは、より小さな離散フーリエ変換(DFT)の結果をより大きな DFT に組み合わせる、またはその逆 (より大きな DFT をサブ変換に分割する) の計算の一部です。「バタフライ」という名前は、以下で説明するように、基数 2 の場合のデータ フロー図の形状に由来します。 ^{[ 1 ]}この用語が印刷物で最初に登場したのは、1969 年のMIT の技術レポートだと考えられています。^{[ 2 ] [ 3 ]}同じ構造は、隠れた状態の最も可能性の高いシーケンスを見つけるために使用されるビタビ アルゴリズムにも見られます。

最も一般的には、「バタフライ」という用語は、クーリー・テューキーFFTアルゴリズムの文脈で用いられます。このアルゴリズムは、合成サイズn = rmのDFTを再帰的にmサイズのr個のより小さな変換に分解します。ここで、rは変換の「基数」です。これらのより小さなDFTは、サイズrのバタフライによって結合されます。バタフライ自体は、サイズrのDFT （対応するサブ変換の出力に対してm回実行される）に、1の平方根（トゥイドルファクターと呼ばれる）を前乗算したものです。（これは「時間間引き」の場合です。逆の手順を実行することもでき、「周波数間引き」と呼ばれます。この場合、バタフライが最初に実行され、後乗算でトゥイドルファクターが乗算されます。クーリー・テューキーFFTの記事も参照してください。）  

基数2のCooley–Tukeyアルゴリズムの場合、バタフライは単純にサイズ2のDFTであり、2つの入力（x ₀、x ₁）（2つのサブ変換の対応する出力）を受け取り、次の式（ twiddleファクターは含まない）によって2つの出力（ y ₀、y ₁ ）を生成します。  

${\displaystyle y_{0}=x_{0}+x_{1}\,}$

${\displaystyle y_{1}=x_{0}-x_{1}.\,}$

この2つの操作のデータフロー図を描くと、( x ₀ , x ₁ )から( y ₀ , y _{1 )への線が交差し、}蝶の羽に似ていることから、この名前が付けられました（右の図も参照）。  

より具体的には、 n  =  2 ^pの入力に対する、原始的なn乗根に関する基数 2 の時間間引き FFT アルゴリズム ${\displaystyle \omega _{n}^{k}=e^{-{\frac {2\pi ik}{n}}}}$次のような形式のO( n  log ₂ n ) 個のバタフライに依存します。 

${\displaystyle y_{0}=x_{0}+x_{1}\omega _{n}^{k}\,}$

${\displaystyle y_{1}=x_{0}-x_{1}\omega _{n}^{k},\,}$

ここで、kは計算対象の変換部分に応じて決まる整数です。対応する逆変換は、 ω をω ^{− 1}に置き換えることで数学的に実行できます（正規化の慣例によっては、全体のスケール係数を乗じる場合もあります）。また、バタフライを直接反転することもできます。

${\displaystyle x_{0}={\frac {1}{2}}(y_{0}+y_{1})\,}$

${\displaystyle x_{1}={\frac {\omega _{n}^{-k}}{2}}(y_{0}-y_{1}),\,}$

これは、周波数間引きFFTアルゴリズムに相当する。

バタフライアルゴリズムは、部分的に乱数の多い大規模な配列のランダム性を向上させるためにも使用できます。これは、任意のハッシュアルゴリズムを介して、32ビットまたは64ビットのすべてのワードを他のすべてのワードと因果的に接触させることで、いずれかのビットの変更が大規模な配列のすべてのビットを変更する可能性を持つようにするためです。^{[ 4 ]}

• 数学的図
• ザッセンハウスの補題
• 信号フローグラフ

• FFTとバタフライ図の説明。
• さまざまな FFT 実装 (基数 2、基数 4、分割基数) のバタフライ図。