# Inverse DFT on the first half time domain

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?

• 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.
– MBaz
Mar 14 at 21:09
• 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. Mar 14 at 21:23

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.

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

• Verified; interesting approach. Mar 16 at 21:07
• 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.
– MBaz
Mar 16 at 21:30
• 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. Mar 17 at 4:22

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