TI-84 Plus Fast Fourier Transform
HAPPY NEW YEAR!
Introduction
The program FFT1 performs the fast Fourier transform of discrete data points named in List 1 (small x, signal at time points) to List 2 (big X, frequency), using the formula:
X_k = ∑( x_n * e^(-i*2*π*k*m)/n from m = 0 to n - 1)
For the set of n signals.
The program IFFT1, the Inverse Fast Fourier Transform, reverses the process (big X to small x, List 2 to List 1).
x_k = 1/n * ∑( x_n * e^(i*2*π*k*m)/n from m = 0 to n - 1)
TI-84 Plus Program FFT1
"FFT VERSION 1"
"EWS 2018-12-09"
Input "SMALL X LIST:",L₁
"SETUP"
dim(L₁)→N
L₁→L₂
a+bi
Radian
"LOOP"
For(M,0,N-1)
0→T
For(K,0,N-1)
T+L₁(K+1)*e^(-2*π*i*K*M/N)→T
End
T→L₂(M+1)
End
Pause L₂
TI-84 Plus Program IFFT1
"IFFT VERSION 1"
"EWS 2018-12-09"
Input "BIG X LIST:",L₂
"SETUP"
dim(L₂)→N
L₂→L₁
a+bi
Radian
"LOOP"
For(M,0,N-1)
0→T
For(K,0,N-1)
T+L₂(K+1)*e^(2*π*i*K*M/N)→T
End
T/N→T
T→L₁(M+1)
End
Pause L₁
Example
FFT Example:
L1 = {2i, 1+i, 3}
Result (Fix 4): {4.0000+3.0000*i, -1.1340+3.2321*i, -2.8660-0.2321*i}
Inverse FFT Example:
L2 = {0.5, -0.7i, 0.9+0.3i}
Result (Fix 4): {0.4667-0.1333*i, 0.3053-0.1931*i, -0.2720+0.3265*i}
Trigonometric Version
For calculators that do not handle complex numbers, here are the sample code that can handle FFT and IFFT. The techinque here is to use a pair of lists, one for the real parts, the other for imaginary parts. Example: {2, 3+3i, -2i} get split into {2, 3, 0} and {0, 3, -2}.
The following identities and calculation are used:
e^(i*θ) = cos θ + i * sin θ
(a + b*i)*e^(-i*θ)
= (a + b*i) * (cos θ - i * sin θ)
= a * cos θ + i * b * cos θ - i * a * sin θ + b * sin θ
= (a * cos θ + b * sin θ) + i * (b * cos θ - a * sin θ)
(a + b*i)*e^(i*θ)
= (a + b*i) * (cos θ + i * sin θ)
= a * cos θ + i * b * cos θ + i * a * sin θ - b * sin θ
= (a * cos θ - b * sin θ) + i * (b * cos θ + a * sin θ)
where θ = 2*π*m*k/n
TI-84 Plus Program FFT1
"FFT VERSION 2"
"EWS 2018-12-10"
Disp "SMALL X","L₁ + I*L₂"
Input "REAL: ",L₁
Input "IMAG: ",L₂
"SETUP"
dim(L₁)→N
L₁→L₃
L₂→L₄
Radian
"LOOP"
For(M,0,N-1)
0→S
0→T
For(K,0,N-1)
2*π*M*K/N→θ
S+L₁(K+1)*cos(θ)+L₂(K+1)*sin(θ)→S
T+L₂(K+1)*cos(θ)-L₁(K+1)*sin(θ)→T
End
S→L₃(M+1)
T→L₄(M+1)
End
Disp "REAL = L₃","IMAG = L₄"
TI-84 Plus Program IFFT1
"IFFT VERSION 2"
"EWS 2018-12-10"
Disp "BIG X","L₃ + I*L₄"
Input "REAL: ",L₃
Input "IMAG: ",L₄
"SETUP"
dim(L₃)→N
L₃→L₁
L₄→L₂
Radian
"LOOP"
For(M,0,N-1)
0→S
0→T
For(K,0,N-1)
2*π*M*K/N→θ
S+L₃(K+1)*cos(θ)-L₄(K+1)*sin(θ)→S
T+L₄(K+1)*cos(θ)+L₃(K+1)*sin(θ)→T
End
S/N→S
T/N→T
S→L₁(M+1)
T→L₂(M+1)
End
Disp "REAL = L₁","IMAG = L₂"
Source:
All original content copyright, © 2011-2018. Edward Shore. Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited. This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author. Please contact the author if you have questions.
