2
$\begingroup$

I have to calculate a 48 point FFT using an N-point FFT library function which only supports lengths that are a power of 2.

Is it possible to calculate a 48-point FFT using a 32-point FFT and 16-point FFT? If not, what is the most efficient way of implementing a 48 point FFT?

$\endgroup$

2 Answers 2

6
$\begingroup$

If not, what is the most efficient way of implementing a 48 point FFT?

Three 16 point FFTs plus one set of 3 point "Butterflies".

Matlab example

%% Do a 48 point FFT, this is NOT efficient but shows the principle
n = 48;
nFFT = 16;
x0 = randn(n,1); % test vector
fx0 = fft(x0); % reference
x1 = reshape(x0,3,nFFT)'; % reshape into 3 N-16 vectors
fx1 = fft(x1);   % 3 FFTs 16 points each
fx2 = [fx1; fx1; fx1]; % periodic repetition for easy butterfly code
W = exp(-1i*2*pi*(0:n-1)'/n); % twiddle factor, N = 48
% execute a 3 point "butterfly"
fy = fx2(:,1) + fx2(:,2).*W + fx2(:,3).*W.^2;
% calculate and print error
d = (fy-fx0);
fprintf('Relative Error = %6.2fdB \n',20*log10(sum(abs(d))./sum(abs(fx0))));
$\endgroup$
6
  • $\begingroup$ don't you mean Three 16-point FFT one 32-point FFT? $\endgroup$
    – Ben
    Oct 18, 2021 at 14:23
  • $\begingroup$ There is no 32-point FFT. $\endgroup$
    – Hilmar
    Oct 18, 2021 at 14:50
  • 1
    $\begingroup$ @Ben, no he doesn't mean that, because it won't work. He means that you should follow three 16-point FFT's with a set of butterfly operations, each on three elements, to finish up the 48-point FFT. $\endgroup$
    – TimWescott
    Oct 18, 2021 at 15:10
  • $\begingroup$ @Hilmar: I feel it would be more clear to say "set of 3-point butterflies", or "3-point vector butterfly" -- the FFT newbie may not realize that you are prescribing one 3-point butterfly primitive to each of the elements in each of the three 16-point FFTs. $\endgroup$
    – TimWescott
    Oct 18, 2021 at 15:11
  • $\begingroup$ @TimWescott: done. Thanks for the suggestion $\endgroup$
    – Hilmar
    Oct 18, 2021 at 15:13
1
$\begingroup$

No, that's not possible. You can piece together a 48-point FFT from factors-of-48-FFTs, in your case from multiple 16-point FFTs using the radix-N method.

You can even use the Split-Radix Algorithm to piece together a 48-point FFT from 32 and 16 point FFTs – but it's not going to be

48-point FFT using a 32-point FFT and 16-point FFT

but

48-point FFT using multiple 32-point FFTs and multiple 16-point FFTs

However, in practice, you'll want to implement your 32-point FFT through Radix-2-combine 16-point FFTs, so this choice is just an "awkward" way of implementing the 48-FFT through 16-point-FFTs, anyway.

$\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.