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$
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$
  • $\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$ – Mustafa Anıl Reşat Oct 22 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 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$ – Mustafa Anıl Reşat Oct 23 at 11:20
  • $\begingroup$ @MustafaAnılReşat I edited the answer, thanks. $\endgroup$ – mfcc64 Oct 23 at 16:24

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.