例えば、1秒間に1024個の音声信号をサンプリングし、それを InR[0]～InR[1023]に格納したとします。これの周波数5Hz成分の強度は、5HzのCOS波、SIN波と掛けあわせた値の和、つまり N=1024:I=5:DTH=2*PI()*I/N:TH=0 FOR J=0 TO N-1 INC OutR[I],InR[J]*COS(TH) INC OutI[I],InR[J]*SIN(TH) INC TH,DTH NEXT と計算できます。結果は、OutR[5]とOutI[5]に入ります。 これをI=0(Hz)から512(Hz)まで全て求めるのが離散フーリエ変換です。ただ、このままだと掛け算が約1024*512*2回ととても多くなるため、途中の計算値をうまく使いまわし、掛け算の回数を1024*10回ととても少なく抑える工夫をしたのが高速フーリエ変換(FFT)です。