2

I am asked to find a pair of sequences, each one of which contains three distinct values and where the convolution is an all-zero sequence.

I've came to the conclusion that one of the sequences must be infinite but just can't think of any examples...

Rayhunter
  • 131
  • 5
  • Can you explain your reasoning for why one of the sequences must be infinite? – Peter K. Nov 06 '13 at 16:14
  • Is this a homework question? :-) – Peter K. Nov 06 '13 at 16:22
  • 1
    Probably a very popular homework question. I answered it here: http://dsp.stackexchange.com/a/11264/5069 – jan Nov 06 '13 at 16:28
  • I vote to reopen this question. In the answer which is claimed to answer this question, one of the sequences takes on three values while the other takes on only one value. Here the requirement is that both sequences must take on three distinct values, and so the other answer is not an answer to this question which is different enough to deserve separate consideration. – Dilip Sarwate Nov 06 '13 at 17:51
  • it is pretty straightforward if at least one of the sequences takes 3 distinct values ({1,0,-1} and {..1,1,1,1..}). The reason why one of the sequences must be infinite is that if both are finite then there is no way we get an all-zero sequence after convolution. – Rayhunter Nov 07 '13 at 01:15
  • Notice my comment in the linked question. If two non-zero sequences have finite length you will always get non-zero convolution tails. – nispio Nov 07 '13 at 03:53
  • Since it is unlikely that Moderator @PeterK. will re-open this question without 5 re-open votes, here is an answer as a comment. Suppose that $$x[n]=e^{j2\pi n/3}\quad\forall n,\qquad y[n]=\begin{cases}e^{j4\pi n/3},&n=0,1,2,\0,&\text{otherwise.}\end{cases}$$ Then, $$\sum_{n=-\infty}^\infty x[k-n]y[n]=\sum_{n=0}^2e^{j2\pi(k-n)/3}e^{j4\pi n/3}=e^{j2\pi k/3}\sum_{n=0}^2e^{j2\pi n/3}=0.$$ Of course, nitpickers might argue that $y$ takes on $4$ values, not $3$, but this does show that there is something more to this question than a duplication of a previously asked question. – Dilip Sarwate Nov 07 '13 at 14:32
  • @DilipSarwate: Thanks for taking the time to write! We already have two re-open votes, so I'll reopen (that's more re-open votes than I've seen on any DSP.SE question!). Open/reopen votes tend to need help of the mods. – Peter K. Nov 07 '13 at 14:53

3 Answers3

4

Expanding on my comment when this question was closed, suppose that $$x[n]=e^{j2\pi n/3},~\forall n,\quad y[n]=\begin{cases}e^{j4\pi n/3}& n=0,1,2,\\0, &\text{otherwise.}\end{cases}$$

Then, $\displaystyle \sum_{n=-\infty}^\infty x[k−n]y[n]= \sum_{n=0}^2 e^{j2\pi (k−n)/3}e^{j4\pi n/3} = e^{j2\pi k/3}\sum_{n=0}^2 e^{j2\pi n/3}=0.$

More generally, $\displaystyle x[n]=e^{j2\pi n/N},~\forall n,\quad y[n]=\begin{cases}e^{j2\pi (N-n)/N}& n=0,1,2,\ldots, N-1\\0, &\text{otherwise,}\end{cases}$ works as a solution for sequences taking on $N$ values. Of course, nitpickers might argue that y takes on $N+1$ values, not $N$ as required by the OP, but in the case $N = 3$, there is an easy workaround. Define $$z[n] = \begin{cases}1, & n = 0,\\ -e^{j2\pi/3}, & n = 1,\\0, &\text{otherwise,}\end{cases}$$ which is clearly a three-valued sequence, and note that $$\displaystyle \sum_{n=-\infty}^\infty x[k−n]z[n]= \sum_{n=0}^1 e^{j2\pi (k-n)/3}z(n) = e^{j2\pi k/3}\cdot 1 + e^{j2\pi (k-1)/3}\cdot (-e^{j2\pi/3}) = e^{j2\pi k/3} - e^{j2\pi k/3} = 0.$$ The real pezzonovante nitpickers who wish to complain that the three values that $z$ takes on are not the same three values that $x$ takes on are invited to work out a more satisfactory solution for themselves.

It is tempting to extend $y$ periodically to be nonzero for all $n$ so as to totally avoid the nitpick, but unfortunately, the infinite sum $\sum_{n=-\infty}^\infty e^{j2\pi n/3}$ that is the result of the convolution is not absolutely convergent. Of course, since both sequences are of period $3$, their convolution could also be defined as a periodic convolution, which is the sum of just $3$ terms, and we are back in business. More generally, note that the periodic convolution of any two rows of the $N\times N$ DFT matrix is $0$, and so we can extend this notion to sequences that take on $N$ distinct values for any $N \geq 3$. For another viewpoint on this approach, see the answer by @Hilmar.

Dilip Sarwate
  • 20,349
  • 4
  • 48
  • 94
2

Here is two example that actually works with 3 distinct values:

x1 = [0 0.866 .866 0 -.866 -.866 0 0.866 .866 0 -.866 -.866] etc (periodic) x2 = [1 -.5 0.5 .5]

x1 = [0 0.866 -.866 0.866 -.866 0 .866 -.866] etc (periodic) x2 = [1 1.5 1.5 .5]

0.866 is short for sqrt(3/4).

Here is the reasoning behind this: Convolution in the time domain is multiplication in the frequency domain. In order to get a zero result, the two signals must be spectrally "disjointed", i.e. at least one of the spectra must be zero at any one frequency. Now finite time domain signals have continuous spectra. They may have discrete zeros in the spectra but two continuous spectra can not be disjointed at all frequencies and so we can conclude that at least one signal needs to be periodic (and hence infinite). Periodic signals have discrete spectra. As Dilip has pointed out, if both signals are periodic, the standard convolution is periodic as well and the sum doesn't converge.

So the best way to do this is to make one signal that's periodic and a second finite signal that is an FIR filter that has it's zeros at the discrete frequencies of the periodic signal.

The "three distinct value" constraint adds an extra complication. We can certainly make a periodic signal that has only three distinct values by picking any three numbers and just repeat them. However that makes for a complicated spectrum so let's stick with sine waves.

For some choices are: 2*pi/3 with any phase, 2*pi/4 with 0 phase, or 2*pi/6 with 0 phase. Each of this will only have three distinct values. We can construct the matching FIR filter by simply putting a conjugate pair of zeros on the unit circle at these frequencies. We get 

2*pi/3 -> [ 1 1 1]
2*pi/4 -> [ 1 0 1]
2*pi/6 -> [1 -1 1]

These FIR filters have zeros for matching frequencies. However they don't have three distinct values. In order to fix this we can arbitrarily throw in a another real zero anywhere just to shuffle the values around. As it turns out an added zero at -0.5 does the trick for 2*pi/3 and 2*pi/6. This zero doesn't do anything useful other than garbling up the FIR filter numbers a bit to satisfy the really arbitrary "3 distinct numbers" constraint.

Hilmar
  • 44,604
  • 1
  • 32
  • 63
1

thanks for the input. I found a simple solution:

sequence A: {...1,0,-1,0,1,0,-1,0...} (i.e. 1,0,-1,0 periodic)

and

sequence B: {0,x,y,x,y,0}

Rayhunter
  • 131
  • 5