fftconversiondlg.cpp

本程序是用C语言实现的实现fft快速算法

// FFTConversionDlg.cpp : 实现文件
//

#include "stdafx.h"
#include "FFTConversion.h"
#include "FFTConversionDlg.h"
#include ".\fftconversiondlg.h"
#include <cmath>
#include "ListOper.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#endif


// 用于应用程序“关于”菜单项的 CAboutDlg 对话框

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// 对话框数据
	enum { IDD = IDD_ABOUTBOX };

	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV 支持

// 实现
protected:
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
END_MESSAGE_MAP()


// CFFTConversionDlg 对话框



CFFTConversionDlg::CFFTConversionDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CFFTConversionDlg::IDD, pParent)
	, m_NumN(0)
	, m_NumF(0)
	, m_NumT(0)
{
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CFFTConversionDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	DDX_Text(pDX, IDC_EDTN, m_NumN);
	DDV_MinMaxInt(pDX, m_NumN, 0, 10000);
	DDX_Text(pDX, IDC_EDTF, m_NumF);
	DDV_MinMaxInt(pDX, (int)m_NumF, 0, 10000);
	DDX_Text(pDX, IDC_EDTT, m_NumT);
	DDV_MinMaxInt(pDX, (int)m_NumT, 0, 10000);
}

BEGIN_MESSAGE_MAP(CFFTConversionDlg, CDialog)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	//}}AFX_MSG_MAP
	ON_BN_CLICKED(IDC_BTNCLOSE, OnBnClickedBtnclose)
	ON_BN_CLICKED(IDC_BTNCAL, OnBnClickedBtncal)
END_MESSAGE_MAP()


// CFFTConversionDlg 消息处理程序

BOOL CFFTConversionDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// 将\“关于...\”菜单项添加到系统菜单中。

	// IDM_ABOUTBOX 必须在系统命令范围内。
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// 设置此对话框的图标。当应用程序主窗口不是对话框时，框架将自动
	//  执行此操作
	SetIcon(m_hIcon, TRUE);			// 设置大图标
	SetIcon(m_hIcon, FALSE);		// 设置小图标

	ShowWindow(SW_SHOW);

	// TODO: 在此添加额外的初始化代码
	((CButton*)this->GetDlgItem(IDC_RADIODFT))->SetCheck(TRUE);
	this->m_NumN = 32;
	this->m_NumF = 50;
	this->m_NumT = (float)0.000625;
	this->UpdateData(FALSE);
	return TRUE;  // 除非设置了控件的焦点，否则返回 TRUE
}

void CFFTConversionDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// 如果向对话框添加最小化按钮，则需要下面的代码
//  来绘制该图标。对于使用文档/视图模型的 MFC 应用程序，
//  这将由框架自动完成。

void CFFTConversionDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // 用于绘制的设备上下文

		SendMessage(WM_ICONERASEBKGND, reinterpret_cast<WPARAM>(dc.GetSafeHdc()), 0);

		// 使图标在工作矩形中居中
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// 绘制图标
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

//当用户拖动最小化窗口时系统调用此函数取得光标显示。
HCURSOR CFFTConversionDlg::OnQueryDragIcon()
{
	return static_cast<HCURSOR>(m_hIcon);
}

void CFFTConversionDlg::OnBnClickedBtnclose()
{
	// TODO: 在此添加控件通知处理程序代码
	this->DestroyWindow();
}
float pi = (float)3.1415926;
int GetInverse(int N,int preNum)
{
	int K = N/2;
	if(preNum<K)
	{
		return K+preNum;
	}
	else
	{
		return GetInverse(K,preNum-K);
	}
}

/*****************************************
*
*	Name     :DFT
*   Function :Disperse Fuliye Transformation
*   Params   :N -- Total count of sampling points
*             X -- Input sequence
*   Return   :XN(k)=sum[x(n)*Pow(e,j2*Pi/N)] 
*                   k,n:0..N-1
*
*
*****************************************/
void DFT(int N,COMP x[],COMP XK[])
{
	double C = (2*pi)/N;
	COMP t(0,0),ret(0,0);
	for(int k=0;k<N;k++)
	{
		ret = COMP(0,0);
		for(int i=0;i<N;i++)
		{
			t = COMP(cos(C*k*i),-sin(C*k*i));
			ret += x[i]*t;
		}
		XK[k] = ret;
	}

}

/*****************************************
*
*	Name     :FFT
*   Function :Fast Fuliye Transformation
*   Params   :N -- Total count of sampling points
*             X -- Input sequence
*   Return   :XN(k)=sum[x(n)*Pow(e,j2*Pi/N)] 
*                   k,n:0..N-1
*
*
*****************************************/
void FFT(int N,COMP X[],COMP XK[])
{
	int j=0;
	COMP U=0,W=0;
	COMP* A = XK;

	//Adjust sequence
	for(int i=0;i<N;i++)
	{
		if(i==0)
		{
			A[0] = X[0];
		}
		else
		{
			j=GetInverse(N,j);
			A[i] = X[j];
		}
	}

	//确定级别数
	for(int M=0;M<N;M++)
	{
		if((1<<M)==N)
			break;
	}


	for(int L=1;L<=M;L++)//1-M级依次确定
	{
		int LE = (int)pow(2,L);//间隔
		int LE1 = LE/2;//W级数,如W0,W1,W2...

		W=COMP(cos(pi/LE1),-sin(pi/LE1));
		U=COMP(1,0);
		for(j=0;j<LE1;j++)//
		{
			i=j;
			while(i<N)
			{
				int IP = i+LE1;
				COMP T=A[IP]*U;
				A[IP]=A[i]-T;//蝶形计算
				A[i]=A[i]+T;
				i+=LE;
			}

			U=U*W;//不同的W次幂
		}


		
	}


	
}
void initX(int N,COMP x[],float F,float T)
{	
	for(int i=0;i<N;i++)
	{
		x[i] = COMP(cos(2*pi*F*T*i),0);
	}
}

void CFFTConversionDlg::OnBnClickedBtncal()
{
	// TODO: 在此添加控件通知处理程序代码
	this->UpdateData(TRUE);
	int nN = this->m_NumN;
	float fF = this->m_NumF;
	float fT = this->m_NumT;

	bool bIsTimesof2 = false;
	for(int i=0;i<100;i++)
	{
        if(nN==(2<<i))
		{
			bIsTimesof2 = true;
			break;
		}
	}
	if(!bIsTimesof2)
	{
		AfxMessageBox("N请输入一个以2为底的幂级数!");
		this->GetDlgItem(IDC_EDTN)->SetFocus();
		return;
	}
	COMP* x = new COMP[nN];//x(n)
	COMP* X = new COMP[nN];//X(k) 
	initX(nN,x,fF,fT);
	CButton* pRadio = (CButton*)this->GetDlgItem(IDC_RADIODFT);


	if(pRadio->GetCheck())
	{
		DFT(nN,x,X);
	}
	else
	{
		FFT(nN,x,X);		
	}

	char buffer[256];
	COMP source = X[nN-1];
	sprintf(buffer,"%f+%fi",source.real(),source.imag());
	CWnd* pwnd = this->GetDlgItem(IDC_EDTRET);
	pwnd->SetWindowText(buffer);
	
	CListCtrl* pList=(CListCtrl*) this->GetDlgItem(IDC_LIST1);
	CListOper oper;
	oper.FillList(*pList,nN,x,X);

	delete[] x; 
	delete[] X;

}

void CFFTConversionDlg::OnOK()
{
	// TODO: 在此添加专用代码和/或调用基类

	//CDialog::OnOK();
}