[Webinar] Streamline your web hosting managementRegister Today

x
?
Solved

2D circular convolution (part 1)

Posted on 2004-11-07
10
Medium Priority
?
1,082 Views
Last Modified: 2008-02-26
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??
0
Comment
Question by:mte01
  • 5
  • 5
10 Comments
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 12519116
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
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 12519160
typo:-      that p+q-2 <= max(M,N)
0
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 12519544
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
Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

 
LVL 3

Author Comment

by:mte01
ID: 12519815
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
 
LVL 3

Author Comment

by:mte01
ID: 12519834
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
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 12520356
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
 
LVL 3

Author Comment

by:mte01
ID: 12520364
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
 
LVL 31

Accepted Solution

by:
GwynforWeb earned 2000 total points
ID: 12521071
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
 
LVL 3

Author Comment

by:mte01
ID: 12521276
Yes, now you have understood my question correctly,; I'll be looking into your answer to try to verify it.......
0
 
LVL 3

Author Comment

by:mte01
ID: 12521303
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

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

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

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
This article covers the basics of data encryption, what it is, how it works, and why it's important. If you've ever wondered what goes on when you "encrypt" data, you can look here to build a good foundation for your personal learning.
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Suggested Courses
Course of the Month9 days, 3 hours left to enroll

590 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question