ares@alessia.dei.unipd.it (Nicola Catacchio 259126) (05/20/91)
I repost my fft version again, because the first time i posted
a listing with some program undocumented in it.Those progs was some attempt
to make tthe program run faster on real sequences, but I couldn't get
any result.
The above is a reply to a reader that asked me some explanation
about the program and the fft .
I'm sorry, but there aren't so many answers to give: the fft is
an acronym to indicate a specific algorithm to perform dft, that is a
VERY particular caseof the Fourier transform.
The algorithm derived directly from the Fourier integal is too
slow and inefficient, so the fft algorithm is universally applied.
The program 'PLOT' shows the ABS value of each element in the
vector output of FFT. It is necessary to perform the ABS, infact the
algorithm gives a complex vector as output.
What does it means? This vector is a set of ordered samples of
the continuous fourier transform: The dft operate only on periodic functions
defined on discrete domains.The function must be seen on a period and
sampled. The more you increase the number of samples and the interval on
which is sampled the more you can take an approximation of the continuous
case.
An example could be :
Take a set of samples of the function 'IFTE(X,SIN(X)/X,1)' on a interval
large enough, i.e.
2: 'IFTE(X,SIN(X)/X,1)'
1: { X -20 20 }
press [SAMP]
take a set of samples of its fourier transform: [FFT]
then,to to make a representation, perform the ABS value of each element:[ABSV]
take a plot: [PLOT]
The result will be an approximation of a function RECT, that is
diffrent from zero only in an interval centered in 0.
Don't forget that this is a representation of a periodic function:
the more you increase sampling points, the greater will become the period
width. Dually, the more you increase the width of the sampling interval,
the better is the definition you get in the calculus of the fourier
tranform.
|------------------------------------------------------------------------------|
|Nicola Catacchio |E-mail: ares@alessia.unipd.it |
|Universita' di Padova |mail : Cannaregio 4389, Venezia, Italy |
| |phone#: 041/5222516 |
|------------------------------------------------------------------------------|
%%HP: T(3)A(R)F(.);
DIR
SAMP
\<< EVAL 3 PICK 3
PICK SWAP - n / \-> F
A B X S
\<< A X STO 1 n
START F
EVAL S X STO+
NEXT n
\->ARRY
\>>
\>>
n 64
ABSV
\<< OBJ\-> EVAL \-> N
\<< 1 N
START N
ROLL C\->R SQ SWAP SQ
+
NEXT N
\->ARRY
\>>
\>>
PLOT
\<< DUP OBJ\-> EVAL
\-> N
\<< 1 N 2 /
START N
ROLL
NEXT { N 1
} \->ARRY STO\GS
BARPLOT GRAPH {
PPAR \GSPAR \GSDAT PICT
} PURGE
\>>
\>>
IFFT
\<< OBJ\-> EVAL \-> N
\<< 2 N 1 -
FOR I I
ROLL
NEXT N IBIT
DTEM \->ARRY N /
\>>
\>>
FFT
\<< OBJ\-> 1 GET
IBIT DTEM \->ARRY
\>>
DTEM
\<< 1 OVER \-> H N
\<< -1 1 ROT LN
2 LN /
START 1 N 2
+ DUP H - 1 +
FOR J J 3
FOR I I
H - ROLL OVER * I
ROLL SWAP DUP2 -
ROT ROT + I ROLLD I
H - ROLLD H DUP +
NEG
STEP
OVER * -1
STEP DROP
H DUP + 'H' STO
CONJ \v/ CONJ
NEXT DROP N
\>>
\>>
IBIT
\<<
IF DUP 2 >
THEN DUP 2 /
DUP \-> N
\<< 1 + 3 ROT
FOR I
IF DUP
I 1 - >
THEN I
ROLL OVER 1 + ROLLD
DUP ROLL I ROLLD
END N
SWAP
WHILE
DUP2 <
REPEAT
OVER - SWAP 2 /
SWAP
END +
NEXT
\>>
END
\>>
END