D703 Real Fast Fourier Transform

Subroutine RFFT computes either:

$•$

the finite Fourier transform of a real periodic sequence, or

$•$

the corresponding inverse transform.

Given a sequence of real numbers $y$₀,y₁,...,y_n-1 , the forward transform computes the terms

$c$k	$=$	$\{1n\}\sum$m=0n-1ymexp( {-i 2πmkn}),
	$=$	$\{1n\}\sum$m=0n-1ymcos( {2πmkn}) -{in}∑m=0n-1ymsin( {2πmkn}),(k=0,1,...,n-1),

which have period n in the subscript k and passess the property $c$_-k=c_k=c_n-k , where $c$_k is the complex conjugate of $c$_k . Therefore only those $c$_k for which $0\; \le k\; \le n/2$

are computed by RFFT.

Conversely, given a sequence of complex numbers $c$₀,c₁,...,c_n-1

possessing the property $c$_-k=c_k , the inverse transform computes the terms

$y$m

$=$

$\sum$k=0n-1ckexp( {i 2πkmn}),(m=0,1,...,n-1),

which have period n in the subscript m and are real. Only those $c$_k for which $0\; \le k\; \le n/2$ need be supplied as input to RFFT for the calculation of (2).

To ensure optimum use of storage, the same array is used for input and output, and all intermediate calculations are carried out in this array.

Structure:

SUBROUTINE subprogram
User Entry Names: RFFT
External References: CFFT (D704)

Usage:

    COMPLEX C(ncdim)
    REAL Y(nydim)
    EQUIVALENCE (C,Y)
    ...
    CALL RFFT (C,M)
    ...

C

( COMPLEX) Array of length ncdim not less than $(n/2+1)$ .

Y

( REAL) Array of length nydim not less than n.

M

( INTEGER) On entry, the absolute value of M determines the value of n through the relation $n=2|M|$ . If M is negative, expression (1) is evaluated. If M is non-negative, expression (2) is evaluated. Unchanged on exit.
M < 0:
On entry, $Y(m+1)=y$_m, (m=0,1,...,n-1) .
On exit, $C(k+1)=c$_k, (k=0,1,...,n/2) , as defined by (1).
$M\; \ge 0:$
On entry, $C(k+1)=c$_k, (k=0,1,...,n/2) .
On exit, $Y(m+1)=y$_m, (m=0,1,...,n/2) , as defined by (2) with $c$_k=c_k .

Method:

RFFT calls the complex fast Fourier transform subroutine CFFT (D704) with sequences of half-length as explained in Ref. 1.

References:

1. E.O. Brigham, The fast Fourier transformation, (Prentice-Hall, Englewood Cliffs 1974) Chap. 10, Sect. 10, Fig. 10-10.

D704