0
$\begingroup$

my question is about reducing the complexity of radix-2 FFT when the input vector has a specific structure.

For an input vector of x with N elements, the complexity is given by O(N log2 N).

My input vector y with N elements has the structure of: y = [x1 x2]T

where,

x1 = x2

and x1 and x2 vectors have N/2 elements. Is it possible to reduce the complexity of radix-2 FFT for this y vector? I think it is possible to not use one of the N/2 DFT blocks of the FFT algorithm in this case. Can anyone show me what is the complexity for this vector? Thanks in advance.

$\endgroup$

1 Answer 1

2
$\begingroup$

if

$$\text{FFT}\{[a, b, c, d]\} = [p, q, r, s]$$

then

$$\text{FFT}\{[a, b, c, d, a, b, c, d]\} = [p, 0, q, 0, r, 0, s, 0]$$

or $$=[2p, 0, 2q, 0, 2r, 0, 2s, 0]\text,$$

depending on normalization.

Edit: Using this property, we can make FFT nearly 2x faster on this specialized data. But the complexity is still $O(n \log n)$. I mean, big O notation doesn't count constant factor.

$\endgroup$
5
  • $\begingroup$ Thank you. Assuming no normalization, i.e., DFT{x}=sum_{i=0}^{N-1} x_i e^{..}, it is known that FFT implementation leads to a complexity of N log_2 N. If we have a structured vector as above, i.e., x=[x_0,x_0,x_1,x_1,...,x_N/2,x_N/2], then can we say that the FFT complexity can be reduced to (N/2) log_2(N/2)? I appreciate your response in advance. $\endgroup$ Oct 22, 2019 at 12:08
  • $\begingroup$ @MustafaAnılReşat So what is actually your question? Something like [a, b, c, d, a, b, c, d] or [a, a, b, b, c, c, d, d] ? $\endgroup$
    – mfcc64
    Oct 23, 2019 at 7:15
  • $\begingroup$ Sorry for previous mistake. I should have written it as a vector structure of [a, b, c, d, a, b, c, d]. Let me repeat the question again correctly. Assuming no normalization, i.e., DFT{x}=sum_{i=0}^{N-1} x_i e^{..}, it is known that FFT implementation leads to a complexity of N log_2 N. If we have a structured vector as x=[x_0,x_1,...,x_N/2,x_0,x_1,...,x_N/2], then can we say that the FFT complexity can be reduced to (N/2) log_2(N/2)? I appreciate your response in advance. $\endgroup$ Oct 23, 2019 at 11:20
  • $\begingroup$ @MustafaAnılReşat I edited the answer, thanks. $\endgroup$
    – mfcc64
    Oct 23, 2019 at 16:24
  • $\begingroup$ @mfcc64 I think if we ignored the multiplication which results 0 values, the complexity will be reduced up to half, right? $\endgroup$
    – Gze
    Jun 28, 2022 at 2:21

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.