C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)算法之實(shí)現(xiàn)快速傅立葉變換
C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)算法之實(shí)現(xiàn)快速傅立葉變換
本實(shí)例將實(shí)現(xiàn)二維快速傅立葉變換,同時(shí)也將借此實(shí)例學(xué)習(xí)用c語(yǔ)言實(shí)現(xiàn)矩陣的基本操作、復(fù)數(shù)的基本掾作,復(fù)習(xí)所學(xué)過(guò)的動(dòng)態(tài)內(nèi)存分配、文件操作、結(jié)構(gòu)指針的函數(shù)調(diào)用等內(nèi)容。
很久以來(lái),傅立葉變換一直是許多領(lǐng)域,如線性系統(tǒng)、光學(xué)、概率論、量子物理、天線、數(shù)字圖像處理和信號(hào)分析等的一個(gè)基本分析工具,但是即便使用計(jì)算速度驚人的計(jì)算機(jī)計(jì)算離散傅立葉變換所花費(fèi)的時(shí)間也常常是難以接受的,因此導(dǎo)致了快速傅立葉變換(FFT)的產(chǎn)生。
本實(shí)例將對(duì)一個(gè)二維數(shù)組進(jìn)行正、反快速傅立葉變換。正傅立葉變換時(shí)dfft()函數(shù)先調(diào)用fft()按行對(duì)數(shù)組進(jìn)行變換,再對(duì)結(jié)果調(diào)用fft()按列進(jìn)行變換,此時(shí)完成了快速傅立葉變換,再調(diào)用rdfft()函數(shù)進(jìn)行傅立葉逆變換。如果程序設(shè)計(jì)正確的話,變換的結(jié)果應(yīng)與原數(shù)組相同。
實(shí)例代碼:
#include <stdio.h> #include <stdlib.h> #include <math.h> #define PI 3.14159265358979323846 struct COMPLEX { float re; float im; } cplx , * Hfield , * S , * R , * w; int n , m; int ln , lm; void initiate (); void dfft (); void rdfft (); void showresult (); void fft (int l , int k); int reverse (int t , int k); void W (int l); int loop (int l); void conjugate (); void add (struct COMPLEX * x , struct COMPLEX * y , struct COMPLEX * z); void sub (struct COMPLEX * x , struct COMPLEX * y , struct COMPLEX * z); void mul (struct COMPLEX * x , struct COMPLEX * y , struct COMPLEX * z); struct COMPLEX * Hread(int i , int j); void Hwrite (int i , int j , struct COMPLEX x); void main () { initiate (); printf("\n原始數(shù)據(jù):\n"); showresult(); getchar (); dfft (); printf("\n快速?gòu)?fù)利葉變換后的結(jié)果:\n"); showresult (); getchar (); rdfft (); printf("\n快速?gòu)?fù)利葉逆變換后的結(jié)果:\n"); showresult (); getchar (); free (Hfield); } void initiate () {//程序初始化操作,包括分配內(nèi)存、讀入要處理的數(shù)據(jù)、進(jìn)行顯示等 FILE * df; df = fopen ("data.txt" , "r"); fscanf (df , "%5d" , &n); fscanf (df , "%5d" , &m); if ((ln = loop (n)) == -1) { printf (" 列數(shù)不是2的整數(shù)次冪 "); exit (1); } if ((lm = loop (m)) == -1) { printf (" 行數(shù)不是2的整數(shù)次冪 "); exit (1); } Hfield = (struct COMPLEX *) malloc (n * m * sizeof (cplx)); if (fread (Hfield , sizeof (cplx) , m * n , df) != (unsigned) (m * n)) { if (feof (df)) printf (" Premature end of file "); else printf (" File read error "); } fclose (df); } void dfft () {//進(jìn)行二維快速?gòu)?fù)利葉變換 int i , j; int l , k; l = n; k = ln; w = (struct COMPLEX *) calloc (l , sizeof (cplx)); R = (struct COMPLEX *) calloc (l , sizeof (cplx)); S = (struct COMPLEX *) calloc (l , sizeof(cplx)); W (l); for ( i = 0 ; i < m ; i++ ) {//按行進(jìn)行快速?gòu)?fù)利葉變換 for (j = 0 ; j < n ; j++) { S[j].re = Hread (i , j)->re; S[j].im = Hread (i , j)->im; } fft(l , k); for (j = 0 ; j < n ; j++) Hwrite (i , j , R[j]); } free (R); free (S); free (w); l = m; k = lm; w = (struct COMPLEX *) calloc (l , sizeof (cplx)); R = (struct COMPLEX *) calloc (l , sizeof (cplx)); S = (struct COMPLEX *) calloc (l , sizeof (cplx)); W (l); for (i = 0 ; i < n ; i++) {//按列進(jìn)行快速?gòu)?fù)利葉變換 for(j = 0 ; j < m ; j++) { S[j].re = Hread(j , i)->re; S[j].im = Hread(j , i)->im; } fft(l , k); for (j = 0 ; j < m ; j++) Hwrite (j , i , R[j]); } free (R); free (S); free (w); } void rdfft () { conjugate (); dfft (); conjugate (); } void showresult () { int i , j; for (i = 0 ; i < m ; i++) { printf ( " \n第%d行\(zhòng)n " , i); for (j = 0 ; j < n ; j++) { if (j % 4 == 0) printf (" \n "); printf(" (%5.2f,%5.2fi) " , Hread (i , j)->re , Hread (i , j)->im); } } } void fft (int l , int k) { int i , j , s , nv , t; float c; struct COMPLEX mp , r; nv = l; c = (float) l; c = pow (c , 0.5); for (i = 0 ; i < k ; i++) { for (t = 0 ; t < l ; t += nv) { for (j = 0 ; j < nv / 2 ; j++) { s = (t + j) >> (k - i -1); s = reverse(s , k); r.re = S[t + j].re; r.im = S[t + j].im; mul (&w[s] , &S[t + j + nv / 2] , &mp);/////////講解傳遞結(jié)構(gòu)指針和結(jié)構(gòu)本身的區(qū)別 add (&r , &mp , &S[t + j]); sub (&r , &mp , &S[t + j + nv / 2]); } } nv = nv >> 1; } for (i = 0 ; i < l ; i++) { j = reverse(i , k); R[j].re = S[i].re / c; R[j].im = S[i].im / c; } } int reverse (int t , int k) { int i , x , y; y = 0; for (i = 0 ; i < k ; i++) { x = t & 1; t = t >> 1; y = (y << 1) + x; } return y; } void W (int l) { int i; float c , a; c = (float) l; c = 2 * PI / c; for (i = 0 ; i < l ; i++) { a = (float) i; w[i].re = (float) cos(a * c); w[i].im = -(float) sin(a * c); } } int loop (int l) {//檢驗(yàn)輸入數(shù)據(jù)是否為2的整數(shù)次冪,如果是返回用2進(jìn)制表示時(shí)的位數(shù) int i , m; if (l != 0) { for (i = 1 ; i < 32 ; i++) { m = l >> i; if (m == 0) break; } if (l == (1 << (i - 1))) return i - 1; } return -1; } void conjugate () {//求復(fù)數(shù)矩陣的共軛矩陣 int i , j; for (i = 0 ; i < m ; i++) { for (j = 0 ; j < n ; j++) { Hread (i , j)->im *= -1; } } } struct COMPLEX * Hread (int i , int j) {//按讀矩陣方式返回Hfield中指定位置的指針 return (Hfield + i * n + j); } void Hwrite (int i , int j , struct COMPLEX x) {//按寫(xiě)矩陣方式將復(fù)數(shù)結(jié)構(gòu)x寫(xiě)到指定的Hfield位置上 (Hfield + i * n + j)->re = x.re; (Hfield + i * n + j)->im = x.im; } void add (struct COMPLEX * x , struct COMPLEX * y , struct COMPLEX * z) {//定義復(fù)數(shù)加法 z->re = x->re + y->re; z->im = x->im + y->im; } void sub (struct COMPLEX * x , struct COMPLEX * y , struct COMPLEX * z) {//定義復(fù)數(shù)減法 z->re = x->re - y->re; z->im = x->im - y->im; } void mul (struct COMPLEX * x , struct COMPLEX * y , struct COMPLEX * z) {//定義復(fù)數(shù)乘法 z->re = (x->re) * (y->re) - (x->im) * (y->im); z->im = (x->im) * (y->re) + (x->re) * (y->im); }
感謝閱讀,希望能幫助到大家,謝謝大家對(duì)本站的支持!
相關(guān)文章
用C++實(shí)現(xiàn)SLR語(yǔ)法分析程序
大家好,本篇文章主要講的是用C++實(shí)現(xiàn)SLR語(yǔ)法分析程序,感興趣的同學(xué)趕緊來(lái)看一看吧,對(duì)你有幫助的話記得收藏一下2022-02-02C++指針和數(shù)組:字符和字符串、字符數(shù)組的關(guān)聯(lián)和區(qū)別
字符串是一種重要的數(shù)據(jù)類型,但是c語(yǔ)言并沒(méi)有顯示的字符串?dāng)?shù)據(jù)類型,因?yàn)樽址宰址A康男问匠霈F(xiàn)或者存儲(chǔ)于字符數(shù)組中。在C++標(biāo)準(zhǔn)模板庫(kù)(STL)中提供了string類,實(shí)現(xiàn)了對(duì)字符串的封裝。2022-12-12C++多態(tài)的實(shí)現(xiàn)機(jī)制深入理解
這篇文章主要介紹了C++多態(tài)的實(shí)現(xiàn)機(jī)制理解的相關(guān)資料,非常不錯(cuò),具有參考借鑒價(jià)值,需要的朋友可以參考下2016-07-07Qt利用tablewidget模擬手指實(shí)現(xiàn)滑動(dòng)
這篇文章主要為大家詳細(xì)介紹了Qt如何利用tablewidget模擬手指實(shí)現(xiàn)滑動(dòng)效果,文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)Qt有一定的幫助,需要的可以參考一下2023-01-01Qt實(shí)現(xiàn)編輯數(shù)據(jù)庫(kù)數(shù)據(jù)的方法詳解
這篇文章主要為大家詳細(xì)介紹了Qt是如何實(shí)現(xiàn)編輯數(shù)據(jù)庫(kù)數(shù)據(jù)的,文中的示例代碼簡(jiǎn)潔易懂,對(duì)我們深入了解QT有一定的幫助,感興趣的小伙伴可以了解一下2023-02-02C++生成dll和調(diào)用dll的方法實(shí)例
C++生成dll和調(diào)用dll的方法實(shí)例,需要的朋友可以參考一下2013-03-03