1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
.\" placed in the public domain by Will Naylor -*- nroff -*-
.\" 1998-08-21 formatting added by Jim Van Zandt <jrv@vanzandt.mv.com>
.TH WNFFT 3 "August 23, 1998" "WNLIB" ""
.SH NAME
wn_fft_vect, wn_inverse_fft_vect, wn_sft_vect, wn_inverse_sft_vect \- discrete Fourier transform package
.SH SYNOPSIS
.nf
.B #include <wn/wnfft.h>
.sp
.B wn_fft_vect(\fIvector\fP, \fIlen_i\fP)
.B wn_cplx \fIvector\fP[];
.B int \fIlen_i\fP;
.sp
.B wn_inverse_fft_vect(\fIvector\fP, \fIlen_i\fP)
.B wn_cplx \fIvector\fP[];
.B int \fIlen_i\fP;
.sp
.B wn_sft_vect(\fIvector\fP, \fIlen_i\fP)
.B wn_cplx \fIvector\fP[];
.B int \fIlen_i\fP;
.sp
.B wn_inverse_sft_vect(\fIvector\fP, \fIlen_i\fP)
.B wn_cplx \fIvector\fP[];
.B int \fIlen_i\fP;
.SH DESCRIPTION
This package implements the discrete Fourier transform and its
inverse. \fIvector\fP is the data to be transformed; \fIlen_i\fP is
its length. The resulting transformed data is also placed in
\fIvector\fP.
\fBwn_fft_vect\fP and \fBwn_sft_vect\fP implement the following DFT:
out[f] =
(\fIlen_i\fP^(-1/2))*sum_over(0<=t<\fIlen_i\fP){in[t]*exp(-j*2*PI*f*t/\fIlen_i\fP)}
\fBwn_inverse_fft_vect\fP and \fBwn_inverse_sft_vect\fP implement
the following inverse DFT:
out[t] =
(\fIlen_i\fP^(-1/2))*sum_over(0<=f<\fIlen_i\fP){in[f]*exp(j*2*PI*f*t/\fIlen_i\fP)}
where j == (-1)^(1/2).
"sft" stands for "slow Fourier transform" while "fft" stands
for "fast Fourier transform". The fft routines are much faster,
but they require that \fIlen_i\fP be a power of 2. The sft routines
are much slower, but place no restriction on \fIlen_i\fP.
Applying fft and then inverse_fft to a \fIvector\fP yields the original
vector.
.SH RESOURCES
\fBwn_fft_vect\fP and \fBwn_inverse_fft_vect\fP require
WORST and AVERAGE CASE:
.sp
time = \fIlen_i\fP*log(\fIlen_i\fP)
.br
stack memory = log(\fIlen_i\fP)
.br
dynamic memory = \fIlen_i\fP
.sp
\fBwn_sft_vect\fP and \fBwn_inverse_sft_vect\fP require
.sp
WORST and AVERAGE CASE:
.sp
time = \fIlen_i\fP^2
.br
stack memory = 1
.br
dynamic memory = \fIlen_i\fP
.\".SH DIAGNOSTICS
.SH BUGS
This code is new and has not been tested in large industrial
applications.
.SH "SEE ALSO"
.I acc/complex/examples.c
.SH AUTHOR
Will Naylor
|
