🚀 go-pugleaf

In article <1811@beguine.UUCP> Jeff.Miller@samba.acs.unc.edu (Jeff Miller) writes:
>Can I "zoom in" on that frequency range, for better resolution, without 
>increasing the sample rate or making any other changes which in the real 
>world (if I applied this to CD audio for example) would be difficult? 
>Don't ask me why I haven't tried by modifying my program...

Consider the "Zoom FFT" suggested by Yip (1976), and discussed in modern 
textbooks of DSP.
Hopefully, someone will post or email the title of a good reference --
else check Blahut's Fast Algorithms for DSP or Taylor's Digital Filter
Design Handbook to see if they describe it.

Regards,
ruck.
--
John R Ruckstuhl, Jr
University of Florida		ruck@cis.ufl.edu, uflorida!ruck

 In a previous article, Jeff.Miller@samba.acs.unc.edu (Jeff Miller) writes:
>I have read a little, experimented a little with the FFT. And I have 
>a question.
>
>This about sums my experience: I have a simple program I converted from 
>BASIC to C which asks for the frequency, amplitude, and phase of four 
>sine components, and then calculates them and sums them into an array. 
>It then does an FFT on them, analyzing at n/2 intervals where n is the 
>number of samples. 
> 
>Now: if you enter sine values that "hit", which is to say are identical 
>to those at which the program analyzes, the output is clean: a well defined 
>line where it should be. But if the sine is just a little bit "off", the 
>results are of course dissapointing and difficult to interpret. 

You are seeing a couple of things, I think.  First, the FFT (and the DFT too)
are only capable of looking at frequencies and resolving them correctly if
if you have enough points in your data sample.  That means you will resolve
them only if you have specified the sample interval and frequencies such
that an integer number of cycles exist in your data.

You also get some discontinuity if your sample frequencies don't match up
with your window exactly.  This is because the FFT algorithm assumes that
your sample window is replicated in time forever.  Look at the following
picture:

|       |    .                     .                    .      
|       |   .  .                  .  .            |    .       
|       |  .    .                .    .           |   .        
|       | .      .              .      .          |  .         
|       |.        .            .        .         | .          
+       .          .          .          .        |.           
|      .|           .        .            .       .            
|     . |            .      .              .     .|            
|    .  |             .    .                .   . |            
|   .   |              .  .                  . .  |            
|  .    |               .                     .   |            
+-----------------------------------------------------------
        T1                                        T2

Note that if your sample window begins at T1 and ends at T2, you can just
replicate the first sample window again and again for all time and you will
get the triangle waveform repeated smoothly and without any glitches.  Now,
look at this picture:

|   |        .                     .                   |.      
|   |       .  .                  .  .                 .       
|   |      .    .                .    .               .|       
|   |     .      .              .      .             . |       
|   |    .        .            .        .           .  |       
+   |   .          .          .          .         .   |       
|   |  .            .        .            .       .    |       
|   | .              .      .              .     .     |       
|   |.                .    .                .   .      |       
|   .                  .  .                  . .       |       
|  .|                   .                     .        |       
+-----------------------------------------------------------
   T1                                                  T2

This is the same picture, I have just moved the sample intervals out to include
more data samples.  If you were to take the samples between T1 and T2 and
replicate them again and again, you would have a big discontinuity where the
previous sample period ended and the next one begins.  If you FFT this, you
will find that the frequency spectrum of the second sample period is radically
different than the first, due to the discontinuity.  To help correct this, you
can 'window' your data so that it starts and ends at zero.  This won't make the
problem go away, but it may help.  The best thing to do is either make your
sample period become an integer multiple of the wave period, or make it much,
much longer than the wave period so that the discontinuity isn't so apparent.

>If I feed the output of this program into a reverse-FFT algorithm, will 
>the original waveform be faithfully reproduced? I would think so.

It should be.

 
   -dave


-- 
Dave McMahan                            mcmahan@netcom.uucp
					{apple,amdahl,claris}!netcom!mcmahan

The following article is being re-posted to this newsgroup at the request
of the original author.  He accidentally sent it to me as a reply when he
really meant to post it in followup.

---------------    Text of the re-post article    --------------------

Date: Mon, 3 Dec 90 12:15:52 -0600
Subject: Re: Having messed with FFT programs, I have a few questions...
Newsgroups: comp.dsp

Wouldn't it be possible to rid yourself of the "glitch" problem by crossfading
the section you are working with?  They do this to get "clickless" loops in
samplers, and it seems the technique might work here.  Just make a copy of the
section, reverse it, ramp the volume up like this:  "/"

Then, ramp the volume down of the original section like this: "\"

And mix the two together.  Then beat until smooth (just kidding).  Then
do your fft on that modified section.  


-- 
Dave McMahan                            mcmahan@netcom.uucp
					{apple,amdahl,claris}!netcom!mcmahan

 In a previous article, By-Tor writes:
>Wouldn't it be possible to rid yourself of the "glitch" problem by crossfading
>the section you are working with?  They do this to get "clickless" loops in
>samplers, and it seems the technique might work here.  Just make a copy of the
>section, reverse it, ramp the volume up like this:  "/"

This is essentially what windowing does, but the window used is better at
filtering out the bogus harmonics without introducing problems of it's own.
Windowing requires the creation of the proper window and then multiplying
it by the data samples.  Instead of being a straight ramp, it is more of a
smooth curve.  Various windows are available, each with benefits and drawbacks
of their own.  Theoretically, it should give you better performance than just
a straight ramp-up ramp-down technique.  After all, you have to decide where
to start the ramp for the downward tailoff and where to end the ramp for the
initial ramp-up.   The ramp technique really is a trapezoidal window and
therefore introduces various types of distortion in the frequency domain.  It
does have the benefit of working well for mixing two signals together for
sending to a speaker and being quite easy to implement, but it isn't the
optimal choice for the task of looking at undistorted data in the frequency
domain.  If somebody wants me to, I'll look up a couple of different types
of windows at work tomorrow and post the formulas used to this newsgroup.
The functions can be easily plotted using a spreadsheet or other program
and you can see for yourself just exactly how each window looks.



   -dave

-- 
Dave McMahan                            mcmahan@netcom.uucp
					{apple,amdahl,claris}!netcom!mcmahan

In article <1811@beguine.UUCP>, Jeff.Miller@samba.acs.unc.edu (Jeff Miller) writes:
> I have read a little, experimented a little with the FFT. And I have 
> a question.

A good cookbook for the FFT is Intel application note AP-275, 
"An FFT Algorithm For MCS-96 Products Including Supporting Routines
and Examples"

It covers the bin side lobes, windowing and other strange stuff.

(Its in the Embedded Contoller Handbook, Volume II, 16 bits)

markz@ssc.uucp