Row-Column 法は,多次元の DFT を一次元 DFT の直積で計算する方法です. 通常多次元 FFT はこの方法をさします.
例えば,二次元 DFT
N1-1 N2-1 j1 k1 j2 k2 A = Σ Σ a W W k1, k2 j1=0 j2=0 j1, j2 N1 N2
は,次のように計算します.
N2-1 N1-1 j1 k1 j2 k2 A = Σ ( Σ a W ) W k1, k2 j2=0 j1=0 j1, j2 N1 N2
すなわち,
N1-1 j1 k1 t = Σ a W k1, j2 j1=0 j1, j2 N1 N2-1 j2 k2 A = Σ t W k1, k2 j2=0 k1, j2 N2
のようにして,まず長さ N1 の DFT を N2 回行い,次に長さ N2 の DFT を N1 回行って計算します.要するに,a を行列とみなして,列方向に対して 一次元 DFT を行い,次に行方向に対して行うという方法です.当然, この演算の順序は交換できます.
次に,二次元の Row-Column 法のルーチン例を示します.
リスト3.1-1. Row-Column 法による 2D-FFT |
---|
/* n1 x n2 二次元 DFT : F[k1][k2]=Σ_j1=0^n1-1 Σ_j2=0^n2-1 a[j1][a2] * exp(±2*pi*i*j1*k1/n1) * exp(±2*pi*i*j2*k2/n2) を計算する. n1, n2 はデータ数で 2 の整数乗, flag は指数部の符号で ±1, tmpr[0...n1-1], tmpi[0...n1-1] は作業領域. */ #include <math.h> void fft2d(int n1, int n2, int flag, double **ar, double **ai, double tmpr[], double tmpi[]) { void fft(int n, double theta, double ar[], double ai[]); int j1, j2; double pi; pi = 4 * atan(1.0); /* ---- FFT of the rows ---- */ for (j1 = 0; j1 < n1; j1++) { fft(n2, flag * 2 * pi / n2, ar[j1], ai[j1]); } /* ---- FFT of the columns ---- */ for (j2 = 0; j2 < n2; j2++) { for (j1 = 0; j1 < n1; j1++) { tmpr[j1] = ar[j1][j2]; tmpi[j1] = ai[j1][j2]; } fft(n1, flag * 2 * pi / n1, tmpr, tmpi); for (j1 = 0; j1 < n1; j1++) { ar[j1][j2] = tmpr[j1]; ai[j1][j2] = tmpi[j1]; } } } |
このルーチンは,前に示した一次元の FFT を呼び出します.この ルーチンは Row-Column 法の一例に過ぎません.たとえば,配列の転置を 行うことで,作業用の配列は省くことが可能です.また,一次元 FFT ルーチンを修正して,二次元配列の行または列方向に対して変換を行う ようにすることもできます.このときも作業用の配列は省くことができます. 一般にこれらの修正は,ハードウエアの特性を十分考慮して行います.