茶年 · 中文维基百科

格策爾演算法

Wikipedia · 2026-06-09 维基百科 👁 1 阅读

格策爾演算法或格茲爾演算法（英語：Goertzel algorithm）是數位訊號處理的一種運算技巧，此運算技巧提供一個有效率的方式來估計部分區域的離散傅立葉轉換，廣泛的運用在數字電話中的雙音多頻信號（每個撥號的數字鍵由兩個頻率的音所組成，一個低頻，一個高頻），此演算法在1958年被所提出。

格策爾演算法與離散傅立葉轉換的相似處在於他們都可以分析某個特定頻段的離散訊號；相反的，它們的不同處在於，格策爾演算法每次疊代的運算都是使用實數的乘法。雖然說在全頻域的計算上，格策爾演算法會比其他的傅立葉轉換快速演算法的複雜度來的高，但是它能區段式的分析每個小區段的頻率組成，因此可以編寫成較簡單的運算架構，實際應用在處理器內的數值計算會更有效率。

格策爾演算法逆向操作生成出弦波，而這個過程只需花費一個乘法和一個加法運算。

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

因為旋轉因子
{{NumBlk|:|{\omega}^{-kN}_N=e^{-j(2{\pi/N})(-kN)}=1|1}}
可得轉換後第k點的頻率為
{{NumBlk|:|X(k)={\omega}^{-kN}_N\sum_{m=0}^{N-1}x(m){\omega}^{km}_N=\sum_{m=0}^{N-1}x(m){\omega}^{-k(N-m)}_N \qquad\quad ,k=0,1,2,...,N-1|2}}
定義y_{k}(n)為
{{NumBlk|:| y_{k}(n)=\sum_{m=0}^{N-1}x(m){\omega}^{-k(n-m)}_N |3.A}}
可將y_{k}(n)理解為由兩個訊號的卷積運算得出的結果
{{NumBlk|:| y_{k}(n)=x(n)\otimes h_k(n) |3.B}}
其中x(n)式輸入的N點訊號，另外一個h_k(n)則被看作是IIR濾波器的脈衝頻率響應
{{NumBlk|:| h_k(n)={\omega}^{-kn}_N \ u(n) |4}}
對比(2)和(3)式，可推知(3.A)進行卷積運算，當n=N時，濾波器的輸出y_{k}(N)即為X(k):
{{NumBlk|:|X(k)=y_k(n)\lfloor_{n=N}|5}}
對(4)進行Z轉換，可得一階IIR轉移函數
{{NumBlk|:|H_k(z)=\frac {1}{1-{{\omega}^{-k} \ z^{-1}}}|6}}
圖一為此系統的流程圖，其對應的差分方程式為:
{{NumBlk|:|y_{k}(n)={\omega}^{-k}_N \ y_k(n-1)+x(n), \qquad \ y(-1)=0|7}}

依照此差分方程進行疊代運算，疊代到n=N 時即可依據(5)式得到X(k)。而依照轉移函數(6)式進行運算時，可以先將旋轉因子{\omega}^k_N儲存起來，每次疊代包含一次複數乘法，則按照(1)式計算N點離散傅立葉轉換時則需要4N^2次實數乘法運算和N(4N-2)次加/減法，加/減法與乘法運算皆為4N^2次，當N不大時運算效率不佳，若改為接下來改進的的格策爾演算法(二階)，所需的實數乘法次數約為原本的一半。

將式(6)上下同乘以1-{\omega}^k_N \ z^{-1}，可得第k點的頻率響應轉移函數為{{NumBlk|:|\begin{alignat}{2} H_k(z) & = \frac {1-{{\omega}^{k}_N \ z^{-1}}}{(1-{{\omega}^{-k}_N \ z^{-1}})(1-{{\omega}^{k}_N \ z^{-1})}}
\\ & = \frac {1-{{\omega}^{k}_N \ z^{-1}}}{1-2 \ \cos((2{\pi}/N)k) z^{-1}+z^{-2})} \\ \end{alignat}
|8}}

此轉移函數所對應的系統流程圖如圖二所示，複數分析(8)式，可得知此二階濾波器有一對共軛的極點與一個零點。圖二中在計算x(n)的轉換結果X(k)時，會有兩個步驟:

共軛極點疊代計算 依序將輸入訊號x(0),x(1),x(2),...,x(n-1)放入濾波器做疊代運算，共作N次疊代，計算量是2N次實數乘法與4N次實數加/減法

零點疊代計算 輸入訊號x(n)是N點的訊號從n=0,1,2,3,...,N-1。加入x(N)=0的邊界條件，可以按照圖二的流程圖計算出y_{k}(N)，此即為所求的x(n)離散傅立葉轉換X(k)，此步驟的計算量為4次實數乘法與4次實數加/減法。

綜合以上步驟，總共的計算量為2N+4次實數乘法運算以及4N+4次實數加法運算，而使用此計算演算法只需儲存{\omega}^k_N與\cos((2{\pi}/N)k)兩個參數。

實際應用與偵測流程
格策爾演算法適合用於只需檢查少數特定頻率的場合。若系統需要取得完整頻譜，通常可使用快速傅立葉轉換一次計算所有頻率點；但若只關心少數幾個已知頻率，格策爾演算法可以逐一估計指定頻率的離散傅立葉轉換係數，因此在實作上較為直接。此特性使它常被用於雙音多頻（DTMF）訊號偵測、頻率偏移調變（FSK）解調，以及其他需要判斷特定音調是否存在的數位訊號處理問題。

以DTMF接收器為例，每個按鍵訊號由一個低頻組頻率與一個高頻組頻率同時組成。接收端通常會先將音訊切成固定長度的分析區段，再對每一段訊號分別計算各個候選頻率的能量。低頻組與高頻組中能量最大的頻率會被選出，兩者的組合即可對應到按鍵或控制符號。例如若低頻組中770 Hz的能量最大，而高頻組中1336 Hz的能量最大，則可判斷該段訊號對應到按鍵「5」。在這類情況下，系統只需要檢查有限個候選頻率，不需要計算完整的頻率軸，因此格策爾演算法具有實作上的優勢。

實作時，格策爾演算法可視為一種二階遞迴濾波器。對於每一個欲偵測的頻率點，演算法會使用與該頻率相關的係數進行遞迴運算，並在處理完一段長度為 N 的輸入資料後，由最後的狀態值計算該頻率的能量。若輸入訊號中含有該頻率成分，對應的能量通常會顯著增加；若該頻率不存在，能量則會相對較低。因此，音調偵測問題可以轉換成「比較少數指定頻率能量大小」的問題。

不過，實際接收器通常不能只依最大能量直接判斷。背景雜訊、音量變化、取樣率誤差、音調頻率偏移、按鍵持續時間不足，以及兩個音調之間能量比例不合理，都可能造成誤判。因此DTMF偵測通常還會搭配門檻判斷、最短持續時間檢查、頻率容忍範圍，以及低頻組與高頻組能量比例檢查。這些判斷條件可避免將語音、環境聲音或短暫雜訊誤判為有效按鍵。格策爾演算法本身提供的是指定頻率能量的有效估計方法，而完整的DTMF接收器仍需搭配額外的判斷規則。

格策爾演算法與快速傅立葉轉換的取捨也與欲分析的頻率數量有關。當需要分析的頻率點很少時，格策爾演算法可以只針對這些頻率逐點計算；當需要分析的頻率點很多，甚至接近完整頻譜時，快速傅立葉轉換通常較有效率。因此，格策爾演算法並不是全面取代快速傅立葉轉換，而是在「少數指定頻率偵測」的問題中較具優勢。這也是它在電話按鍵音、嵌入式系統與即時音訊偵測中經常被採用的主要原因。

相關條目

  • 雙音多頻
  • 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

外部連結

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

评论 (0)

  • 还没有评论，来抢沙发吧。