Talk:Circular convolution

Cyclic convolution is already mentioned in convolution, and it's not clear that it needs its own article. In any case, it is logically independent of the DFT — which just happens to give a way to compute cyclic convolutions. Cyclic convolutions are a perfectly well defined mathematical operation, and are often useful in their own right; this article gives the impression that they are always a mere artifact, an unwanted side-effect of a particular FFT-based algorithm.

Moreover, cyclic boundary conditions are merely one possible boundary condition for convolution. One can also have e.g. even/odd boundary conditions of various types. (For example, every type of discrete cosine transform and discrete sine transform corresponds to convolutions with a different distinct boundary condition.)

—Steven G. Johnson 22:05, 9 December 2005 (UTC)

It is even more than "mentioned" in Discrete_Fourier_transform#Circular_convolution_theorem_and_cross-correlation_theorem. And neither article makes all the points made here. So what also is not clear is where these points should be made. There seemed to be a need for its own place to be.

You make some good points about the incompleteness of this article, but merging it into convolution will not address those issues. Instead, why not expand this article? That is actually what I was hoping for when I started it. I know there is a way to indicate that the article is a work in progress. Why not do that?

--Bob K 23:30, 9 December 2005 (UTC)

"Merge" means "add any missing stuff to the other article" not just "delete this article". Why not expand convolution? The various boundary conditions have so much in common, in how you define, understand, and apply them, that it makes more sense to me to describe them all in one place rather than having a separate article for each. —Steven G. Johnson 04:34, 10 December 2005 (UTC)

I understand, because that is what I would have done, except for the Discrete_Fourier_transform#Circular_convolution_theorem_and_cross-correlation_theorem article, which already has a better treatment than convolution. I am not opposed to merging all this stuff, but to be honest, it was much easier to use the powerful advantage of internal links that wikipedia offers. I confess to taking the easy way out of the dilemma. And I don't know as much about convolution as you apparently do, so I am not really in a position to write the definitive article anyway. This article was only meant to plug a small hole that seemed to be overlooked... a simple, graphic, layman's explanation. Demystification, because there is a lot of unnecessary misunderstanding about this relatively simple thing. If it serves as a catalyst for bigger and better things, that's fine too. But I am now satisfied. So that is a project for someone else. --Bob K 18:23, 11 December 2005 (UTC)

Are you really sure that the symmetric convolutions article - the article describing convolutions that result from the fact that "every type of discrete cosine transform and discrete sine transform corresponds to convolutions with a different distinct boundary condition" - has nothing to do with this article and should not be linked here? Chadernook (talk) 17:12, 13 June 2013 (UTC)

Yes. Although the "symmetric" article apparently depends (in small part) of the "circular" article, the converse is not true. BTW, the symmetric article has been flagged as "confusing or unclear" (and I agree) since 2009. Can you fix that? --Bob K (talk) 21:40, 13 June 2013 (UTC)

Periodic-extension definition

I'm not sure the definition of periodic extension given here is appropriate. In particular, it has the odd property that a periodic function does not have a periodic extension (the sum diverges)!

My impression is that a more conventional definition of the periodic extension of a function is to take some unit interval of the function, e.g, $[0,T]$, and repeat it periodically. Equivalently, it is an infinite summation as defined in the article, but applied to the function multiplied by a rectangular unit window function of support $[0,T]$. This definition has the property of being idempotent, i.e. the periodic extension of a periodic function is the same function.

Also, it might be more natural to define the circular convolution as the convolution of two periodic functions (e.g. this is how it is defined in Oppenheim & Schafer), and afterwards define the periodic extension of aperiodic functions so as to apply the cyclic convolution to them. Another clarification that is needed is that it is possible and natural to define the periodic extension and cyclic convolution for functions whose domain is only the $[0,T]$ interval (i.e. the functions aren't even defined outside that interval until you form their periodic extension, which isn't handled by the present definition).

Similar comments apply to the convolution article.

—Steven G. Johnson (talk) 21:19, 22 July 2008 (UTC)

O&S (1999) uses both Periodic convolution and Circular convolution for a summation over N terms of the product of two sequences. The only distinction is whether: (1) the sequences are N-periodic (infinitely long), or (2) they are just one period of each sequence, with one of the sequences addressed by modulo N indexing for the n-sample offsets. But:

$\sum _{m=0}^{N-1}x_{N}[m]\cdot y_{N}[n-m]=\sum _{m=-\infty }^{\infty }x_{N}[m]\cdot y[n-m]=\sum _{m=-\infty }^{\infty }x_{N}[n-m]\cdot y[m]\ \triangleq \ x_{N}*y,$

where $y[n]$ is any sequence for which $y_{N}[n]=\sum _{m=-\infty }^{\infty }y[n-mN].$

Note the difference between periodic summation and periodic extension... the length of $y$ is not limited to $N.$ But presumably because that is the most important/useful case, O&S imposes that condition, resulting in:

$\sum _{m=0}^{N-1}x_{N}[n-m]\cdot y[m],$   which they call periodic convolution, but it is just a special case of  $x_{N}*y.$

The article cites a couple of other authors who call  $x_{N}*y$  a circular convolution (of x and y), where:

$x_{N}[n]=\sum _{m=-\infty }^{\infty }x[n-mN].$

--Bob K (talk) 13:48, 16 June 2020 (UTC)

I'm probably in over my head, but I think the "best" answer is something less drastic than either of those suggestions. The periodic extension at Poisson_summation_formula#Definition, for instance, requires f(t) to be "integrable" but not of finite duration. And the frequency domain dual of the Poisson summation formula involves the periodic extension of a function's Fourier transform, whether or not it is band-limited. The overlap, of course, is how we usually explain aliasing.

Caveat: When I say "best", I only mean in the sense that necessary and sufficient is better than just sufficient. I'm not talking about how well it matches Oppenheim & Schafer, which is a different, but valid, metric. Truncating a sequence is merely a sufficient condition for periodically extending it, and I think O&S only concern themselves with truncated sequences.

--Bob K (talk) 13:31, 8 January 2009 (UTC)

Steven says "it might be more natural to define the circular convolution as...", but the most striking shortcoming to me about this article is that it never defines circular convolution at all. Look at the opening sentence:

A circular convolution of two Lebesgue integrable functions, for instance, is often expressed in terms of the periodic extension of one or both functions.

That's not a definition. It merely says how one specific instance of one is often expressed. It's like looking in a textbook and starting to read at the second paragraph Can anyone add a better introductory paragraph? I'm not competent to do so.

-- Timrprobocom (talk) 20:26, 2 April 2009 (UTC)

Periodic and Circular convolution

Indeed, this equation is wrong. Except for special cases, the convolution of two periodic functions results in an integral that blows up. This is usually fixed by simply defining it as the integral over one period. To get more intuition, one could define it as

$y(t)=\lim _{N\to \infty }{\frac {1}{N}}\int _{-N/2}^{N/2}x(\tau )h(t-\tau )d\tau .$

The nice thing about this definition is that the Fourier series of y(t) is simply the product of the Fourier series of h and x.

--Hpfister (talk) 23:22, 21 March 2013 (UTC)

To avoid unnecessary confusion, I added the caveat about existence (to the article), deleted the subsequently irrelevant 4-year-old discussion (here), and changed the title of this section (above).  For convenience, here is the sentence (in the article) that explains the difference between circular and periodic convolutions:

This operation is a periodic convolution of functions x_T and h_T.  When x_T is expressed as the periodic summation of another function, x, the same operation may also be referred to as a circular convolution of functions h and x.

The integral over one cycle represents them both. If the starting point is two periodic functions (such as two DTFTs), it's called periodic convolution. Circular convolution, on the other hand, can also be expressed in the normal (Euclidean) form (infinite limits).

--Bob K (talk) 13:43, 22 March 2013 (UTC)

I agree that the limit of the integral is a overkill. I have changed things a bit more to make this even clearer. I think Bob's edits made the statements correct but some of the unchanged parts were still confusing. Now, the conditions are stated more explicitly. One things that drew me to this page is that I am teaching a signals and systems class and the definition on the page does not match the standard textbook by Oppenheim and Willsky. Therefore, I also added a comment about the (standard?) normalization which is not used in this article.

PS: I must admit that I made my changes before seeing Bob's edit to the talk page. I wasn't expecting such a quick response. Now I am "watching" the page.

--Hpfister (talk) 17:39, 22 March 2013 (UTC)

References