4
$\begingroup$

Consider a discrete time waveform $x[n]$ with $n \in [0...N-1]$ that is zero for all samples $n > N/2$ and non-zero elsewhere. Is there a waveform such that its Discrete Fourier Transform $X[k]$ with $k \in [0...N-1]$ also has the property that $X[k] = 0$ for $k > N/2$?

If so, this could be viewed as a discrete time "causality" in both domains, treating the upper half of both sequences as representing the negative of the independent variable (time or frequency).

More background:

In this related question:

One-sided waveforms in both time and frequency?

MattL provided a succinct answer proving that a one-sided continuous time waveform cannot exist in both time and frequency, meaning we cannot simultaneously have a causal waveform, $x(t) = 0$ for all $t<0$, and a similar positive only spectrum with $X(\omega) = 0$ for all $\omega<0$.

As Matt presented, the sufficiency was based on Schwartz's Paley-Wiener condition which proves that $\int_{-\infty}^\infty|\ln X(\omega)|d\omega$ must converge for all causal waveforms. Therefore beyond singularities which will converge using Cauchy's principal value, $X(\omega)$ cannot be zero over any interval. Since $\ln(\epsilon)\rightarrow -\infty $ as $\epsilon \rightarrow 0$, there can be no causal waveforms that have no negative frequency components.

The values of the DFT are mathematically equivalent to samples of the continuous Discrete Time Fourier Transform. Similarly to what Matt confirmed the DTFT cannot be zero over any interval, but it can regularly pass through zero without violating the constraint provided by the Paley-Wiener Condition. Since the DTFT can periodically pass through zero, this leads me to suspect that there may possibly be a solution? OR how do we prove even this case cannot exist since this doesn’t appear (as far as I can tell) to be covered by Matt’s excellent response for the continuous time cases?

$\endgroup$
7
  • 1
    $\begingroup$ Dan, I'm very pressed for time at the moment, but I would start by using the DFT matrix to write a set of linear equations relating $x$ and $X$ as you have defined them, and then seeing if it has any solutions. $\endgroup$
    – MBaz
    Jun 15 at 16:42
  • $\begingroup$ @MBaz I like that and immediately see using that approach how the two and four pt DFT’s are not possible with reasoning that can likely be extended for any N. I’ll wait a few days and will expand on that if you or no one else doesn’t complete it first. $\endgroup$ Jun 15 at 17:36
  • 2
    $\begingroup$ @DanBoschen: I just did the same thing. N=2 and N=4 are no go. I think the way to go is expand this into any N and proof it's a no go. $\endgroup$
    – Hilmar
    Jun 15 at 18:17
  • 1
    $\begingroup$ @OverLordGoldDragon Nice one to you. Do you mean to say you saw instantly that odd N would work? $\endgroup$ Jun 16 at 2:10
  • 1
    $\begingroup$ @DanBoschen Yeah, for "can it be done" I favor an information-oriented perspective. I've learned to pay attention to "left > right" in odd DFT; if "causal" was defined as zeros from $0$ to $N/2$, no cake. $\endgroup$ Jun 16 at 2:37
2
$\begingroup$

Doable. But only for odd $N$. And it will have infinite solutions.

Example:

$$ \begin{align} x &= [x_0, x_1, 0] \\ x_0 &= 0.5 \left(1 + \frac{1}{\sqrt{3}}\right) + j 0.5\left(1 - \frac{1}{\sqrt{3}}\right) \\ x_1 &= 0.5 \left(1 - \frac{1}{\sqrt{3}}\right) + j 0.5\left(1 - \frac{1}{\sqrt{3}}\right) \end{align} $$

import numpy as np
x = np.array([.5 + .5/np.sqrt(3) + 1j*(.5 - .5/np.sqrt(3)),
              .5 - .5/np.sqrt(3) + 1j*(.5 + .5/np.sqrt(3)), 
              0])
xf = np.fft.fft(x)
assert np.allclose(xf[2], 0)

Proof

We seek to encode $N / 2 - 1$ bits of information${}^1$ with $N / 2$ degrees of freedom; there are infinite such encodings. For even case, we seek to enforce $N/2$ zeros with $N/2$ degrees of freedom. We know one solution is $x=X=0$. By uniqueness (one-to-one), we thus conclude it is the only solution.

I derive the solution for $N=3$, which generalizes for any odd $N$:

x * exp(k) = X
(x.re + x.im) * (cos - i*sin)
(x.re*cos - x.re*i*sin) + (x.im*i*cos - x.im*i*i*sin) = X.re + X.im*i
x.re*cos + x.im*sin = X.re
x.im*cos - x.re*sin = X.im
 cos(k=0) * x.re + sin(k=0) * x.im = X[0].re
 cos(k=1) * x.re + sin(k=1) * x.im = X[1].re
 cos(k=2) * x.re + sin(k=2) * x.im = X[2].re

-sin(k=0) * x.re + cos(k=0) * x.im = X[0].im
-sin(k=1) * x.re + cos(k=1) * x.im = X[1].im
-sin(k=2) * x.re + cos(k=2) * x.im = X[2].im
[1   1   1] * r + [0    0     0] * i = R0
[1 -.5 -.5] * r + [0   .87 -.87] * i = R1
[1 -.5 -.5] * r + [0  -.87  .87] * i = R2

[0    0     0] * r + [1   1   1] * i = I0
[0  -.87  .87] * r + [1 -.5 -.5] * i = I1
[0   .87 -.87] * r + [1 -.5 -.5] * i = I2
r2 = i2 = 0
-->
[1   1   0] * r + [0    0   0] * i = R0
[1 -.5   0] * r + [0   .87  0] * i = R1
[1 -.5   0] * r + [0  -.87  0] * i = R2

[0    0   0] * r + [1   1  0] * i = I0
[0  -.87  0] * r + [1 -.5  0] * i = I1
[0   .87  0] * r + [1 -.5  0] * i = I2
r0 +    r1          = R0;
r0 - .5*r1 + .87*i1 = R1;
r0 - .5*r1 - .87*i1 = R2;

          i0 +    i1 = I0;
-.87*r1 + i0 - .5*i1 = I1;
 .87*r1 + i0 - .5*i1 = I2;

Now we arbitrarily set R0=I0=1 and feed it to Wolfram Alpha, which gives us (I set g as placeholder for sin(2pi/3)):

and for the general case:


1 - Note: it's actually $N - 1$ bits of information ($\lfloor N/2 \rfloor$ reals and imaginaries) and $N + 1$ degrees of freedom ($\lceil N/2 \rceil$ re & im), which shows in the example where we specify two values (R0, I0) to obtain one solution.

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