1

I'm currently studying DFT and FFT and we were given this simple question: se the recursive FFT to compute the DFT of this polynomial of third degree: -1 + 4x + 3x^2.

So, I'm considering this algorithm:
enter image description here

How does this recursion work? Is the for loop positioned at the end of all the recursion calls? Or every time y goes back to y^0 and y^1? Can someone guide me? Of course, not all the steps, just some examples? Thank you so much in advance!

Vitality
  • 20,705
  • 4
  • 108
  • 146
user2637293
  • 333
  • 1
  • 5
  • 17
  • look here http://stackoverflow.com/a/26355569/2521214 go to the fast agoritms bullet there and read also both two links in that sections – Spektre Jan 28 '15 at 22:01

3 Answers3

1

The recursive implementation of the radix-2 Decimation In Frequency algorithm can be understood using the following two figures. The first one refers to pushing the stack phase, while the second one illustrates the popping the stack phase.

enter image description here

enter image description here

In particular, the two figures illustrate the following Matlab implementation:

% --- Radix-2 Decimation In Frequency - Iterative approach

function y = radix2_DIF_Recursive(x)

global sumCount mulCount

N = length(x);
phasor = exp(-2 * pi * 1i / N) .^ (0 : N / 2 - 1);

if N == 1
    y = x;
else
    y_top       = radix2_DIF_Recursive(x(1: 2 : (N - 1)));
    y_bottom    = radix2_DIF_Recursive(x(2 : 2 : N));
    z           = phasor .* y_bottom;
    y           = [y_top + z, y_top - z];
    sumCount    = sumCount + 6 * (N / 2);
    mulCount    = mulCount + 4 * (N / 2);
end

Use the following main script to test it:

% --- Radix-2 Decimation In Frequency - Iterative approach

clear all
close all
clc

global sumCount mulCount

N = 32;

x = randn(1, N);

sumCount = 0;
mulCount = 0;

tic
xhat = radix2_DIF_Recursive(x);
timeCooleyTukey = toc;

tic
xhatcheck = fft(x);
timeFFTW = toc;

rms = 100 * sqrt(sum(sum(abs(xhat - xhatcheck).^2)) / sum(sum(abs(xhat).^2)));

fprintf('Time Cooley-Tukey = %f; \t Time FFTW = %f\n\n', timeCooleyTukey, timeFFTW);
fprintf('Theoretical multiplications count \t = %i; \t Actual multiplications count \t = %i\n', ...
         2 * N * log2(N), mulCount);
fprintf('Theoretical additions count \t\t = %i; \t Actual additions count \t\t = %i\n\n', ...
         3 * N * log2(N), sumCount);
fprintf('Root mean square with FFTW implementation = %.10e\n', rms);

The above recursive implementation is the counterpart of the iterative implementation of the radix-2 Decimation In Frequency at Implementation of the Discrete Fourier Transform - FFT. Please, note that the present recursive one does not require any reverse bit ordering, neither of the input nor of the output sequences.

Community
  • 1
  • 1
Vitality
  • 20,705
  • 4
  • 108
  • 146
0

Essentially, Recursive-FFT is working its way backwards through a, starting at (a0,a1,a2,...an).

At each subsequent recursive call to Recursive-FFT a subset of a is used, thus a in each newly called Recursive-FFT becomes ever smaller until its length as assigned to n is 1, at which point the last call to Recursive-FFT returns to the previous one.

It is not until Recursive-FFT has returned, when n = 1, to its caller, that the last part of the routine, the for-loop, is executed, at which point y is returned to either the previous Recursive-FFT, or the original caller (code that is not Recursive-FFT) when no more calls from Recursive-FFT exist on the stack.

Jool
  • 1,706
  • 16
  • 14
0

Form the vector a = [-1, 4, 3, 0], which has a length of n=2=2^2.

Then (using a piece of paper) go through the steps of the algorithm: splitting the sequence into even/odd vectors etc. Have fun (or choose another subject for your studies).

By the way: the polynomial is only second degree, not third as you mention!?!

Jens
  • 409
  • 4
  • 11