【正文】 以表示成這兩種形式。下面將定義這兩種形式。 由歐拉公式， ()X? 可以寫成如下形式： ( ) ( ) c os ( ) si nX x t w t dt j x t w t dt? ??? ? ? ????? 令 ()R? 和 ()I? 是的實值函數，定義如下： ( ) = ( ) c o s( ) = ( ) sinR x t wt dtI x t wt dt??????????? 則的直角坐標表達式為： ( )= ( )+j ( )X R I? ? ? ()X? 的極坐標表達式，由下式給出： ()( ) | ( ) | jXX X e ??? ?? (115) 式中，是的模，是的輻角。利用下面的關系，可以由直角坐標表達式換成極坐標表達式： 22| ( ) | ( ) ( )X R I? ? ??? ()a r c t a n , ( ) 0()()()a r c t a n , ( ) 0()I RRXI RR? ???????? ????? ?? ???? 離散時間信號的傅里葉分析 DTFT 已知一個離散時間信號 []xn ,他的離散時間傅里葉變換（ DTFT）定義為： ( ) [ ] jnnX x n e? ??????? ? (116) 一般地，由上式定義的 DTFT ()X? 是實變量 ? 的復值函數。 對于所有的實值 ? ，如果上式中的雙邊無限求和收斂，則稱離散時間信號 []xn 有一般意義的 DTFT。 []xn 有一般意義的 DTFT 的充分條件是 []xn 絕對可和，即： | [ ]|n xn???? ??? 如果是時限的離散時間信號，顯然，上式中的和是有限值，類似這樣的信號都存在一般意義下的 DTFT。 已知離散時間信號 []xn ，其 DTFT 為 ()X? ，由于 ()X? 一般是復數，可以 用直角坐標或極坐標的形式來表示。利用歐拉公式得到的 ()X? 的直角坐標形式： ( )= ( )+ j ( )X R I? ? ? 其中： ( ) [ ] c os( ) [ ] c osnnR x n nI x n n????????? ? ?? ? ? ??? ()X? 的極坐標形式是 : ()( ) | ( ) | jXX X e ??? ? ? 其中： 22| ( ) | ( ) ( )X R I? ? ? ? ? ()a r c t a n , ( ) 0()()()a r c t a n , ( ) 0()I RRXI RR???? ??? ???? ? ?? ? ? ?? ?? []xn 是一個離散時間信號，其 DTFT 為 ()X? ，由于 ()X? 是連續(xù)變量 ? 的函數，除非 ()X? 可以表示為封閉形式，否則不能保存在數字計算及的存儲器中。為了能在數字計算及上實現(xiàn) DTFT，必須在頻率上離散化，從而引出了下面定義的離散傅里葉變換的概念。 假設對于所有 0n n N??和 的整數，離散時間信號 []xn 等于零， N 是一個固定的正整數。整數 N 可能很大，例如 102 1024N ?? 。 []xn 的 N 點離散傅里葉變換（ DFT） kX 定義為： 1 2/0= [ ] , 0 , 1 , 2 , , 1N j k n Nk nX x n e k N?? ?? ??? (116) 由式（ 116）可見， DFT kX 是離散變量 k 的函數。 kX 可表示成極坐標形式或直角坐標形式。極坐標形式是： = | | 0 , 1 , 2 , 1kjXkkX X e k N? ?? 直角坐標形式是： = +j 0 , 1 , 2 , 1k k kX R I k N??， 其中： 112( 0 ) [ ] c o sNknknR x x n N????? ? 112[ ] sinNknknI x n N?????? FFT算法 時間抽取算法的基本思想是把時間間隔細分，細分后的時間間隔內包含的點數較少。 kX 的計算可以分成兩部分，首先對符號進行簡化，令 2/jNNWe??? ,復數 NW 是單位 1 的 N 次開放，即： 2 1NjNWe???? 假設 N1，這樣 1NW? 。根據 NW 的表示方法， N 點 DFT 和 DFT 反變換為： 10= [ ] , 0 ,1 , 2 ,N knkNnX x n W k?? ?? 111[ ] , 0 ,1 , 2 ,N knkNkx n X W kN? ????? 現(xiàn)在令 N 是一個偶整數，以便 N/2 是一個整數。已知信號 x[n],令 a[n]為 x[n]的偶數次項， b[n]為x[n]的級數次項。令 kA 和 kB 分別代表 []an 和 []bn 的（ N/2）點 DFT，即： / 2 1/21/ 2 1/21[ ] , 0 , 1 , 2 ,[ ] , 0 , 1 , 2 ,NknkNnNknkNnA a n W kB b n W k???????? 令 kX 代表 []xn 的 N 點 DFT，可有： ( / 2 )= , 0 , 1 , 2 , , / 2 1= , 0 , 1 , 2 , , / 2 1kk k N kkN k k N kX A W B k NX A W B k N?? ? ??? 由上兩式計算 kX 需要 2 / 2 / 2NN? 次乘法。為了看清這一點，首先注意到計算 kA 需要22( / 2) / 4NN? 次乘法，和 kB 一樣多，在上兩式中計算 kNkWB需要 N/2 次乘法，所以，總的乘法次數為 2 / 2 / 2NN? ，比 2N 次乘法少 2 / 2 / 2NN? 次，因此，當 N 非常大時， 可以大大減少乘法次數。 如果 N/2 是偶數， []an 和 []bn 又可以分別表示為兩部分，進而重復上面的過程。如果 q 為正整數，這個遞減的過程可以重復進行，知道信號只剩下一個非零值。 下圖給出了 N=8 時 FFT 算法的流程圖（圖 11），在最左側輸入的是已知信號 []xn ，需要注意信號 []xn 輸入的順序，該順序可以通過“倒位序”的方法來確定。假設 2qN? ，已知整數 n 的范圍是 0~N1，時間標號 n 可以用 q 位二進制數來表示，把這 q 位二進制數進行倒位序排列，記得 FFT 算法每一行的輸入信號 []xn 。表 11 給出了圖 11 中 FFT 算法的輸入信號值的順序。 圖 11 N=8 時的 FFT 算法流程圖 表 11 N=8 時的倒位序排列 時間（ n） 二進制代碼 倒位序代碼 排序 0 000 000 x[0] 1 001 100 x[4] 2 010 010 x[2] 3 011 110 x[6] 4 100 001 x[1] 5 101 101 x[5] 6 110 011 x[3] 7 111 111 x[7] 倒位序算法 在進行 FFT 運算時，第一步要實現(xiàn)的就是倒位序排列。 假設使用 A[I]存的是順序位序，而 B[J]存的是倒位序。 IJ 的時候需要變序， IJ 的時候就不用。不然就相當于作了兩次變序，又變回去了。 從表 11可知，按自然順序排列的二進制數，其下面的數總是比其上面的數大 1，即下面的數是上面的數在最低位加 1 并向高位進位而得到的。而倒位序二進制數的下面的數是上面的數在最高位加 1 并由高位向低位進位而得到。 由數組的性質可知， I、 J 都是從 0 開始，若已知某個倒位序 J，要求下一個倒位序數，則應先判斷 J 的最高位是否為 0，這可與 flag=N/2 相比較。如果 flagJ，則 J 的最高位為 0，只要把該位變?yōu)?1（ J 與 flag=N/2 相加即可），就得到下一個倒位序數；如果 flag=J，則 J 的最高位為 1， 可將最高位變?yōu)?0（ J 與 flag=N/2 相減即可）。然