# Prove Convolution Property for DFT using duality

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.

• if your last relationship is "incorrect", then how does it differ from the "correct" expression? Sep 8 at 19:43
• @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}$ Sep 9 at 7:08

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.

• Thanks a lot @Fat32 Sep 9 at 2:52