格策爾演算法

格策爾演算法或格茲爾演算法（英語：Goertzel algorithm）是數位訊號處理的一種運算技巧，此運算技巧提供一個有效率的方式來估計部分區域的離散傅立葉轉換，廣泛的運用在數字電話中的雙音多頻信號（每個撥號的數字鍵由兩個頻率的音所組成，一個低頻，一個高頻），此演算法在1958年被所提出Goertzel, G. (January 1958), "An Algorithm for the Evaluation of Finite Trigonometric Series", American Mathematical Monthly, 65 (1): 34–35, doi:10.2307/2310304。

格策爾演算法與離散傅立葉轉換的相似處在於他們都可以分析某個特定頻段的離散訊號Mock, P. (March 21, 1985), "Add DTMF Generation and Decoding to DSP-μP Designs " (PDF), EDN, ISSN 0012-7515 ; also found in DSP Applications with the TMS320 Family, Vol. 1, Texas Instruments, 1989.Chen, Chiouguey J. (June 1996), Modified Goertzel Algorithm in DTMF Detection Using the TMS320C80 DSP (PDF), Application Report, Texas Instruments, SPRA066Schmer, Gunter (May 2000), DTMF Tone Generation and Detection: An Implementation Using the TMS320C54x  (PDF), Application Report, Texas Instruments, SPRA096a；相反的，它們的不同處在於，格策爾演算法每次疊代的運算都是使用實數的乘法。雖然說在全頻域的計算上，格策爾演算法會比其他的傅立葉轉換快速演算法的複雜度來的高，但是它能區段式的分析每個小區段的頻率組成，因此可以編寫成較簡單的運算架構，實際應用在處理器內的數值計算會更有效率。

格策爾演算法逆向操作生成出弦波，而這個過程只需花費一個乘法和一個加法運算http://haskell.cs.yale.edu/wp-content/uploads/2011/01/AudioProc-TR.pdf.。

 演算法 
格策爾演算法把離散傅立葉轉換看成是一組濾波器，將輸入的訊號與濾波器中的脈衝響應做卷積運算，求得濾波器的輸出，即得到頻率域其中一點的頻率。此演算法利用旋轉因子的週期性，將離散傅立葉轉換轉換為線性的濾波運算。

因為旋轉因子

可得轉換後第k點的頻率為

定義為

可將理解為由兩個訊號的卷積運算得出的結果

其中式輸入的N點訊號，另外一個則被看作是IIR濾波器的脈衝頻率響應

對比(2)和(3)式，可推知(3.A)進行卷積運算，當n=N時，濾波器的輸出即為:

對(4)進行Z轉換，可得一階IIR轉移函數

圖一為此系統的流程圖，其對應的差分方程式為:

缩略图|550x550像素|圖一、格策爾一階濾波器系統示意圖
依照此差分方程進行疊代運算，疊代到時即可依據(5)式得到。而依照轉移函數(6)式進行運算時，可以先將旋轉因子儲存起來，每次疊代包含一次複數乘法，則按照(1)式計算N點離散傅立葉轉換時則需要次實數乘法運算和次加/減法http://www.docin.com/p-577391532.html，加/減法與乘法運算皆為次，當N不大時運算效率不佳，若改為接下來改進的的格策爾演算法(二階)，所需的實數乘法次數約為原本的一半。

將式(6)上下同乘以，可得第k點的頻率響應轉移函數為
缩略图|566x566像素|圖二、格策爾二階濾波器系統圖
此轉移函數所對應的系統流程圖如圖二所示，複數分析(8)式，可得知此二階濾波器有一對共軛的極點與一個零點。圖二中在計算的轉換結果時，會有兩個步驟:
 共軛極點疊代計算   依序將輸入訊號放入濾波器做疊代運算，共作N次疊代，計算量是次實數乘法與次實數加/減法
 零點疊代計算   輸入訊號是N點的訊號從。加入的邊界條件，可以按照圖二的流程圖計算出，此即為所求的離散傅立葉轉換，此步驟的計算量為4次實數乘法與4次實數加/減法。
綜合以上步驟，總共的計算量為次實數乘法運算以及次實數加法運算，而使用此計算演算法只需儲存與兩個參數。

 相關條目 
 雙音多頻
 Chirp-Z轉換
 頻率偏移調變(FSK)
 相位偏移調變(PSK)

 參考資料 

 延伸閱讀 
 Proakis, J. G.; Manolakis, D. G. (1996), Digital Signal Processing: Principles, Algorithms, and Applications, Upper Saddle River, NJ: Prentice Hall, pp. 480–481

 外部連結 
 格策爾演算法網站介紹(英文)
 頻域分析數位訊號數理演算法 (英文)
 格策爾演算法網站介紹 (英文) 作者: Kevin Bank,2002

Category:快速傅立葉轉換演算法
Category:线性滤波器
Category:離散轉換