From 1a219839034e9b11a4771fb84c90d4a2667365ce Mon Sep 17 00:00:00 2001 From: Roland Stigge Date: Sat, 16 Feb 2019 23:37:21 +0100 Subject: Added IFFT + AutoCorrelation --- Makefile | 2 +- TODO | 8 +++++++ debian/control | 1 + fft.cpp | 73 ++++++++++++++++++++++++++++++++++++++++++++++++++++++---- fft.h | 36 +++++++++++++++++++++++++---- main.cpp | 24 +++++++++++++++++++ 6 files changed, 133 insertions(+), 11 deletions(-) diff --git a/Makefile b/Makefile index 2a2971a..b945f7c 100644 --- a/Makefile +++ b/Makefile @@ -21,6 +21,6 @@ main.o: main.cpp fft.h install: clean: - rm -f fft + rm -f fft *.o .PHONY: clean diff --git a/TODO b/TODO index e69de29..e31bca0 100644 --- a/TODO +++ b/TODO @@ -0,0 +1,8 @@ +TODO +==== + +google test +debian + +tuner +android diff --git a/debian/control b/debian/control index 67ff324..4107bec 100644 --- a/debian/control +++ b/debian/control @@ -1 +1,2 @@ +Package: rit-fft Depends: g++, clang diff --git a/fft.cpp b/fft.cpp index 42b0acf..7d76e23 100644 --- a/fft.cpp +++ b/fft.cpp @@ -43,7 +43,7 @@ RIT::FFT::FFT(int size, bool halfOnly): mSize(size), order(size), expLUT(size/2) } -std::vector> RIT::FFT::operator()(const std::vector> &v) { +std::vector> RIT::FFT::operator()(const std::vector> &v) const { if (v.size() != mSize) throw std::length_error("Bad input size"); @@ -64,7 +64,7 @@ RIT::FFT& RIT::FFT::SetHalfOnly(bool enable) { return *this; } -int RIT::FFT::bitreverse(int i) { +int RIT::FFT::bitreverse(int i) const { int size{mSize}; int result{0}; @@ -78,7 +78,7 @@ int RIT::FFT::bitreverse(int i) { return result; } -void RIT::FFT::reorder(const std::vector>& src, std::vector>& dst) { +void RIT::FFT::reorder(const std::vector>& src, std::vector>& dst) const { int size = src.size(); dst.resize(size); @@ -94,7 +94,7 @@ void RIT::FFT::reorder(const std::vector>& src, std::vector // Because of Nyquist theorem, N samples means // only first N/2 FFT results in X[] are the answer. // (upper half of X[] is a reflection with no new information). -void RIT::FFT::fft_recursive(std::vector>::iterator X, int N) { +void RIT::FFT::fft_recursive(std::vector>::iterator X, int N) const { if(N > 2) { fft_recursive(X, N/2); // recurse even items fft_recursive(X+N/2, N/2); // recurse odd items @@ -111,7 +111,7 @@ void RIT::FFT::fft_recursive(std::vector>::iterator X, int } // Same as fft_recursive, but results in only half the result due to symmetry in real input -void RIT::FFT::fft_half(std::vector>::iterator X, int N) { +void RIT::FFT::fft_half(std::vector>::iterator X, int N) const { if(N > 2) { fft_recursive(X, N/2); // recurse even items fft_recursive(X+N/2, N/2); // recurse odd items @@ -121,3 +121,66 @@ void RIT::FFT::fft_half(std::vector>::iterator X, int N) { X[k] += expLUT[k * mSize / N] * X[k+N/2]; } } + +struct RIT::IFFT::Impl { +public: + using transform_function = std::complex (*)(const std::complex&); + + Impl(int size): mFft(std::make_shared(size)) {} + Impl(std::shared_ptr fft): mFft(fft) {} + ~Impl(){} + std::shared_ptr mFft; +}; + +RIT::IFFT::IFFT(int size): mImpl(std::make_unique(size)) +{ +} + +RIT::IFFT::IFFT(std::shared_ptr fft): mImpl(std::make_unique(fft)) +{ +} + +RIT::IFFT::~IFFT() +{ +} + +std::vector> RIT::IFFT::operator()(const std::vector> &v) const +{ + std::vector> input(v.size()); + + std::transform(std::begin(v), std::end(v), std::begin(input), static_cast(std::conj)); + + auto result = (*mImpl->mFft)(input); + + const double factor = 1.0 / v.size(); + std::transform(std::begin(result), std::end(result), std::begin(result), + [=](const auto& x){return std::conj(x) * factor;}); + + return result; +} + +struct RIT::AutoCorrelation::Impl { +public: + Impl(int size): mFft(std::make_shared(size)), mIfft(mFft) {} + std::shared_ptr mFft; + RIT::IFFT mIfft; +}; + +RIT::AutoCorrelation::AutoCorrelation(int size): mImpl(std::make_unique(size)) +{ +} + +RIT::AutoCorrelation::~AutoCorrelation() +{ +} + +std::vector> RIT::AutoCorrelation::operator()(const std::vector> &v) const +{ + auto result = (*mImpl->mFft)(v); + + std::transform(std::begin(result), std::end(result), std::begin(result), + [=](const auto& x){return x * std::conj(x);}); + + return mImpl->mIfft(result); +} + diff --git a/fft.h b/fft.h index f2b7038..8c1e161 100644 --- a/fft.h +++ b/fft.h @@ -3,10 +3,12 @@ #pragma once #include +#include #include namespace RIT { +// Fast Fourier Transform class FFT { private: int mSize; @@ -17,18 +19,42 @@ private: public: FFT(int size, bool halfOnly = false); - std::vector> operator()(const std::vector> &v); + std::vector> operator()(const std::vector> &v) const; FFT& SetHalfOnly(bool enable); private: - int bitreverse(int i); + int bitreverse(int i) const; - void reorder(const std::vector>& src, std::vector>& dst); - void fft_recursive(std::vector>::iterator X, int N); - void fft_half(std::vector>::iterator X, int N); + void reorder(const std::vector>& src, std::vector>& dst) const; + void fft_recursive(std::vector>::iterator X, int N) const; + void fft_half(std::vector>::iterator X, int N) const; }; // class FFT +// Inverse FFT +class IFFT { +public: + IFFT(int size); + IFFT(std::shared_ptr fft); + ~IFFT(); + std::vector> operator()(const std::vector> &v) const; + +private: + struct Impl; + std::unique_ptr mImpl; +}; // class IFFT + +class AutoCorrelation { +public: + AutoCorrelation(int size); + ~AutoCorrelation(); + std::vector> operator()(const std::vector> &v) const; + +private: + struct Impl; + std::unique_ptr mImpl; +}; // class AutoCorrelation + std::vector magnitudes(std::vector>& v); } // namespace RIT diff --git a/main.cpp b/main.cpp index 42cd466..3945cff 100644 --- a/main.cpp +++ b/main.cpp @@ -218,6 +218,24 @@ public: } }; +class MeasureIFFT_RR: public Measure { + RIT::IFFT mIFFT; +public: + MeasureIFFT_RR(const Data& in): Measure(in), mIFFT(in.size()) { mName = "IFFT RR";} + void run_impl() override { + mResult = mIFFT(mIn); + } +}; + +class MeasureAutoCorrelation_RR: public Measure { + RIT::AutoCorrelation mAC; +public: + MeasureAutoCorrelation_RR(const Data& in): Measure(in), mAC(in.size()) { mName = "AutoCorrelation RR";} + void run_impl() override { + mResult = mAC(mIn); + } +}; + int main(int argc, char* argv[]) { std::vector> v(4096, 0); @@ -239,6 +257,12 @@ int main(int argc, char* argv[]) { MeasureFFT_RR_half_magnitudes measureFFT_RR_half_magnitudes(v, measureDFT); measureFFT_RR_half_magnitudes.run(); + + MeasureIFFT_RR measureIFFT_RR(v); + measureIFFT_RR.run(); + + MeasureAutoCorrelation_RR measureAutoCorrelation_RR(v); + measureAutoCorrelation_RR.run(); return 0; } -- cgit v1.2.3