Truncation error for Fourier transform?

Hi folks,

I'm sure I've been told that there are known bounds on the mean square
error caused by the truncation of the Fourier transform (analogue,
preferably). Anyone know what I'm talking about? I haven't had much luck
with Google. I have access to a uni library, so if you know a textbook with
something relevent in it, I can follow that up.

Many thanks,
John

On Jan 12, 1:59 pm, "jhealy" <johnjhe...@gmail.com> wrote:
> Hi folks,
>
> I'm sure I've been told that there are known bounds on the mean square
> error caused by the truncation of the Fourier transform (analogue,
> preferably). Anyone know what I'm talking about? I haven't had much luck
> with Google. I have access to a uni library, so if you know a textbook with
> something relevent in it, I can follow that up.
>
> Many thanks,
> John

What is being truncated, and what are you talking about that is
analogue?

On Jan 12, 1:59&#4294967295;pm, "jhealy" <johnjhe...@gmail.com> wrote:
>
> I'm sure I've been told that there are known bounds on the mean square
> error caused by the truncation of the Fourier transform (analogue,
> preferably). Anyone know what I'm talking about?

at first i thought so, then reading closer, maybe not.  i'm with
julius.  what the heck is this "analogue" truncation of the Fourier
transform?

the consequences of rounding or truncation done in the Discrete
Fourier Transform (DFT or "FFT") are a pretty well known species of
animal.  it depends on how you do it, but it that is well defined
(what the radix is, DIT vs. DIF vs. Winograd vs. Hartley vs. whatever
the FFTW folks are doing), all sorts of people have written about it
since the 60s or 70s.

but this is something done in computers but not the analog kind.

r b-j

jhealy wrote:
> Hi folks,
>
> I'm sure I've been told that there are known bounds on the mean square
> error caused by the truncation of the Fourier transform (analogue,
> preferably). Anyone know what I'm talking about? I haven't had much
> luck with Google. I have access to a uni library, so if you know a
> textbook with something relevent in it, I can follow that up.
>
> Many thanks,
> John

John,

First you might consider that there are two or three kinds of "errors".

1) There is the error in the frequency response that comes from truncating 
the filter coefficients.  This could be an "analog" FIR or transversal 
filter if the filter coefficients are taken out to finite precision.  How 
that happens doesn't need to be due to quantization exactly.  It could be in 
the precision of resistors used for weighting filter "taps".  In any case, 
an approximation program (let us say with infinite precision) will give you 
the needed coefficient values for the computed frequency response.  Then, 
when you implement, the limitation in coefficient precision could be the 
issue you're concerned about.

2) There is the error in the frequency response that might be caused by the 
finite length of the temporal record that is processed or the finite length 
of the filter - a type of truncation also.  This is called "leakage" and 
causes frequency response "ripple".  The shorter the filter, the less sharp 
the frequency response.  This affect is generally taken into account in the 
filter design programs - so I don't generally think of it as an "error".  It 
depends on your frame of reference I suppose.

3) There are the errors in the filter output that are caused by word length 
limitations - "quantization" or word-length truncation if you will.  These 
errors generally show up as white noise.  As such, they cause frequency 
components at the output that differ from the frequency content of the 
input.  Because it's usually white noise then these components show up 
everywhere in frequency.

You can use a least squares measure on any of these errors - or some other 
measure.  You'd have to be more definitive in your description to take this 
aspect further.

Fred 

I seem to have been characteristically unclear. 

F(k) is the function defined by the Fourier transform of f(x), obtained by
an integral over a range from minus infinity to infinity (This is what I
meant by analogue - continuous is the term I meant). If we change the
limits to some finite range, we get a function which is increasingly unlike
F(k). This is the error I'm looking for information on. 

I think Fred is talking about this when he mentions leakage or ripple. Can
you point me in the direction of something on this Fred?

As someone said, the equivalent case for the DFT depends on what algorithm
you use, but I'm not interested in that right now. 

Regards,
John

jhealy wrote:
> I seem to have been characteristically unclear. 
> 
> F(k) is the function defined by the Fourier transform of f(x), obtained by
> an integral over a range from minus infinity to infinity (This is what I
> meant by analogue - continuous is the term I meant). If we change the
> limits to some finite range, we get a function which is increasingly unlike
> F(k). This is the error I'm looking for information on. 
> 
> I think Fred is talking about this when he mentions leakage or ripple. Can
> you point me in the direction of something on this Fred?
> 
> As someone said, the equivalent case for the DFT depends on what algorithm
> you use, but I'm not interested in that right now. 

If instead of integrating from -infinity to +infinity, you integrate 
from -a to +b, the error depends on the integrals from -infinity to -a 
and from +b to +infinity. There is a definite answer for every f(x). I 
don't see how you can generalize.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

On 15 Jan, 19:42, "jhealy" <johnjhe...@gmail.com> wrote:
> I seem to have been characteristically unclear.
>
> F(k) is the function defined by the Fourier transform of f(x), obtained by
> an integral over a range from minus infinity to infinity (This is what I
> meant by analogue - continuous is the term I meant). If we change the
> limits to some finite range, we get a function which is increasingly unlike
> F(k). This is the error I'm looking for information on.

This is windowing by a rectangular window. The finite integral
(view with fixed-width font)

         b
X(w) = integral x(t) exp(jwt) dt
         a

is equivalent to the infinite integral

           inf
X'(w) = integral w(t) x(t) exp(jwt) dt
          -inf

where w(t) is the rectangular window function such that

        0   t < a
w(t) =  1   a <= t < b
        0   b <= t

As you can see, the integrand w(t)x(t)exp(jwt) equals 0
outside the interval [a,b].

Rune

jhealy wrote:

> I'm sure I've been told that there are known bounds on the mean
> square error caused by the truncation of the Fourier transform
> (analogue, preferably). Anyone know what I'm talking about?

I don't know if this is it, but often a signal's spectrum is 
stipulated to decay exponentially fast outside a certain frequency 
interval. In that case, if you truncate outside that interval, the 
integral of spectral magnitude over the tails exists and is bounded 
by the largest (lowest-frequency) tail magnitude times a constant 
(related to the decay rate).


Martin

-- 
Quidquid latine scriptum est, altum videtur.

jhealy <johnjhealy@gmail.com> wrote:
> I seem to have been characteristically unclear. 
 
> F(k) is the function defined by the Fourier transform of f(x), obtained by
> an integral over a range from minus infinity to infinity (This is what I
> meant by analogue - continuous is the term I meant). If we change the
> limits to some finite range, we get a function which is increasingly unlike
> F(k). This is the error I'm looking for information on. 

The Fourier series is defined for periodic functions, integrating
(or summing) over one period.  I believe that the FFT is misnamed
(should be FFS) but it is a little late now.
 
> I think Fred is talking about this when he mentions leakage or ripple. Can
> you point me in the direction of something on this Fred?

If the function isn't periodic you do get 'leakage' or whatever you
want to call it.  That depends on how far from periodic the function
is, data not available to the transform routine.

> As someone said, the equivalent case for the DFT depends on what algorithm
> you use, but I'm not interested in that right now. 

-- glen

On 2009-01-15 16:58:07 -0400, glen herrmannsfeldt <gah@ugcs.caltech.edu> said:

> jhealy <johnjhealy@gmail.com> wrote:
>> I seem to have been characteristically unclear.
> 
>> F(k) is the function defined by the Fourier transform of f(x), obtained by
>> an integral over a range from minus infinity to infinity (This is what I
>> meant by analogue - continuous is the term I meant). If we change the
>> limits to some finite range, we get a function which is increasingly unlike
>> F(k). This is the error I'm looking for information on.
> 
> The Fourier series is defined for periodic functions, integrating
> (or summing) over one period.  I believe that the FFT is misnamed
> (should be FFS) but it is a little late now.

It is the correct Fourier Transform over its index group. It is
just that the classical mathematical physics never bothered with
sampled and periodic time. They did continuous unbounded, sampled
unbounded and continuous periodic time. Leaving out the only case
that could actual be subject to arithmetical procedures which
is the DFT and its efficent version called the FFT.

>  I think Fred is talking about this when he mentions leakage or ripple. Can
>> you point me in the direction of something on this Fred?
> 
> If the function isn't periodic you do get 'leakage' or whatever you
> want to call it.  That depends on how far from periodic the function
> is, data not available to the transform routine.
> 
>> As someone said, the equivalent case for the DFT depends on what algorithm
>> you use, but I'm not interested in that right now.
> 
> -- glen