Radix-2 vs Radix-4 FFT

Question

What are the differences between radix-2 FFT and radix-4 FFT,

Are the only differences following two:

In case of radix-2 $N$ is a number that is a power of 2 and in case of radix-4 $N$ is a number that is a power of 4
Incase of radix-2 the butterfly diagram increases or decreases density by a factor of 2, while in case of radix-4 the butterfly diagram increases or decreases density by factor of 4

1)makes little sense, since any power of 4 is also a power of 2 — Marcus Müller, Jun 16 '20 at 07:59
really, the difference is that Radix-2 FFTs are built from butterflies of 2 inputs each, and radix-4 of butterflies with 4 inputs each. That's all there is to it. https://dsp.stackexchange.com/a/50144/13320 — Marcus Müller, Jun 16 '20 at 08:00
1)makes little sense, since any power of 4 is also a power of 2 @MarcusMüller Yes, any power of 4 is also a power of 2, but not every power of 2 is an (integer) power of 4. So, there can be a radix-2 FFT for some powers of 2 for which a radix-4 FFT does not exist (without tweaking etc). — Dilip Sarwate, Jun 16 '20 at 11:44
@DilipSarwate point is that the length of the FFT can't generally tell you whether it's Radix-2 or Radix-4. "256-point FFT" can absolutely be either, both, or neither. — Marcus Müller, Jun 16 '20 at 12:03
@MarcusMüller You are misunderstanding my point. An FFT of length 128 can be implemented as a Radix-2 FFT. Can it be implemented directly without any tweaks as a Radix-4 FFT? If you are setting half the inputs to a Radix-4 FFT of length 256 and claiming the output can be viewed directly (or perhaps after some massaging) as the FFT of length 128 of the original sequence. which inputs are you setting to 0 and which of the 256 outputs are the FFT of length 128? or what post-FFT massaging are you doing so that you can say that 128 items of the post-massaged output are the length-128 FFT? — Dilip Sarwate, Jun 16 '20 at 14:04
@DilipSarwate I think we agree. What you say is "ok, if you have a non-power-of-4 length that is a power of 2, we can be sure this isn't pure radix-4". I say "even if we know the length to be a power of 4, we can't be sure that this is pure radix-4". — Marcus Müller, Jun 16 '20 at 14:46

Dan Boschen · Accepted Answer · 2020-06-17T13:19:55.297

5

The reason the Radix-4 FFT is of interest is in the simplicity of multiplying by $\pm j$ in actual implementation. Below shows the Radix-4 4 point DFT core processing element as part of the Radix-4 FFT Butterfly in comparision to the Radix-2 FFT butterfly (with 2 point DFT core processing element) and the resulting decrease in number of operations, applicable when the input signal is of a length that is a power of 4 (or for portions of the signal that are).

To further see how the radix-4 algorithm reduces multiplications consider the number of real multipliers and additions in a complex multiplier:

$$V_1V_2 = I_{out}+jQ_{out}= (I_1+jQ_1)(I_2+jQ_2) = (I_1 I_2 - Q_1 Q_2) + j(I_1Q_2+I_2Q_1)$$

Where we see from above there are 4 real multipliers and 2 additions (Where the real and imaginary components are maintained on separate paths so not actually added).

Now consider if $V_2$ above was $j$, then $I_2 = 0$ and $Q_2 = 1$:

$$V_1V_2 = V_1j = (I_1 0 - Q_1 1) + j(I_1 1 +0 Q_1) = -Q_1 + jI_1$$

We see that multiplying a complex number $I_1+jQ_1$ by $j$ is done by simply changing the sign of $Q$ and then swapping $I$ and $Q$. Similarly multiply by $-j$ would be done by changing the sign of $I$ and then swapping $I$ and $Q$.

The radix-4 allows for an increased number of multiplications by $\pm j$ where the radix-2 solution minimizes all complex multiplications including multiplying by $\pm j$.

edited Jun 17 '20 at 13:19

answered Jun 16 '20 at 15:15

Dan Boschen

50,942
2
57
135

Have you benchmarked a radix-4 vs radix 2 implementation? What can we expect performance-wise ? I recently implemented a radix-2 algorithm using SIMD processor extensions (using 128 bit registers), which significantly improved performance, if performance is important for you, data parallelism seems to be the way to go. – dsp_user Jun 16 '20 at 16:38
1

@dsp_user it depends on what resources you have; as noted here the Radix 4 specifically results in less complex multipliers but that may not be the limiting factor. The FFTW is an interesting implementation in terms of overall speed and efficiency. – Dan Boschen Jun 16 '20 at 16:46
Where in your answer is radix 4 butterfly ?the one immediately below heading 4 pt dft? – DSP_CS Jun 16 '20 at 17:39
@Man Yes similar to the 2pt DFT is the radix-2 butterfly (with the additional phase rotation)... so the phase rotation part of the radix-4 butterfly is not shown – Dan Boschen Jun 16 '20 at 17:41
1

remember those "multiplies" really are just data transfers and additions. sometimes reals and imaginaries are swapped. sometimes you add and sometimes you subtract. – robert bristow-johnson Jun 16 '20 at 18:35
I have been looking for this answer (and question) for so long. Thank! Now I raise another one. Are the complexities the same at the end of the day? Are they both $N log(N)$ ? – Eduardo Reis Aug 14 '20 at 04:42
@EduardoReis I don't think I understand your question since the answer specifically talks about the relative complexities and why Radix-4 is less complex when the length of the DFT is a power of 4. – Dan Boschen Aug 14 '20 at 11:00
@DanBoschen, I meant order of complexity. Radix-2 is known for being $\mathcal{O}(N log N)$. Radix-4 have less multiplications operations, but is it still $\mathcal{O}(N log N)$? – Eduardo Reis Aug 14 '20 at 17:50
1

@EduardoReis yes on that order but 75% the number of complex multipliers – Dan Boschen Aug 14 '20 at 18:01

Radix-2 vs Radix-4 FFT

1 Answers1