D700: Real Fast Fourier Transform

Author(s): C. Iselin	Library: MATHLIB
Submitter:	Submitted: 04.09.1972
Language: Fortran	Revised: 15.01.1977

Let the discrete Fourier transform be defined by

The subroutines of package RFT compute this transform or its inverse

for real functions, with the restriction that N is a power of 2.

Structure:

SUBROUTINE subprograms
User Entry Names: RFT, RCA, RPA, RPS, RSA
Internal Entry Names: D700SU
Files Referenced: Printer
COMMMON Block Names and Lengths: /D700DT/ 6, /FWORK/ 321

Usage:

CALL RFT(M,X,IX,Y,IY,MODE) or

CALL RCA(M,X,IX,Y,IY) or

CALL RPA(M,X,IX,Y,IY) or

CALL RPS(M,X,IX,Y,IY) or

CALL RSA(M,X,IX,Y,IY)

M

(INTEGER) Number m (such that ) of input values (full period or half period).

X

(REAL) Input array. The input values are taken from for .

Y

(REAL) Output array. The results are stored in for .

MODE

(INTEGER) Selects the mode of operation for RFT as follows:

MODE = 1: Analysis of a general real function.

CALL RFT(M,X,IX,Y,IY,1) or

CALL RPA(M,X,IX,Y,IY)

assumes to define a full period of the function to be analysed. The value is ignored. The results are returned in the following order:

.

The other values in Y are not changed.

MODE = 4: Synthesis of a general real function.

CALL RFT(M,X,IX,Y,IY,4) or

CALL RPS(M,X,IX,Y,IY)

is exactly the inverse of MODE=1 as described above. The value is set equal to .
MODE=2/5: Analysis/Synthesis of a real even function.
For an even function, the transform is identical to its inverse.

CALL RFT(M,X,IX,Y,IY,2) or

CALL RFT(M,X,IX,Y,IY,5) or

CALL RCA(M,X,IX,Y,IY)

all assume that define a half-period of the function to be analysed and that the other half period is generated by even continuation. The results returned are the cosine terms

Note that the full period has 2n=N points.
MODE = 3/6: Analysis/Synthesis of a real odd function.
For an odd function the transform is also identical to its inverse. All assume that ;

CALL RFT(M,X,IX,Y,IY,3) or

CALL RFT(M,X,IX,Y,IY,6) or

CALL RSA(M,X,IX,Y,IY)

define a half-period of the function to be analysed and that the other half period is generated by odd continuation. The results returned are the sine terms

.

Note that and that the values returned are and . Again the full period has 2n=N points.

Restrictions:

These subroutines work for any input such that the full period has at least four points, i.e., for general functions, or for odd or even functions. If the number of data points exceeds 129 ( ), the calling program must provide sufficient working storage by using the statement

    COMMON /FWORK/ W(nnn)

where .

References:

1. C. Iselin, An approach to fast Fourier transform, CERN 71-19.

A copy of Ref. 1 is available.