2D circular convolution (part 1)

Two 2D sequences, each of which is 3 x 4 points in extent, are circularly convolved using (6 x 6)-point 2-D DFTs (Discrete Fourier Transforms). Which samples of the (6 x 6)-output array are identical to the samples of the linear convolution of the two input arrays & which are different??
LVL 3
mte01Asked:
Who is Participating?
 
GwynforWebCommented:
I think I am having problems understanding the question ( English is not my first  langauge)

If I now understand you right it is:-  what (x,y) values are the same if you convolute linearly or circularly. In which case

You can think of the convolution of A and B as placing the reflection of B on A  summing then shifing along/up to calculate the terms 1 by 1. For the 2 techniques to be the same in general you require the shifted matrix no to wrap around the region of have a zero interection with A in this case a  6x6 region.  

For a 6X6 region and a pair of 3X4 functions then you when you shift up you have no intersection with A  or do not  wrap around the top of the region  only at y=0,1,2,3.  As you move along the x  same occurs with the left hand side at x=0,1,2. So the points that would be the same are those in the 4 by 3 block in the corner.

(I have placed the corners of the functions A and B at (0,0) here)

Sorry if I still have problem wrong.

 
0
 
GwynforWebCommented:
Frstly could you confirm your defnition of circular definition (I have seen a number of defnitions). Do you mean that A & B have periocity M in the x and N in the y ie that

A(x+M,y+N) = A(x,y)

in which case the results are always the same as the FFT method of convolution since it assumes periodicty in its calculation. This would also mean that if you are defining linear convolultion by not assuming periodicity, and merely padding to the side with zeroes, that for periodicity not to be a factor you would require, if  A=p by q and  B=q by p,  that p+q-2 < max(M,N)

Or am I misunderstanding the question?

0
 
GwynforWebCommented:
typo:-      that p+q-2 <= max(M,N)
0
Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 
GwynforWebCommented:
better written as  for linear convolutionto be the same as circular p+q-1<max(M,N)

essentially if I am understanding right the functions when layed edge overlapping edge should not wrap round due to periodicty to intersect on the other side. But still I am not sure if I understand right.
0
 
mte01Author Commented:
Yes GwynWeb, your last comment is correct.........this is the difference between linear & periodic (circular) convolution. In circular conv., if we are convolving two P x Q sequences in an N x N DFT, we would pad zeros to each signal, so they would become N x N each, then we would apply the DFT to each signal, and multiply the results, and then apply the IDFT of the product, we would get the resultant signal, which would be the same if we were linearly convolving the two signals (the size would be different, but if the larger matrix was spatially aliased, the two result matrices would be identical.
0
 
mte01Author Commented:
For example, if we were convolving these two 2 x 2 signals:

A:

1 0
2 1

& B:
1 0
1 1

this would be the result of the circular convolution:

0 0 0 0
1 0 0 0
3 2 0 0
2 3 1 0

and this would be the result of the linear convolution:

3 2
4 3

The two results are the same if the larger matrix is spatially aliased to produce a 2 x 2 matrix.

Here because N >= P+Q-1, the number of points different between circular & linear convolution is 0 (like in 2D circular convolution (part 1))
0
 
GwynforWebCommented:
the only way I can see the linear and circular convolution (as definied above) being the same is when one of the functions is an impulse function ie a 1 by 1. I tried constucting examples in 1-D and always came back to an impulse function, same for 2x2 functions. Proving this in general would be hard .
0
 
mte01Author Commented:
No GwynforWeb, I don't want a case where they're equal, if you re-read my question, I only want the number of points which would be common between the 2 convolutions....
0
 
mte01Author Commented:
Yes, now you have understood my question correctly,; I'll be looking into your answer to try to verify it.......
0
 
mte01Author Commented:
Yes, thinking in a reasonable manner, your answer seems to be the perfect correct answer, but I was not able to prove it (It's hard to do so in the 1st place because you are doing it for two general inputs, so I think your explanation would be enough)........Good Work!!
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.