# One Sided Waveforms in Discrete Time and Frequency?

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?

• 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.
– MBaz
Jun 15 '21 at 16:42
• @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. Jun 15 '21 at 18:17
• @OverLordGoldDragon Nice one to you. Do you mean to say you saw instantly that odd N would work? Jun 16 '21 at 2:10
• @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. Jun 16 '21 at 2:37
• @DanBoschen My perspective's entirely from code - whether indexing or plotting, DC always ends up on left, when output directly by fft(x). Surely this is arbitrary and centering DC is nicer in its own regards, like saying $0$ is neither $+$ nor $-$. But yes, I meant len(x[:N//2+1]) > len(x[N//2+1:]). Jan 13 at 12:47

## 1 Answer

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.