IMG_2451.jpeg

# MatDeck ## FFT ### Formula $y(j)=\sum_{k=1}^{N} x(k) w_{N}^{(k-1)(j-1)}$ $j= 1,2,3,...,N$ ### Variables * **y** is the complex vector of the FFT output * **x** is the complex vector of the FFT input * **N** is the size of the FFT * **$w_{N}=e^{(-j2\pi/N)}$** ### Description FFT (Fa...

# MatDeck ## FFT ### Formula $y(j)=\sum_{k=1}^{N} x(k) w_{N}^{(k-1)(j-1)}$ $j= 1,2,3,...,N$ ### Variables * **y** is the complex vector of the FFT output * **x** is the complex vector of the FFT input * **N** is the size of the FFT * **$w_{N}=e^{(-j2\pi/N)}$** ### Description FFT (Fast Fourier Transform) is an algorithm used to compute DFT (Discrete Fourier Transform). DFT is used to transform a function from its original domain (time or space) to a representation in the frequency domain. FFT is used in a wide range of applications, like signal processing and analyzing, solving partial differential equations, filtering, large integer multiplication etc. ### Example ``` X:=vector(1,2,3,4,5,6,7,8) Y:=FFT(X) ``` | Index | Real | Imaginary | | :---- | :--------- | :--------- | | 1 | 36 | 0 | | 2 | -4 | 9.65 | | 3 | -4 | 4 | | 4 | -4 | 1.65 | | 5 | -4 | 0 | | 6 | -4 | -1.65 | | 7 | -4 | -4 | | 8 | -4 | -9.65 | | | | | | Index | ABS | Argument | | 1 | 36 | 0 | | 2 | 10.44 | 1.97 | | 3 | 5.65 | 2.35 | | 4 | 4.31 | 2.74 | | 5 | 4 | 3.14 | | 6 | 4.31 | -2.74 | | 7 | 5.65 | -2.35 | | 8 | 10.44 | -1.97 | | | | | | Index | Power | | 1 | 1296 | | 2 | 109 | | 3 | 32 | | 4 | 18.6 | | 5 | 16 | | 6 | 18.6 | | 7 | 32 | | 8 | 109 | ### Errors * If the input is not a vector. * If the input vector contains non-numerical values. ### Complexity The complexity of the FFT algorithm is $O(N\log N)$, where N is the size of the input. ## IFFT ### Formula $x(j)=\frac{1}{N}\sum_{k=1}^{N} y(k) W_{N}^{-(k-1)(j-1)}$ $j= 1,2,3,...,N$ ### Variables * **x** is the complex vector of the IFFT output * **y** is the complex vector of the IFFT input * **N** is the size of the IFFT * **$w_{N}=e^{(-j2\pi/N)}$** ### Description IFFT (Inverse Fast Fourier Transform) is an algorithm used to compute IDFT (Inverse Discrete Fourier Transform). IDFT is used to transform a function from the frequency domain to its original domain (time or space). IFFT is the inverse operation of the FFT. ### Example ``` Y:=vector(1,2,3,4,5,6,7,8) X:=IFFT(Y) ``` | Index | Real | Imaginary | | :---- | :-------- | :-------- | | 1 | 4.5 | 0 | | 2 | -3.5 | 1.2 | | 3 | -3.5 | 0.5 | | 4 | -3.5 | 0.2 | | 5 | -3.5 | 0 | | 6 | -3.5 | -0.2 | | 7 | -3.5 | -0.5 | | 8 | -3.5 | -1.2 | | | | | | Index | ABS | Argument | | 1 | 4.5 | 0 | | 2 | 3.7 | 2.8 | | 3 | 3.5 | 2.9 | | 4 | 3.5 | 3 | | 5 | 3.5 | 3.1 | | 6 | 3.5 | -3 | | 7 | 3.5 | -2.6 | | 8 | 3.7 | -1.3 | | | | | | Index | Power | | 1 | 20 | | 2 | 14 | | 3 | 12 | | 4 | 12 | | 5 | 12 | | 6 | 12 | | 7 | 12 | | 8 | 14 | ### Errors * If the input is not a vector. * If the input vector contains non-numerical values. ### Complexity The complexity of the IFFT algorithm is $O(N\log N)$, where N is the size of the input.