1
$\begingroup$

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: For example

Anyone know what I am doing wrong?

$\endgroup$

1 Answer 1

1
$\begingroup$

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);
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.