FFT Question

Why is it that in older textbooks the DFT or FFT is defined as having scaling of (1/N) for direct FFT whereas in newer ones it doesn't? If we take the DFT of say 1,1,1,1 the answer is 4 but surely an answer of 1 makes more sense as it is the average value. of 4 ones.

I know people say - "Oh we can scale it later", but it doesn't make mathematical sense.  The other point is that the Fourier transform doesn't apply to a step function anyway so why does the DFT?

Am 02.09.20 um 07:00 schrieb Tom Killwhang:
> Why is it that in older textbooks the DFT or FFT is defined as having scaling of (1/N) for direct FFT whereas in newer ones it doesn't? If we take the DFT of say 1,1,1,1 the answer is 4 but surely an answer of 1 makes more sense as it is the average value. of 4 ones.
> 
> I know people say - "Oh we can scale it later", but it doesn't make mathematical sense.  The other point is that the Fourier transform doesn't apply to a step function anyway so why does the DFT?

I think this for technical reasons. If you program FFT with twiddle 
factors taken from the unit circle you get a total scale factor of N for 
a full turn around. Typically it is less work to compensate for this 
factor at another place.

Take also into account the scale factor of the inverse FFT. If you scale 
by 1/N you must *not* scale the inverse FFT to get the original values 
back. If you want to operate symmetrically you need to scale both by 
1/sqrt(N) which is even more non intuitive. But this keeps the RMS 
energy constant.


Marcel

On 2020-09-02 03:01, Marcel Mueller wrote:
> Am 02.09.20 um 07:00 schrieb Tom Killwhang:
>> Why is it that in older textbooks the DFT or FFT is defined as having 
>> scaling of (1/N) for direct FFT whereas in newer ones it doesn't? If 
>> we take the DFT of say 1,1,1,1 the answer is 4 but surely an answer of 
>> 1 makes more sense as it is the average value. of 4 ones.
>>
>> I know people say - "Oh we can scale it later", but it doesn't make 
>> mathematical sense.  The other point is that the Fourier transform 
>> doesn't apply to a step function anyway so why does the DFT?
> 
> I think this for technical reasons. If you program FFT with twiddle 
> factors taken from the unit circle you get a total scale factor of N for 
> a full turn around. Typically it is less work to compensate for this 
> factor at another place.
> 
> Take also into account the scale factor of the inverse FFT. If you scale 
> by 1/N you must *not* scale the inverse FFT to get the original values 
> back. If you want to operate symmetrically you need to scale both by 
> 1/sqrt(N) which is even more non intuitive. But this keeps the RMS 
> energy constant.

The question of how to normalize FFTs goes back way before computers 
were even invented, on account of that vexing factor of 2*pi.

The EE contingent tends to define the continuous-time FT with the 2*pi 
factors in the exponent, i.e.

G(f) = F(g) = integral[-inf, inf] exp( j 2 pi f t) g(t) dt

and

g(t) = Finv(G) = integral[-inf, inf] exp( -j 2 pi f t) G(f) df.

The physics and math contingents tend to use omega = 2 pi f as the 
independent frequency variable, so that the 2*pi winds up as a 
multiplicative constant outside the integral, either asymmetrically as 
1/(2 pi) on the inverse transform, or symmetrically, as
in 1/sqrt(2 pi) on both forward and reverse.  The main effect is on the 
statement of FT theorems.

IMNSHO putting the 2*pi in the exponent is a huge win, in both the 
continuous and discrete cases

Cheers

Phil Hobbs

-- 
Dr Philip C D Hobbs
Principal Consultant
ElectroOptical Innovations LLC / Hobbs ElectroOptics
Optics, Electro-optics, Photonics, Analog Electronics
Briarcliff Manor NY 10510

http://electrooptical.net
http://hobbs-eo.com

Tom Killwhang wrote:
> Why is it that in older textbooks the DFT or FFT is defined as having
> scaling of (1/N) for direct FFT whereas in newer ones it doesn't? If
> we take the DFT of say 1,1,1,1 the answer is 4 but surely an answer
> of 1 makes more sense as it is the average value. of 4 ones.
> 
> I know people say - "Oh we can scale it later", but it doesn't make
> mathematical sense.  The other point is that the Fourier transform
> doesn't apply to a step function anyway so why does the DFT?
> 

A lot of implementations don't scale the output. Most prominently
FFTW. Some do. It's sort of open to the implementation. I believe the 
argument for not doing it is somet5hing like roundoff error.

And I'd call a step function ( all 1's ) a pretty good test case for an 
FFT. Not much point in using an FFT on one if you know it's a step 
function in an implementation but it's a quick check of an implementation

-- 
Les Cargill

On Thursday, September 3, 2020 at 3:47:41 PM UTC-7, Phil Hobbs wrote:

(snip)

> The question of how to normalize FFTs goes back way before computers 
> were even invented, on account of that vexing factor of 2*pi. 


(snip of EE contingent)

> The physics and math contingents tend to use omega = 2 pi f as the 
> independent frequency variable, so that the 2*pi winds up as a 
> multiplicative constant outside the integral, either asymmetrically as 
> 1/(2 pi) on the inverse transform, or symmetrically, as 
> in 1/sqrt(2 pi) on both forward and reverse. The main effect is on the 
> statement of FT theorems. 

> IMNSHO putting the 2*pi in the exponent is a huge win, in both the 
> continuous and discrete cases 

Not only in the Fourier transform, but in all the rest of the equations,
omega works out much better than f.  It is only convenient to use f
when you are actually counting frequencies.  (That is, no-one makes
frequency counters to output in omega.)  There are some who use
wavelength over 2pi, but that is rare.  Using omega and k, you get
exp(i.k.x - i.omega.t) for propagating waves.   (Where k is the
wave number or wave vector, magnitude 2 pi over wavelength.)

It is, then, convenient for the Fourier transform to put the 1/(2pi)
along with the d omega. 

In the case of FFT in fixed point, best is to do all with enough bits so
as not to overflow and not divide by N until the end, if it is needed.

In floating point with radix other than 2, it is a little complicated where
to put the divide, but note that bits can be lost when dividing by two.
(Specifically, IBM used radix 16 for many years, and still supports it,
along with 2 a little recently, and 10 on newer machines.  Yes,
some machines support all three.)

Step functions in continuous Fourier transforms are not rare, but
a little complicated.  Delta functions are not unusual.  But for DFT
(defined for periodic band-limited signals) a step function is
not all that special.  Especially for small N, where it isn't all
that steep.  And note that this all applies for DST or DCT, too.

On 2020-09-09 19:12, ga...@u.washington.edu wrote:
> On Thursday, September 3, 2020 at 3:47:41 PM UTC-7, Phil Hobbs wrote:
> 
> (snip)
> 
>> The question of how to normalize FFTs goes back way before computers
>> were even invented, on account of that vexing factor of 2*pi.
> 
> 
> (snip of EE contingent)
> 
>> The physics and math contingents tend to use omega = 2 pi f as the
>> independent frequency variable, so that the 2*pi winds up as a
>> multiplicative constant outside the integral, either asymmetrically as
>> 1/(2 pi) on the inverse transform, or symmetrically, as
>> in 1/sqrt(2 pi) on both forward and reverse. The main effect is on the
>> statement of FT theorems.
> 
>> IMNSHO putting the 2*pi in the exponent is a huge win, in both the
>> continuous and discrete cases
> 
> Not only in the Fourier transform, but in all the rest of the equations,
> omega works out much better than f.  It is only convenient to use f
> when you are actually counting frequencies.  (That is, no-one makes
> frequency counters to output in omega.)  There are some who use
> wavelength over 2pi, but that is rare.  Using omega and k, you get
> exp(i.k.x - i.omega.t) for propagating waves.   (Where k is the
> wave number or wave vector, magnitude 2 pi over wavelength.)

Sure, when the spatial transform is in view as well, I use exp(i(omega t 
- k dot x)) too. (I'm a physicist, after all.)  Some years back I wrote 
a scalable clusterized FDTD simulator, and the far-field and 
order-source calculations are all done in the (k, omega) basis.

But in a DSP context, putting the 2*pi in the exponent is almost always 
a win IMO.

Cheers

Phil Hobbs

-- 
Dr Philip C D Hobbs
Principal Consultant
ElectroOptical Innovations LLC / Hobbs ElectroOptics
Optics, Electro-optics, Photonics, Analog Electronics
Briarcliff Manor NY 10510

http://electrooptical.net
http://hobbs-eo.com

I noticed another problem that arises from this. The units don't match up w=
hen you use Parseval's theorem and the FFT. Look ta the equation near the b=
ottom that uses the FFT for Parseval's theorem
https://en.wikipedia.org/wiki/Parseval%27s_theorem
I did a simulation with white noise through a bandpass filter.=20

Now I found the periodogram and this gives me power vs frequency. when you =
sum them up you do indeed get the same answer - but the expression on the l=
eft of the equation is the sum of squares of a random variable and that is =
not power. The power is variance after you divide by N. Hence both sides ne=
ed to be divided by N otherwise we are equating energies and not power. I a=
lways understood variance (with no dc) is average power and not energy.

Thx



On Thursday, September 10, 2020 at 11:12:25 AM UTC+12, ga...@u.washington.e=
du wrote:
> On Thursday, September 3, 2020 at 3:47:41 PM UTC-7, Phil Hobbs wrote:=20
>=20
> (snip)
> > The question of how to normalize FFTs goes back way before computers=20
> > were even invented, on account of that vexing factor of 2*pi.
> (snip of EE contingent)
> > The physics and math contingents tend to use omega =3D 2 pi f as the=20
> > independent frequency variable, so that the 2*pi winds up as a=20
> > multiplicative constant outside the integral, either asymmetrically as=
=20
> > 1/(2 pi) on the inverse transform, or symmetrically, as=20
> > in 1/sqrt(2 pi) on both forward and reverse. The main effect is on the=
=20
> > statement of FT theorems.=20
>=20
> > IMNSHO putting the 2*pi in the exponent is a huge win, in both the=20
> > continuous and discrete cases
> Not only in the Fourier transform, but in all the rest of the equations,=
=20
> omega works out much better than f. It is only convenient to use f=20
> when you are actually counting frequencies. (That is, no-one makes=20
> frequency counters to output in omega.) There are some who use=20
> wavelength over 2pi, but that is rare. Using omega and k, you get=20
> exp(i.k.x - i.omega.t) for propagating waves. (Where k is the=20
> wave number or wave vector, magnitude 2 pi over wavelength.)=20
>=20
> It is, then, convenient for the Fourier transform to put the 1/(2pi)=20
> along with the d omega.=20
>=20
> In the case of FFT in fixed point, best is to do all with enough bits so=
=20
> as not to overflow and not divide by N until the end, if it is needed.=20
>=20
> In floating point with radix other than 2, it is a little complicated whe=
re=20
> to put the divide, but note that bits can be lost when dividing by two.=
=20
> (Specifically, IBM used radix 16 for many years, and still supports it,=
=20
> along with 2 a little recently, and 10 on newer machines. Yes,=20
> some machines support all three.)=20
>=20
> Step functions in continuous Fourier transforms are not rare, but=20
> a little complicated. Delta functions are not unusual. But for DFT=20
> (defined for periodic band-limited signals) a step function is=20
> not all that special. Especially for small N, where it isn't all=20
> that steep. And note that this all applies for DST or DCT, too.

On Wednesday, September 9, 2020 at 8:09:15 PM UTC-7, gyans...@gmail.com wrote:
> I noticed another problem that arises from this. The units don't match up when you 
> use Parseval's theorem and the FFT. Look ta the equation near the bottom that uses the FFT for Parseval's theorem 
> https://en.wikipedia.org/wiki/Parseval%27s_theorem 
> I did a simulation with white noise through a bandpass filter. 

> Now I found the periodogram and this gives me power vs frequency. when you sum them
> up you do indeed get the same answer - but the expression on the left of the equation
> is the sum of squares of a random variable and that is not power.
> The power is variance after you divide by N. Hence both sides need to be divided by N
> otherwise we are equating energies and not power.
> I always understood variance (with no dc) is average power and not energy. 

Seems like a usual problem when working with discrete signals.

There should be a factor of the sampling period to make it look like an integral,
so that would make it energy instead of power.  But yes, it is usual to factor
out the (presumed constant and known) sampling rate.  

If you consider the earlier integral on the page, it is over one period of a
periodic function.  That normalizes out the length (time) of the period.

Seems not worse than many mathematics formulas which completely
get units wrong.  That is, for example, add quantities with different units.

When you use them, you have to put back any normalizations that
they left out, such as sampling rate.  Conveniently, in many cases you can
ignore the sampling rate, for example when designing filters, after you
factor it out.