# `Macaw.Data.FFT`
[🔗](https://github.com/dcoai/macaw_data/blob/v0.5.3/lib/macaw/data/fft.ex#L1)

The fast Fourier transform of a real or complex sequence (spec/04 §4.11): a radix-2
Cooley–Tukey decimation in time over lists, `O(N log N)`, pure Elixir. The engine of the
`spectrum` transform, ported from visualize's `Visualize.Data.FFT`.

A time series becomes its frequency spectrum through `spectrum/3`: the newest power of
two of samples, tapered by a window, transformed, and read as one-sided amplitudes —
what the `spectrum` transform of spec/04 §4.11 answers.

    iex> Macaw.Data.FFT.fft([1, 0, 0, 0])
    [{1.0, 0.0}, {1.0, 0.0}, {1.0, 0.0}, {1.0, 0.0}]

# `complex`

```elixir
@type complex() :: {float(), float()}
```

A complex number as `{re, im}`.

# `line`

```elixir
@type line() :: %{frequency: float(), magnitude: float(), phase: float()}
```

One line of a spectrum.

# `fft`

```elixir
@spec fft([number() | complex()]) :: [complex()]
```

The discrete Fourier transform of a sequence whose length is a power of two: numbers
are taken as real, `{re, im}` pairs as complex. Raises `ArgumentError` for any other
length.

    iex> Macaw.Data.FFT.fft([0, 1, 0, -1]) |> Enum.map(fn {re, im} -> {Float.round(re, 9) + 0.0, Float.round(im, 9) + 0.0} end)
    [{0.0, 0.0}, {0.0, -2.0}, {0.0, 0.0}, {0.0, 2.0}]

# `magnitudes`

```elixir
@spec magnitudes([complex()]) :: [float()]
```

The magnitude `sqrt(re² + im²)` of every term.

# `spectrum`

```elixir
@spec spectrum([number()], number(), keyword()) :: [line()]
```

The one-sided amplitude spectrum of a series sampled every `every` seconds: the newest
`samples` values (the largest power of two not above the count when not given), tapered
by `window` (`:hann`), transformed, and read as `samples / 2` lines — `frequency` is
`k / (samples · every)` hertz, `magnitude` the amplitude `|X_k| · 2 / (samples · gain)`
with the window's mean gain divided out (the DC line not doubled), `phase` the argument
of `X_k`. Fewer than two values yield `[]`.

## Options

  * `:samples` - the window length, a power of two; raises `ArgumentError` otherwise
  * `:window` - one of `windows/0` (default `:hann`)
  * `:detrend` - subtract the window's mean before transforming, so an offset does not
    leak from the DC line into its neighbors (default `false`)

    iex> every = 1 / 64
    iex> values = for i <- 0..63, do: :math.sin(2 * :math.pi() * 8 * i * every)
    iex> lines = Macaw.Data.FFT.spectrum(values, every, window: :none)
    iex> peak = Enum.max_by(lines, & &1.magnitude)
    iex> {length(lines), Float.round(peak.frequency, 6), Float.round(peak.magnitude, 6)}
    {32, 8.0, 1.0}

# `window`

```elixir
@spec window([number()], atom()) :: [float()]
```

The sequence tapered by a window: `:hann` (`0.5 − 0.5 cos(2πi/(N−1))`), `:hamming`
(`0.54 − 0.46 cos(2πi/(N−1))`) or `:none`; a sequence shorter than four is not tapered.

    iex> Macaw.Data.FFT.window([1, 1, 1, 1, 1], :hann) |> Enum.map(&Float.round(&1, 3))
    [0.0, 0.5, 1.0, 0.5, 0.0]

# `windows`

```elixir
@spec windows() :: [atom(), ...]
```

The window functions `window/2` applies, `:hann` first.

---

*Consult [api-reference.md](api-reference.md) for complete listing*