home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / C / FFT142.ZIP / FFT.DOC < prev    next >
Encoding:
Text File  |  1991-06-06  |  5.9 KB  |  121 lines
  1. NAME
  2.     fft - calculate fast Fourier transform of time domain curve
  3.  
  4. SYNOPSIS
  5.     fft  [infile  [outfile]]  [options]
  6.  
  7. USAGE
  8.     FFT reads times and amplitudes and calculates a discrete Fourier
  9.     transform.  By default, input is from stdin and output is to
  10.     stdout.
  11.  
  12.     FFT attempts to find an approximation to the Fourier transform
  13.     of a time domain signal which is conceptually of infinite
  14.     duration.  It assumes that the input file includes samples from
  15.     only part of the signal, but that the signal is "small" outside
  16.     the sampled interval.  FFT can adjust the input data in two
  17.     ways to improve this approximation.
  18.  
  19.     By default, FFT "pads" its input file by a factor of four by
  20.     appending zeros.  This increases the apparent resolution in
  21.     frequency space, including adding low-frequency points, and can
  22.     help separate peaks at nearly equal frequencies.  A padding
  23.     factor of 1 results in only enough padding to bring the number
  24.     of data points up to the next power of two.
  25.     
  26.     When the signal has a significant amount of energy just outside
  27.     the sampling interval, the sampling effectively introduces a
  28.     discontinuity which leads to "ringing" in the transform.  FFT
  29.     cannot recreate the missing data, but can suppress the ringing
  30.     by "windowing" - premultiplying by a filtering function that
  31.     suppresses the signal near the ends of the interval.  FFT will
  32.     optionally perform "supergaussian" windowing [1].  The
  33.     windowing is controlled by two parameters: the degree and the
  34.     weight.  A low degree suppresses ringing best but decreases the
  35.     effective observation time (broadens frequency domain peaks). 
  36.     A high degree makes the filtering function change faster near
  37.     the edges of the interval.  This results in narrower frequency
  38.     domain peaks but more ringing.  An infinite degree would
  39.     represent rectangular windowing, which is the result of the
  40.     naive procedure.  The weight governs the placement of the
  41.     window edge with respect to the data provided.  The lower the
  42.     weight at the edge, the more data is affected by the windowing. 
  43.     Windowing is applied before padding, and padding is applied before
  44.     shifting (see -z option).
  45.  
  46. OPTIONS
  47.     Options can appear anywhere in the command line, provided any
  48.     following file names cannot be confused with optional switch
  49.     arguments.
  50.  
  51.   -a  [time_step]    automatic abscissas - times are omitted from
  52.                      input file and frequencies are omitted from output
  53.                      file.  This considerably speeds handling of large
  54.                      data files, since fewer numbers must be converted
  55.                      to and from ASCII.  If the time step is supplied,
  56.                      a comment line is added to the output file
  57.                      indicating the frequency step.
  58.   -n  num            keep only first  num  data points
  59.   -o  num            Input data is oversampled (more samples than required
  60.                      by Nyquist sampling theorem).
  61.                      num<32:  oversampled by a factor of num.  Output data
  62.                      at only the first 1/num of the frequencies.
  63.                      num>=32: output data at the first num of the frequencies.
  64.   -p  num            if num<32, pad data by factor of num (default 4 to 8)
  65.                      if num>=32, pad data to bring the number of points in
  66.                      the time domain to num (or the next greater power of 2).
  67.   -m                 print only frequencies and magnitudes
  68.   -s  [deg [wt]]     perform supergaussian windowing of
  69.                      degree  deg (6, 10, or 16, default 10) with
  70.                      weight "wt" on last point (default .1)
  71.   -z  origin         subtract "origin"  from each abscissa value
  72.                      (useful for eliminating phase wraps).  Values
  73.                      before time "origin" are wrapped to the end of the
  74.                      interval.
  75.  
  76. FILES
  77.     FFT reads an ASCII text file.  Blank lines are ignored.  Lines
  78.     beginning with a semicolon are echoed to the output file. 
  79.     Otherwise, each line has two real numbers representing a time
  80.     and an amplitude.  Text following the second number is ignored. 
  81.     Times must be equidistant and increasing.  The input file may
  82.     be displayed by GRAPH.
  83.  
  84.     FFT writes an ASCII text output file.  Each line has three real
  85.     numbers representing a frequency and the real and imaginary
  86.     part of the Fourier transform.  The output file may be
  87.     converted by RI2M to a file which can be displayed by GRAPH.
  88.  
  89. METHOD
  90.     An 8087 or 80287 numeric coprocessor is used if available.  64 or
  91.     80 bit floating point arithmetic is performed (depending on whether
  92.     an 8087 is present), but values are stored as 32 bit floating point
  93.     numbers.  This allows up to 4096 point (i.e.  4096 time domain
  94.     values) transforms.  FFT uses the fact that all input values are
  95.     real to convert the transform to one involving half as many complex
  96.     points.  The method is described by Brigham [2].
  97.  
  98. PERFORMANCE
  99.     These times were recorded on an IBM AT running at 6 MHz with
  100.     an 80287 running at 4 MHz, with all files on a ramdisk:
  101.  
  102.     points in   automatic              values   values   
  103.     fft         abscissas    output    read     printed   time
  104.     4096            no       re & im   1200*2   4096*3    85.57 sec
  105.     4096            no         mag     1200*2   4096*2    73.33 sec
  106.     4096           yes       re & im   1200*1   4096*2    65.91 sec
  107.     4096           yes         mag     1200*1   4096*1    54.27 sec
  108.     2048           yes         mag     1200*1   2048*1    29.22 sec
  109.  
  110.     Evidently, the execution time depends more on the number of values
  111.     read or written (actually, the number of conversions between binary
  112.     and decimal) than on the number of points in the transform.
  113.  
  114. REFERENCES
  115.     [1]    H. J. Weaver, "Applications of Discrete and Continuous
  116.         Fourier Analysis".
  117.     [2] Brigham, "Fast Fourier Transforms".
  118.  
  119. AUTHOR
  120.     James R. Van Zandt, 27 Spencer Dr., Nashua NH 03062, jrv@mbunix.mitre.org.
  121.