1
$\begingroup$

Can anyone help with this exercise from my Signal Processing exam? The text is:

Given two sequences $x$ and $y$ whose supports are respectively $[0,1]$ and $[0,3]$ and their circular convolution's DFT is equally null, if the first value of $x$ sequence is $x(0)=2$ and the first value of $y$ sequence is $y(0)=1$ then obtain $x(1), y(1), y(2), y(3)$

I have tried to solve that supposing respectively that $X(k)=0$ for a first case, $Y(k)=0$ for a second case and then both equal to zero, and I have found two solution for each case. The problem is that my professor tell me that it has just one solution and it can be solve using DFT properties in, more or less, 1 minute, without solving linear system or doing hypothesis on the DFTs but I really don't understand what is referring to because I don't find anything on my notes or on my book.

Is there anyone that have 1-minute solution? :S

$\endgroup$
2
$\begingroup$

Your professor is wrong, the solution is not unique. There are two (real-valued) solutions:

x1 = [2, 2, 0, 0]; y1 = [1, -1, 1, -1]

with DFTs

X1 = [4, 2-2i, 0, 2+2i]; Y1 = [0, 0, 4, 0]

(the product of which is obviously zero)

and

x2 = [2, -2, 0, 0]; y2 = [1, 1, 1, 1]

with DFTs

X2 = [0, 2+2i, 4, 2-2i]; Y2 = [4, 0, 0, 0]

(the product of which is also zero).

This is how you obtain these two solutions: first of all, note that the DFT of the circular convolution of the two sequences is equal to the product of the DFTs of the two sequences, where the individual DFTs are of length $4$. The product is zero for all indices $0\le k<4$ if for each index at least one of the two DFTs is zero. Since I assume that we're talking about real-valued sequences, we only need to consider the indices up to and including Nyquist (i.e. index $k=2$), because the last index $k=3$ is redundant due to the symmetry of the DFTs.

Since none of the two sequences can be identical to zero ($x[0]$ and $y[0]$ are both given and non-zero), only specific DFT bins can be zero, not all of them. For the length $4$ DFT of the zero-padded length $2$ sequence $x[n]$ it is easy to see that its DFT is given by

$$\begin{align}X[0]&=x[0]+x[1]\\ X[1]&=x[0]-jx[1]\\ X[2]&=x[0]-x[1]\\ X[3]&=x[0]+jx[1]\;\;(=X^*[1]\;)\end{align}\tag{1}$$

from which it is clear that with $x[0]\neq 0$, only $X[0]$ or $X[2]$ (but not both) can be zero. $X[1]$ can never be zero (for real-valued $x[1]$), from which it follows that $Y[1]$ must be zero. Since $Y[k]$ cannot be zero for all $k$, $X[0]$ or $X[2]$ must be zero. This leaves us with two possible choices for $x[1]$:

$$x[1]=x[0]\rightarrow X[2]=0\tag{a}$$

or

$$x[1]=-x[0]\rightarrow X[0]=0\tag{b}$$

In the first case, we need a DFT $Y[k]$ which is zero for all $k$ except for $k=2$, in the other case $Y[k]$ must be zero for all $k$ except for $k=0$. Note that $k=0$ corresponds to DC, and $k=2$ corresponds to Nyquist. The DFT of a sequence is zero everywhere except at DC if the sequence is constant, and it is zero everywhere except at Nyquist if the sequence is alternating. So for choice $(a)$ we need to choose $y[n]$ to alternate, and for choice $(b)$, $y[n]$ needs to be constant. These are the only two real-valued options.

EDIT: If you allow the sequences $x[n]$ and $y[n]$ to be complex-valued, there are two additional solutions. From $(1)$ it can be seen that for $x[0]\neq 0$, $X[k]$ can only be made zero for one index $k$. This means that $Y[k]$ must be zero for all indices except for that one index where $X[k]$ is zero. Therefore, $Y[k]$ must be a spectral line, i.e. its corresponding sequence $y[n]$ must be a complex exponential on the DFT ($N=4$) grid:

$$y[n]=e^{j\pi nl/2},\quad l=0,1,2,3\tag{2}$$

For $y[n]$ as given by $(2)$, $Y[k]$ is zero for $k=l$. The solutions $l=0$ (constant sequence), and $l=2$ alternating sequence are real-valued and were given above. The two other solutions are

y3 = [1, i, -1, -i]

($l=1$) and

y4 = [1, -i, -1, i]

($l=3$). The DFT of the corresponding sequences $x[n]$ must have a zero at $k=l$. From $(1)$ we get

x3 = [2, -2i, 0, 0] and x4 = [2, 2i, 0, 0]

The DFTs are

X3 = [2 - 2i, 0, 2 + 2i, 4]; Y3 = [0 4 0 0]

and

X4 = [2 + 2i, 4, 2 - 2i, 0]; Y4 = [0 0 0 4]

Both products are clearly zero.

In sum, there are four solutions to the problem, two of which are real-valued.

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