I would like to optimise FFT algorithm by only using a FFT of size $N/2$ to transform a real sequence of length $N$. There are already many questions and many excellent answers on the matter (here for example).
I've been trying to follow the linked answer to implement the splitting algorithm in Matlab and I checked against the standard FFT Matlab routine. I found a shift of 1 sample in the spectrum (sine input) and a weird peak at a (seems to me) random frequency. I would really appreciate a review of my code or simply a hint to debug the problem.
As a side note, I'm trying this route because I need a memory efficient FFT for an embedded device.
close all; clear all; clc; %% Parameters sample_rate = 50; % Hz frequency = 10; % Hz N = 256; p = 1:N; t = (p-1) / sample_rate; f = sample_rate*(0:(N/2 -1))/N; % frequency vector %% Generate real sequence data = sin(2*pi*p*frequency/sample_rate); figure(); plot(t, data); title('Input'); %% Split even-odd % Even indeces are odd because % Matlab starts indexing from 1 idx_even = 1:2:N; idx_odd = idx_even+1; data_even = data(idx_even); data_odd = data(idx_odd); data_cpx = complex(data_even, data_odd); %% Perform FFT of length N/2 X = fft(data_cpx, N/2); %% Perform Butterfly k = 0:(N/2 -1); W = exp(-2*pi*1i*k/N); X_even = 0.5*(X(k+1) + conj(X(N/2 - k))); X_odd = -1i*0.5*(X(k+1) - conj(X(N/2 - k))); G = X_even + W .* X_odd; %% Perform FFT of length N to check results X_N = fft(data, N); %% Plot figure(); plot(f, real(X_N(1:128))); hold on plot(f, real(G)); title('Real'); figure(); plot(f, imag(X_N(1:128))); hold on plot(f, imag(G)); title('Imag'); figure(); plot(f, abs(X_N(1:128))); hold on plot(f, abs(G)); title('Mag'); figure(); plot(f, angle(X_N(1:128))); hold on plot(f, angle(G)); title('Phase');