mathbh / dft Goto Github PK
View Code? Open in Web Editor NEWA bunch of FFT algorithms
A bunch of FFT algorithms
Tesla Belzile-Ha December 5th 2018 ---------------- ----------------- :Fast Fourier Transform Algorithms: -\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\- Implementations of Fast Fourier Transform Algorithms: ===================================================== Currently includes: ------------------- 0) Brute-Force DFT Algorithm 1) Cooley-Tukey FFT Algorithm 2) Prime-Factor FFT Algorithm -------------------------------------------------------------------------------------------------- \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ [0] Brute-Force DFT Algorithm: ============================== A class built from the "DFTAlgorithm" template. Calculates a sample set's Discrete Fourier Transform using a brute-force implementation. Brute Force Algorithm based on equations from "Numerical Recipes in C++" p.508. Files: ====== "BruteForceDft.h", "BruteForceDft.cpp" Functions: ========== reverseDft(dft): ---------------- Rebuilts the original signal from the input dft. input: vector<complex<double>> dft: discrete fourier transform of a signal output: vector<complex<double>> signal: signal constructed from the input dft Templates: ========= "DFTAlgorithm.h": ----------------- Template denoting a class that can calculate the discrete fourier transform for a given set of samples Functions: ========== getDft(samples): ---------------- Calculates the discrete fourier transform of given samples. input: vector<complex<double>> samples: Data set from which the dft is to be calculated. output: vector<complex<double>> dft: Discrete fourier transform calculated from the input samples. [1] Cooley-Tukey FFT Algorithm: =============================== Class with the "DFTAlgorithm" template. Code modified from "Numerical Recipes in C++" p.513. Calculates a sample set's Discrete Fourier Transform using the Cooley-Tukey Algorithm. Files: ====== "CooleyTukeyFFT.h", "CooleyTukeyFFT.cpp" Templates: ========= "DFTAlgorithm.h": ----------------- Template denoting a class that can calculate the discrete fourier transform for a given set of samples Functions: ========== getDft(samples): ---------------- Calculates the discrete fourier transform of given samples. input: vector<complex<double>> samples: Data set from which the dft is to be calculated. output: vector<complex<double>> dft: Discrete fourier transform calculated from the input samples. [2] Prime-Factor FFT Algorithm: =============================== Class with the "DFTAlgorithm" template. Calculates a sample set's Discrete Fourier Transform using the Prime-Factor algorithm. Algorithm from "Fast Fourier Transform and Convolution Algorithms" p.125-129. Files: ====== "PrimeFactorDft.h", "PrimeFactorDft.cpp" Templates: ========= "DFTAlgorithm.h": ----------------- Template denoting a class that can calculate the discrete fourier transform for a given set of samples Functions: ========== getDft(samples): ---------------- Calculates the discrete fourier transform of given samples. input: vector<complex<double>> samples: Data set from which the dft is to be calculated. output: vector<complex<double>> dft: Discrete fourier transform calculated from the input samples. Related Classes: ================ The Prime-Factor Algorithm splits up the data into smaller data sets which it then passes to sub-algorithms. The sub algorithms used are as follows, - BruteForceDft: used as last resort - CooleyTukeyFFT: used when data subset is of a size that does not match any other subalgorithm but is a power of 2. - <SmallDFTs>: Set of classes for calculating small dfts. Algorithms from "Fast Fourier Transform and Convolution" p.145 - p150. These are used by the Prime-Factor Algorithm along with the Brute-Force Algorithm and Cooley-Tukey Algorithm. When splitting the data into factors, any factor that matches the small dfts is calculated with them, any factor that does not match but is a power of two is calculated using the Cooley-Tukey Algorithm. All other factor's corresponding subsets are calculated using the Brute-Force algorithm. Files: "SmallDFTs.h", "SmallDFTs.cpp" Classes: - DFT2: 2-point dft evaluator - template: DFTAlgorithm - DFT3: 3-point dft evaluator - template: DFTAlgorithm - DFT4: 4-point dft evaluator - template: DFTAlgorithm - DFT5: 5-point dft evaluator - template: DFTAlgorithm - DFT7: 7-point dft evaluator - template: DFTAlgorithm -------------------------------------------------------------------------------------------------- \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.