write the fft function without using the built in fft function in matlab

To write the FFT function without using the built-in FFT function in Matlab, we can use the Cooley-Tukey algorithm. The Cooley-Tukey algorithm is a popular and efficient method for computing the FFT.

Here's an implementation of the FFT function in Matlab using the Cooley-Tukey algorithm:

main.m
function y = myFFT(x)

% Get input size
N = length(x);

% Compute recursion exit condition
if N == 1
    y = x;
    return;
end

% Split input sequence into even and odd parts
x_even = x(1:2:N);
x_odd = x(2:2:N);

% Compute FFT of even and odd parts recursively
y_even = myFFT(x_even);
y_odd = myFFT(x_odd);

% Compute twiddle factors
w = exp(-1i*2*pi/N*(0:N/2-1));

% Compute FFT of input sequence
y_top = y_even + w .* y_odd;
y_bottom = y_even - w .* y_odd;

% Assemble output sequence
y = [y_top, y_bottom];
end
515 chars
30 lines

This function takes an input vector x and computes its FFT using the Cooley-Tukey algorithm. The function recursively splits the input into even and odd parts, computes the FFT of each part, and then combines the results using twiddle factors.

Note that this implementation assumes that the length of the input sequence is a power of 2. A more general implementation would need to handle sequences of arbitrary length.