NAME
	fft - calculate fast Fourier transform of time domain curve

SYNOPSIS
	fft  [infile  [outfile]]  [options]

USAGE
	FFT reads times and amplitudes and calculates a discrete Fourier
	transform.  By default, input is from stdin and output is to
	stdout.

	FFT attempts to find an approximation to the Fourier transform
	of a time domain signal which is conceptually of infinite
	duration.  It assumes that the input file includes samples from
	only part of the signal, but that the signal is "small" outside
	the sampled interval.  FFT can adjust the input data in two
	ways to improve this approximation.

	By default, FFT "pads" its input file by a factor of four by
	appending zeros.  This increases the apparent resolution in
	frequency space, including adding low-frequency points, and can
	help separate peaks at nearly equal frequencies.  A padding
	factor of 1 results in only enough padding to bring the number
	of data points up to the next power of two.
	
	When the signal has a significant amount of energy just outside
	the sampling interval, the sampling effectively introduces a
	discontinuity which leads to "ringing" in the transform.  FFT
	cannot recreate the missing data, but can suppress the ringing
	by "windowing" - premultiplying by a filtering function that
	suppresses the signal near the ends of the interval.  FFT will
	optionally perform "supergaussian" windowing [1].  The
	windowing is controlled by two parameters: the degree and the
	weight.  A low degree suppresses ringing best but decreases the
	effective observation time (broadens frequency domain peaks). 
	A high degree makes the filtering function change faster near
	the edges of the interval.  This results in narrower frequency
	domain peaks but more ringing.  An infinite degree would
	represent rectangular windowing, which is the result of the
	naive procedure.  The weight governs the placement of the
	window edge with respect to the data provided.  The lower the
	weight at the edge, the more data is affected by the windowing. 
	Windowing is applied before padding, and padding is applied before
	shifting (see -z option).

OPTIONS
	Options can appear anywhere in the command line, provided any
	following file names cannot be confused with optional switch
	arguments.

  -a  [time_step]    automatic abscissas - times are omitted from
                     input file and frequencies are omitted from output
                     file.  This considerably speeds handling of large
                     data files, since fewer numbers must be converted
                     to and from ASCII.  If the time step is supplied,
                     a comment line is added to the output file
                     indicating the frequency step.
  -n  num            keep only first  num  data points
  -o  num            Input data is oversampled (more samples than required
                     by Nyquist sampling theorem).
                     num<32:  oversampled by a factor of num.  Output data
                     at only the first 1/num of the frequencies.
                     num>=32: output data at the first num of the frequencies.
  -p  num            if num<32, pad data by factor of num (default 4 to 8)
                     if num>=32, pad data to bring the number of points in
                     the time domain to num (or the next greater power of 2).
  -m                 print only frequencies and magnitudes
  -s  [deg [wt]]     perform supergaussian windowing of
                     degree  deg (6, 10, or 16, default 10) with
                     weight "wt" on last point (default .1)
  -z  origin         subtract "origin"  from each abscissa value
                     (useful for eliminating phase wraps).  Values
                     before time "origin" are wrapped to the end of the
                     interval.

FILES
	FFT reads an ASCII text file.  Blank lines are ignored.  Lines
	beginning with a semicolon are echoed to the output file. 
	Otherwise, each line has two real numbers representing a time
	and an amplitude.  Text following the second number is ignored. 
	Times must be equidistant and increasing.  The input file may
	be displayed by GRAPH.

	FFT writes an ASCII text output file.  Each line has three real
	numbers representing a frequency and the real and imaginary
	part of the Fourier transform.  The output file may be
	converted by RI2M to a file which can be displayed by GRAPH.

METHOD
	An 8087 or 80287 numeric coprocessor is used if available.  64 or
	80 bit floating point arithmetic is performed (depending on whether
	an 8087 is present), but values are stored as 32 bit floating point
	numbers.  This allows up to 4096 point (i.e.  4096 time domain
	values) transforms.  FFT uses the fact that all input values are
	real to convert the transform to one involving half as many complex
	points.  The method is described by Brigham [2].

PERFORMANCE
	These times were recorded on an IBM AT running at 6 MHz with
	an 80287 running at 4 MHz, with all files on a ramdisk:

	points in   automatic              values   values   
	fft         abscissas    output    read     printed   time
	4096            no       re & im   1200*2   4096*3    85.57 sec
	4096            no         mag     1200*2   4096*2    73.33 sec
	4096           yes       re & im   1200*1   4096*2    65.91 sec
	4096           yes         mag     1200*1   4096*1    54.27 sec
	2048           yes         mag     1200*1   2048*1    29.22 sec

	Evidently, the execution time depends more on the number of values
	read or written (actually, the number of conversions between binary
	and decimal) than on the number of points in the transform.

REFERENCES
	[1]	H. J. Weaver, "Applications of Discrete and Continuous
		Fourier Analysis".
	[2] Brigham, "Fast Fourier Transforms".

AUTHOR
	James R. Van Zandt, 27 Spencer Dr., Nashua NH 03062, jrv@mbunix.mitre.org.