summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile2
-rw-r--r--TODO8
-rw-r--r--debian/control1
-rw-r--r--fft.cpp73
-rw-r--r--fft.h36
-rw-r--r--main.cpp24
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<std::complex<double>> RIT::FFT::operator()(const std::vector<std::complex<double>> &v) {
+std::vector<std::complex<double>> RIT::FFT::operator()(const std::vector<std::complex<double>> &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<std::complex<double>>& src, std::vector<std::complex<double>>& dst) {
+void RIT::FFT::reorder(const std::vector<std::complex<double>>& src, std::vector<std::complex<double>>& dst) const {
int size = src.size();
dst.resize(size);
@@ -94,7 +94,7 @@ void RIT::FFT::reorder(const std::vector<std::complex<double>>& 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<std::complex<double>>::iterator X, int N) {
+void RIT::FFT::fft_recursive(std::vector<std::complex<double>>::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<std::complex<double>>::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<std::complex<double>>::iterator X, int N) {
+void RIT::FFT::fft_half(std::vector<std::complex<double>>::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<std::complex<double>>::iterator X, int N) {
X[k] += expLUT[k * mSize / N] * X[k+N/2];
}
}
+
+struct RIT::IFFT::Impl {
+public:
+ using transform_function = std::complex<double> (*)(const std::complex<double>&);
+
+ Impl(int size): mFft(std::make_shared<RIT::FFT>(size)) {}
+ Impl(std::shared_ptr<RIT::FFT> fft): mFft(fft) {}
+ ~Impl(){}
+ std::shared_ptr<RIT::FFT> mFft;
+};
+
+RIT::IFFT::IFFT(int size): mImpl(std::make_unique<RIT::IFFT::Impl>(size))
+{
+}
+
+RIT::IFFT::IFFT(std::shared_ptr<RIT::FFT> fft): mImpl(std::make_unique<RIT::IFFT::Impl>(fft))
+{
+}
+
+RIT::IFFT::~IFFT()
+{
+}
+
+std::vector<std::complex<double>> RIT::IFFT::operator()(const std::vector<std::complex<double>> &v) const
+{
+ std::vector<std::complex<double>> input(v.size());
+
+ std::transform(std::begin(v), std::end(v), std::begin(input), static_cast<Impl::transform_function>(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<RIT::FFT>(size)), mIfft(mFft) {}
+ std::shared_ptr<RIT::FFT> mFft;
+ RIT::IFFT mIfft;
+};
+
+RIT::AutoCorrelation::AutoCorrelation(int size): mImpl(std::make_unique<RIT::AutoCorrelation::Impl>(size))
+{
+}
+
+RIT::AutoCorrelation::~AutoCorrelation()
+{
+}
+
+std::vector<std::complex<double>> RIT::AutoCorrelation::operator()(const std::vector<std::complex<double>> &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 <complex>
+#include <memory>
#include <vector>
namespace RIT {
+// Fast Fourier Transform
class FFT {
private:
int mSize;
@@ -17,18 +19,42 @@ private:
public:
FFT(int size, bool halfOnly = false);
- std::vector<std::complex<double>> operator()(const std::vector<std::complex<double>> &v);
+ std::vector<std::complex<double>> operator()(const std::vector<std::complex<double>> &v) const;
FFT& SetHalfOnly(bool enable);
private:
- int bitreverse(int i);
+ int bitreverse(int i) const;
- void reorder(const std::vector<std::complex<double>>& src, std::vector<std::complex<double>>& dst);
- void fft_recursive(std::vector<std::complex<double>>::iterator X, int N);
- void fft_half(std::vector<std::complex<double>>::iterator X, int N);
+ void reorder(const std::vector<std::complex<double>>& src, std::vector<std::complex<double>>& dst) const;
+ void fft_recursive(std::vector<std::complex<double>>::iterator X, int N) const;
+ void fft_half(std::vector<std::complex<double>>::iterator X, int N) const;
}; // class FFT
+// Inverse FFT
+class IFFT {
+public:
+ IFFT(int size);
+ IFFT(std::shared_ptr<FFT> fft);
+ ~IFFT();
+ std::vector<std::complex<double>> operator()(const std::vector<std::complex<double>> &v) const;
+
+private:
+ struct Impl;
+ std::unique_ptr<Impl> mImpl;
+}; // class IFFT
+
+class AutoCorrelation {
+public:
+ AutoCorrelation(int size);
+ ~AutoCorrelation();
+ std::vector<std::complex<double>> operator()(const std::vector<std::complex<double>> &v) const;
+
+private:
+ struct Impl;
+ std::unique_ptr<Impl> mImpl;
+}; // class AutoCorrelation
+
std::vector<double> magnitudes(std::vector<std::complex<double>>& 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<std::complex<double>> 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;
}
generated by Reichwein.IT Webserver and cgit