天文学辞典 | 天文に関する用語を3000語以上収録。専門家がわかりやすく解説します。

高速フーリエ変換

 

よみ方

こうそくふーりえへんかん

英 語

fast Fourier transform

説 明

クーリー(J.W. Cooley)とチューキー(J.W. Tukey)によって1965年によって見いだされた、有限区間の離散フーリエ変換を計算機を用いて高速に行う算法のこと。有限区間に等間隔にN個の点を考え、そこでの関数の値がf_kk=1, 2, \cdots, N)で与えられているとき、離散フーリエ変換は
 \hat{f}_j \equiv \sum_{k=1}^N f_k\exp(-2\pi i j k /N) j=1,2,\cdots, N
で与えられる(iは虚数単位)。容易にわかるように、単純にこれを得るために必要な計算量はN^2に比例するが、高速フーリエ変換は、Nが2のべき乗で表されるとき、N \log_2 Nに比例する計算量で求めることができる算法である。

2018年04月23日更新

関連画像