# 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:

1. Load 2D array by rows
2. Transform each column
3. Twiddle each element
4. Transform each row
5. 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);