こうそくふーりえへんかん
離散フーリエ変換(DFT)を、少ない演算で正確に計算するアルゴリズムの総称。N点のDFTを半分の大きさのDFTに次々に分けて共通の計算をまとめる方法(クーリー・テューキーのアルゴリズム)が代表的で、演算の回数は定義どおりの約 N² 回から約 N log₂N 回に減る。N = 1024 ならおよそ100分の1である。点数が2のべき乗のときに最も簡単な形になるが、ほかの点数に使える方法もある。スペクトルの解析のほか、OFDMの変調・復調や、長い畳み込みの高速な計算にも使われる。
「高速フーリエ変換(FFT)」は、2分野の4問の練習問題に出てきます(デジタル信号処理の基礎, 無線通信の基礎など)。
この用語の分野: デジタル信号処理の基礎
N点のDFTを、偶数番目と奇数番目のサンプルの2つの N/2 点のDFTに分けると、回転因子 e^(−j2πk/N) を掛けて足し引きするだけで元の結果を組み立てられます。これをくり返すと log₂N 段に分かれ、各段の演算はおよそ N 回なので、全体は N log₂N 程度になります。この足し引きの組は、その形から「バタフライ演算」と呼ばれます。
比は N/log₂N で、N = 1024 なら 1024 ÷ 10 = 102.4、N = 65536 なら 65536 ÷ 16 = 4096 です。点数が大きいほど効果が大きく、実時間のスペクトル表示や、通信の受信機のように多くのDFTを続けて計算する用途には欠かせません。
2つの系列の畳み込みは、周波数の側では掛け算になります。そこで、両方をFFTで変換して掛け合わせ、逆FFTで戻すと、長いFIRフィルタの畳み込みを直接計算するより少ない演算で求められます。ただし、DFTどうしの掛け算は巡回畳み込みに当たるので、ゼロパディングで長さをそろえて、端の回り込みを防ぐ必要があります。
正解：B. 約100分の1
N² = 1024² ≈ 105万、N log₂N = 1024 × 10 = 10240 で、比は N/log₂N = 1024 ÷ 10 = 102.4、つまり約100分の1です。N が大きいほど差は広がり、例えば N = 65536 では約4096分の1になります。FFTは、DFTを半分の大きさのDFTに次々に分けて、共通の計算をまとめることで演算を減らします。
いいえ。2のべき乗のときが最も簡単で速いことが多いのですが、3や5などの因数に分ける混合基数のFFTや、素数の点数を扱う方法もあり、一般的なライブラリは任意の点数を計算できます。2のべき乗にそろえたい場合は、ゼロパディングで点数を増やすこともあります。
同じ値を計算する方法なので、丸め誤差を除いて一致します。FFTは近似ではなく、計算の順序を工夫して、同じ結果を速く得るアルゴリズムです。
FFTは、DFTを半分の大きさのDFTに次々に分けて、共通の計算をまとめることで演算を減らします。
N点のDFTを定義どおりに計算すると約 N² 回、FFT(高速フーリエ変換)では約 N log₂N 回の演算で済むとす…ゼロパディングは、ピークの位置を読み取りやすくしたり、FFTのために点数を2のべき乗にそろえたりするのに使われます。
256点の信号のあとに0を768個付け足して(ゼロパディング)、1024点のDFTを計算した。256点のままDFTを計…送信側は逆高速フーリエ変換(IFFT)、受信側は高速フーリエ変換(FFT)で効率よく処理でき、無線LAN、4G LTE、5G NR、地上デジタル放送などで使われています。
OFDM(直交周波数分割多重)の説明として、適切なものはどれか。さらに、CPがシンボルの末尾のコピーなので、遅れて届いた電波もFFTで処理する区間の中では周期的な信号に見え、サブキャリアどうしの直交性が保たれます。
OFDMで、各シンボルの末尾の一部をコピーしてシンボルの先頭に付け加えるサイクリックプレフィックス(CP)の主な目的は…Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。
OFDM(直交周波数分割多重) 周波数分解能 IIRフィルタ 移動平均フィルタ インパルス応答 FIRフィルタ 群遅延 差分方程式 スペクトル漏れ z変換