Documentation
¶
Overview ¶
Package fft implements Fast-Fourier Transforms.
Algorithm ¶
Example of the alogrithm with N=8 (P=3) Butterfly diagram:
1st stage p=0 2nd state p=1 3rd stage p=2
IN +------------------+ +--------------------+ +-----------------------+
overwrite overwrite output
x0 -\/- x0 + E20 * x1 -> x0 -\ /- x0 + E40 * x2 -> x0 -\ /- x0 + E80 * x4 -> x0
x1 -/\- x0 + E21 * x1 -> x1 -\\//- x1 + E41 * x3 -> x1 -\\ //- x1 + E81 * x5 -> x1
/\ \\ //
x2 -\/- x0 + E22 * x1 -> x2 -//\\- x0 + E42 * x2 -> x2 -\ \\/ /- x2 + E82 * x6 -> x2
x3 -/\- x0 + E23 * x1 -> x3 -/ \- x1 + E43 * x3 -> x3 -\\/\\//- x3 + E83 * x7 -> x3
\\/\\
x4 -\/- x0 + E24 * x1 -> x4 -\ /- x4 + E44 * x6 -> x4 -//\\/\\- x0 + E84 * x4 -> x4
x5 -/\- x0 + E25 * x1 -> x5 -\\//- x5 + E45 * x7 -> x5 -/ /\\ \- x1 + E85 * x5 -> x5
/\ // \\
x6 -\/- x0 + E26 * x1 -> x6 -//\\- x4 + E46 * x6 -> x6 -// \\- x2 + E86 * x6 -> x6
x7 -/\- x0 + E27 * x1 -> x7 -/ \- x5 + E47 * x7 -> x7 -/ \- x3 + E87 * x7 -> x7
Enk are the N complex roots of 1 which were precomputed in E[0]..E[N-1]. The stride s is N/n, and the index in E is k*s mod N, so E21 of the first stage is E[1*8/2 mod 8] = E[4]. These are +/- 1 alternating. and E45 of the second stage is E[5*8/4 mod 8] = E[2]. These are 1,-i,-1,i and again. E8k are all the roots (with stride=1) in increasing order: E[k].
Before starting with the first stage, the input array must be permutated by the bit-inverted order.
References ¶
Based on the public domain version by ktye.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type FFT ¶
type FFT struct {
N int // Fft length, power of 2.
E []complex128 // Precomputed roots table, length N.
// contains filtered or unexported fields
}
FFT base
func (FFT) Inverse ¶
func (f FFT) Inverse(x []complex128) []complex128
Inverse is the backwards transform.
func (FFT) Transform ¶
func (f FFT) Transform(x []complex128) []complex128
Forward transform. The forward transform overwrites the input array.
Source Files