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??
typo:- that p+q-2 <= max(M,N)
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.
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.
ASKER
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.
ASKER
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))
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))
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 .
ASKER
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....
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Yes, now you have understood my question correctly,; I'll be looking into your answer to try to verify it.......
ASKER
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!!
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?