arb-fft-0.1.0.0: Pure Haskell arbitrary length FFT library

Numeric.FFT

Description

Arbitrary input vector lengths are handled using a mixed-radix Cooley-Tukey decimation in time algorithm with residual prime length vectors being treated using Rader's algorithm or hand-coded codelets for small primes.

Synopsis

# Documentation

Forward FFT with embedded plan calculation.

Inverse FFT with embedded plan calculation.

Forward FFT with pre-computed plan.

Inverse FFT with pre-computed plan.

Plan calculation for a given problem size.

planFromFactors :: Int -> (Int, Vector Int) -> IO PlanSource

Plan calculation for a given problem factorisation.

execute :: Plan -> Direction -> VCD -> VCDSource

Main FFT plan execution driver.

data Plan Source

A FFT plan. This depends only on the problem size and can be pre-computed and reused to transform (and inverse transform) any number of vectors of the given size.

Constructors

 Plan FieldsplDLInfo :: Vector (Int, Int, VVVCD, VVVCD)Size information and diagonal matrix entries for Danielson-Lanczos recursive decomposition of problem size. plPermute :: Maybe VIInput vector permutation to use before base transformation and recursive Danielson-Lanczos composition. plBase :: BaseTransformBase transformation used for each sub-vector before performing recursive Danielson-Lanczos steps to form the full FFT result.

Instances

 Eq Plan Show Plan

data Direction Source

Transform direction: `Forward` is the normal FFT, `Inverse` is inverse FFT.

Constructors

 Forward Inverse

Instances

 Eq Direction Show Direction

A base transform used at the bottom of the recursive Cooley-Tukey decomposition of the input problem size: either a simple DFT, a special hard-coded small problem size case, or a Rader prime-length FFT invocation.

Constructors

 SpecialBase Hard-coded small-size base transform. FieldsbaseSize :: Int DFTBase Simple DFT base transform, giving problem size and powers of roots of unity needed for transform. FieldsbaseSize :: Int dftWsFwd :: VCD dftWsInv :: VCD RaderBase Prime-length Rader FFT base transform, giving problem size, output index permutation (the input index permutation is folded into the main input permutation of the full transform), pre-transformed Rader b sequence for forward and inverse problems, the (padded or not) problem size for Rader sequence convolution and a sub-plan (either of size baseSize-1 or the next larger power of two) for computing the Rader convolution. FieldsbaseSize :: Int raderOutPerm :: VI raderBFwd :: VCD raderBInv :: VCD raderConvSize :: Int raderConvPlan :: Plan

Instances

 Eq BaseTransform Show BaseTransform