Friday, August 3, 2018

fourier transform - Convolution in frequency domain


Simple math question. The convolution theorem states that multiplication in time domain is equal to convolution in frequency domain and vice versa. There is a condition that the signal has to be properly zero padded as to not cause aliasing.


This question concerns convolution in the frequency domain. The difficulty arises from the fact that we are dealing with a complex signal which has a positive and a negative side. Let's consider two frequency domain signals, with negative frequencies included, presented in polar coordinates []:



a=[0,1(3π/4),0,1(π/2),0)]
b=[1,1,1,1,1]

So we have a sine wave and a zero-phase dirac delta. It's apparent that the time domain product is zero. But coming to this conclusion via using convolution in frequency domain doesn't seem to be so simple. I get (rectangular):


[-j,-j,-j,-j, 0,j,j,j,j,j]
=> [-2j,-2j,0,2j,2j]

Which is not correct. Even for a cosine I get a row of twos, which is not correct either (should be row of ones). Where am I going wrong?



Answer



If you have two DFTs $A[k]$ and $B[k]$ (note the correct representation of a sinusoid at DFT bin number $1$)



A = [0,-j,0,0,j]; B = [1,1,1,1,1];


with the corresponding time-domain sequences $a[n]$ and $b[n]$



a = ifft(A); % [0, 0.38042, 0.23511, -0.23511, -0.38042];
b = ifft(B); % [1,0,0,0,0];

then the multiplication of the time-domain sequences $c[n]=a[n]b[n]$ corresponds to the cyclic (or circular) convolution of the DFTs $A[k]$ and $B[k]$:


$$\text{DFT}\{c[n]\}=C[k]=\frac{1}{N}\sum_{n=0}^{N-1}A[n]B[k-n]_{\text{mod} N},\quad k=0,1,\ldots,N-1\tag{1}$$


where the indices are taken modulo $N$ ($N=5$ in this case), such that they remain in the range $[0,N-1]$:


$$\begin{align}C[0]&=\left(A[0]B[0]+A[1]B[N-1]+\ldots+A[N-1]B[1]\right)\cdot\frac{1}{N}\\ C[1]&=\left(A[0]B[1]+A[1]B[0]+\ldots+A[N-1]B[2]\right)\cdot\frac{1}{N}\\&\vdots\\ C[N-1]&=\left(A[0]B[N-1]+A[1]B[N-2]+\ldots+A[N-1]B[0]\right)\cdot\frac{1}{N} \end{align}$$



It's easy to see that the cyclic convolution of $A[k]$ and $B[k]$ as given above results in the zero vector, because due to $B[k]=1$ for all values of $k$, each element of the result is the sum of all elements of $A[k]$, which is always zero.


No comments:

Post a Comment

periodic trends - Comparing radii in lithium, beryllium, magnesium, aluminium and sodium ions

Apparently the of last four, $\ce{Mg^2+}$ is closest in radius to $\ce{Li+}$. Is this true, and if so, why would a whole larger shell ($\ce{...