3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ How should one read your polar coordinate data? $\endgroup$ – Olli Niemitalo Nov 7 '15 at 21:06
  • $\begingroup$ @OlliNiemitalo I have the magnitude as the first number and the phase in parentheses. I might have made a mistake in the notation... The signal itself is supposed to be a sine wave in the first bin (bin 0 being DC). In rectangular format it would be [0, -j, 0 , j, 0]. $\endgroup$ – Dole Nov 7 '15 at 21:20
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Where does that frequency domain representation of the sine wave come from? Don't the negative and positive parts always need to be symmetric around the DC offset bin? $\endgroup$ – Dole Nov 9 '15 at 17:25
  • 1
    $\begingroup$ @Dole: They are symmetric: the first element is the zeroth bin (DC), the second element is bin number 1 (the frequency of the sinusoid); and the last element is bin number -1 (the negative frequency of the sinusoid). Try to see it by periodic continuation of the vector: (...,0,j,[0,-j,0,0,j],0,-j,...) $\endgroup$ – Matt L. Nov 9 '15 at 18:35
  • $\begingroup$ L Thanks, I forgot that positive imaginary part actually reflects inverted sine wave, that threw me off a bit there. Indeed I had the spectrum from negative to positive and you have it from 0 up. $\endgroup$ – Dole Nov 9 '15 at 19:36
  • $\begingroup$ Why does A equal ` [0,-j,0,0,j]` ? I am puzzled by the two 0's in a row. $\endgroup$ – Dilip Sarwate Nov 20 '15 at 14:20
  • $\begingroup$ @DilipSarwate: Note that it's an odd length DFT, that's why there is no bin at Nyquist. The two 0's are the (conjugate complex) elements at indices $-2$ and $2$, just below Nyquist. $\endgroup$ – Matt L. Nov 20 '15 at 14:24
2
$\begingroup$

(EDIT: Never mind, I misinterpreted the question being about length 4 FFT specifically.)

You have made the mistake of having both a positive and a negative Nyquist frequency (sampling frequency / 2) bin. Only one is needed because they are equal in the discrete time sense: $$e^{i\pi k} = e^{i-\pi k} \text{, for } k\in\text{integer}.$$ Remove the negative Nyquist frequency bin, making your data of length 4 instead of length 5.

$\endgroup$
  • $\begingroup$ Note that for an odd DFT length (which is of course possible), there is no point that corresponds to the Nyquist frequency. The problem is a different one, as explained in my answer. $\endgroup$ – Matt L. Nov 8 '15 at 19:02
  • $\begingroup$ @MattL. Ah, right, I misinterpreted Doles's comment. I recognized a sinusoid of period 4 multiplied by i in a=[0,1(3π/4),0,1(π/2),0)]. But that is just a coincidence, a being in frequency domain and the sinusoid being in time domain. $\endgroup$ – Olli Niemitalo Nov 8 '15 at 20:31

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.