0
$\begingroup$

I'm learning about Fourier transform, and was asked whether the following FT can be expressed as a convolution: $$X[k] = \sum\limits_{n=0}^{N=1} x[n]e^{-i\frac{2\pi}{N}kn}$$

There are two things I don't understand:

  1. Why would anyone want to express the FT itself as a convolution? from what I understand, FT is used to express convolution, as stated by the Convolution Theorem.
  2. Assuming it does make sense to express an FT as a convolution, how can we do that with the above FT?
Improve this question
$\endgroup$
5
  • $\begingroup$ Are you sure that it says $N=1$ on top of the sum, instead of $N-1$, i.e., a general formula for a length $N$ DFT? $\endgroup$
    – Matt L.
    Commented Jul 31, 2020 at 15:49
  • $\begingroup$ I'm sure as I can be $\endgroup$
    – odyssey
    Commented Jul 31, 2020 at 16:23
  • $\begingroup$ Also the term 'FT' is used for the continuous case, DFT for the discrete. CTFT if FT is too bland or ambiguous, depends on context. $\endgroup$
    – Cedron Dawg
    Commented Jul 31, 2020 at 17:41
  • $\begingroup$ It can be seen like this, a weighted sum of Roots of Unity: $$ X[k] = \sum\limits_{n=0}^{N-1} x[n]\left( e^{-i\frac{2\pi}{N}k} \right)^n = \sum\limits_{n=0}^{N-1} x[n]R_k^n $$ and it can be seen as a dot product: $$ X[k] = (x[0],x[1],x[2],x[3],...,x[N-1]) \cdot ( 1, e^{-i\frac{2\pi}{N}}, e^{-i\frac{2\pi}{N}2}, ... e^{-i\frac{2\pi}{N}(N-1)} ) $$ but in either case the summation does go up to $N-1$ so you can never be too sure. $\endgroup$
    – Cedron Dawg
    Commented Jul 31, 2020 at 17:45
  • $\begingroup$ You should probably read this too. Maybe that is where the '1' comes from. dsp.stackexchange.com/questions/69430/… $\endgroup$
    – Cedron Dawg
    Commented Jul 31, 2020 at 17:50

1 Answer 1

Reset to default
1
$\begingroup$

As for the why, it's always good to come up with alternatives, even if one doesn't immediately see their benefit. In this case it's about efficiency, especially if the FFT length is a prime. The resulting algorithm can also be used to solve the more general problem of computing (samples of) the $\mathcal{Z}$-transform on circles or spirals in the complex plane. You can also zoom into a certain frequency region without the need to compute the DFT over the whole range.

The resulting algorithm is called Bluestein's algorithm or Chirp Z-transform. The basic trick to represent the DFT (or $\mathcal{Z}$-transform) by a convolution is to write

$$nk=\frac{n^2+k^2-(n-k)^2}{2}\tag{1}$$

and use this expression in the original formula. This results in the representation of the original DFT sum by $(i)$ a multiplication of the original sequence with a chirp sequence, $(ii)$ a convolution, and $(iii)$ another multiplication with a chirp sequence. The details are explained in the link cited above.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.