class FFT
****
FFT class. Useful routines include:
____fft_basic:_Radix-2_FFT,_in-place_and_in-order._in-order_result.
____fft_real_:_Radix-2_FFT,_fft_basic,_but_optimized_for_real_input_data._
____fft_torl_:_Radix-2_iFFT,_but_optimized_for_real_result_data._
____dft:_direct_DFT_routine.
____fft:_various_flavors_of_simplified_radix-2_fft_routines.
____fft_2dimensional_:_Image_FFT,_for_real_data.
____ifft_2dimensional:_inverse_of_the_above

For those fft's that take a 'twid' argument (twiddle factors), you must first assign the complex exponential factors using the routine 'assign_basis(size)'. Some routines take a twid argument thereby optimizing for speed.




Public


Features
assign_basis(n:INT):ARRAY{CPX}
**** Return up the complex array to be the array of <cos,sin> pairs (i.e., twiddle factors) corresponding to the desired fft size 'n'. This routine allocates memory for you.
conj_scale(x:ARRAY{CPX},n:INT,scale:FLT)
**** Conjugate and scale complex data (e.g. prior to IFFT by FFT)
dft(data:ARRAY{CPX},res:ARRAY{CPX},twid:ARRAY{CPX}):ARRAY{CPX}
**** Perform direct Discrete Fourier Transform (DFT). 'data' may be any length.
fft(x:ARRAY2{CPX})
**** Perform 2D FFT on image (both dims must be powers of 2). We assume here that row order is fastest in 'x'.
fft(x:ARRAY3{CPX})
**** Perform 3D FFT on image (both dims must be powers of 2). We assume here that row order is fastest in 'x'.
fft(x:ARRAY{CPX})
fft(x:ARRAY{CPX},stride:INT)
**** complex data in x, complex result in x in order.
fft(x:ARRAY{FLT}):ARRAY{CPX}
fft(x:ARRAY{FLT},stride:INT):ARRAY{CPX}
**** real data in x, in-order result returned as a new array.
fft_2dimensional(x:ARRAY2{CPX})
**** Perform 2D FFT on image (both dims must be powers of 2). IMAGE IS ASSUMED PURE-REAL (i.e., imaginary portions are zeros). If the image is not real, the 'fft_real' call should be change to 'fft_basic'. We assume here that row order is fastest in 'x'.
fft_3dimensional(x:ARRAY3{CPX})
**** Perform 3D FFT on image (both dims must be powers of 2). IMAGE IS ASSUMED PURE-REAL (i.e., imaginary portions are zeros). If the image is not real, the 'fft_real' call should be change to 'fft_basic'. We assume here that row order is fastest in 'x'.
fft_basic(x:ARRAY{CPX},stride:INT)
fft_basic(x:ARRAY{CPX},stride:INT,twid:ARRAY{CPX})
fft_raw(x:ARRAY{CPX},n:INT,dilate:INT,stride:INT,twid:ARRAY{CPX})
**** Data is x. Data size is n. 'dilate' means: library global expn is the (cos, -j sin) array, EXCEPT for effective data size n/dilate, stride is the offset of each successive data term, as in "fft" above.
fft_real(x:ARRAY{CPX},stride:INT)
fft_real(x:ARRAY{CPX},stride:INT,twid:ARRAY{CPX})
fft_torl(x:ARRAY{CPX},stride:INT,scale:FLT)
fft_torl(x:ARRAY{CPX},stride:INT,scale:FLT,twid:ARRAY{CPX})
find_table(n:INT):ARRAY{CPX}
**** search our list of existing twiddle arrays
ifft(x:ARRAY2{CPX})
ifft(x:ARRAY3{CPX})
ifft(x:ARRAY{CPX})
ifft(x:ARRAY{CPX},stride:INT)
**** inverse fft, complex data in x, complex result in x.
ifft_2dimensional(x:ARRAY2{CPX})
**** Perform 2D inverse FFT on image (both dims must be powers of 2). Assume row indexing is the fastest varying index.
ifft_3dimensional(x:ARRAY3{CPX})
**** Perform 3D inverse FFT on image (both dims must be powers of 2). Assume row indexing is the fastest varying index.
ifft_real(x:ARRAY{CPX})
ifft_real(x:ARRAY{CPX},stride:INT)
**** assumped complex conj. sym. data in x, from real data. Produces a real result (i.e., .im attributes are all zeros).
ifft_stride(x:ARRAY{CPX},stride:INT)
**** optimized for stride indexing.
init
int_2_complex(s:ARRAY{INT},c:ARRAY{CPX}):ARRAY{CPX}
**** create a complex array fttable from an integer array
is_power_of_two(n:INT):BOOL
**** Query whether n is a 2^k for some k
pure_real(x:ARRAY{CPX},n:INT):BOOL
****
__Query_whether_the_data_in_x_is_all_real.
reals(x:ARRAY{CPX},stride:INT,sign:INT,twid:ARRAY{CPX})
**** This routine separates out the reals from the result when we do a real n point fft using an n/2 point complex fft. 'sign' is 1 for FFT2real, -1 for torl.
reverse_dig(x:ARRAY{CPX},n:INT,stride:INT)
**** bit reverse the elements in array x


Private

shared twiddles:FLIST{ARRAY{CPX}};
**** prestored twiddle factors.
shared twiddles:FLIST{ARRAY{CPX}};
**** prestored twiddle factors.

The Sather Home Page