実データ1次元離散フーリエ変換 One-Dimensioanal DFTs of Real Data


 実際の利用上、多くの場合、入力データin[i]は実数で、その場合DFTの出力は、”エルミート冗長性”を満たします。すなわち、out[i]はout[n-i]の共役となります。この性質の利点を生かすと、大雑把にいえば、スピードの向上と、メモリ節約を図ることができます

 このスピード向上と、メモリ節約といった利点と引き換えに、ユーザーはFFTWの複素変換の簡易性を犠牲にしなければなりません。
 第1に、入出力の配列が異なるサイズ、型になります。入力がn個の実数だった場合、出力は(冗長でない形で)n/2+1個の複素数となります。また、入出力が等しい、in-place変換の場合、入力の配列にわずかに”パディング”(余白)を設ける必要があります。
 第2に、複素数から実数への逆変換は、デフォルトで、入力配列が変化してしまうという副作用があります。どちらの不便もユーザーに対して重大な問題は引き起こしませんが、十分意識することが重要です。

 この実データ変換のルーチンは、複素変換のものとほとんど同じです。
すなわち、doubleまたは、fftw_complex型の配列のメモリを確保し(fftw_malloc推奨)、fftw_planを作成し、fftw_execute(plan)を必要な回数だけ実行し、fftw_destroy_plan(plan)によって、後処理をします(fftw_freeも)。
違いといえば、入力(または出力)がdouble型で、新しいプラン生成のルーチンがあるだけです。1次元では、

fftw_plan fftw_plan_dft_r2c_1d( int n, double *in, fftw_complex *out,
                                unsigned flags );
fftw_plan fftw_plan_dft_c2r_1d( int n, fftw_complex *in, double *out,
                                unsigned flags );

 となります。
それぞれ、実入力から複素エルミート出力(r2c)、複素エルミート入力から実出力(c2r)の変換です。複素離散フーリエ変換プランナーとは異なり、signの引数がありません。代わりに、r2c離散フーリエ変換は、常にFFTW_FORWARDで、c2rはFFTW_BACKWARDとします。(単精度/倍倍精度の、fftwfとfftwlに対しては、doubleをそれぞれfloattとlong doubleに置き換えてください)

 ここで、nは離散フーリエ変換の”論理”サイズで、必ずしも配列の物理的サイズではありません。詳しくいえば、実数(double)の配列はn個の要素を持ちますが、一方でfftw_complexは、n/2+1個(切り捨て)の要素となります。入出力が同じ、in-place変換では、inとoutが別名の同じ配列で、これは入出力の両者を格納できる大きさである必要があります。したがって、実配列は、実際のところ2*(n/2+1)個の要素を持ち、最初のn個以降は使用されないパディングとなります。
複素配列のk番目の要素は、対応する複素離散フーリエ変換のk番目の要素にきっかり等しくなります。また、すべての正のnがサポートされています。もっとも、小さな素数の積が最も効率がよく、最悪の場合でもO(nlogn)アルゴリズムとなります。

 上述の通り、c2r変換は、たとえ入出力が異なるout-of-place変換であっても、入力配列の値は変換前後で保持されません。これに対しては、必要であれば、FFTW_PRESERVE_INPUTオプションを、flagに設けることでこれを防ぐことができますが、残念なことにある程度パフォーマンスが低下します。このオプションは、現在は次の章の実データ多次元の離散フーリエ変換には対応していません。

 実データの離散フーリエ変換に慣れている読者なら、複素出力の、0番目(DC)とn/2番目(nが偶数のとき、ナイキスト周波数)の要素は、実数になることを思い出していただけるかと思います。いくつかの実装では、入出力の配列サイズをそろえるため、上記性質を利用し、ナイキスト周波数の要素をDCの虚部に格納することがあります。しかしながら、このような実装は高次の変換に対しては一般性がなく、メモリ節約は枝葉末節であるため、FFTWではサポートしません。

 1次元のr2cやc2r離散フーリエ変換の代替インターフェースとして、”r2r”というものがあります(2.5.1節 The Halfcomplex-format DFTを参照)。
これは、入力配列と同じ型、サイズの、"halfcomplex"形式の出力が用いられるものです。このインターフェースは、多次元変換に対しては大変便利というものではありませんが、よりよい性能を発揮することもしばしあります。
最終更新:2009年01月21日 20:20