离散傅里叶DFT变换

目录：1、傅里叶变换的问题2、复数的基础知识3、傅里叶变换的基础知识4、离散傅里叶变换5、递推离散傅里叶6、问题的解答7、总结1、傅里叶变换的问题下面两道题关于使用傅里叶变换的， 这应该是很常见的嵌入式问题：A)系统用 ADC(16bit) 采样 50Hz 交流电流电压，采样频率 800Hz，试求出电流、电压幅值以及功率和功率因数。B)上面的 50Hz 电压中， 混入了另一个 50Hz 的电压，求出这两个电压的幅值。这两道题使用 16bit、32bit 的整数运算，不使用浮点运算，可以在 MCU 上实现。C)完成一个 wav 声音文件的变速不变调的程序。2、复数的基础知识在讲解 Fourier Transform 前，必须知道一点基本的复数知识。在复平面上的一个点P(x, y) 用复数表示为：P = x + iy用极坐标表示为：P = r *e^(ia)r = √(x*x + y*y) 是点(x, y) 到原点的距离， θ = arctan(x, y) 是角度，e(数学-e的自然之美) 是自然常数。这里引出一个非常重要的表达式：e^(iθ) = cos(θ) + i sin(θ)，公式推导来自：数学的精美之4、欧拉公式推导★。此式利用复数完成角度变换和三角函数变换的利器。例如，把点P 旋转 b 角度，那么新点(x1, y1) 的角度为 a+b，距离仍为 r。 P1 = x1 + i y1 = r * e^[i (a+b)] = r*e^(i a) * e^(i b) = (x + i y) * [cos(b)+i sin(b)] = [x * cos(b) - y * sin(b)] + i [ y * cos(b) + x * sin(b)]3、傅里叶变换的基础知识傅里叶变换是一个积分变换， 可直接打开链接以获取更详尽的解释：快速傅里叶FFT变换、基2 FFT时间抽取和频域抽取算法。4、离散傅里叶变换1）变换公式离散傅里叶变换即DFT的公式：其中，X(k) 是第 k次谐波的复数；N为周期采样点数；x(n)为输入，n从0到N-1。用伪代码更直观地说明：typedef short int16; typedef int int32; typedef struct SComplex { int16 Real;//实部 int16 Image;//虚部 } Complex; void CalculateHarmonic(Complex* X, int harmonic) //计算谐波，harmonic为x次谐波，x=1、2、3…… { for (int i=0; iN; i++) { X-Real = x(i) * cos( 2*PI* i/N * harmonic)/N; //x(i)为输入，i从0到i-1 X-Image = x(i) * sin(-2*PI* i/N * harmonic)/N; //N=16 } }可以看到，离散傅里叶变换基本运算其实很简单， 没有那么复杂。只要有了 N个输入，比如说通过 AD 采样了 N个数据后，可以轻易的计算出各次谐波，虽然计算量大了些。下面要做的就是减少计算量，这可以用两种方法： 一种当然就是熟知的FFT，还有一种就是递推。2）代码解析struct ffts { double real; double imag; }DFTSWN[2][16]={ {/**********一次波（基波）***************/ {1.000000e+00,-0.000000e+00}, //01 {9.238795e-01,-3.826834e-01}, //02 {7.071068e-01,-7.071068e-01}, //03 {3.826834e-01,-9.238795e-01}, //04 {-8.269461e-16,-1.000000e+00}, //05 {-3.826834e-01,-9.238795e-01}, //06 {-7.071068e-01,-7.071068e-01}, //07 {-9.238795e-01,-3.826834e-01}, //08 {-1.000000e+00,1.653892e-15}, //09 {-9.238795e-01,3.826834e-01}, //10 {-7.071068e-01,7.071068e-01}, //11 {-3.826834e-01,9.238795e-01}, //12 {2.480838e-15,1.000000e+00}, //13 {3.826834e-01,9.238795e-01}, //14 {7.071068e-01,7.071068e-01}, //15 {9.238795e-01,3.826834e-01}, //16 }, { /***********二次谐波***************/ {1.000000e+00,-0.000000e+00}, //01 {7.071068e-01,-7.071068e-01}, //02 {-8.269461e-16,-1.000000e+00}, //03 {-7.071068e-01,-7.071068e-01}, //04 {-1.000000e+00,1.653892e-15}, //05 {-7.071068e-01,7.071068e-01}, //06 {2.480838e-15,1.000000e+00}, //07 {7.071068e-01,7.071068e-01}, //08 {1.000000e+00,-3.307784e-15}, //09 {7.071068e-01,-7.071068e-01}, //10 {-4.134730e-15,-1.000000e+00}, //11 {