INTERFACE PZFourier;

(* Fourier transform operations *)
(* Last edited on 1999-08-06 22:04:19 by hcgl *)

FROM PZTypes IMPORT LONG, LONGS, NAT;

TYPE
  T = ARRAY OF LONGS;
    (* 
      Row i of a Fourier.T contains the Fourier coefficients of 
      coordinate i of a FloatCurve. *)

PROCEDURE FFT(VAR V: LONGS; VAR F: LONGS);
  (*
    Computes the Fourier transform "F" of a sample vector "V",
    destroying "V" in the process.
    
    This routine computes the ``smart'' Fourier transform "F" of a
    vector "V".  By definition he two are related by the equation

      "V[i] = Sum { F[j] * basis(N,j)(i) : j = 0..N-1 }

    where

      "basis(N,j)(i) = sqrt(2/N) * cos((2*Pi*j*i / N) + Pi/4)"

    and

      "N = NUMBER(V) = NUMBER(F)".
      
    The "basis" functions are orthonormal, meaning that
    
      "Sum { basis(N,j)(i)*basis(N,k)(i) : i = 0..N-1 } = dirac(j,k)"
      
    for all "j" and "k" in "0..N-1". Therefore, the Fourier
    transform "F" can be computed by scalar products:
    
      "F[j] = Sum { V[i] * basis(N,j)(i) : i = 0..N-1 }"
      
    The actual frequency of component "F[j]" is 
    "MIN(j MOD N, (N-j) MOD N)".  *)
  
PROCEDURE Order(band, step, length: LONG): NAT;
  (*
    Selects a suitable number of resampling points for computing
    the FFT of a FloatCurve, given the filter cutoff wavelength
    "band", the minimum spacing "step", and the total curve
    length "length". *)

PROCEDURE Diff(VAR  F: T; order: NAT); 
  (*
    Replaces the FFT of a curve by the FFT of its 
    "order"th derivative, after discarding the maximum
    frequency term.
  *)

END PZFourier.
(*
  Copyright © 2001 Universidade Estadual de Campinas (UNICAMP).
  Authors: Helena C. G. Leitão and Jorge Stolfi.
  
  This file can be freely distributed, used, and modified, provided
  that this copyright and authorship notice is preserved, and that any
  modified versions are clearly marked as such.
  
  This software has NO WARRANTY of correctness or applicability for
  any purpose. Neither the authors nor their employers chall be held
  responsible for any losses or damages that may result from its use.
*)