1math::fourier(n)               Tcl Math Library               math::fourier(n)
2
3
4
5______________________________________________________________________________
6

NAME

8       math::fourier - Discrete and fast fourier transforms
9

SYNOPSIS

11       package require Tcl  8.4
12
13       package require math::fourier  1.0.2
14
15       ::math::fourier::dft in_data
16
17       ::math::fourier::inverse_dft in_data
18
19       ::math::fourier::lowpass cutoff in_data
20
21       ::math::fourier::highpass cutoff in_data
22
23______________________________________________________________________________
24

DESCRIPTION

26       The  math::fourier  package implements two versions of discrete Fourier
27       transforms, the ordinary transform and the fast Fourier  transform.  It
28       also provides a few simple filter procedures as an illustrations of how
29       such filters can be implemented.
30
31       The purpose of this document is to describe the implemented  procedures
32       and  provide some examples of their usage. As there is ample literature
33       on the algorithms involved, we refer to relevant text  books  for  more
34       explanations.  We  also  refer to the original Wiki page on the subject
35       which describes some of the considerations behind the current implemen‐
36       tation.
37

GENERAL INFORMATION

39       The two top-level procedures defined are
40
41       ·      dft data-list
42
43       ·      inverse_dft data-list
44
45       Both take a list of complex numbers and apply a Discrete Fourier Trans‐
46       form (DFT) or its inverse respectively to these lists  of  numbers.   A
47       "complex  number"  in this case is either (i) a pair (two element list)
48       of numbers, interpreted as the real and imaginary parts of the  complex
49       number, or (ii) a single number, interpreted as the real part of a com‐
50       plex number whose imaginary part is zero. The return value is always in
51       the  first  format. (The DFT generally produces complex results even if
52       the input is purely real.) Applying first one and  then  the  other  of
53       these  procedures  to  a  list of complex numbers will (modulo rounding
54       errors due to floating point arithmetic) return the  original  list  of
55       numbers.
56
57       If the input length N is a power of two then these procedures will uti‐
58       lize the O(N log N) Fast Fourier Transform algorithm. If  input  length
59       is not a power of two then the DFT will instead be computed using a the
60       naive quadratic algorithm.
61
62       Some examples:
63
64
65                  % dft {1 2 3 4}
66                  {10 0.0} {-2.0 2.0} {-2 0.0} {-2.0 -2.0}
67                  % inverse_dft {{10 0.0} {-2.0 2.0} {-2 0.0} {-2.0 -2.0}}
68                  {1.0 0.0} {2.0 0.0} {3.0 0.0} {4.0 0.0}
69                  % dft {1 2 3 4 5}
70                  {15.0 0.0} {-2.5 3.44095480118} {-2.5 0.812299240582} {-2.5 -0.812299240582} {-2.5 -3.44095480118}
71                  % inverse_dft {{15.0 0.0} {-2.5 3.44095480118} {-2.5 0.812299240582} {-2.5 -0.812299240582} {-2.5 -3.44095480118}}
72                  {1.0 0.0} {2.0 8.881784197e-17} {3.0 4.4408920985e-17} {4.0 4.4408920985e-17} {5.0 -8.881784197e-17}
73
74
75       In the last case, the imaginary parts <1e-16 would have  been  zero  in
76       exact arithmetic, but aren't here due to rounding errors.
77
78       Internally,  the  procedures  use  a  flat list format where every even
79       index element of a list is a real part and every odd index  element  is
80       an  imaginary  part. This is reflected in the variable names by Re_ and
81       Im_ prefixes.
82
83       The package includes two simple filters. They have an analogue  equiva‐
84       lent  in  a  simple electronic circuit, a resistor and a capacitance in
85       series. Using these filters requires the math::complexnumbers package.
86

PROCEDURES

88       The public Fourier transform procedures are:
89
90       ::math::fourier::dft in_data
91              Determine the Fourier transform of the  given  list  of  complex
92              numbers.  The  result  is a list of complex numbers representing
93              the (complex) amplitudes of the Fourier components.
94
95              list in_data
96                     List of data
97
98
99       ::math::fourier::inverse_dft in_data
100              Determine the inverse Fourier transform of  the  given  list  of
101              complex  numbers  (interpreted  as  amplitudes). The result is a
102              list of complex numbers representing the original (complex) data
103
104              list in_data
105                     List of data (amplitudes)
106
107
108       ::math::fourier::lowpass cutoff in_data
109              Filter the (complex) amplitudes so  that  high-frequency  compo‐
110              nents  are  suppressed.  The implemented filter is a first-order
111              low-pass filter, the discrete equivalent of a simple  electronic
112              circuit with a resistor and a capacitance.
113
114              float cutoff
115                     Cut-off frequency
116
117              list in_data
118                     List of data (amplitudes)
119
120
121       ::math::fourier::highpass cutoff in_data
122              Filter the (complex) amplitudes so that low-frequency components
123              are suppressed. The implemented filter is a first-order low-pass
124              filter,  the  discrete equivalent of a simple electronic circuit
125              with a resistor and a capacitance.
126
127              float cutoff
128                     Cut-off frequency
129
130              list in_data
131                     List of data (amplitudes)
132
133

BUGS, IDEAS, FEEDBACK

135       This document, and the package it describes, will  undoubtedly  contain
136       bugs  and  other  problems.  Please report such in the category math ::
137       fourier of the Tcllib Trackers  [http://core.tcl.tk/tcllib/reportlist].
138       Please  also  report any ideas for enhancements you may have for either
139       package and/or documentation.
140
141       When proposing code changes, please provide unified diffs, i.e the out‐
142       put of diff -u.
143
144       Note  further  that  attachments  are  strongly  preferred over inlined
145       patches. Attachments can be made by going  to  the  Edit  form  of  the
146       ticket  immediately  after  its  creation, and then using the left-most
147       button in the secondary navigation bar.
148

KEYWORDS

150       FFT, Fourier transform, complex numbers, mathematics
151

CATEGORY

153       Mathematics
154
155
156
157tcllib                               1.0.2                    math::fourier(n)
Impressum