Hello forum, another basic questions, but you experts are better than any book. Give two finite sequences X and Y of duration, respectively N and M samples, the convolution will be a new sequence G of length M+N-1 samples. that said, what is the wraparound error? The discrete convolution assumes that both X and Y are periodic sequences. (That way we can approximate the convolution integral whose limits are + and - infinity in the continuous time domain). Both X and Y need to have the same period P however.Why? I know that P can be: P=M+N-1 P>M+N-1 P<M+N-1 What happens if P<M+N-1? Wraparound error.....What is it? Do I need to worry or does matlab take care of it when it performs conv(X,Y)? thanks fisico32
circular convolution and wraparound error....
Started by ●May 12, 2010
Reply by ●May 12, 20102010-05-12
On 5/12/2010 3:33 PM, fisico32 wrote:> Hello forum, > > another basic questions, but you experts are better than any book. > > Give two finite sequences X and Y of duration, respectively N and M > samples, the convolution will be a new sequence G of length M+N-1 samples. > > that said, what is the wraparound error? > > The discrete convolution assumes that both X and Y are periodic sequences. > > (That way we can approximate the convolution integral whose limits are + > and - infinity in the continuous time domain). > > Both X and Y need to have the same period P however.Why? > > I know that P can be: > > P=M+N-1 > P>M+N-1 > P<M+N-1 > > What happens if P<M+N-1? Wraparound error.....What is it? Do I need to > worry or does matlab take care of it when it performs conv(X,Y)?Forget the interior magic of Matlab. Do a simple case by hand and you will see that there is no wraparound error. I think you are confused by a processing trick: when using an FFT to perform fast convolution, the result is circular convolution. If enough zeros are added to the ends, circular and linear convolution give numerically the same result. Convolve these two time sequences and tell me what you call wraparound error: 1 3 5 7 6 4 2 and 5 2 1. (I know they aren't the same length. They don't need to be.) Like any tool, Matlab is an idiot. If you let it think for you, you become an idiot too. Jerry -- "I view the progress of science as ... the slow erosion of the tendency to dichotomize." --Barbara Smuts, U. Mich. �����������������������������������������������������������������������
Reply by ●May 12, 20102010-05-12
On 5/12/2010 3:53 PM, Jerry Avins wrote:> On 5/12/2010 3:33 PM, fisico32 wrote: >> Hello forum, >> >> another basic questions, but you experts are better than any book. >> >> Give two finite sequences X and Y of duration, respectively N and M >> samples, the convolution will be a new sequence G of length M+N-1 >> samples. >> >> that said, what is the wraparound error? >> >> The discrete convolution assumes that both X and Y are periodic >> sequences. >> >> (That way we can approximate the convolution integral whose limits are + >> and - infinity in the continuous time domain). >> >> Both X and Y need to have the same period P however.Why? >> >> I know that P can be: >> >> P=M+N-1 >> P>M+N-1 >> P<M+N-1 >> >> What happens if P<M+N-1? Wraparound error.....What is it? Do I need to >> worry or does matlab take care of it when it performs conv(X,Y)? > > Forget the interior magic of Matlab. Do a simple case by hand and you > will see that there is no wraparound error. I think you are confused by > a processing trick: when using an FFT to perform fast convolution, the > result is circular convolution. If enough zeros are added to the ends, > circular and linear convolution give numerically the same result. > > Convolve these two time sequences and tell me what you call wraparound > error: 1 3 5 7 6 4 2 and 5 2 1. (I know they aren't the same length. > They don't need to be.) > > Like any tool, Matlab is an idiot. If you let it think for you, you > become an idiot too.You didn't mention circular convolution in the body of the text, so I missed that. Even circular convolution can be performed with sequences of different length, but one-pass fast convolution, whether circular or not, requires (possibly zero padded) sequences of the same length. Convolution in the time domain is multiplication in the frequency domain. Since the multiplication is to be done term by term, the sequences must be the same length. When the lengths are different, one does linear convolution with overlap-add or overlap-save. Jerry -- "I view the progress of science as ... the slow erosion of the tendency to dichotomize." --Barbara Smuts, U. Mich. �����������������������������������������������������������������������
Reply by ●May 12, 20102010-05-12
Yes, the issue was that the result from the temporal convolution is different the result obtained by first taking the DFT of both sequence, multiply the two and take the IDFT.... In the second case we obtain the circular, cyclic convolution....>On 5/12/2010 3:33 PM, fisico32 wrote: >> Hello forum, >> >> another basic questions, but you experts are better than any book. >> >> Give two finite sequences X and Y of duration, respectively N and M >> samples, the convolution will be a new sequence G of length M+N-1samples.>> >> that said, what is the wraparound error? >> >> The discrete convolution assumes that both X and Y are periodicsequences.>> >> (That way we can approximate the convolution integral whose limits are+>> and - infinity in the continuous time domain). >> >> Both X and Y need to have the same period P however.Why? >> >> I know that P can be: >> >> P=M+N-1 >> P>M+N-1 >> P<M+N-1 >> >> What happens if P<M+N-1? Wraparound error.....What is it? Do I need to >> worry or does matlab take care of it when it performs conv(X,Y)? > >Forget the interior magic of Matlab. Do a simple case by hand and you >will see that there is no wraparound error. I think you are confused by >a processing trick: when using an FFT to perform fast convolution, the >result is circular convolution. If enough zeros are added to the ends, >circular and linear convolution give numerically the same result. > >Convolve these two time sequences and tell me what you call wraparound >error: 1 3 5 7 6 4 2 and 5 2 1. (I know they aren't the same length. >They don't need to be.) > >Like any tool, Matlab is an idiot. If you let it think for you, you >become an idiot too. > >Jerry >-- >"I view the progress of science as ... the slow erosion of the tendency > to dichotomize." --Barbara Smuts, U. Mich. >����������������������������������������������������������������������� >
Reply by ●May 12, 20102010-05-12
On 5/12/2010 5:31 PM, fisico32 wrote:> Yes, > the issue was that the result from the temporal convolution is different > the result obtained by first taking the DFT of both sequence, multiply the > two and take the IDFT.... > In the second case we obtain the circular, cyclic convolution....Yes what? Both results are the same if, for the DFT, the sequences are suitably zero extended, then the extra zeros removed. Jerry -- "I view the progress of science as ... the slow erosion of the tendency to dichotomize." --Barbara Smuts, U. Mich.
