0
$\begingroup$

I have been reading quite a bit about FFTs and I understand quite well the following:

  • radix 2 FFT, and its 'divide and conquer' advantage vs DFT,
  • radix 4 FFT, and why it is better than radix 2 FFT (1 radix 4 needs an overall lower number of operations than 2 radix 2 FFTs),
  • split radix 4/2 FFT: 'naively' it looks like there are more operations than radix 4, but actually quite a few more trivial operations (in particular multiplications by 1, -1, i, -i that actually need no complex multiplications), so less 'expensive' operations overall.

My question is: I cannot find as much / I read much less about 'higher radix' FFTs: I can find a bit here and there about radix 8, very little about radix 16, nothing so far about radix 32, 64, and 2**n in general. Naively, I would have guessed that going for higher and higher 2**n radix for array length that are compatible with it should give additional gains compared with combining several lower radix stages. Is this wrong / any reason why higher radix FFTs are not discussed as much?

$\endgroup$
2
  • $\begingroup$ the radix-4 FFT butterfly actually contains 4 radix-2 FFT butterflies. $\endgroup$ Nov 14, 2021 at 15:50
  • 1
    $\begingroup$ One thing that came up for me implementing a radix 8 on a cortex M4 was register usage. Beyond a given size enough time was spent pushing and popping from the stack that there was actually a drop in performance without carefully crafting the source code. $\endgroup$
    – Dan Szabo
    Nov 15, 2021 at 14:19

3 Answers 3

3
$\begingroup$

Let's take a closer look how the FFT butterflies actually work (we stick with decimation in time for simplicity)

For Radix N, you take N samples, multiply these with N twiddle factors and than multiply the resulting vector with a N by N "recombination" matrix to get N output samples. This covers $\log_2(N)$ stages. The first twiddle factor is always 1 so we need N-1 actual twiddle factors

We can write this roughly as $$Y_k = X_k\cdot \hat{W}_{N,k} \cdot M_N$$

For N=2 the recombination matrix is simply

$$ M_2 = \begin{bmatrix} 1 & 1\\ -1 & 1 \end{bmatrix} $$

For N = 4, we get

$$M_4 = \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & -j & -1 & j\\ 1 & -1 & 1 & -1\\ 1 & j & -1 & -j \end{bmatrix} $$

Note that the first column is always 1.

For the execution of the radix 2 butterfly we need 1 complex multiply and 2 complex adds (or subtracts). That's a total of 4 real multiplies and 6 real adds.

For the execution of the radix 4 butterfly we need 3 complex multiplies for the twiddle factors. The recombination matrix consists ONLY of powers of $j$ so we don't have to actually execute any complex multiplies but can achieve this by simply swapping real/imaginary parts and/or signs. Due to the specific structure of this matrix we can implement this with 8 complex adds (not 12 if we were to do this directly). That's a total of 12 real multiplies and 22 real adds.

A radix 4 butterfly does 4 times the work of a radix-2 butterfly, so to compare apples, we need to divide by 4. A radix 4 butterfly requires 3 real multiplies 5.5 real adds per radix-2 butterfly. So it's only relatively mild improvement.

For higher radix butterflies the recombination matrix becomes truly complex. For a radix 8 butterfly half of the elements in the matrix will require a an actual complex multiply. You can still take advantage of the structure of the matrix but you will pick up at least 16 additional real multiples (with $\sqrt(0.5)$). At the same time the code becomes pretty complicated and unwieldy, so it's a questionable value proposition.

$\endgroup$
2
  • $\begingroup$ i wonder what a radix-8 butterfly looks like for a matrix? $\endgroup$ Nov 14, 2021 at 15:52
  • $\begingroup$ The recombination matrix is simply M8 = exp(-j*2*pi*(0:7)'*(0:7)/8). That's not the most efficient way to implement it, but it's a good reference $\endgroup$
    – Hilmar
    Nov 14, 2021 at 17:21
2
$\begingroup$

I believe that there are diminishing returns beyond radix 4. While arithmetic complexity probably continues to decrease (?) that decrease is too slow to compensate for «other factors».

Finding new factorizations that have lower arithmetic complexity is an interesting venture, but in practical applications, stuff like cache organization, simd instructions, the presence of bit reverse instructions can be more important than going for he currently lowest arithmetic complexity. I guess that could change if someone find a radically simpler factorization (I dont know that there is a theoretical bound on how simple factorizations might be found, but it seems that it is s fairly well studied topic).

-k

$\endgroup$
1
$\begingroup$

The package FFTW will work on vectors of any length. According to this presentation it uses both Rader's and Bluestein's algorithms. See also "prime factor FFT".

I found this out by doing a brief web search on the terms "fast fourier transform with vectors of prime length". Algorithms for doing this sort of thing appear to have been known since at least the 1960's (and Karl Gauss was doing interesting stuff with the FFT in the late 18th or early 19th century, but his results were not published until after his death, so the credit goes to Fourier).

$\endgroup$
1
  • $\begingroup$ Thanks :) I was kind of aware about this, and I suppose the reason why these higher factors are used is because, in this case / the cases discussed in this pdf, one cannot use a 'some power of 2' radix because, as you say, this is to take the FFT of vectors which length is not a power of 2, but some products of relatively large primes. I think this is a distinct question from what I asked. Ie in the case you show, one has to use these slightly exotic methods, but I do not think these are as attractive in the cases I ask about - ie length a power of 2 and radix 2 / 4 / 8 / 16 etc. $\endgroup$
    – Zorglub29
    Nov 14, 2021 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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