Prev: Literature on tracking
Next: open source projects
From: fisico32 on 12 May 2010 15:33
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
From: Jerry Avins on 12 May 2010 15:53
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.
�����������������������������������������������������������������������
From: Jerry Avins on 12 May 2010 16:13
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.
�����������������������������������������������������������������������
From: fisico32 on 12 May 2010 17:31
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-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.
>�����������������������������������������������������������������������
>
From: Jerry Avins on 12 May 2010 20:15
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.
 | 
Pages: 1
Prev: Literature on tracking
Next: open source projects