reconciling conv in time domain = multiplication in freq domain

Hi,

I'm not that experienced with DSP, but I understand that convolution in the
time domain is equivalent to multiplication in the frequency domain. I'm
having trouble reconciling this in my mind at least with the following
thought experiment:

If I have 8 samples in the time domain and take an FFT, I obtain 8 samples
(8 frequency bins) in the frequency domain. If I multiple this FFT by an 8
sample filter, I end up with an 8-sample filtered-FFT spectrum. If I then
IFFT this filtered-FFT spectrum, I obtain 8 time-domain samples.

How does this work using convolution? If I take an IFFT of the 8 sample
filter above, I end up with an 8 sample time-response for the filter. If I
convolve these two waveforms, I end up with 2x8-1 = 15 samples, which is
obviously a different result than my above thinking using the frequency
domain. Can someone help me understand where my thinking is off? I must be
missing something fundamental.

Thanks in advance! -ggk

On Sep 17, 4:48&#4294967295;am, "all4dsp" <all4dsp@n_o_s_p_a_m.comcast.net> wrote:
> Hi,
>
> I'm not that experienced with DSP, but I understand that convolution in the
> time domain is equivalent to multiplication in the frequency domain. I'm
> having trouble reconciling this in my mind at least with the following
> thought experiment:
>
> If I have 8 samples in the time domain and take an FFT, I obtain 8 samples
> (8 frequency bins) in the frequency domain. If I multiple this FFT by an 8
> sample filter, I end up with an 8-sample filtered-FFT spectrum. If I then
> IFFT this filtered-FFT spectrum, I obtain 8 time-domain samples.
>
> How does this work using convolution? If I take an IFFT of the 8 sample
> filter above, I end up with an 8 sample time-response for the filter. If I
> convolve these two waveforms, I end up with 2x8-1 = 15 samples, which is
> obviously a different result than my above thinking using the frequency
> domain. Can someone help me understand where my thinking is off? I must be
> missing something fundamental.

Check out 'circular convolution'.

The problem is that you use the FFT, which works on sequences
of finite length, and not the DTFT, which handles infinitely
long sequences. With the FFT you need to ensure up front that
the end result fits inside the FFT length.

Rune

>On Sep 17, 4:48=A0am, "all4dsp" <all4dsp@n_o_s_p_a_m.comcast.net> wrote:
>> Hi,
>>
>> I'm not that experienced with DSP, but I understand that convolution in
t=
>he
>> time domain is equivalent to multiplication in the frequency domain.
I'm
>> having trouble reconciling this in my mind at least with the following
>> thought experiment:
>>
>> If I have 8 samples in the time domain and take an FFT, I obtain 8
sample=
>s
>> (8 frequency bins) in the frequency domain. If I multiple this FFT by an
=
>8
>> sample filter, I end up with an 8-sample filtered-FFT spectrum. If I
then
>> IFFT this filtered-FFT spectrum, I obtain 8 time-domain samples.
>>
>> How does this work using convolution? If I take an IFFT of the 8 sample
>> filter above, I end up with an 8 sample time-response for the filter. If
=
>I
>> convolve these two waveforms, I end up with 2x8-1 =3D 15 samples, which
i=
>s
>> obviously a different result than my above thinking using the frequency
>> domain. Can someone help me understand where my thinking is off? I must
b=
>e
>> missing something fundamental.
>
>Check out 'circular convolution'.
>
>The problem is that you use the FFT, which works on sequences
>of finite length, and not the DTFT, which handles infinitely
>long sequences. With the FFT you need to ensure up front that
>the end result fits inside the FFT length.
>
>Rune

OK, I'm looking at http://www.dspguide.com/ch9/3.htm which helps. So, my
thinking of the time-domain seems correct... the result should be 15
samples long. It seems my understanding of how things work above in the
frequency domain is wrong, and leads to circular convolution. 

To eliminate circular convolution, I should zero-pad the 8 sample
time-domain sequence with a number of zeros = (number of samples in filter)
- 1, or 8-1 = 7. Thus the "modified" time-domain sequence should be the
original 8 samples plus 7 zeros. The filter should also add zeros to be the
same length as this "modified" time-domain sequence (15 samples). Thus, the
FFT of both modified time-domain sequence and modified filter will both be
15 frequency-bins long. The product of these spectra will also be 15 bins
long, and thus the IFFT of this will provide a filtered time-domain
waveform of 15 samples long (and NO circular convolution).

Assuming this is the correct understanding, I'm still left with a dilemma:
the first half of the filtered time-domain waveform is filling up the
filter and the last half of the filtered time-domain waveform is emptying
the filter and there's no steady-state response.

Must I then add Z number of zeros to the modified time-domain sequence and
the modified filter above so that the IFFT of the product of these spectras
returns Z number of samples in the time-domain representing a steady-state
response?

>>On Sep 17, 4:48=A0am, "all4dsp" <all4dsp@n_o_s_p_a_m.comcast.net> wrote:
>>> Hi,
>>>
>>> I'm not that experienced with DSP, but I understand that convolution
in
>t=
>>he
>>> time domain is equivalent to multiplication in the frequency domain.
>I'm
>>> having trouble reconciling this in my mind at least with the following
>>> thought experiment:
>>>
>>> If I have 8 samples in the time domain and take an FFT, I obtain 8
>sample=
>>s
>>> (8 frequency bins) in the frequency domain. If I multiple this FFT by
an
>=
>>8
>>> sample filter, I end up with an 8-sample filtered-FFT spectrum. If I
>then
>>> IFFT this filtered-FFT spectrum, I obtain 8 time-domain samples.
>>>
>>> How does this work using convolution? If I take an IFFT of the 8
sample
>>> filter above, I end up with an 8 sample time-response for the filter.
If
>=
>>I
>>> convolve these two waveforms, I end up with 2x8-1 =3D 15 samples,
which
>i=
>>s
>>> obviously a different result than my above thinking using the
frequency
>>> domain. Can someone help me understand where my thinking is off? I
must
>b=
>>e
>>> missing something fundamental.
>>
>>Check out 'circular convolution'.
>>
>>The problem is that you use the FFT, which works on sequences
>>of finite length, and not the DTFT, which handles infinitely
>>long sequences. With the FFT you need to ensure up front that
>>the end result fits inside the FFT length.
>>
>>Rune
>
>OK, I'm looking at http://www.dspguide.com/ch9/3.htm which helps. So, my
>thinking of the time-domain seems correct... the result should be 15
>samples long. It seems my understanding of how things work above in the
>frequency domain is wrong, and leads to circular convolution. 
>
>To eliminate circular convolution, I should zero-pad the 8 sample
>time-domain sequence with a number of zeros = (number of samples in
filter)
>- 1, or 8-1 = 7. Thus the "modified" time-domain sequence should be the
>original 8 samples plus 7 zeros. The filter should also add zeros to be
the
>same length as this "modified" time-domain sequence (15 samples). Thus,
the
>FFT of both modified time-domain sequence and modified filter will both
be
>15 frequency-bins long. The product of these spectra will also be 15 bins
>long, and thus the IFFT of this will provide a filtered time-domain
>waveform of 15 samples long (and NO circular convolution).
>
>Assuming this is the correct understanding, I'm still left with a
dilemma:
>the first half of the filtered time-domain waveform is filling up the
>filter and the last half of the filtered time-domain waveform is emptying
>the filter and there's no steady-state response.
>
>Must I then add Z number of zeros to the modified time-domain sequence
and
>the modified filter above so that the IFFT of the product of these
spectras
>returns Z number of samples in the time-domain representing a
steady-state
>response?
>

Hmm, no it seems adding Z zeros is no substitute for real data so this
won't work. Only cutting the length of the original filter will provide any
length of steady-state transient response.

On 09/16/2010 08:35 PM, all4dsp wrote:
>> On Sep 17, 4:48=A0am, "all4dsp"<all4dsp@n_o_s_p_a_m.comcast.net>  wrote:
>>> Hi,
>>>
>>> I'm not that experienced with DSP, but I understand that convolution in
> t=
>> he
>>> time domain is equivalent to multiplication in the frequency domain.
> I'm
>>> having trouble reconciling this in my mind at least with the following
>>> thought experiment:
>>>
>>> If I have 8 samples in the time domain and take an FFT, I obtain 8
> sample=
>> s
>>> (8 frequency bins) in the frequency domain. If I multiple this FFT by an
> =
>> 8
>>> sample filter, I end up with an 8-sample filtered-FFT spectrum. If I
> then
>>> IFFT this filtered-FFT spectrum, I obtain 8 time-domain samples.
>>>
>>> How does this work using convolution? If I take an IFFT of the 8 sample
>>> filter above, I end up with an 8 sample time-response for the filter. If
> =
>> I
>>> convolve these two waveforms, I end up with 2x8-1 =3D 15 samples, which
> i=
>> s
>>> obviously a different result than my above thinking using the frequency
>>> domain. Can someone help me understand where my thinking is off? I must
> b=
>> e
>>> missing something fundamental.
>>
>> Check out 'circular convolution'.
>>
>> The problem is that you use the FFT, which works on sequences
>> of finite length, and not the DTFT, which handles infinitely
>> long sequences. With the FFT you need to ensure up front that
>> the end result fits inside the FFT length.
>>
>> Rune
>
> OK, I'm looking at http://www.dspguide.com/ch9/3.htm which helps. So, my
> thinking of the time-domain seems correct... the result should be 15
> samples long. It seems my understanding of how things work above in the
> frequency domain is wrong, and leads to circular convolution.
>
> To eliminate circular convolution, I should zero-pad the 8 sample
> time-domain sequence with a number of zeros = (number of samples in filter)
> - 1, or 8-1 = 7. Thus the "modified" time-domain sequence should be the
> original 8 samples plus 7 zeros. The filter should also add zeros to be the
> same length as this "modified" time-domain sequence (15 samples). Thus, the
> FFT of both modified time-domain sequence and modified filter will both be
> 15 frequency-bins long. The product of these spectra will also be 15 bins
> long, and thus the IFFT of this will provide a filtered time-domain
> waveform of 15 samples long (and NO circular convolution).
>
> Assuming this is the correct understanding, I'm still left with a dilemma:
> the first half of the filtered time-domain waveform is filling up the
> filter and the last half of the filtered time-domain waveform is emptying
> the filter and there's no steady-state response.
>
> Must I then add Z number of zeros to the modified time-domain sequence and
> the modified filter above so that the IFFT of the product of these spectras
> returns Z number of samples in the time-domain representing a steady-state
> response?
>
You need to learn the math behind the FFT, and you need to learn the 
other Fourier transforms.  Then you'll understand the very narrow 
conditions under which the FFT is exact, and how it is that feeding 
real-world data to an FFT causes an implicit approximation.

Once you know that, then you'll understand a lot of the song and dance 
that you have to do whenever you choose to use the FFT.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" was written for you.
See details at http://www.wescottdesign.com/actfes/actfes.html

On Sep 17, 12:36&#4294967295;am, Tim Wescott <t...@seemywebsite.com> wrote:
> On 09/16/2010 08:35 PM, all4dsp wrote:
>
> >> On Sep 17, 4:48=A0am, "all4dsp"<all4dsp@n_o_s_p_a_m.comcast.net> &#4294967295;wrote:
> >>> Hi,
>
> >>> I'm not that experienced with DSP, but I understand that convolution in
> > t=
> >> he
> >>> time domain is equivalent to multiplication in the frequency domain.
> > I'm
> >>> having trouble reconciling this in my mind at least with the following
> >>> thought experiment:
>
> >>> If I have 8 samples in the time domain and take an FFT, I obtain 8
> > sample=
> >> s
> >>> (8 frequency bins) in the frequency domain. If I multiple this FFT by an
> > =
> >> 8
> >>> sample filter, I end up with an 8-sample filtered-FFT spectrum. If I
> > then
> >>> IFFT this filtered-FFT spectrum, I obtain 8 time-domain samples.
>
> >>> How does this work using convolution? If I take an IFFT of the 8 sample
> >>> filter above, I end up with an 8 sample time-response for the filter. If
> > =
> >> I
> >>> convolve these two waveforms, I end up with 2x8-1 =3D 15 samples, which
> > i=
> >> s
> >>> obviously a different result than my above thinking using the frequency
> >>> domain. Can someone help me understand where my thinking is off? I must
> > b=
> >> e
> >>> missing something fundamental.
>
> >> Check out 'circular convolution'.
>
> >> The problem is that you use the FFT, which works on sequences
> >> of finite length, and not the DTFT, which handles infinitely
> >> long sequences. With the FFT you need to ensure up front that
> >> the end result fits inside the FFT length.
>
> >> Rune
>
> > OK, I'm looking athttp://www.dspguide.com/ch9/3.htmwhich helps. So, my
> > thinking of the time-domain seems correct... the result should be 15
> > samples long. It seems my understanding of how things work above in the
> > frequency domain is wrong, and leads to circular convolution.
>
> > To eliminate circular convolution, I should zero-pad the 8 sample
> > time-domain sequence with a number of zeros = (number of samples in filter)
> > - 1, or 8-1 = 7. Thus the "modified" time-domain sequence should be the
> > original 8 samples plus 7 zeros. The filter should also add zeros to be the
> > same length as this "modified" time-domain sequence (15 samples). Thus, the
> > FFT of both modified time-domain sequence and modified filter will both be
> > 15 frequency-bins long. The product of these spectra will also be 15 bins
> > long, and thus the IFFT of this will provide a filtered time-domain
> > waveform of 15 samples long (and NO circular convolution).
>
> > Assuming this is the correct understanding, I'm still left with a dilemma:
> > the first half of the filtered time-domain waveform is filling up the
> > filter and the last half of the filtered time-domain waveform is emptying
> > the filter and there's no steady-state response.
>
> > Must I then add Z number of zeros to the modified time-domain sequence and
> > the modified filter above so that the IFFT of the product of these spectras
> > returns Z number of samples in the time-domain representing a steady-state
> > response?
>
> You need to learn the math behind the FFT, and you need to learn the
> other Fourier transforms. &#4294967295;Then you'll understand the very narrow
> conditions under which the FFT is exact, and how it is that feeding
> real-world data to an FFT causes an implicit approximation.
>
> Once you know that, then you'll understand a lot of the song and dance
> that you have to do whenever you choose to use the FFT.

actually i would say that all4 needs to learn the more fundamental
math of what we usually call the "DFT" (Discrete Fourier Transform").
the FFT is a "fast" method of computing the DFT, but the math behind
this circular convolution thing is fundamental of the DFT, whether
it's computed fast or not.  all4dsp does not need (yet) to learn about
the DIT or DIF (decimation in time or frequency) algs or any of this
Cooley-Tukey-Gauss stuff.

i would add something else to what Rune said:  The DFT or iDFT operate
on periodic (or circular) discrete-time or discrete-frequency
sequences only.  they are infinitely long, but fully describable by
one period of the discrete sequence, which is a finite set of
numbers.  that finite set of numbers that go into or come out of the
DFT (or FFT) represent *one* period of the periodic sequence.  but you
should remember that beyond x[0] and x[N-1] there are implied samples
that are the periodic extension of those between x[-1] and x[N].  you
only specify {x[0], x[1], ... x[N-1]}, but they are part of an
infinite and periodic sequence (and will be treated as such by the
DFT) such that

    x[n+N] = x[n]    for  -inf < n < +inf

*everything* that you do to these sequences with the DFT can be
thought of as happening to the periodic extension of those sequences.
that makes all of these operations circular, but if the operation is a
simple one (like adding or scaling the data) the need to consider any
circular effect is not apparent.  but if you delay or convolve (or
their counterparts in the other domain), the circular or periodic
nature is apparent.

r b-j

On 09/17/2010 06:44 AM, robert bristow-johnson wrote:
> On Sep 17, 12:36 am, Tim Wescott<t...@seemywebsite.com>  wrote:
>> On 09/16/2010 08:35 PM, all4dsp wrote:
>>
>>>> On Sep 17, 4:48=A0am, "all4dsp"<all4dsp@n_o_s_p_a_m.comcast.net>    wrote:
>>>>> Hi,
>>
>>>>> I'm not that experienced with DSP, but I understand that convolution in
>>> t=
>>>> he
>>>>> time domain is equivalent to multiplication in the frequency domain.
>>> I'm
>>>>> having trouble reconciling this in my mind at least with the following
>>>>> thought experiment:
>>
>>>>> If I have 8 samples in the time domain and take an FFT, I obtain 8
>>> sample=
>>>> s
>>>>> (8 frequency bins) in the frequency domain. If I multiple this FFT by an
>>> =
>>>> 8
>>>>> sample filter, I end up with an 8-sample filtered-FFT spectrum. If I
>>> then
>>>>> IFFT this filtered-FFT spectrum, I obtain 8 time-domain samples.
>>
>>>>> How does this work using convolution? If I take an IFFT of the 8 sample
>>>>> filter above, I end up with an 8 sample time-response for the filter. If
>>> =
>>>> I
>>>>> convolve these two waveforms, I end up with 2x8-1 =3D 15 samples, which
>>> i=
>>>> s
>>>>> obviously a different result than my above thinking using the frequency
>>>>> domain. Can someone help me understand where my thinking is off? I must
>>> b=
>>>> e
>>>>> missing something fundamental.
>>
>>>> Check out 'circular convolution'.
>>
>>>> The problem is that you use the FFT, which works on sequences
>>>> of finite length, and not the DTFT, which handles infinitely
>>>> long sequences. With the FFT you need to ensure up front that
>>>> the end result fits inside the FFT length.
>>
>>>> Rune
>>
>>> OK, I'm looking athttp://www.dspguide.com/ch9/3.htmwhich helps. So, my
>>> thinking of the time-domain seems correct... the result should be 15
>>> samples long. It seems my understanding of how things work above in the
>>> frequency domain is wrong, and leads to circular convolution.
>>
>>> To eliminate circular convolution, I should zero-pad the 8 sample
>>> time-domain sequence with a number of zeros = (number of samples in filter)
>>> - 1, or 8-1 = 7. Thus the "modified" time-domain sequence should be the
>>> original 8 samples plus 7 zeros. The filter should also add zeros to be the
>>> same length as this "modified" time-domain sequence (15 samples). Thus, the
>>> FFT of both modified time-domain sequence and modified filter will both be
>>> 15 frequency-bins long. The product of these spectra will also be 15 bins
>>> long, and thus the IFFT of this will provide a filtered time-domain
>>> waveform of 15 samples long (and NO circular convolution).
>>
>>> Assuming this is the correct understanding, I'm still left with a dilemma:
>>> the first half of the filtered time-domain waveform is filling up the
>>> filter and the last half of the filtered time-domain waveform is emptying
>>> the filter and there's no steady-state response.
>>
>>> Must I then add Z number of zeros to the modified time-domain sequence and
>>> the modified filter above so that the IFFT of the product of these spectras
>>> returns Z number of samples in the time-domain representing a steady-state
>>> response?
>>
>> You need to learn the math behind the FFT, and you need to learn the
>> other Fourier transforms.  Then you'll understand the very narrow
>> conditions under which the FFT is exact, and how it is that feeding
>> real-world data to an FFT causes an implicit approximation.
>>
>> Once you know that, then you'll understand a lot of the song and dance
>> that you have to do whenever you choose to use the FFT.
>
> actually i would say that all4 needs to learn the more fundamental
> math of what we usually call the "DFT" (Discrete Fourier Transform").
> the FFT is a "fast" method of computing the DFT, but the math behind
> this circular convolution thing is fundamental of the DFT, whether
> it's computed fast or not.  all4dsp does not need (yet) to learn about
> the DIT or DIF (decimation in time or frequency) algs or any of this
> Cooley-Tukey-Gauss stuff.
>
> i would add something else to what Rune said:  The DFT or iDFT operate
> on periodic (or circular) discrete-time or discrete-frequency
> sequences only.  they are infinitely long, but fully describable by
> one period of the discrete sequence, which is a finite set of
> numbers.  that finite set of numbers that go into or come out of the
> DFT (or FFT) represent *one* period of the periodic sequence.  but you
> should remember that beyond x[0] and x[N-1] there are implied samples
> that are the periodic extension of those between x[-1] and x[N].  you
> only specify {x[0], x[1], ... x[N-1]}, but they are part of an
> infinite and periodic sequence (and will be treated as such by the
> DFT) such that
>
>      x[n+N] = x[n]    for  -inf<  n<  +inf
>
> *everything* that you do to these sequences with the DFT can be
> thought of as happening to the periodic extension of those sequences.
> that makes all of these operations circular, but if the operation is a
> simple one (like adding or scaling the data) the need to consider any
> circular effect is not apparent.  but if you delay or convolve (or
> their counterparts in the other domain), the circular or periodic
> nature is apparent.

That's pretty much what I would have said, had I taken the time for a 
long answer.  And yes -- it's more important to understand how the DFT 
relates to the continuous-time nonperiodic Fourier transform than it is 
to understand how the FFT algorithms speed up the DFT.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" was written for you.
See details at http://www.wescottdesign.com/actfes/actfes.html

>On 09/17/2010 06:44 AM, robert bristow-johnson wrote:
>> On Sep 17, 12:36 am, Tim Wescott<t...@seemywebsite.com>  wrote:
>>> On 09/16/2010 08:35 PM, all4dsp wrote:
>>>
>>>>> On Sep 17, 4:48=A0am, "all4dsp"<all4dsp@n_o_s_p_a_m.comcast.net>   
wrote:
>>>>>> Hi,
>>>
>>>>>> I'm not that experienced with DSP, but I understand that convolution
in
>>>> t=
>>>>> he
>>>>>> time domain is equivalent to multiplication in the frequency
domain.
>>>> I'm
>>>>>> having trouble reconciling this in my mind at least with the
following
>>>>>> thought experiment:
>>>
>>>>>> If I have 8 samples in the time domain and take an FFT, I obtain 8
>>>> sample=
>>>>> s
>>>>>> (8 frequency bins) in the frequency domain. If I multiple this FFT
by an
>>>> =
>>>>> 8
>>>>>> sample filter, I end up with an 8-sample filtered-FFT spectrum. If
I
>>>> then
>>>>>> IFFT this filtered-FFT spectrum, I obtain 8 time-domain samples.
>>>
>>>>>> How does this work using convolution? If I take an IFFT of the 8
sample
>>>>>> filter above, I end up with an 8 sample time-response for the
filter. If
>>>> =
>>>>> I
>>>>>> convolve these two waveforms, I end up with 2x8-1 =3D 15 samples,
which
>>>> i=
>>>>> s
>>>>>> obviously a different result than my above thinking using the
frequency
>>>>>> domain. Can someone help me understand where my thinking is off? I
must
>>>> b=
>>>>> e
>>>>>> missing something fundamental.
>>>
>>>>> Check out 'circular convolution'.
>>>
>>>>> The problem is that you use the FFT, which works on sequences
>>>>> of finite length, and not the DTFT, which handles infinitely
>>>>> long sequences. With the FFT you need to ensure up front that
>>>>> the end result fits inside the FFT length.
>>>
>>>>> Rune
>>>
>>>> OK, I'm looking athttp://www.dspguide.com/ch9/3.htmwhich helps. So,
my
>>>> thinking of the time-domain seems correct... the result should be 15
>>>> samples long. It seems my understanding of how things work above in
the
>>>> frequency domain is wrong, and leads to circular convolution.
>>>
>>>> To eliminate circular convolution, I should zero-pad the 8 sample
>>>> time-domain sequence with a number of zeros = (number of samples in
filter)
>>>> - 1, or 8-1 = 7. Thus the "modified" time-domain sequence should be
the
>>>> original 8 samples plus 7 zeros. The filter should also add zeros to
be the
>>>> same length as this "modified" time-domain sequence (15 samples).
Thus, the
>>>> FFT of both modified time-domain sequence and modified filter will
both be
>>>> 15 frequency-bins long. The product of these spectra will also be 15
bins
>>>> long, and thus the IFFT of this will provide a filtered time-domain
>>>> waveform of 15 samples long (and NO circular convolution).
>>>
>>>> Assuming this is the correct understanding, I'm still left with a
dilemma:
>>>> the first half of the filtered time-domain waveform is filling up the
>>>> filter and the last half of the filtered time-domain waveform is
emptying
>>>> the filter and there's no steady-state response.
>>>
>>>> Must I then add Z number of zeros to the modified time-domain sequence
and
>>>> the modified filter above so that the IFFT of the product of these
spectras
>>>> returns Z number of samples in the time-domain representing a
steady-state
>>>> response?
>>>
>>> You need to learn the math behind the FFT, and you need to learn the
>>> other Fourier transforms.  Then you'll understand the very narrow
>>> conditions under which the FFT is exact, and how it is that feeding
>>> real-world data to an FFT causes an implicit approximation.
>>>
>>> Once you know that, then you'll understand a lot of the song and dance
>>> that you have to do whenever you choose to use the FFT.
>>
>> actually i would say that all4 needs to learn the more fundamental
>> math of what we usually call the "DFT" (Discrete Fourier Transform").
>> the FFT is a "fast" method of computing the DFT, but the math behind
>> this circular convolution thing is fundamental of the DFT, whether
>> it's computed fast or not.  all4dsp does not need (yet) to learn about
>> the DIT or DIF (decimation in time or frequency) algs or any of this
>> Cooley-Tukey-Gauss stuff.
>>
>> i would add something else to what Rune said:  The DFT or iDFT operate
>> on periodic (or circular) discrete-time or discrete-frequency
>> sequences only.  they are infinitely long, but fully describable by
>> one period of the discrete sequence, which is a finite set of
>> numbers.  that finite set of numbers that go into or come out of the
>> DFT (or FFT) represent *one* period of the periodic sequence.  but you
>> should remember that beyond x[0] and x[N-1] there are implied samples
>> that are the periodic extension of those between x[-1] and x[N].  you
>> only specify {x[0], x[1], ... x[N-1]}, but they are part of an
>> infinite and periodic sequence (and will be treated as such by the
>> DFT) such that
>>
>>      x[n+N] = x[n]    for  -inf<  n<  +inf
>>
>> *everything* that you do to these sequences with the DFT can be
>> thought of as happening to the periodic extension of those sequences.
>> that makes all of these operations circular, but if the operation is a
>> simple one (like adding or scaling the data) the need to consider any
>> circular effect is not apparent.  but if you delay or convolve (or
>> their counterparts in the other domain), the circular or periodic
>> nature is apparent.
>
>That's pretty much what I would have said, had I taken the time for a 
>long answer.  And yes -- it's more important to understand how the DFT 
>relates to the continuous-time nonperiodic Fourier transform than it is 
>to understand how the FFT algorithms speed up the DFT.
>
>-- 
>
>Tim Wescott
>Wescott Design Services
>http://www.wescottdesign.com
>
>Do you need to implement control loops in software?
>"Applied Control Theory for Embedded Systems" was written for you.
>See details at http://www.wescottdesign.com/actfes/actfes.html

I just wanted to thank everyone for your patience on answering my question
in detail. I can now "see" the convolution and how to avoid it's circular
nature. Thanks so much!

On Thu, 16 Sep 2010 21:48:02 -0500, "all4dsp"
<all4dsp@n_o_s_p_a_m.comcast.net> wrote:

>Hi,
>
>I'm not that experienced with DSP, but I understand that convolution in the
>time domain is equivalent to multiplication in the frequency domain. I'm
>having trouble reconciling this in my mind at least with the following
>thought experiment:
>
>If I have 8 samples in the time domain and take an FFT, I obtain 8 samples
>(8 frequency bins) in the frequency domain. If I multiple this FFT by an 8
>sample filter, I end up with an 8-sample filtered-FFT spectrum. If I then
>IFFT this filtered-FFT spectrum, I obtain 8 time-domain samples.
>
>How does this work using convolution? If I take an IFFT of the 8 sample
>filter above, I end up with an 8 sample time-response for the filter. If I
>convolve these two waveforms, I end up with 2x8-1 = 15 samples, which is
>obviously a different result than my above thinking using the frequency
>domain. Can someone help me understand where my thinking is off? I must be
>missing something fundamental.
>
>Thanks in advance! -ggk

Hello all4dsp,
   You ask a terrific question.

I believe the answer is related to the fact that 
convolution in the time domain is equivalent to multiplication 
in the frequency domain for continuous (analog) signals.
But when we're dealing with discrete samples, unexpected things
happen.

For example, the period (time-duration) of exactly one cycle 
an analog 50 Hz sinewave is equal to 20 millisecond.  However, 
the time-duration of exactly one cycle of a discrete 1 Hz sinewave, 
sampled at 1000 samples/second, is equal to 19 milliseconds.
Interesting, huh?

In any case here's something to think about:
Think about a time sequence, x, that is 15 samples in length,
and a filter impulse response, h, that's 4 samples in length.
If you perform a full convolution of x and h, the result 
will be 18 samples in length.

The first three samples of the convolution sequence will be 
the unusable "beginning transient response" of the filter, 
and the last three samples of the convolution sequence will be 
the unusable "ending transient response" of the filter.
This means the "steady-state response" of the filter will be 
the middle 12 samples of the convolution sequence, i.e., the 
only samples that are not "transient" samples.

As it turns out, if you zero pad the three-sample h sequence 
to a length of 15 samples, multiply the 15-point DFTs of h and 
the zero-padded h sequences, the inverse DFT of the product will 
have 15 samples.  Here's the neat part: the last 12 samples of that 
inverse-DFT sequence are *EXACTLY* equal to the steady-state 
response output (the useful samples) of your convolutional filter.
Neat, huh?

[-Rick-]

On Sep 20, 4:12&#4294967295;pm, Rick Lyons <R.Lyons@_BOGUS_ieee.org> averred:

>
> For example, the period (time-duration) of exactly one cycle
> an analog 50 Hz sinewave is equal to 20 millisecond. &#4294967295;However,
> the time-duration of exactly one cycle of a discrete 1 Hz sinewave,
> sampled at 1000 samples/second, is equal to 19 milliseconds.
> Interesting, huh?
>


Wow!  If Rick says so, it must be true; and now I
am going to spend a sleepless night trying to figure
out how the one-second duration of one period of
a 1 Hz wave got squeezed into just 19 samples
out of 1000.  It is not even a harmonic relation...

--Dilip Sarwate