csfft2du,zdfft2du(3F) csfft2du,zdfft2du(3F)NAME
csfft2du, zdfft2du - 2D, Complex-to-Real, Inverse Fast Fourier
Transforms.
SYNOPSYS
Fortran :
subroutine csfft2du( sign, n1, n2, array, lda, coef )
integer sign, n1, n2, lda
real array(lda,n2), coef((n1+15)+2*(n2+15))
subroutine zdfft2du( sign, n1, n2, array, lda, coef )
integer sign, n1, n2, lda
real*8 array(lda,n2), coef((n1+15)+2*(n2+15))
C :
#include <fft.h>
int csfft2du ( int sign, int n1, int n2, float *array,
int lda, float *coef);
int zdfft2du ( int sign, int n1, int n2, double *array,
int lda, double *coef);
DESCRIPTIONcsfft2du and zdfft2du compute in place the inverse Fourier transform of
real 2D sequence of size N1 x N2. The value F{k,l} of the transform of
the 2D sequence f{i,j} is equal to:
F{k,l} = Sum ( W1^(i*k) * W2^(j*l) * f{i,j} ),
for i =0,...,(N1-1), j=0,...,(n2-1)
W1 = exp( (Sign*2*sqrt(-1)*PI) / N1 )
W2 = exp( (Sign*2*sqrt(-1)*PI) / N2 )
Storage
It is assumed that the (N1 x N2) 2D sequence is stored along dimension
N1. So the index {i+1,j} has an offset of 1 element with respect to
{i,j}, and {i,j+1} an offset of lda elements with respect to {i,j}.
NOTE : lda must be larger (or equal) to 2*((N1+2)/2).
Algorithm
The complex-to-real Inverse 2D Fourier transform is computed with a row-
column approach.
- first, N1 FFTs complex-to-complex of size N2 are preformed,
stride=lda/2, and leading_dimension=1.
- then, N2 FFTs complex-to-real of size N1 are evaluated, stride = 1
and leading_dimension=lda.
As the final sequence has real values, only half of the complex Fourier
Transform is used. The sample {(N1-k),l} of the Fourier transform is the
conjugate of the sample {k,l}.
However, some extra space is necessary, and the relation
Page 1
csfft2du,zdfft2du(3F) csfft2du,zdfft2du(3F)
(lda>=2*((N1+2)/2)) must hold.
PARAMETERS
SIGN Integer specifying which sign to be used for the expression of W
(see above) - must be either +1 or -1.
Unchanged on exit.
N1 Integer, the first dimension size of the 2D sequence.
Unchanged on exit.
N2 Integer, the second dimension size of the 2D sequence.
Unchanged on exit.
ARRAY Array containing the samples of the 2D sequence to be transformed.
On input, the element {i,j} of the sequence is stored as A(i,j) in
Fortran , and A[i+j*lda] in C.
On exit, the array is overwritten by its transform.
LDA Integer, leading dimension: increment between the samples of two
consecutive sub-sequences (e.g between {i,j+1} and {i,j} ).
Unchanged on exit.
COEFF Array of at least ( (N+15)+2*(N2+15) ) elements. On entry it
contains the Sines/Cosines and factorization of N. COEFF needs to be
initialized with a call to scfft2dui or dzfft2dui. Unchanged on
exit.
Example of Calling Sequence
Direct then Inverse 2D FFT computed on a 64*1024 sequence of real values.
The elements of the sequence are stored with increment (stride) 1, and
the offset between the first element of two succesive sub-sequences
(leading dimension) is 1026.
Note : 1026 >= 1024+2 .
Fortran
real array(0:1026-1,0:64-1), coeff(1024+15 + 2*(64+15))
call scfft2dui( 1024, 64, coeff)
call csfft2du( -1, 1024, 64, array, 1026, coeff)
call scfft2du( 1, 1024, 64, array, 1026, coeff)
C
#include <fft.h>
float array[64*1026], *coeff;
coeff = scfft2dui( 1024, 64, NULL);
csfft2du( -1, 1024, 64, array, 1026, coeff);
scfft2du( 1, 1024, 64, array, 1026, coeff);
NOTE_1 : The Direct and Inverse transforms should use opposite signs -
Which one is used (+1 or -1) for Direct transform is just a matter of
convention-
Page 2
csfft2du,zdfft2du(3F) csfft2du,zdfft2du(3F)
NOTE_2 : The Fourier Transforms are not normalized so the succession
Direct-Inverse transform scales the input data by a factor equal to the
size of the transform.
SEE ALSO
fft, scfft2dui, dzfft2dui, scal2d, dscal2d
Page 3
