# Basic Confusion About the DFT and Convolution

I am learning DSP (with Digital Images) and I have some elementary confusion about the convolution between two discrete periodic signals. Specifically, I have learnt that when filtering an image, we apply convolution between the image (as discrete 2D signal) and a kernel filter. To visualize what happens in the frequency domain, we calculate the DFT of the image and the kernel and since we are convolving in the space domain, in the frequency domain this corresponds to a point per point multiplication of the two spectrums.

Now, the DFT assumes that the signal to transform is discrete AND periodic, resulting in a spectrum which is discrete and periodic. So here we are assuming that both the signal and the filter are discrete and periodic signals which repeat (usually) after the same M samples. My confusion is, how can convolution work for two discrete periodic signals? Since they repeat infinitely, applying the convolution usual definition as a flipped-shifting multiplication and sum, we would end up with an infinite sum in some single points if the signal to be filtered and the filter overlap. (Because they would overlap in the current repetition, in the next, and the next ad infinitum)

As an example in 1D, let $$x[n]$$ be our discrete function, which is periodic with a period of $$N$$ samples in the spatial domain. And let $$h[n]$$ be the filter impulse response in the spatial domain, also periodic of $$N$$ samples. We want to filter $$x[n]$$ with $$h[n]$$ and get the filtered signal $$y[n]$$. To do this we convolve these two periodic discrete signals:

$$y[n] = \sum_{k = -\infty}^\infty x[k]h[n - k]$$

However this convolution for a certain $$n$$, e.g. $$n=0$$, can lead to an $$y$$ which is infinite, as both $$x[n]$$ and $$h[n]$$ are periodic.

When we convolve between the image and the kernel, we are only considering one repetition of $$h[n]$$ and one repetition of $$x[n]$$. Like this:

$$y[n] = \sum_{k = 0}^{N-1} x[k]h[n - k]$$

Why can we do this? Will this still give us a periodic discrete $$y[n]$$ whose representation in the frequency domain is the point-per-point multiplication of the original signal and filter?

• Would it be possible to clarify what you are asking please? Maybe trying to use some notation so that we are clear which domain you have in mind when describing the question? The trigonometric functions extend to infinity. Their combination creates interference patches that tile the domain. You don't need to see all of it, you just look at one of them. – A_A Oct 18 '18 at 9:06
• @A_A I've updated the question with more details, is it clear enough what my doubt is now? – A. S. Oct 18 '18 at 9:46
• So, the question is about $h$ having a finite length? Or is it about applying the function? Just a quick check, $y[n]$ does what it says. Once you run the sum for $y$ you then do it for $y$ and then again for $y$ and so on. You don't just do $y$. The discrete convolution expression you provide is supposed to be applied to every sample of your $x[n]$ to produce the $y[n]$. – A_A Oct 18 '18 at 10:23
• @A_A Not exactly (see geo's answer) I was giving y just as an example and saying it may go to infinity (diverge), so my question was how are we supposed to convolve those two signals. – A. S. Oct 18 '18 at 10:57

As I understand your question, it boils down to: why is it ok, to take the convolution of a periodic signal only on an interval rather than over infinity? The DFT or discrete nature of the signal does not really play a role in your question. It merely provides the basis of assumung your two signals $$f$$ and $$g$$ as periodic, on the interval $$[0,T]$$ such that $$f(t+T)=f(t-T)=f(t)$$ and obviously $$g(t+T)=g(t-T)=g(t)$$.

Now assume that you define the convolution over the whole $$(-\infty,\infty)$$ like so: $$y(t):=(f\ast g)(t)=\int_{-\infty}^\infty d\tau\, f(t-\tau)g(\tau)$$

From the periodicity above follows that $$\int_{-\infty}^\infty d\tau\, f(t-\tau)g(\tau) = \int_{-\infty}^\infty d\tau\, f(t+T-\tau)g(\tau)$$ which you can intepret intuitevely to mean that the convolution should also be periodic. I write "intuitively" because the integral is divergent as we will see below.

Furthermore you can split the integral into a sum of integrals where $$\tau$$ goes over intervals of length $$T$$, such as $$[n\cdot T,(n+1)\cdot T]$$ with $$n$$ a signed integer number in $$(-\infty,\infty)$$. Doing that we have (after some simplifications)

$$\begin{eqnarray} y(t)&=&(f\ast g)(t)=\int_{-\infty}^\infty d\tau\, f(t-\tau)g(\tau) \\ &=&\sum_{n=-\infty}^\infty \int_0^Td\tau\,f(t-\tau)g(\tau) \end{eqnarray}$$ which would be divergent just because of the sum. Thus, the convolution of periodic functions produces a divergent integral. Sticking to this definition of the convolution would make it impossible to define the convolution like that. At least one of the functions must go to zero sufficiently fast, to produce a finite integral. Your periodic functios, however, will violate this decay condition. Thus it makes sense to window the functions with a rect function that captures all the information in one period.

So you see why it would make sense to define the cyclic convolution as just the integral

$$y(t)=\int_0^Td\tau\,f(t-\tau)g(\tau)$$

and use the periodic extension, since we already provided some intuition as to why setting $$y(t+T)=y(t)$$ makes sense. Thus the cyclic convolution carries all the information you would have from the regular definition but avoids the divergence due to the infinite sum. I hope this helps.

• Thanks for the clarification! This was what I was looking for. So the Inverse DFT of X(w) multiplied by G(w) in the frequency domain should give us a periodic extension of the cyclic convolution y(t) above in the time domain. Did I understand it correctly? – A. S. Oct 18 '18 at 10:54
• Unfortunately, this answer is incorrect in that the $y(t)$ as "defined" in the second displayed equation is the "value" of a divergent integral and so claims of periodicity such as $y(t) = y(t+T)$ cannot be made. – Dilip Sarwate Oct 18 '18 at 11:08
• @DilipSarwate thanks for the comment. I have edited my answer to be more mathematically rigorous. However, I disagree that my answer does not have value because of that because it provides a good and intuitive explanation to the question above. – geo Oct 18 '18 at 11:39
• @A.S., yes exactly. Also mind the comment of Dilip Sarwate, who correctly claims that the answer is not perfectly mathematically rigorous. Use it as an intuitive way of justifying your understanding. – geo Oct 18 '18 at 11:44
• @geo I still have one doubt though, in the last equation we are considering just the interval [0, T], so for example if we want to find y(0), in that equation it will have a finite value. However the “real” y(0), which is an infinite sum of the value we found, will still diverge. In image processing I guess we are interested in the real y(0) which should be the filtered image pixel, what’s the sense of it being infinite? – A. S. Oct 18 '18 at 11:51