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!
