快速傅里叶变换C++递归算法实现

快速傅里叶变换C++递归算法实现

网上有些算法资料经测试运行结果是错误的,虽然代码的使用的是非递归形式。为了方便验证快速傅里叶变换的准确性,我提供了自己设计的递归算法。

基于时域抽取的“基2”快速傅里叶变换算法代码:

    Fouier.h文件:

#pragma once
#include"Complex.h"
class Fouier
{
    Complex * data;
 void fft(int start,int step,int len);
    Complex W(int k,int n);//e^(-i*2*pi*k/n)
public:
    Fouier(void);
    ~Fouier(void);
 
 void fft();
};

    Fouier.c文件:

#include "Fouier.h"
#include<iostream>
using namespace std;
#include<cmath>
#include<ctime>
#define DATALEN 32
#define KEYVALUE 10000 //生成随机浮点数的值,保证分子和分母在这个值之内
#define PI 3.14159265358979323846
Fouier::Fouier(void)
{
    data=new Complex[DATALEN];
    srand(unsigned int(time(0)));
    cout<<"源数据:"<<endl;
 for(int i=0;i<DATALEN;i++)
    {
        data[i]=(rand()%(KEYVALUE))/(double)(rand()%(KEYVALUE)+1);
 if(i%5==0&&i!=0)
            cout<<endl;
        cout<<data[i]<<" ";
    }
    cout<<endl;
}


Fouier::~Fouier(void)
{
    delete [] data;
}
Complex Fouier:: W(int k,int n)//欧拉公式
{
 double alpha=-2*PI*k/n;
 return Complex(cos(alpha),sin(alpha));
}
void Fouier::fft(int start,int step,int len)
{
 if(len==1)//一个元素
    {
 //一个元素不需要变换
 return ;
    }
    fft(start,step*2,len/2);//X1(k)
    fft(start+step,step*2,len/2);//X2(k)
    Complex X1,X2;
 for(int i=0;i<len/2;i++)
    {
        X1=data[start+step*i*2];
        X2=data[start+step*(i*2+1)];
 //计算X(k):k=0~N/2-1
        data[start+step*i]=X1+W(i,len)*X2;
 //计算X(k):k=N/2~N-1
        data[start+step*(i+len/2)]=X1-W(i,len)*X2;
    }
}
void Fouier::fft()
{
    fft(0,1,DATALEN);
    cout<<"变换后数据:"<<endl;
 for(int i=0;i<DATALEN;i++)
    {
 if(i%5==0&&i!=0)
            cout<<endl;
        cout<<data[i]<<" ";
    }
}

Complex.h文件:

#pragma once
#include<iostream>
using namespace std;
class Complex//a+b*i
{
 double a;//实数部分
 double b;//虚数部分
public:
    Complex(double a=0,double b=0);
 //+操作
    friend Complex operator +(Complex &x,Complex &y);
    friend Complex operator +(double x,Complex &y);
    friend Complex operator +(Complex &x,double y);
 //-操作
    friend Complex operator -(Complex &x,Complex &y);
    friend Complex operator -(double x,Complex &y);
    friend Complex operator -(Complex &x,double y);
 //*操作
    friend Complex operator *(Complex &x,Complex &y);
    friend Complex operator *(double x,Complex &y);
    friend Complex operator *(Complex &x,double y);
 //=操作
    Complex operator =(Complex &x);
    Complex operator =(double x);
 //<<操作
    friend ostream & operator<<(ostream&out,Complex&c);

    ~Complex(void);
};
    Complex.c文件:
#include "Complex.h"

Complex::Complex(double a,double b)//虚部默认是0
{
 this->a=a;
 this->b=b;
}


Complex::~Complex(void)
{
}

Complex operator +(Complex &x,Complex &y)
{
 return Complex(x.a+y.a,x.b+y.b);
}
Complex operator +(double x,Complex &y)
{
 return Complex(x+y.a,y.b);
}
Complex operator +(Complex &x,double y)
{
 return Complex(x.a+y,x.b);
}

Complex operator -(Complex &x,Complex &y)
{
 return Complex(x.a-y.a,x.b-y.b);
}
Complex operator -(double x,Complex &y)
{
 return Complex(x-y.a,-y.b);
}
Complex operator -(Complex &x,double y)
{
 return Complex(x.a-y,x.b);
}

Complex operator *(Complex &x,Complex &y)
{
 return Complex(x.a*y.a-x.b*y.b,x.a*y.b+x.b*y.a);
}
Complex operator *(double x,Complex &y)
{
 return Complex(x*y.a,x*y.b);
}
Complex operator *(Complex &x,double y)
{
 return Complex(x.a*y,x.b*y);
}

Complex Complex::operator =(Complex &x)
{
    a=x.a;
    b=x.b;
 return *this;
}
Complex Complex::operator =(double x)
{
    a=x;
    b=0;
 return *this;
}
ostream & operator<<(ostream&out,Complex&c)
{
 if(c.a!=0||c.a==0&&c.b==0)
 out<<c.a;
 if(c.b!=0)
    {
 if(c.b>0)
 out<<"+";
 if(c.b!=1)
 out<<c.b;
 out<<"i";
    }
 return out;
}

    main.c文件:

#include<iostream>
using namespace std;
#include"Fouier.h"

int main()
{
    Fouier f;
    f.fft();
 return 0;
}

    如有错误,欢迎批评指正!

    参考资料:http://zhoufazhe2008.blog.163.com/blog/static/63326869200971010421361/

       维基百科:http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E5%82%85%E7%AB%8B%E5%8F%B6%E5%8F%98%E6%8D%A2

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏haifeiWu与他朋友们的专栏

Python基础(一)

以#开头的语句是注释,解释器会忽略掉注释。其他每一行都是一个语句,当语句以冒号:结尾时,缩进的语句视为代码块。

17450
来自专栏软件开发 -- 分享 互助 成长

C++ STL之查找算法

C++STL有好几种查找算法,但是他们的用法上有很多共同的地方: 1、除了binary_search的返回值是bool之外(查找的了返回true,否则返回fal...

27260
来自专栏ml

nyoj-----前缀式计算

前缀式计算 时间限制:1000 ms  |           内存限制:65535 KB 难度:3 描述 先说明一下什么是中缀式: 如2+(3+4)*5这种我...

34760
来自专栏PHP实战技术

你应该这个姿势学习PHP(2)

1、循环数组有哪几种方式 1)foreach(能够循环关联和索引数组以及对象) 2)for(只能循环索引数组) 3)list和each配合使用循环数组 $arr...

291100
来自专栏章鱼的慢慢技术路

多维数组的传递

16640
来自专栏desperate633

LintCode 字符大小写排序题目分析代码

9110
来自专栏生信小驿站

python-运算符与表达式

你所编写的大多数语句(逻辑行)都包含了表达式(Expressions)。一个表达式的简单例子便是 2+3。表达式可以拆分成运算符(Operators)与操作数(...

22220
来自专栏Python小屋

Python内置函数sorted()和列表方法sort()排序规则不得不说的事

Python内置函数sorted()和列表方法sort()可以使用key参数指定排序规则,并且都是稳定排序,也就是说,对于指定规则不能涵盖的元素,本来谁在前面,...

28130
来自专栏简书专栏

Python正则表达式re库的使用

re.search函数需要传入2个参数,第1个参数是正则表达式,第2个参数是要进行搜索的源字符串。 re.search函数返回结果的数据类型是sre.SRE_...

19920
来自专栏PHP在线

PHP函数

请点击上面蓝色PHP关注 你知道这些简单的函数中的方法吗? count() 函数计算数组中的单元数目或对象中的属性个数。 对于数组,返回其元素的个数,对于其他值...

30150

扫码关注云+社区

领取腾讯云代金券