1
$\begingroup$

If $x_1[n]$ and $x_2[n]$ are finite length sequences of length $N$

$$\mathcal{DFT}(x_1[n] \circledast x_2[n]) = X_1[k]X_2[k]$$

where $X_1[k]$ and $X_2[k]$ are the DFTs of$x_1[n]$ and $x_2[n]$, respectively, and "$\circledast$" represents circular convolution.

I want to prove the converse that multiplication in time domain results in convolution in frequency domain using the duality theorem which suggests that if

$$x[n] \iff X[k]$$

then

$$X[n] \iff Nx[-k] \quad .$$

Note: I'm able to prove this without duality but using duality my results do not match.

Using duality what I get is :

$$x_1[n]x_2[n] \iff N \sum_{m=0}^{N-1} X_1[m]X_2[k-m]$$

which is incorrect.

$\endgroup$
2
  • $\begingroup$ if your last relationship is "incorrect", then how does it differ from the "correct" expression? $\endgroup$ Sep 8 at 19:43
  • $\begingroup$ @robert bristow johnson the "correct expression" was $\frac{1}{N}\sum_{m=0}^{N-1}X_1[m]X_2[k-m]$ where I was unable to account for the $\frac{1}{N}$ $\endgroup$
    – Orpheus
    Sep 9 at 7:08
1
$\begingroup$

It's a matter of careful interpretation.

Duality : $$x[n] \iff X[k]$$

then

$$X[n] \iff Nx[-k]\quad , \tag{1}$$

where $X[k]$ is the N-point DFT of N-point $x[n]$.

Now, let $x_1[n]$ and $x_2[n]$ be sequences of length $N$, whose N-point DFTs are $X_1[k]$ and $X_2[k]$, respectively.

Given that : $$\mathcal{DFT}(x_1[n] \circledast x_2[n]) = X_1[k]X_2[k]$$

then duality suggests:

$$ X_1[n] X_2[n] \iff N x_1[-k] \circledast x_2[-k] \tag{2}$$

, which is correct indeed.

Looking at eq.(2), however, the sequences on the left ($X_1, X_2$) are freq-domain sequences, and the sequences on the right ($x_1,x_2$) are the originating time-domain sequences.

But this is opposite of the usual DFT property notation where the sequences on the left are time-domain sequences, and those on the left are their forward DFT sequences which express the corresponding property.

So what's the forward DFT of $X_1[n]$...? It's $N x_1[-n]$ (from Eq.(1)), and also for $X_2[n]$ is $N x_2[-n]$.

Now re-interpret Eq.(2) as follows:

$$ X_1[n] X_2[n] \iff \frac{1}{N} (N x_1[-k]) \circledast (N x_2[-k]) \tag{3}$$

or further:

$$ X_1[n] X_2[n] \iff \frac{1}{N} \mathcal{DFT}\{ X_1[n] \} \circledast \mathcal{DFT}\{ X_2[n] \} \tag{4}$$

Now in this expression in Eq.4, the sequences on the left are arbitrary time-domain interpreted sequences, and the ones on the right will the their corresponding forward DFT sequences.

Finally, names of the sequences $X_1,X_2$ can be replaced with usual DFT notation, with $x[n] \iff X[k]$, and $h[n] \iff H[k]$ as DFT pairs:

$$ \mathcal{DFT}\{ x[n] h[n] \} \iff \frac{1}{N} X[k] \circledast H[k] \tag{5}$$

, which is the result you were looking for.

$\endgroup$
1
  • $\begingroup$ Thanks a lot @Fat32 $\endgroup$
    – Orpheus
    Sep 9 at 2:52

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.