Skip to content
TheChatArchiveThe Chat Archive
gpt-4o-2024-11-20· OpenAIAi2 WildChat-4.8M (AI2)

can you create for me a complete FFT algorithm in both python Language and Matlab

  1. User

    can you create for me a complete FFT algorithm in both python Language and Matlab

  2. 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

    1. Base Case:

      • If the input signal has length 1, simply return the value since the FFT of a single point is the point itself.
    2. Divide and Conquer:

      • The input array is divided into an even-indexed and odd-indexed sub-array.
    3. Recursion:

      • Recursively compute the FFT of both sub-arrays.
    4. 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.

    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!