Solved

2D circular convolution (part 1)

Posted on 2004-11-07
1,064 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
Question by:mte01
    10 Comments
     
    LVL 31

    Expert Comment

    by:GwynforWeb
    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
    typo:-      that p+q-2 <= max(M,N)
    0
     
    LVL 31

    Expert Comment

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

    Author Comment

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

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone. Privacy Policy Terms of Use

    Featured Post

    Learn The Basics of Ethical Hacking & Pen Testing

    Computer and network security is one of the fastest growing and most essential industries in technology, meaning companies will pay big bucks for ethical hackers. This is the perfect course to leap into this lucrative career, learning how to use ethical hacking to reveal ...

    Have you ever thought of installing a power system that generates solar electricity to power your house? Some may say yes, while others may tell me no. But have you noticed that people around you are now considering installing such systems in their …
    We are taking giant steps in technological advances in the field of wireless telephony. At just 10 years since the advent of smartphones, it is crucial to examine the benefits and disadvantages that have been report to us.
    This Experts Exchange video Micro Tutorial shows how to tell Microsoft Office that a word is NOT spelled correctly. Microsoft Office has a built-in, main dictionary that is shared by Office apps, including Excel, Outlook, PowerPoint, and Word. When …
    In this sixth video of the Xpdf series, we discuss and demonstrate the PDFtoPNG utility, which converts a multi-page PDF file to separate color, grayscale, or monochrome PNG files, creating one PNG file for each page in the PDF. It does this via a c…

    877 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

    Need Help in Real-Time?

    Connect with top rated Experts

    21 Experts available now in Live!

    Get 1:1 Help Now