4
$\begingroup$

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

Are the only differences following two:

  1. 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

  2. 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

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 1)makes little sense, since any power of 4 is also a power of 2 $\endgroup$
    – Marcus Müller
    Jun 16 '20 at 7:59
  • $\begingroup$ 2) what's "density" in this context? $\endgroup$
    – Marcus Müller
    Jun 16 '20 at 7:59
  • 1
    $\begingroup$ 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. dsp.stackexchange.com/a/50144/13320 $\endgroup$
    – Marcus Müller
    Jun 16 '20 at 8:00
  • 1
    $\begingroup$ 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). $\endgroup$
    – Dilip Sarwate
    Jun 16 '20 at 11:44
  • 1
    $\begingroup$ @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? $\endgroup$
    – Dilip Sarwate
    Jun 16 '20 at 14:04
5
$\begingroup$

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).

Radix 4

4 pt DFT

Radix 2

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

Improve this answer
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – dsp_user
    Jun 16 '20 at 16:38
  • 1
    $\begingroup$ @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. $\endgroup$
    – Dan Boschen
    Jun 16 '20 at 16:46
  • $\begingroup$ Where in your answer is radix 4 butterfly ?the one immediately below heading 4 pt dft? $\endgroup$
    – DSPCS
    Jun 16 '20 at 17:39
  • 1
    $\begingroup$ remember those "multiplies" really are just data transfers and additions. sometimes reals and imaginaries are swapped. sometimes you add and sometimes you subtract. $\endgroup$
    – robert bristow-johnson
    Jun 16 '20 at 18:35
  • 1
    $\begingroup$ @EduardoReis yes on that order but 75% the number of complex multipliers $\endgroup$
    – Dan Boschen
    Aug 14 '20 at 18:01

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.