15 releases (stable)
|3.3.0||May 28, 2023|
|3.2.0||Dec 8, 2022|
|3.1.0||Nov 9, 2022|
|3.0.0||Feb 9, 2022|
|0.2.1||Jul 22, 2020|
#44 in Algorithms
45,403 downloads per month
Used in 69 crates (22 directly)
RealFFT: Real-to-complex forward FFT and complex-to-real inverse FFT based on RustFFT
This library is a wrapper for RustFFT that enables fast and convenient FFT of real-valued data. The API is designed to be as similar as possible to RustFFT.
Using this library instead of RustFFT directly avoids the need of converting real-valued data to complex before performing a FFT. If the length is even, it also enables faster computations by using a complex FFT of half the length. It then packs a real-valued signal of length N into an N/2 long complex buffer, which is transformed using a standard complex-to-complex FFT. The FFT result is then post-processed to give only the first half of the complex spectrum, as an N/2+1 long complex vector.
The inverse FFT goes through the same steps backwards, to transform a complex spectrum of length N/2+1 to a real-valued signal of length N.
The speed increase compared to just converting the input to a length N complex vector and using a length N complex-to-complex FFT depends on the length of the input data. The largest improvements are for longer FFTs and for lengths over around 1000 elements there is an improvement of about a factor 2. The difference shrinks for shorter lengths, and around 30 elements there is no longer any difference.
Why use real-to-complex FFT?
Using a complex-to-complex FFT
A simple way to transform a real valued signal is to convert it to complex, and then use a complex-to-complex FFT.
x is a 6 element long real vector:
x = [x0r, x1r, x2r, x3r, x4r, x5r]
We now convert
x to complex by adding an imaginary part with value zero.
Using the notation
(xNr, xNi) for the complex value
xN, this becomes:
x_c = [(x0r, 0), (x1r, 0), (x2r, 0), (x3r, 0), (x4r, 0), (x5r, 0)]
Performing a normal complex FFT, the result of
FFT(x_c) = [(X0r, X0i), (X1r, X1i), (X2r, X2i), (X3r, X3i), (X4r, X4i), (X5r, X5i)]
But because our
x_c is real-valued (all imaginary parts are zero), some of this becomes redundant:
FFT(x_c) = [(X0r, 0), (X1r, X1i), (X2r, X2i), (X3r, 0), (X2r, -X2i), (X1r, -X1i)]
The last two values are the complex conjugates of
X3i are zero.
As we can see, the output contains 6 independent values, and the rest is redundant.
But it still takes time for the FFT to calculate the redundant values.
Converting the input data to complex also takes a little bit of time.
If the length of
x instead had been 7, result would have been:
FFT(x_c) = [(X0r, 0), (X1r, X1i), (X2r, X2i), (X3r, X3i), (X3r, -X3i), (X2r, -X2i), (X1r, -X1i)]
The result is similar, but this time there is no zero at
Also in this case we got the same number of independent values as we started with.
Using a real-to-complex FFT removes the need for converting the input data to complex. It also avoids calculating the redundant output values.
The result for 6 elements is:
RealFFT(x) = [(X0r, 0), (X1r, X1i), (X2r, X2i), (X3r, 0)]
The result for 7 elements is:
RealFFT(x) = [(X0r, 0), (X1r, X1i), (X2r, X2i), (X3r, X3i)]
This is the data layout output by the real-to-complex FFT, and the one expected as input to the complex-to-real inverse FFT.
RealFFT matches the behaviour of RustFFT and does not normalize the output of either forward or inverse FFT.
To get normalized results, each element must be scaled by
length is the length of the real-valued signal.
If the processing involves both an FFT and an iFFT step,
it is advisable to merge the two normalization steps to a single, by scaling by
The full documentation can be generated by rustdoc. To generate and view it run:
cargo doc --open
To run a set of benchmarks comparing real-to-complex FFT with standard complex-to-complex, type:
The results are printed while running, and are compiled into an html report containing much more details.
To view, open
target/criterion/report/index.html in a browser.
Transform a signal, and then inverse transform the result.
use realfft::RealFftPlanner; use rustfft::num_complex::Complex; use rustfft::num_traits::Zero; let length = 256; // make a planner let mut real_planner = RealFftPlanner::<f64>::new(); // create a FFT let r2c = real_planner.plan_fft_forward(length); // make a dummy real-valued signal (filled with zeros) let mut indata = r2c.make_input_vec(); // make a vector for storing the spectrum let mut spectrum = r2c.make_output_vec(); // Are they the length we expect? assert_eq!(indata.len(), length); assert_eq!(spectrum.len(), length/2+1); // forward transform the signal r2c.process(&mut indata, &mut spectrum).unwrap(); // create an inverse FFT let c2r = real_planner.plan_fft_inverse(length); // create a vector for storing the output let mut outdata = c2r.make_output_vec(); assert_eq!(outdata.len(), length); // inverse transform the spectrum back to a real-valued signal c2r.process(&mut spectrum, &mut outdata).unwrap();
- 3.3.0: Add method for getting the length of the complex input/output. Bugfix: clean up numerical noise in the zero imaginary components.
- 3.2.0: Allow scratch buffer to be larger than needed.
- 3.1.0: Update to RustFFT 6.1 with Neon support.
- 3.0.2: Fix confusing typos in errors about scratch length.
- 3.0.1: More helpful error messages, fix confusing typos.
- 3.0.0: Improved error reporting.
- 2.0.1: Minor bugfix.
- 2.0.0: Update RustFFT to 6.0.0 and num-complex to 0.4.0.
- 1.1.0: Add missing Sync+Send.
- 1.0.0: First version with new api.
realfft crate has the same rustc version requirements as RustFFT.
The minimum rustc version is 1.37 on all platforms except AArch64.
On AArch64 the minimum rustc version is 1.61.