FFT

出典: くみこみックス

FFT 【Fast Fourier Transform】

　離散フーリエ変換を高速に計算する手法を高速フーリエ変換（FFT）といいます．コンピュータでフーリエ変換を行うには，フーリエ変換を離散化した離散フーリエ変換（DFT）を実行する必要があります．しかし，DFTは元データがN点の場合，その計算量がN2に比例して増加してしまいます．FFTはDFTの周期性を利用することで演算の冗長性を省き，計算量をN log Nにまで減らすことができる手法です．

【出典】（株）アルティマ 技術統括部 一同，下馬場 朋禄，山際 伸一，横溝 憲治；システム開発者のためのFPGA用語集，Design Wave Magazine 2008年12月号 別冊付録，CQ出版社，2008年12月．