4
$\begingroup$

Assume to have c[] representing N DFT coefficients. The complex-valued signal of N samples in the time domain is computed by idft(c, N).

Is there a straightforward way of reconstructing the signal just in the first half of the time domain by manipulating c[], and executing only idft(., N/2) multiple times?

$\endgroup$
2
  • 2
    $\begingroup$ The answer is No, it's not possible. However, if you explain what you're trying to do, and define "manipulate", it may be possible to provide some pointers. $\endgroup$
    – MBaz
    Mar 14 at 21:09
  • $\begingroup$ If the signal in the time domain is all real (or is all imaginary) then you can use just the N/2 coefficients as you suggest. Please clarify is that is the case. $\endgroup$ Mar 14 at 21:23

3 Answers 3

2
$\begingroup$

Mirroring isn't required; this simply utilizes "subsampling in time <=> folding in Fourier", with duality and an extra step. Hence,

x = np.random.randn(128) + 1j * np.random.randn(128)

xf = fft(x)
A = ifft(xf[::2])
B = ifft(xf[1::2])
rotate = np.exp(1j * 2 * np.pi * np.arange(len(x)//2) / len(x))
x_half = (A + B*rotate) / 2

assert np.allclose(x[:len(x)//2], x_half)

Performance-wise, not much gain. In terms of pure FFT, it's more computationally efficient: $2 (N/2) \log(N / 2) < N \log(N)$. However, there's also complex multiplication that's $O(N/2)$. Assuming we pre-compute and reuse rotate (sampling exp(jw) is expensive), my benchmarks show the naive approach is superior for N that's a power of 2, and same or a little slower for other N. If we don't pre-compute, naive always wins.

Credit to OP for initial solution.


Details

A folds the second half of x onto the first: xA = x.reshape(2, -1).mean(axis=0), or (x[:8] + x[8:])/2, while B*rotate does the same except the folding is a subtraction, xB = (x[:8] - x[8:])/2, hence xA + xB = x_half.

$\endgroup$
2
$\begingroup$

UPDATE: OverLordGoldDragon gave a solution that is superior to mine on every aspect. He got rid of mirroring, but more importantly he clearly exposed the insight to solve this problem. I hope he gets a shower of points!

It turns out to be not that difficult. At least when N is a power of 2.

The cornerstone of my approach is mirroring. Vanilla code (python):

import numpy as np

def mir(xin):
        n = xin.shape[0]
        return np.array([xin[-i & (n - 1)] for i in range(n)])

Now I can build an "unscaled" dft, using mir and idft (which is ifft here):

  import numpy.fft as fft

  def dft(xin) : 
     return fft.ifft(mir(xin))

I first mirror the frequencies to implement idft as radix-2 DIT, allowing in turn to reconstruct only half of the signal. But I need twiddle factors.

def split(xin) : 
    t = np.transpose(xin.reshape(-1, 2))
    return t[0], t[1]

def ifft_half(c):
        e, o = split(mir(c))
        
        G = dft(e)
        H = dft(o)
        
        N = c.shape[0]
        W = [np.exp(-1j * 2 * np.pi * k / N) for k in range(N//2)] #twiddle
        
        return (G + W * H) / 2
$\endgroup$
3
  • $\begingroup$ Verified; interesting approach. $\endgroup$ Mar 16 at 21:07
  • $\begingroup$ Interesting. I must say I didn't understand your original question (I thought you wanted to avoid using half the DFT coefficients). It would be nice to know what is the complexity of your approach compared to a single full-size DFT. $\endgroup$
    – MBaz
    Mar 16 at 21:30
  • $\begingroup$ Good point. This approach requires two $N/2$-point IFFT, one $N/2$-point add and two $N/2$-point multiplication and some memory processes. I think these make the total complexity similar to one single $N$-point FFT. $\endgroup$
    – ZR Han
    Mar 17 at 4:22
1
$\begingroup$

For long sequences, there's very little computational gain from this arrangement.

Consider a sequence x[n] of length N, and its N-point DFT $X[k]$. Denote the first half of $x[n]$ as $x_1$, and its second half as $x_2$, then it can be shown that:

$$ \frac{N}{2}-DFT\{ x_1 + x_2 \} = X[2k] = X_e[k] \tag{1}$$ $$ \frac{N}{2}-DFT\{ W_1 x_1 + W_2 x_2 \} = X[2k+1] = X_o[k] \tag{2}$$

where $W_1$ and $W_2$ are the first & second halves of the sequence $W = e^{-j \frac{2\pi}{N} n } ~~,~~ n = 0,1,...,N-1$. Also, $X_e[k]$ and $X_o[k]$ are the even and odd indexed parts of $X[k]$ respectively.

Then, it's a matter of algebra to show the following:

$$ x_1 + x_2 = \frac{N}{2}-IDFT \{ X_e[k] \} \tag{3}$$ $$ W_1 x_1 + W_2 x_2 = \frac{N}{2}-IDFT \{ X_o[k] \} \tag{4}$$

then, multiply Eq.3 with $W_2$

$$ W_2 x_1 + W_2 x_2 = W_2 \cdot \left( \frac{N}{2}-IDFT \{ X_e[k] \} \right) \tag{5} $$ $$ W_1 x_1 + W_2 x_2 = \frac{N}{2}-IDFT \{ X_o[k] \} \tag{6}$$

and solve for $x_1$:

$$x_1 = \frac{ W_2 \cdot \left( \frac{N}{2}-IDFT \{ X_e[k] \} \right) - \left( \frac{N}{2}-IDFT \{ X_o[k] \} \right) }{ W_2 - W_1 } \tag{7}$$

Eq.7 indicates that the first half of the sequence $x[n]$ is obtained by two $\frac{N}{2}$-point inverse DFTs performed on even & odd indexed parts of $X[k]$ (which is your $c[n]$ sequence).

$\endgroup$

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.