diff --git a/HW3/fft.hh b/HW3/fft.hh index 78f4a71..71dc58d 100644 --- a/HW3/fft.hh +++ b/HW3/fft.hh @@ -1,112 +1,133 @@ #ifndef FFT_HH #define FFT_HH /* ------------------------------------------------------ */ #include "matrix.hh" #include "my_types.hh" #include /* ------------------------------------------------------ */ struct FFT { static Matrix transform(Matrix& m); static Matrix itransform(Matrix& m); static Matrix> computeFrequencies(int size); }; /* ------------------------------------------------------ */ inline Matrix FFT::transform(Matrix& m_in) { // Implementation for the Forward FFT UInt N = m_in.cols(); // The sampled size UInt Sz = N*N; // Size of the Matrix NxN fftw_plan P; // Initialize a plan // 2D Complex Matricies alocation complex *m_out_f = new complex[Sz], *m_in_f= new complex[Sz]; // Casting Values for (auto&& entry : index(m_in)){ int i = std::get<0>(entry); int j = std::get<1>(entry); auto& val = std::get<2>(entry); m_in_f[i*N+j] = val;} -// I've obtained this (following lines) solution from this link (Not sure but should work): -// http://www.fftw.org/fftw3_doc/Complex-numbers.html -// https://www.reddit.com/r/cpp/comments/jfk9q/is_there_a_quick_way_to_convert_fftw_complex_to_a/ +/// I've obtained this (following lines) solution from this link (Not sure but should work): +/// http://www.fftw.org/fftw3_doc/Complex-numbers.html +/// https://www.reddit.com/r/cpp/comments/jfk9q/is_there_a_quick_way_to_convert_fftw_complex_to_a/ P = fftw_plan_dft_2d( N, N, reinterpret_cast(m_in_f), reinterpret_cast(m_out_f), FFTW_FORWARD, FFTW_ESTIMATE // Your flags here. ); fftw_execute(P); // Casting the final output matrix -> m_out_f_f Matrix m_out_f_f(N); for (auto&& entry : index(m_out_f_f)) { int i = std::get<0>(entry); int j = std::get<1>(entry); auto& val = std::get<2>(entry); val = m_out_f[i*N+j];} // Dealocation (FFTW Destructor) fftw_destroy_plan(P); fftw_free(m_in_f); fftw_free(m_out_f); return m_out_f_f; } /* ------------------------------------------------------ */ inline Matrix FFT::itransform(Matrix& m_in) { // Goes the same as the previouse one // The results are not normalized in this function (Divide by N^2 the output) UInt N = m_in.cols(); UInt Sz = N*N; fftw_plan P; complex *m_out_f = new complex[Sz], *m_in_f= new complex[Sz]; for (auto&& entry : index(m_in)){ int i = std::get<0>(entry); int j = std::get<1>(entry); auto& val = std::get<2>(entry); m_in_f[i*N+j] = val;} P = fftw_plan_dft_2d( N, N, reinterpret_cast(m_in_f), reinterpret_cast(m_out_f), FFTW_BACKWARD, FFTW_ESTIMATE ); fftw_execute(P); Matrix m_out_f_f(N); for (auto&& entry : index(m_out_f_f)) { int i = std::get<0>(entry); int j = std::get<1>(entry); auto& val = std::get<2>(entry); val = m_out_f[i*N+j];} fftw_destroy_plan(P); fftw_free(m_in_f); fftw_free(m_out_f); return m_out_f_f; } /* ------------------------------------------------------ */ /* ------------------------------------------------------ */ inline Matrix> FFT::computeFrequencies(int size) { +/// The i stands for the real part, whereas the j stands for the imaginary part +/// Explanation of procedure on the link: +/// http://www.fftw.org/fftw3.pdf?fbclid=IwAR3bgzRkoSBACIJnMNfk79RX29rsVkIhWgGYg_iJcPvTM_8wLLN045ntywk, specially the figure 2.1 + +int mid = (size % 2 == 0) ? size / 2 : size / 2 + 1; + Matrix> freq(size); + for (auto&& entry : index(freq)) { + int i = std::get<0>(entry); + int j = std::get<1>(entry); + auto& val = std::get<2>(entry); + if(i < mid) + val.real(i); + else + val.real(i - size); + + if(j < mid) + val.imag(j); + else + val.imag(j - size); + } + return freq; } #endif // FFT_HH