ベクトル基数FFTアルゴリズム

ベクトル基数FFTアルゴリズムは、多次元高速フーリエ変換（FFT）アルゴリズムであり、変換次元を任意の基数で分割する通常のCooley–Tukey FFTアルゴリズムの一般化です。多次元（MD）離散フーリエ変換（DFT）を、最終的には自明なMD DFTのみを評価する必要があるまで、より小さなMD DFTに順次分解します。^{[ 1 ]}

最も一般的な多次元FFTアルゴリズムは行列アルゴリズムであり、これは配列をまず一方のインデックスで変換し、次に他方のインデックスで変換することを意味します（FFTで詳細を参照） 。次に、基数2の直接2次元FFTが開発され^{[ 2 ]}、従来の行列アプローチと比較して乗算を25%削減できます。また、このアルゴリズムは矩形配列と任意の基数に拡張され^{[ 3 ]}、一般的なベクトル基数アルゴリズムとなっています。

ベクトル基数FFTアルゴリズムは、行ベクトルアルゴリズムと比較して、複素乗算の数を大幅に削減できます。たとえば、${\displaystyle N^{M}}$要素行列（M次元、各次元のサイズはN）の場合、基数2のベクトル基数FFTアルゴリズムの複素数の倍数は${\displaystyle {\frac {2^{M}-1}{2^{M}}}N^{M}\log _{2}N}$一方、行列アルゴリズムでは、${\displaystyle {\frac {MN^{M}}{2}}\log _{2}N}$一般的に、このアルゴリズムをより大きな基数や高次元配列に適用すると、乗算回数の削減効果がさらに大きくなります。^{[ 3 ]}

全体として、ベクトル基数アルゴリズムは、より優れたインデックス付けスキームにより、従来のDFTの構造的複雑さを大幅に軽減しますが、その代償として演算回数がわずかに増加します。そのため、このアルゴリズムは、画像処理^{[ 4 ]}や高速FFTプロセッサの設計^{[ 5 ]など、工学、科学、数学の多くのアプリケーションで広く使用されています。}

クーリー・テューキーFFTアルゴリズムと同様に、2次元ベクトル基数FFTは、通常の2次元DFTを「twiddle」係数を乗じたより小さなDFTの和に分解することによって導出されます。

時間間引き（DIT）アルゴリズムとは、時間領域に基づいて分解を行うアルゴリズムのことである。${\displaystyle x}$詳しくは、Cooley–Tukey FFTアルゴリズムを参照してください。

2次元DFTは次のように定義されると仮定します。

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

どこ${\displaystyle k_{1}=0,\dots ,N_{1}-1}$、 そして${\displaystyle k_{2}=0,\dots ,N_{2}-1}$、 そして${\displaystyle x[n_{1},n_{2}]}$は${\displaystyle N_{1}\times N_{2}}$行列、そして${\displaystyle W_{N}=\exp(-j2\pi /N)}$。

簡略化のため、次のように仮定しましょう。${\displaystyle N_{1}=N_{2}=N}$、基数-${\displaystyle (r\times r)}$は、${\displaystyle N/r}$整数です。

変数変換を用いる：

• ${\displaystyle n_{i}=rp_{i}+q_{i}}$、 どこ${\displaystyle p_{i}=0,\ldots ,(N/r)-1;q_{i}=0,\ldots ,r-1;}$
• ${\displaystyle k_{i}=u_{i}+v_{i}N/r}$、 どこ${\displaystyle u_{i}=0,\ldots ,(N/r)-1;v_{i}=0,\ldots ,r-1;}$

どこ${\displaystyle i=1}$または${\displaystyle 2}$すると、2次元DFTは次のように記述できます。^{[ 6 ]}

${\displaystyle X(u_{1}+v_{1}N/r,u_{2}+v_{2}N/r)=\sum _{q_{1}=0}^{r-1}\sum _{q_{2}=0}^{r-1}\left[\sum _{p_{1}=0}^{N/r-1}\sum _{p_{2}=0}^{N/r-1}x[rp_{1}+q_{1},rp_{2}+q_{2}]W_{N/r}^{p_{1}u_{1}}W_{N/r}^{p_{2}u_{2}}\right]\cdot W_{N}^{q_{1}u_{1}+q_{2}u_{2}}W_{r}^{q_{1}v_{1}}W_{r}^{q_{2}v_{2}},}$

上記の式は、2次元DIT基数の基本構造を定義します。${\displaystyle (r\times r)}$「バタフライ」。（クーリー・テューキーFFTアルゴリズムにおける1次元「バタフライ」を参照）

いつ${\displaystyle r=2}$、この方程式は4つの総和に分解でき、次のようになります。^{[ 1 ]}

${\displaystyle X(k_{1},k_{2})=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 0\leq k_{1},k_{2}<{\frac {N}{2}}}$、

どこ${\displaystyle S_{ij}(k_{1},k_{2})=\sum _{n_{1}=0}^{N/2-1}\sum _{n_{2}=0}^{N/2-1}x[2n_{1}+i,2n_{2}+j]\cdot W_{N/2}^{n_{1}k_{1}}W_{N/2}^{n_{2}k_{2}}}$。

の${\displaystyle S_{ij}}$と見なすことができる${\displaystyle N/2}$次元DFT、それぞれ元のサンプルのサブセットに対して：

• ${\displaystyle S_{00}}$これらのサンプルに対する DFT は${\displaystyle x}$両方${\displaystyle n_{1}}$そして${\displaystyle n_{2}}$等しい。
• ${\displaystyle S_{01}}$は、サンプルに対する DFT であり、${\displaystyle n_{1}}$は均等で${\displaystyle n_{2}}$奇妙だ。
• ${\displaystyle S_{10}}$は、サンプルに対する DFT であり、${\displaystyle n_{1}}$奇妙で${\displaystyle n_{2}}$偶数である。
• ${\displaystyle S_{11}}$は、両方のサンプルに対する DFT です。${\displaystyle n_{1}}$そして${\displaystyle n_{2}}$奇妙だ。

複素指数関数の周期性のおかげで、次の追加の恒等式が得られます。${\displaystyle 0\leq k_{1},k_{2}<{\frac {N}{2}}}$:

• ${\displaystyle X{\biggl (}k_{1}+{\frac {N}{2}},k_{2}{\biggr )}=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{\biggl (}k_{1},k_{2}+{\frac {N}{2}}{\biggr )}=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{\biggl (}k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}{\biggr )}=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}}}$。

同様に、周波数間引き（DIF、サンデ・テューキーアルゴリズムとも呼ばれる）アルゴリズムは、周波数領域に基づいて分解が行われることを意味する。${\displaystyle X}$詳しくは、Cooley–Tukey FFTアルゴリズムを参照してください。

変数変換を用いる：

• ${\displaystyle n_{i}=p_{i}+q_{i}N/r}$、 どこ${\displaystyle p_{i}=0,\ldots ,(N/r)-1;q_{i}=0,\ldots ,r-1;}$
• ${\displaystyle k_{i}=ru_{i}+v_{i}}$、 どこ${\displaystyle u_{i}=0,\ldots ,(N/r)-1;v_{i}=0,\ldots ,r-1;}$

どこ${\displaystyle i=1}$または${\displaystyle 2}$、そしてDFT方程式は次のように書くことができる：^{[ 6 ]}

${\displaystyle X(ru_{1}+v_{1},ru_{2}+v_{2})=\sum _{p_{1}=0}^{N/r-1}\sum _{p_{2}=0}^{N/r-1}\left[\sum _{q_{1}=0}^{r-1}\sum _{q_{2}=0}^{r-1}x[p_{1}+q_{1}N/r,p_{2}+q_{2}N/r]W_{r}^{q_{1}v_{1}}W_{r}^{q_{2}v_{2}}\right]\cdot W_{N}^{p_{1}v_{1}+p_{2}v_{2}}W_{N/r}^{p_{1}u_{1}}W_{N/r}^{p_{2}u_{2}},}$

分割基数FFTアルゴリズムは、1次元DFTに有用な方法であることが証明されています。そして、この方法はベクトル基数FFTに適用され、分割ベクトル基数FFTが得られています。^{[ 6 ] [ 7 ]}

従来の2次元ベクトル基数アルゴリズムでは、インデックスを分解します。${\displaystyle k_{1},k_{2}}$4つのグループに分けます。

${\displaystyle {\begin{array}{lcl}X(2k_{1},2k_{2})&:&{\text{even-even}}\\X(2k_{1},2k_{2}+1)&:&{\text{even-odd}}\\X(2k_{1}+1,2k_{2})&:&{\text{odd-even}}\\X(2k_{1}+1,2k_{2}+1)&:&{\text{odd-odd}}\end{array}}}$

分割ベクトル基数アルゴリズムにより、最初の3つのグループは変更されず、4番目の奇数-奇数グループはさらに4つのサブグループに分解され、合計7つのグループになります。

${\displaystyle {\begin{array}{lcl}X(2k_{1},2k_{2})&:&{\text{even-even}}\\X(2k_{1},2k_{2}+1)&:&{\text{even-odd}}\\X(2k_{1}+1,2k_{2})&:&{\text{odd-even}}\\X(4k_{1}+1,4k_{2}+1)&:&{\text{odd-odd}}\\X(4k_{1}+1,4k_{2}+3)&:&{\text{odd-odd}}\\X(4k_{1}+3,4k_{2}+1)&:&{\text{odd-odd}}\\X(4k_{1}+3,4k_{2}+3)&:&{\text{odd-odd}}\end{array}}}$

つまり、2次元DIT基数の第4項は${\displaystyle (2\times 2)}$方程式、${\displaystyle S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$こうなります：^{[ 8 ]}

${\displaystyle A_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}+A_{13}(k_{1},k_{2})W_{N}^{k_{1}+3k_{2}}+A_{31}(k_{1},k_{2})W_{N}^{3k_{1}+k_{2}}+A_{33}(k_{1},k_{2})W_{N}^{3(k_{1}+k_{2})},}$

どこ${\displaystyle A_{ij}(k_{1},k_{2})=\sum _{n_{1}=0}^{N/4-1}\sum _{n_{2}=0}^{N/4-1}x[4n_{1}+i,4n_{2}+j]\cdot W_{N/4}^{n_{1}k_{1}}W_{N/4}^{n_{2}k_{2}}}$

2-DN by N DFTは、上記の分解を最終段階まで連続的に使用することによって得られる。

分割ベクトル基数アルゴリズムは、典型的なケースにおいて、複素乗算を約30%、複素加算をほぼ同数削減できることが示されています。${\displaystyle 1024\times 1024}$配列は、ベクトル基数アルゴリズムと比較されます。^{[ 7 ]}