Row-Column 法は，多次元の DFT を一次元 DFT の直積で計算する方法です． 通常多次元 FFT はこの方法をさします．
例えば，二次元 DFT
N1-1 N2-1 j1 k1 j2 k2
Ａ ＝ Σ Σ ａ Ｗ Ｗ
k1, k2 j1=0 j2=0 j1, j2 N1 N2
は，次のように計算します．
N2-1 N1-1 j1 k1 j2 k2
Ａ ＝ Σ （ Σ ａ Ｗ ） Ｗ
k1, k2 j2=0 j1=0 j1, j2 N1 N2
すなわち，
N1-1 j1 k1
ｔ ＝ Σ ａ Ｗ
k1, j2 j1=0 j1, j2 N1
N2-1 j2 k2
Ａ ＝ Σ ｔ Ｗ
k1, k2 j2=0 k1, j2 N2
のようにして，まず長さ N1 の DFT を N2 回行い，次に長さ N2 の DFT を N1 回行って計算します．要するに，ａ を行列とみなして，列方向に対して 一次元 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 ルーチンを修正して，二次元配列の行または列方向に対して変換を行う ようにすることもできます．このときも作業用の配列は省くことができます． 一般にこれらの修正は，ハードウエアの特性を十分考慮して行います．