**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:

"An Interactive Guide To The Fourier Transform" Better Explained. Retrieved December 9, 2018. https://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/

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.