# Fixed-point Fast Fourier Transform

This "no-std" crate is intended for use with cores without an FPU and that can
perform a fixed point FFT more quickly. The FFT code uses
a signed 16 bit number format, which is interpreted as a Q15
format (i.e. one sign bit, 15 fractional bits).

The code was written under the assumption that a Count Leading Zeros (CLZ)
instruction is available on the target architecture and that
`leading_zeros()`uses this instruction.

This code was inspired by [fix_fft.c](https://gist.github.com/Tomwi/3842231),
which is a very simple fixed-point FFT function written in C. The idea is to provide
a simple, straightforward and target-independent FFT implementation.

## Example with complex input data

```rust
use fixed_fft::{fft_radix2_q15, Direction};
use num_complex::Complex;

fn main() {
    let mut samples = [Complex::new(1000, 0); 8];

    println!("input data: {:?}", samples);
    fft_radix2_q15(&mut samples, Direction::Forward).unwrap();
    println!("output data: {:?}", samples);
}
```

## Example with real input data

```rust
use fixed_fft::fft_radix2_real_q15;
use num_complex::Complex;

fn main() {
    let mut samples = [1000; 8];
    let mut result = [Complex::new(0, 0); 5];

    println!("input data: {:?}", samples);
    fft_radix2_real_q15(&mut samples, &mut result, false).unwrap();
    println!("output data: {:?}", result);
}
```