C語言做離散傅里葉變換和逆變換

快速傅里葉換要求做傅里葉變換的數據點數是2的整數次冪，即點數是2,4,8,16,32,64,128,256,512,1024,…。實際使用中很多數據點數并不是2的整數次冪，這時可以利用數據變化規律將其拓展為2的整數次冪個數據點，當然，還可以直接使用離散傅里葉變化，離散傅里葉變換對數據點數沒有要求，本文分享自己使用的C語言做離散傅里葉變換和逆變換的代碼。需要注意的是，快速傅里葉變化的時間復雜度是O(nlogn),而離散傅里葉變換的時間復雜度是O(n*n),當數據點數在1000以上時，離散傅里葉變化花費的時間明顯大于快速傅里葉變換。

#include <stdio.h> #include <stdlib.h> #include <math.h> #define PI 3.1415926typedef struct {double real,imag; } complex; //定義復數結構void DFT_Calculate_Point(complex Input_Squence[], complex Result_Point[], int k, int len) {int n = 0;complex Sum_Point;complex One_Point[len];Sum_Point.real = 0;Sum_Point.imag = 0;for (n = 0; n < len; n++){One_Point[n].real = (Input_Squence[n].real) * cos(2 * PI * k * n / len)+ Input_Squence[n].imag * sin(2 * PI * k * n / len); //復數的實部One_Point[n].imag = Input_Squence[n].imag * cos(2 * PI * k * n / len)- (Input_Squence[n].real) * sin(2 * PI * k * n / len); //復數的虛部Sum_Point.real += One_Point[n].real; //對實部求和Sum_Point.imag += One_Point[n].imag; //對虛部求和}Result_Point[k].real = Sum_Point.real;Result_Point[k].imag = Sum_Point.imag; }void DFT_Calculate(complex Input_Squence[], complex Result_Point[], int len) {int i = 0;for (i = 0; i < len; i++){DFT_Calculate_Point(Input_Squence, Result_Point, i, 14);printf("%lf %lf\n", Result_Point[i].real, Result_Point[i].imag);} }void IDFT_Calculate_Point(complex Input_Squence[], complex Result_Point[], int k, int len) {int n = 0;complex Sum_Point;complex One_Point[len];Sum_Point.real = 0;Sum_Point.imag = 0;for (n = 0; n < len; n++){One_Point[n].real = (Input_Squence[n].real) * cos(2 * PI * k * n / len)- Input_Squence[n].imag * sin(2 * PI * k * n / len); //復數的實部One_Point[n].imag = Input_Squence[n].imag * cos(2 * PI * k * n / len)+ (Input_Squence[n].real) * sin(2 * PI * k * n / len); //復數的虛部Sum_Point.real += One_Point[n].real; //對實部求和Sum_Point.imag += One_Point[n].imag; //對虛部求和}Result_Point[k].real = (Sum_Point.real) / len;Result_Point[k].imag = (Sum_Point.imag) / len; }void IDFT_Calculate(complex Input_Squence[], complex Result_Point[], int len) {int i = 0;for (i = 0; i < len; i++){IDFT_Calculate_Point(Input_Squence, Result_Point, i, 14);printf("%lf %lf\n", Result_Point[i].real, Result_Point[i].imag);} }int main(int argc, char *argv[]) {int i = 0;complex Input_Squence[14], Result_Point[100];// Input_Squence[0].real=105, Input_Squence[0].imag=0;// Input_Squence[1].real=-7, Input_Squence[1].imag=30.669;// Input_Squence[2].real=-7, Input_Squence[2].imag=14.53565;// Input_Squence[3].real=-7, Input_Squence[3].imag=8.77772;// Input_Squence[4].real=-7, Input_Squence[4].imag=5.58231;// Input_Squence[5].real=-7, Input_Squence[5].imag=3.37102;// Input_Squence[6].real=-7, Input_Squence[6].imag=1.59770;// Input_Squence[7].real=-7, Input_Squence[7].imag=0;// Input_Squence[8].real=-7, Input_Squence[8].imag=-1.59770;// Input_Squence[9].real=-7, Input_Squence[9].imag=-3.37102;// Input_Squence[10].real=-7, Input_Squence[10].imag=-5.58231;// Input_Squence[11].real=-7, Input_Squence[11].imag=-8.77772;// Input_Squence[12].real=-7, Input_Squence[12].imag=-14.53565;// Input_Squence[13].real=-7, Input_Squence[13].imag=-30.669;for (i = 0; i < 14; i++) //產生輸入序列{Input_Squence[i].real = i + 1;Input_Squence[i].imag = 0;}// IDFT_Calculate(Input_Squence, Result_Point, 14); //進行DFT計算DFT_Calculate(Input_Squence, Result_Point, 14);return 0; }

上面給出了做離散傅里葉變換和逆變換的示例代碼，包含了測試代碼。分享一個在線做傅里葉變換的網站，可以驗證自己做傅里葉變換的結果。http://www.yunsuan.info/signalprocessing/compute_fft_2d.html

總結

以上是生活随笔為你收集整理的C语言做离散傅里叶变换和逆变换的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。