実数および対称的な入力への最適化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/08 05:20 UTC 版)
「高速フーリエ変換」の記事における「実数および対称的な入力への最適化」の解説
多くの応用において、FFTに対する入力データは実数の列(実入力)であり、このとき変換された出力の列は次の対称性を満たす（ は複素共役）： F ( − t ) = F ( t ) ¯ . {\displaystyle F(-t)={\overline {F(t)}}.} そこで、多くの効率的なFFTアルゴリズム は入力データが実数であることを前提に設計されている。 入力データが実数の場合の効率化の手段としては、次のようなものがある。 クーリー-テューキー型アルゴリズムなど典型的なアルゴリズムを利用して、時間とメモリーの両方のコストを低減する。 入力データが偶数の長さのフーリエ係数はその半分の長さの複素フーリエ係数として表現できる（出力の実数/虚数成分は、それぞれ入力の偶関数/奇関数成分に対応する）ことを利用する。 かつては実数の入力データに対するフーリエ係数を求めるのには、実数計算だけで行える離散ハートリー変換（英語版） (discrete Hartley transform, DHT)を用いると効率的であろうと思われていた。しかしその後に、最適化された離散フーリエ変換 (discrete Fourier transform, DFT) アルゴリズムの方が、離散ハートリー変換アルゴリズムに比べて必要な演算回数が少ないということが判明した。また当初は、実数入力に対してブルーン (Bruun) FFT アルゴリズムは有利であると云われていたが、その後そうではないことが判った。 また、偶奇の対称性を持つ実入力の場合には、DFTはDCTやDST（英語版）となるので、演算と記憶に関してほぼ2倍の効率化が得られる。よって、そのような場合にはDFTのアルゴリズムをそのまま適用するよりも、DCTやDSTを適用してフーリエ係数を求める方が効率的である。
※この「実数および対称的な入力への最適化」の解説は、「高速フーリエ変換」の解説の一部です。
「実数および対称的な入力への最適化」を含む「高速フーリエ変換」の記事については、「高速フーリエ変換」の概要を参照ください。
- 実数および対称的な入力への最適化のページへのリンク
