fft.h
#ifndef FFT_H
#define FFT_H
#include <QObject>
#include <QDebug>
* 计算傅里叶变换频谱
#define MAX_MATRIX_SIZE 4194304
#define PI 3.141592653
#define MAX_VECTOR_LENGTH 10000
typedef struct Complex
double rl;
double im;
}Complex;
class fft : public QObject
Q_OBJECT
public:
explicit fft(QObject *parent = nullptr);
bool fft1(QVector<Complex>inVec, int const len, QVector<Complex>&outVec);
bool ifft(Complex const inVec[], int const len, Complex outVec[]);
int get_computation_layers(int num);
bool is_power_of_two(int num);
void test();
signals:
public slots:
#endif
fft.cpp
#include "fft.h"
#include <QDebug>
fft::fft(QObject *parent) : QObject(parent)
bool fft::fft1(QVector<Complex> inVec, const int len, QVector<Complex> &outVec)
if ((len <= 0) || (inVec.isEmpty()) || ( outVec.isEmpty()))
return false;
if (!is_power_of_two(len))
return false;
qDebug()<<"come in";
Complex *pVec = new Complex[len];
Complex *Weights = new Complex[len];
Complex *X = new Complex[len];
int *pnInvBits = new int[len];
for(int i = 0; i < len;i++)
pVec[i].im = inVec.at(i).im;
pVec[i].rl = inVec.at(i).rl;
double fixed_factor = (-2 * PI) / len;
for (int i = 0; i < len / 2; i++) {
double angle = i * fixed_factor;
Weights[i].rl = cos(angle);
Weights[i].im = sin(angle);
for (int i = len / 2; i < len; i++) {
Weights[i].rl = -(Weights[i - len / 2].rl);
Weights[i].im = -(Weights[i - len / 2].im);
int r = get_computation_layers(len);
int index = 0;
for (int i = 0; i < len; i++) {
index = 0;
for (int m = r - 1; m >= 0; m--) {
index += (1 && (i & (1 << m))) << (r - m - 1);
pnInvBits[i] = index;
X[i].rl = pVec[pnInvBits[i]].rl;
X[i].im = pVec[pnInvBits[i]].im;
for (int L = 1; L <= r; L++) {
int distance = 1 << (L - 1);
int W = 1 << (r - L);
int B = len >> L;
int N = len / B;
for (int b = 0; b < B; b++) {
int mid = b*N;
for (int n = 0; n < N / 2; n++) {
int index = n + mid;
int dist = index + distance;
pVec[index].rl = X[index].rl + (Weights[n*W].rl * X[dist].rl - Weights[n*W].im * X[dist].im);
pVec[index].im = X[index].im + Weights[n*W].im * X[dist].rl + Weights[n*W].rl * X[dist].im;
for (int n = N / 2; n < N; n++) {
int index = n + mid;
pVec[index].rl = X[index - distance].rl + Weights[n*W].rl * X[index].rl - Weights[n*W].im * X[index].im;
pVec[index].im = X[index - distance].im + Weights[n*W].im * X[index].rl + Weights[n*W].rl * X[index].im;
for(int i = 0; i< len;i++)
X[i].im = pVec[i].im;
X[i].rl = pVec[i].rl;
for(int i = 0; i < len;i++)
outVec[i].im = pVec[i].im;
outVec[i].rl = pVec[i].rl;
if (Weights) delete[] Weights;
if (X) delete[] X;
if (pnInvBits) delete[] pnInvBits;
if (pVec) delete[] pVec;
return true;
