多次元信号のための高速アルゴリズム

出典：^{[ 3 ]}

DFTの合計${\displaystyle X\left(k_{1},k_{2}\right)}$前述の式は、次の形式でも表すことができます。

${\displaystyle X\left(k_{1},k_{2}\right)=\sum _{n_{1}=0}^{N_{1}-1}\left[\sum _{n_{2}=0}^{N_{2}-1}x(n_{1},n_{2})W_{N_{2}}^{n_{2}k_{2}}\right]W_{N_{1}}^{n_{1}k_{1}}}$

させて ${\displaystyle G\left(n_{1},k_{2}\right)}$括弧内の量を表し、次式で与えられる。

${\displaystyle G\left(n_{1},k_{2}\right)=\sum _{n_{2}=0}^{N_{2}-1}x(n_{1},n_{2})W_{N_{2}}^{n_{2}k_{2}}}$

${\displaystyle X\left(k_{1},k_{2}\right)=\sum _{n_{1}=0}^{N_{1}-1}G\left(n_{1},k_{2}\right)W_{N_{1}}^{n_{1}k_{2}}}$

この方法を採用すると、DFT${\displaystyle X}$は複数の 1-D DFT として計算できます。つまり、${\displaystyle G}$対応する列の 1 次元 DFT と考えることができる${\displaystyle x}$（${\displaystyle n_{1}}$= 定数)。そして各行は${\displaystyle X}$は、対応する行の 1-DFT です。 ${\displaystyle G}$（${\displaystyle n_{2}}$（＝定数）。したがって、2次元DFTを行DFTと列DFTに分解して計算します。

M次元信号のMD DFTを評価する際にも、同じ原理が用いられる。

それでは、このアプローチを使用することで得られる計算上の節約についてお話ししましょう。必要なのは${\displaystyle N_{1}N_{2}(N_{1}+N_{2})}$複雑な加算と乗算。さらに、これらの 1-D DFT のそれぞれを 1-D FFT を使用して計算すると、複雑な乗算の数をさらに削減できます。 ${\displaystyle N_{1}N_{2}{\frac {\log _{2}N_{1}N_{2}}{2}}}$

出典：^{[ 3 ]}

1次元FFTと同様に、2次元信号の場合も時間方向の間引き処理を行うことができます。長さが2のべき乗である信号の1次元DFTは、2つの半分の長さのDFTで表すことができ、それぞれは4分の1の長さのDFTの組み合わせで表すことができ、以下同様です。

2次元信号の場合、次のように表現できます。${\displaystyle (N_{1}{\text{ x }}N_{2})}$4つの観点から見たDFT${\displaystyle {\frac {N_{1}}{2}}{\text{ x }}{\frac {N_{2}}{2}}}$DFT（仮定）${\displaystyle N_{1}}$そして${\displaystyle N_{2}}$は2のべき乗です。簡単にするために、${\displaystyle N_{1}=N_{2}=N}$DFT の二重和は、4 つの別々の和に分解できます。${\displaystyle x}$両方${\displaystyle n_{1}}$そして${\displaystyle n_{2}}$等しく、${\displaystyle n_{1}}$は均等で${\displaystyle n_{2}}$奇妙だ、${\displaystyle n_{1}}$奇妙で${\displaystyle n_{2}}$偶数であり、最後のものは${\displaystyle n_{1}}$そして${\displaystyle n_{2}}$奇妙だ。

これは次のように書かれています 。

${\displaystyle X\left(k_{1},k_{2}\right)=S_{00}(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$

どこ

${\displaystyle S_{00}(k_{1},k_{2})\equiv \sum _{m_{1}=0}^{N/2-1}\sum _{m_{2}=0}^{N/2-1}x(2m_{1},2m_{2})W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}}$

${\displaystyle S_{01}(k_{1},k_{2})\equiv \sum _{m_{1}=0}^{N/2-1}\sum _{m_{2}=0}^{N/2-1}x(2m_{1},2m_{2}+1)W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}}$

${\displaystyle S_{10}(k_{1},k_{2})\equiv \sum _{m_{1}=0}^{N/2-1}\sum _{m_{2}=0}^{N/2-1}x(2m_{1}+1,2m_{2})W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}}$

${\displaystyle S_{11}(k_{1},k_{2})\equiv \sum _{m_{1}=0}^{N/2-1}\sum _{m_{2}=0}^{N/2-1}x(2m_{1}+1,2m_{2}+1)W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}}$

すべての配列${\displaystyle S_{00}S_{01}S_{10}}$そして ${\displaystyle S_{11}}$それぞれ周期的である${\displaystyle (k_{1},k_{2})}$水平周期と垂直周期を持つ${\displaystyle {\frac {N}{2}}}$この事実と、${\displaystyle W_{N}^{N/2}=-1,}$以下の恒等式が得られます 。

${\displaystyle X\left(k_{1},k_{2}\right)=S_{00}(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$

${\displaystyle X\left(k_{1}+{\frac {N}{2}},k_{2}\right)=S_{00}(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}-S_{10}(k_{1},k_{2})W_{N}^{k_{1}}-S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$

${\displaystyle X\left(k_{1},k_{2}+{\frac {N}{2}}\right)=S_{00}(k_{1},k_{2})-S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1}}-S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$

${\displaystyle X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)=S_{00}(k_{1},k_{2})-S_{01}(k_{1},k_{2})W_{N}^{k_{2}}-S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$

上記の式は、4つのDFTポイントを計算する方法を示しています。${\displaystyle X\left(k_{1},k_{2}\right)X\left(k_{1}+{\frac {N}{2}},k_{2}\right)X\left(k_{1},k_{2}+{\frac {N}{2}}\right){\text{ and }}X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)}$特定の値に対して${\displaystyle (k_{1},k_{2})}$4つのポイントから ${\displaystyle S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})}$。${\displaystyle S_{00}(k_{1},k_{2})}$評価することで得られる${\displaystyle \left({\frac {N}{2}}\times {\frac {N}{2}}\right)}$-点DFT（同様に他の${\displaystyle S_{ij}}$入手可能です）。

したがって、${\displaystyle N\times N}$DFTは4つの要素で表現できる${\displaystyle {\frac {N}{2}}\times {\frac {N}{2}}}$DFT（密度汎関数理論）。

1次元の場合との類推により、下図に示す計算は${\displaystyle {\text{butterfly}}}$あるいはもっと正確に言うと${\displaystyle radix-(2\times 2){\text{ butterfly}}}$。

各蝶は、入力から出力を計算するために3つの複雑な乗算と8つの複雑な加算を必要とします。そして、すべてのサンプルを計算するには、${\displaystyle X}$から${\displaystyle S_{00}(k_{1},k_{2}),S_{01}(k_{1},k_{2}),S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})}$計算が必要です${\displaystyle {\frac {N^{2}}{4}}}$蝶々。

この間引き処理は実行されます ${\displaystyle \log _{2}N}$そういう時${\displaystyle N}$は 2 のべき乗です。 100 段階はそれぞれ以下で構成されます。${\displaystyle {\frac {N^{2}}{4}}}$蝶々、そして各蝶々は 3 つの複雑な乗算と 8 つの複雑な加算を含むため、計算中に実行する必要のある複雑な乗算の数は${\displaystyle (N\times N)}$-小数点基数${\displaystyle (2\times 2)}$FFTは次のように与えられる。

${\displaystyle C_{vectorRadix(2\times 2)}={\frac {3N^{2}}{4}}\log _{2}N}$