gpt-4o-2024-11-20· OpenAI
WildChat-4.8M (AI2)
can you create for me a complete FFT algorithm in both python Language and Matlab
- User
can you create for me a complete FFT algorithm in both python Language and Matlab
- Assistant
Certainly! Below, I'll provide a Fast Fourier Transform (FFT) algorithm in Python and MATLAB.
1. Python FFT Implementation
import numpy as np def fft(x): """ Compute the Fast Fourier Transform (FFT) of a 1D numpy array. Args: x (np.array): Input signal (assumed a power-of-2 length). Returns: np.array: FFT of the input signal. """ N = len(x) if N <= 1: # Base case: if the array has one element return x if N % 2 > 0: raise ValueError("Size of x must be a power of 2.") # Split the array into even and odd components even = fft(x[::2]) odd = fft(x[1::2]) # Combine T = [np.exp(-2j * np.pi * k / N) * odd[k] for k in range(N // 2)] return np.array([even[k] + T[k] for k in range(N // 2)] + [even[k] - T[k] for k in range(N // 2)]) # Example Usage if __name__ == "__main__": # Sample input signal (length must be a power of 2) x = np.array([0, 1, 2, 3, 4, 5, 6, 7]) fft_result = fft(x) print("FFT Result:") print(fft_result) # Compare with numpy's built-in FFT function print("\nNumpy FFT (for verification):") print(np.fft.fft(x))
2. MATLAB FFT Implementation
function X = fft_algorithm(x) % FFT_ALGORITHM Compute the Fast Fourier Transform (FFT) of a 1D array. % X = FFT_ALGORITHM(x) takes a vector x (length must be a power of 2) % and returns its FFT. % % Args: % x : Input signal (1D array, power of 2 length) % % Returns: % X : FFT of the input signal N = length(x); if N <= 1 X = x; % Base case return; end if mod(N, 2) ~= 0 error('Length of x must be a power of 2'); end % Split into even and odd indexed parts x_even = x(1:2:end); x_odd = x(2:2:end); % Recursively calculate FFT X_even = fft_algorithm(x_even); X_odd = fft_algorithm(x_odd); % Combine the sub-results X = zeros(1, N); for k = 1:(N / 2) t = exp(-2j * pi * (k - 1) / N) * X_odd(k); X(k) = X_even(k) + t; X(k + N/2) = X_even(k) - t; end end % Example Usage x = [0, 1, 2, 3, 4, 5, 6, 7]; % Input signal, ensure length is power of 2 fft_result = fft_algorithm(x); disp('FFT Result:'); disp(fft_result); % Compare with built-in FFT for verification disp('MATLAB FFT (for verification):'); disp(fft(x));
Details on the Implementation
-
Base Case:
- If the input signal has length 1, simply return the value since the FFT of a single point is the point itself.
-
Divide and Conquer:
- The input array is divided into an even-indexed and odd-indexed sub-array.
-
Recursion:
- Recursively compute the FFT of both sub-arrays.
-
Combining Results:
- The FFT result is constructed by combining the results of the even and odd components using
T = exp(-2*pi*i*k/N) * odd.
- The FFT result is constructed by combining the results of the even and odd components using
Verification
Both codes include comparisons to their respective built-in FFT functions:
- In Python,
np.fft.fft() - In MATLAB,
fft()
This is to ensure the correctness of the implementation. Both implementations assume the input length is a power of 2, complying with the Cooley-Tukey FFT algorithm's assumption.
Let me know if you need further clarifications or extensions of the algorithm!
-