Cooley-Tukey Implementation of FFT in Matlab For my course I need to implement a 30 point Cooley-Tukey DFT by transforming it into a 5x6 matrix.

I have tried to implement using the following Matlab code:

clc; clf; close all; clear all;
N = 30;
rows = 5;
columns=6;
data = linspace(0, 2*pi, N);
data = sin(data)+0.1*sin(pi*data);
plot(data);
count=1;
matrix=(reshape(data, 6, 5))'; % Read in row wise
test = matrix;
%Perform column-wise dft
for x=1:columns
    matrix(:,x)=dft(matrix(:,x));
end
%Perform Twiddles
for x=1:columns
    for y=1:rows
        matrix(y,x)=matrix(y,x)*exp((-2*pi*y*x/N)*1i);
    end
end
%Perform FFT on rows
for y=1:rows
    matrix(y,:)=dft(matrix(y,:));
end
out=20*log10(abs(reshape(matrix,1,N)));
figure
subplot(211);
stem(out); title('Using cooley-tukey');
subplot(212);
stem(20*log10(abs(fft(data)))); title('Using fft');


Where dft is defined as:

function output = dft(input)
 n = length(input);
 output = zeros(size(input));
 for k = 0 : n - 1  % For each output element
   s = 0;
    for t = 0 : n - 1  % For each input element
     s = s + input(t + 1) * exp(-2i * pi * t * k / n);
   end
   output(k + 1) = s;
 end
end


The instructions that were in our lecture were:


Load 2D array by rows 
Transform each column 
Twiddle each element
Transform each row 
Unload 2D array by columns


Now it outputs some very different outputs:


Anyone know what I am doing wrong?
The problem is in the definition of the twiddle factors. Your indices go from 1 to columns and from 1 to rows, whereas the indices in the power of the exponential function should go from 0 to columns-1 and from 0 to rows-1. So with this line of code in the twiddle factor loop everything should be fine:

matrix(y,x)=matrix(y,x)*exp((-2*pi*(y-1)*(x-1)/N)*1i);