# DFT as convolution question

I have tried to make this question as readable and consistent as possible. The short of it, is that I am trying to ascertain how one gets from the math equation shown, (which I understand), to the correct implementation. (Which I also understand). However, how/why one gets from one to the other seems unclear to me.

Here is my setup:

We have an $M$ length 'original' signal $x[m]$: (Equation 1)

$$x[m] , \space m = 0,1,..M-1$$

We wish to take a 'zoom-DFT' of it, where the DFT length will be, $N$, where $N > M$.

We thus now have an $N$ length zero-padded new signal, lets call it $x_p[n]$, where: (Equation 2) $$x_p[n], \space n = 0,1,...N-1$$

Our discrete time variable is now $n = 0,1,...N-1$, and our discrete frequency variable is $k = 0,1,...N-1$.

The $N$-length DFT of a signal is defined as such: (Equation 3)

$$X[k] = \sum_{n=0}^{N-1} x_p[n]\space e^{-j\frac{2\pi nk}{N}}$$

If the $nk$ in the DFT equation is written as $\frac{-(k-n)^2 + n^2 + k^2}{2}$, then the DFT can now be written as: (Equation 4)

$$X[k] = e^{-j\frac{\pi k^2}{N}} \space \sum_{n=0}^{N-1} x_p[n]\space e^{-j\frac{\pi n^2}{N}} \space e^{j\frac{\pi (k-n)^2}{N}}$$

This expresses the full DFT, (i.e, the DFT from 0 to nyquist), as a convolution. To evaluate the 'Zoom-DFT', where we want to interrogate only frequencies between $f_1$ and $f_2$, and so the following minor modification is made: If we let $F_{\Delta} = \frac{(f_2 - f_1)}{f_s}$, and $F_1 = \frac{f_1}{f_s}$, then the zoom-DFT, $X_{z}[k]$ becomes: (Equation 5)

$$X_z[k] = e^{-j\frac{\pi F_{\Delta} k^2}{N}} \space \sum_{n=0}^{N-1} x_p[n]\space e^{-j\frac{\pi n^2}{N}} \space e^{-j 2\pi \space F_1 n}\space e^{j\frac{\pi F_{\Delta} (k-n)^2}{N}}$$

We can then simplify, if we let: (Equation 6)

$$a[u] = x_p[u]\space e^{-j\frac{\pi u^2}{N}} \space e^{-j 2\pi \space F_1 u} \\ b[u] = e^{j\frac{\pi F_{\Delta} u^2}{N}}$$

, where $u$ is just some general dummy variable, (you will see why I picked it later). Anyway, now finally, we simply have: (Equation 7)

$$X_z[k] = b^*[k] \space \sum_{n=0}^{N-1} a[n] \space b[k-n]$$

This, as we are told here, and here, page 183, is how the DFT can be re-written as a convolution.

Great! So far so good. The problem comes in interpretation vs implementation.

The problem:

My interpretation of (Equation 7), is that $a[u]$ is of length $N$, and $b[u]$ is also of length $N$, where we evaluate then for $u = 0,1,...N-1$. Then, we do a circular convolution of the series $a[u]$ and $b[u]$, to attain a series also of length $N$, (which is our desired DFT length), before we finally perform an element-by-element post-multiply with another series, also of length $N$. I dont so much care about post-multiply, that is not the point of this question. The point here is that $a[u]$ is length $N$, $b[u]$ is also length $N$, and $u$ for both of them is evaluated for $0 \leq u \leq N-1$, and then we do a circular convolution, modulo-$N$.

If you however now take this interpretation and implement it, you will not get the right answer. In fact, you will only ever get the right answer, if the $u$ variable for evaluation of $a[u]$ is taken from $u = 0,1,...N-1$, (same as above), BUT, the $u$ variable for evaluation of $b[u]$ is taken from $-(M-1) \leq u \leq N-1$. So now the series $b[u]$ is not length $N$ anymore, it is of length $N+M-1$. Then, if we do a modulo-($N+M-1$) circular convolution, and extract the indicies from $M$ to $M+N-1$, we will get the right answer.

...How, from equation-1, does one possibly get this 'correct' interpretation though? This, I cannot seem to explain, however I understand everything else.

FWIW, I have sat down and done the computation 'by hand', so I can 'see' why $b[u]$ MUST be taken from $-(M-1) \leq u \leq N-1$. (It would otherwise be impossible to compute the DFT for $k = 0,1,...N-1$). However I do not understand how one goes from (Equation 7), to this conclusion. Right now, to me, EQ-1 just looks like a garden variety circular convolution, with no hints as to the details for now $a[u]$ and $b[u]$ must be exactly evaluated.

Put another way - AFAIK, when we see equation-1, we simply assume that $a[u]$ and $b[u]$ are evaluated from $0 \leq u \leq N-1$, and then we do a circular convolution, modulo-$N$ - how/why then do we derive the proper evaluations for $a$ and $b$ from this equation??

Thanks!

-
Looking at the text, it states that the convolution is linear, not circular and that to do this, values of bn are required from -(M-1) to (N-1). Then I think the circular convolution and linear convolution become equivalent. –  user2718 Feb 17 '13 at 5:01
@BruceZenone Well, I know that this is indeed a linear convolution. However, what I do not understand is, how is it obvious from the equation, that b[u] must be evaluated from $-(M-1) \leq u \leq N-1$, and not $0 \leq u \leq M+N-1$? –  Mohammad Feb 17 '13 at 21:14

You're interpretation that a[u] and b[u] are both N length sequences is incorrect. a[u] is of length N because it is effectively truncated by the length of your input sequence. The period of b[u] is not necessarily N. Depending on the value of N, b[u] may not even be periodic, so what you have in Equation 7 is a linear convolution of two sequences. One sequence (a[u] has length N, the other (b[u]) has length unknown. The limits of summation in the convolution equation are strictly set by the length of $a[u]$ and don't imply circular convolution or anything about the length of sequence b[u].

Next you have to consider what range of values of b[u] are required to compute the convolution. Straight from the form of EQUATION 1, you see that b[u] in general must be defined in the range -[N-1] to N-1. The negative boundary is set by the most negative b[u] value required to calculate X[0] (i.e. you need b[0−(N-1)] for this calculation). The positive boundary is set by the maximum spectral step you want to evaluate in the chirp Z transform (X[K] max). From the way the question has been posed, X[k] is best interpreted as $X[N-1]$.

The reason your computations work with a range that only goes back as far as -[M-1] is because you started with an M length sequence and zero padded it up to length N which zeros out any b[u] values going back further than -[M-1].

There is an interesting write up of Chirp-Z along with Goertzel's algorithm that I think puts this in proper perspective: http://www.google.com/url?sa=t&rct=j&q=goertzel%20algorithm&source=web&cd=3&sqi=2&ved=0CEIQFjAC&url=http%3A%2F%2Focw.mit.edu%2Fcourses%2Felectrical-engineering-and-computer-science%2F6-341-discrete-time-signal-processing-fall-2005%2Flecture-notes%2Flec20.pdf&ei=rawjUd6sM-LE0QHJ2IGQAQ&usg=AFQjCNEFEo7R7VSmk5jWYon0f4WqZYpvzg&bvm=bv.42553238,d.dmQ

-
Bruce, FYI, I edited the question and put an equation label for every equation, so that discussing them becomes easier. Thanks for your answer. Also, let us just put some numbers to assist. Say $M = 10$, (original length signal), and $N = 20$, (DFT length desired). –  Mohammad Feb 19 '13 at 15:35
So, I have struggled to find the words that describe my confusion, while simultaneously keeping it succinct, and there are two parts: Part1) ...How does a person, looking at equation 7,...know before hand, the length of what 'b' is supposed to be? How is a person, supposed to look at eq-7, and say "ah! This is totally a M+N-1 = 29 length vector". Now, if I manage to convince myself of Part1 (and I think I can, because I worked it by hand, and can see that b must be an M+N-1 length vector for the evaluation of the DFT), then the Part2) question is, WHY must b be evaluated from u = -9 to 19? –  Mohammad Feb 19 '13 at 15:39
I think what I am trying to get at is, did the 'physics' of the problem, dictate to us what the 1) length of and 2)evaluation indicies for 'b' must be, or was this somehow obvious to a casual observer simply looking at equation-4, or equation-7? This is the root of it. –  Mohammad Feb 19 '13 at 15:40
So Bluestein employed a mathematical trick to rearrange the original DFT so an FFT could be exploited in computing a convolution instead of directly computing the DFT. Once the equations are massaged to reveal the convolution, nothing is obvious and a casual observer would be confused without carefully inspecting the convolution to identify what information is actually required (i.e. what values of b[u] are required) to properly carry out the computation. If you try to carry out the convolution, you immediately are hit with a need for values of b[u] going back to -[N-1]. –  user2718 Feb 19 '13 at 16:15
BTW - I see 3 common methods in use for doing a ZOOM FFT. 1) shift the frequency range of interest down towards DC, down sample and recalculate the FFT. 2) Zero pad the original data to increase frequency resolucion. 3) Use Bluestein's method and calculated only over the range of interest. You seem to be mixing options 2 and 3. –  user2718 Feb 19 '13 at 16:41