One Sided Waveforms in Discrete Time and Frequency?

Question

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?

Answer 1

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.