Basic Confusion About the DFT and Convolution

Question

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[0]$ 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?

Answer 1

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.