괴르첼 알고리즘

괴르첼 알고리즘은 이산 푸리에 변환(DFT)의 개별 용어를 효율적으로 평가하기 위한 디지털 신호 처리(DSP) 기법이다. 기존의 아날로그 전화기의 키패드의 푸시버튼에 의해 생성되는 듀얼 톤 다중주파수신호(DTMF) 톤의 인식과 같은 특정 실용적 용도에 유용하다. 이 알고리즘은 1958년 제럴드 괴르첼에 의해 처음 설명되었다.^[1]

DFT와 마찬가지로 괴르첼 알고리즘은 이산 신호에서 선택 가능한 주파수 성분을 분석한다.^[2][3][4] 직접 DFT 계산과 달리 괴르첼 알고리즘은 실제 값 입력 시퀀스에 대해 실제 값 산술을 사용하여 각 반복마다 단일 실제 값 계수를 적용한다. 전체 스펙트럼을 커버하는 경우, 괴르첼 알고리즘은 빠른 FFT(Fast Fourier Transform) 알고리즘보다 복잡도 순서가 높지만, 소수의 선택된 주파수 성분을 계산하는 경우에는 수치적으로 더 효율적이다. 괴르첼 알고리즘의 단순한 구조로 소형 프로세서와 임베디드 애플리케이션에 잘 적합하다.

괴르첼 알고리즘은 또한 사인 합성 함수로 "역방향으로" 사용될 수 있는데, 이 함수는 생성된 샘플당 1개의 곱셈과 1개의 뺄셈을 필요로 한다.^[5]

알고리즘

이 섹션은 위키피디아의 품질 기준을 충족시키기 위해 정리가 필요할 수 있다. 구체적인 문제는 방정식과 레이블 사이의 일관성 없는 스타일이다. 가능한 경우 이 섹션을 개선하는 데 도움을 주십시오. (2014년 2월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

괴르첼 알고리즘의 주요 계산은 디지털 필터의 형태를 가지고 있으며, 이러한 이유로 알고리즘을 괴르첼 필터라고 부르는 경우가 많다. 필터는 $\Omega {\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$ 매개변수로 2단계 계단식으로 입력$$ 시퀀스 $x{\displaystyle }$[$n]$에서 작동하여 분석할 주파수를 샘플당 라디안으로 정규화한다.

첫 번째 단계는 중간 시퀀스, $s{\displaystyle }$[${\displaystyle n}$ ${\displaystyle ]}$ ${\displaystyle s[n]}$을(를) 계산한다$.$

${\displaystyle s[n]=x[n]+2\cos(\omega _{0}s[n-1]-s[n-2].}$

(1)

두 번째 단계는 $출력{\displaystyle }$ 시퀀스 $y{\displaystyle }$[${\displaystyle n}$ ${\displaystyle s[n]}$에 다음 필터를 적용하며$,$ 출력 시퀀스 y [${\displaystyle n}$ ${\displaystyle ]}$ ${\displaystyle y[n]}$을(를) 생성한다$.$

${\displaystyle y[n]=s[n]-e^{-j\omega_{0}s[n-1].}$

(2)

첫 번째 필터 단계는 직접 형태 구조를 가진 2차 IIR 필터로 관찰할 수 있다. 이 특정 구조는 내부 상태 변수가 해당 단계의 과거 출력 값과 같다는 속성을 갖는다. < ${\displaystyle n<0}$에 대한 입력 값 $x{\displaystyle }$[$n]$은 모두 0으로 가정한다. $초기{\displaystyle }$ 필터 상태를 설정하여 샘플 ${\displaystyle \mathrm{x}}$[ 0 ${\displaystyle ]}$ ${\displaystyle x[0]$에서 평가를 시작할$$수 있도록 하기 위해 필터 $상태$에 초기 값 s${\displaystyle }$[${\displaystyle }$- ${\displaystyle 2}$ ${\displaystyle ]}$= s${\displaystyle }$[${\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle ]}$= ${\displaystyle 0}$ ${\displaystyle$ s$[-2]=s[-1]=0}$을(를) 할당한다$.$ 앨리어싱 위험을 피하기 위해 주파수 $\Omega {\displaystyle {}_{}}$ {\$displaystytype \oon$ \s \s$_{0}$을 0 ~ }로 제한하는 경우가$$ 많다.$ee$ Nyquist-Shannon 샘플링 정리);이 범위를 벗어나는 값을 사용하는 것은 무의미하지 않지만, 지수 함수는 $0$에서 2㎛의 기간으로 주기 때문에 이 범위 내에서 $앨리어싱된$ 주파수를 사용하는 것과 동등하다$.$

2단계 필터는 과거 출력을 전혀 사용하지 않기 때문에 FIR 필터로 관찰할 수 있다.

필터 계단식 특성을 연구하기 위해 Z 변환 방법을 적용할 수 있다. 식 (1)에서 주어진 첫 번째 필터 단계의 Z 변환은

${\displaystyle {\begin{aligned}{\frac {S(z)}{X(z)}}&={\frac {1}{1-2\cos(\omega _{0})z^{-1}+z^{-2}}}\\&={\frac {1}{(1-e^{+j\omega _{0}}z^{-1})(1-e^{-j\omega _{0}}z^{-1})}}.\end{정렬}}}$

(3)

등식 (2)에서 주어진 두 번째 필터 단계의 Z 변환은

${\displaystyle {\frac {Y(z)}{S(z)}}=1-e^{-e^{j\omega_{0}z^{-1}.}$

(4)

두 필터 단계의 계단식 복합 전달 기능은 다음과 같다.

${\displaystyle {\begin{aligned}{\frac {S(z)}{X(z)}}{\frac {Y(z)}{S(z)}}={\frac {Y(z)}{X(z)}}&={\frac {(1-e^{-j\omega _{0}}z^{-1})}{(1-e^{+j\omega _{0}}z^{-1})(1-e^{-j\omega _{0}}z^{-1})}}\\&={\frac {1}{1-e^{+j\omega _{0}}z^{-1}}}.\end{정렬}}}$

(5)

이는 동일한 시간 영역 시퀀스로 다시 변환할 수 있으며, 인덱스 $n{\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle n=0}$에서 첫 번째 입력 항으로 롤백되지 않은 용어$:$^{[citation needed]}

${\displaystyle {\begin{aligned}y[n]&=x[n]+e^{+j\omega _{0}}y[n-1]\\&=\sum _{k=-\infty }^{n}x[k]e^{+j\omega _{0}(n-k)}\\&=e^{j\omega _{0}n}\sum _{k=0}^{n}x[k]e^{-j\omega _{0}k}\qquad {\text{since }}\forall k<0,x[k]=0.\end{정렬}}}$

(6)

수치안정성

필터의 Z 변환의 극은 복잡한 Z 변환면의 원점을 중심으로 한 단위 반지름 원 위에$$$e{\displaystyle {}^{+{j\Omega \mathrm{}}_{}}}$ 0 ${\$ e$^{+j\omega _{0}}$ 및$$ $e{\displaystyle {}^{{}_{}}}$ ${\displaystyle {{0\mathrm{}}_{}}^{}}$ ${\$에 위치하는 것을 관찰할 수 있다. 이 특성은 저정밀 산술과 긴 입력 시퀀스를 사용하여 계산했을 때 필터 공정이 약간 안정적이고 수치 오류 축적에 취약함을 나타낸다.^[6] 크리스찬 리퍼치가 수치로 안정된 버전을 제안했다.^[7]

DFT 연산

DFT 용어 계산의 중요한 경우, 다음과 같은 특별한 제한이 적용된다.

• 필터링은 색인 $N{\displaystyle }$= ${\displaystyle N}$ ${\displaystyle$ n$=N}$에서 종료되며$,$ 여기서 $N{\displaystyle }$ ${\displaystyle N}$은 DFT의 입력 시퀀스에 있는 항의 수입니다.
• Gaertzel 분석을 위해 선택한 주파수는 특수 양식으로 제한된다.

${\displaystyle \omega _{0}=2\pi {\frac {k}{N}}.}$

(7)

• DFT의 "주파수 빈"을 나타내는$$ 인덱스 번호 $k{\displaystyle }$ ${\displaystyle$ k$}$이(가) 인덱스 번호 집합에서 선택됨

${\displaystyle k\in \{0,1,2,...,N-1\}.}$

(8)

이러한 대체를 방정식 (6)로 만들고 $e{\displaystyle {}^{}}$+ j ${\displaystyle 2^{}}$ ${\displaystyle {\pi }^{}}$ ${\displaystyle \mathrm{k}{}^{}}$= 1 ${\displaystyle e^{+j2\pi$ k$}=1$ 방정식 (6)을 관찰하면 다음과 같은 형태가 된다.

${\displaystyle y[N]=\sum _{n=0}^{N}x[n]e^{-j2\pi {\frac {nk}{N}}}}.}$

(9)

방정식(9)의 오른쪽이 지수 $번호{\displaystyle }$ k의 $DFT{\displaystyle }$ ${\displaystyle \mathrm{용어}}$ X${\displaystyle }$[$$k ${\displaystyle ]}$ {\$displaystyle$$$X$[$$k]}$에 대한 정의 공식과 매우 유사하지만 정확히 동일하지는 않다는 것을 관찰할 수 있다$.$ 방정식(9)에 표시된 합계는 ${\displaystyle \mathrm{N}}$+ $1{\displaystyle }$ ${\displaystyle$ N$+1$} 입력$$ 항을 필요로 하지만 DFT를 평가할 때는 $N{\displaystyle }$ ${\displaystyle N}$ 입력$$ 항만 사용할 수 있다. 지만 우아하지 못한 간단한 방편 .[8]우리는 방정식에서(9)은 최종 결과에 관한 수학적 효과가 가중에서 용어)[N]{\displaystyle x[N]}을 제거하게 돼 같다를 볼 수 있다니 더 많은 인공 가치와 같이[n]{\displaystyle x[n]})[N])입력 시퀀스 0{\displaystyle x[N]=0}업무를 하고 있다. 드의도된 DFT 값의 간을 맞춘다.

그러나 여분의 필터 패스를 피하는 더욱 우아한 접근법이 있다. 식 (1)로부터, 우리는 확장된 입력 $용어{\displaystyle }$ x${\displaystyle }$[ ${\displaystyle N}$ ${\displaystyle ]}$= ${\displaystyle 0}$ ${\displaystyle x[N]=0}$을(를) 최종 단계에서 사용할 때,

$[\displaystyle s[N]=2\cos(\omega _{0})s[N-1]-s[N-2].}$

(10)

따라서 알고리즘은 다음과 같이 완료할 수 있다.

• 입력 용어 $x{\displaystyle }$[ ${\displaystyle N}$- ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle x[N-1]}$을(를) 처리한 후 IIR 필터를 종료하십시오$.$
• 식(10)을 적용하여 이전 $출력{\displaystyle }$ s${\displaystyle }$[${\displaystyle N}$- ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle$ $s$$[N-1]$ 및 $s$ [${\displaystyle N}$- ${\displaystyle 2}$ ${\displaystyle ]}$ ${\displaystyle s[N-2]}$에서 s${\displaystyle }$[${\displaystyle N}$ ${\displaystyle ]}$을$$생성한다$.$
• 계산된 $s{\displaystyle }$[ N ${\displaystyle ]}$ ${\displaystyle s[N]}$ 값과$$ 필터의 최종 직접 계산에 의해 생성된$$ $s{\displaystyle }$[${\displaystyle N}$- ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle s[N-1]}$을(를) 사용하여 방정식을 적용한다.

마지막 두 수학 연산을 대수적으로 결합하여 단순화한다.

${\displaystyle {\begin{aligned}y[N]&=s[N]-e^{-j2\pi {\frac {k}{N}}}s[N-1]\\&=(2\cos(\omega _{0})s[N-1]-s[N-2])-e^{-j2\pi {\frac {k}{N}}}s[N-1]\\&=e^{j2\pi {\frac {k}{N}s[N-1]-s[N-2].\end{정렬}}}$

(11)

용어 $N{\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle N-1}$에서 필터 업데이트를 중지하고$$ 방정식(11)이 아닌 방정식(2)을 즉시 적용하면 최종 필터 상태 업데이트가 누락되어 위상이 부정확한 결과가 나온다는 점에 유의하십시오.^[9]

괴르첼 알고리즘에 대해 선택된 특정 필터링 구조가 효율적인 DFT 계산의 핵심이다. DFT 계산에는 출력 값 $y{\displaystyle }$[ ${\displaystyle N}$ ${\displaystyle ]}$ ${\displaystyle y[N]}$만 사용되므로$$ 다른 모든 출력 항에 대한 계산은 생략된다. FIR 필터가 계산되지 않으므로 IIR 단계 $계산$은 ${\displaystyle \mathrm{1단계}}$의 $내부$ 상태를 업데이트한 후 $즉시$ 폐기할 수 있다$.$

이는 역설적인 것으로 보인다: 알고리즘을 완성하려면 FIR 필터 스테이지가 IIR 필터 스테이지의 최종 두 출력을 사용하여 한 번 평가되어야 하는 반면, 계산 효율을 위해 IIR 필터 반복은 출력 값을 무시한다. 직형 필터 구조의 속성이 적용되는 곳이다. IIR 필터의 두 내부 상태 변수는 FIR 필터 단계의 평가에 필요한 용어인 IIR 필터 출력의 마지막 두 값을 제공한다.

적용들

파워스펙트럼 용어

Examining equation (6), a final IIR filter pass to calculate term ${\displaystyle y[N]}$ using a supplemental input value ${\displaystyle x[N]=0}$ applies a complex multiplier of magnitude 1 to the previous term ${\displaystyle y[N-1]}$. Consequently, ${\displaystyle y[N]}$ and ${\displaystyle y[}$${\displaystyle N}$- ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle y[N-1]}$은 등가 신호 출력을 나타낸다. 등식 (11)을 적용하고 $y{\displaystyle [N}$ $][\displaystyle$ y$[N]]}$에서 신호 출력을 계산하거나$$ (2)를 적용하여 y${\displaystyle [}N{\displaystyle }$ - ${\displaystyle 1]}$ ${\displaystyle y[N-1]}$에서 신호 출력을 계산하는 것이 동등하게 유효하다$.$ 두 경우 모두 DFT $용어{\displaystyle }$X [ ${\displaystyle k}$ ${\displaystyle ]}${\$displaystylease$로 대표되는 신호 출력에 대해 다음과 같은 식을 도출한다.$X[k]}$:

${\displaystyle {\begin{aligned}X[k]\,X'[k]&=y[N]\,y'[N]=y[N-1]\,y'[N-1]\\&=s^{2}[N-1]+s^{2}[N-2]-2\cos \left(2\pi {\frac {k}{N}}\right)\,s[N-1]\,s[N-2].\end{정렬}}}$

(12)

아래 유사 코드에서 변수 sprev 그리고 sprev2 IIR 필터의 출력 기록을 임시로 저장하는 동안 x[n] 배열의 색인화된 요소 x입력을 저장하는 것.

Nterms defined here Kterm selected here ω = 2 × π × Kterm / Nterms; cr := cos(ω) ci := sin(ω) coeff := 2 × cr  sprev := 0 sprev2 := 0 for each index n in range 0 to Nterms-1 do     s := x[n] + coeff × sprev - sprev2     sprev2 := sprev     sprev := s end  power := sprev2 × sprev2 + sprev × sprev - coeff × sprev × sprev2 

다른 처리가 완료된 후 최종 전력 결과에 액세스하여 들어오는 샘플이 업데이트 사이의 필터 상태를 유지하는 소프트웨어 객체에 단독으로 전달되도록 연산을 체계화할^[10] 수 있다.

실제 값을 산술한 단일 DFT 항

실제 값 입력 데이터의 경우는 특히 입력 스트림이 물리적 프로세스의 직접 측정에서 발생하는 임베디드 시스템에서 빈번하게 발생한다. 입력 데이터가 실제 값일 때 필터 내부 상태 변수인 이전 섹션의 그림과 비교 sprev 그리고 sprev2 또한 실제 값을 관측할 수 있으며, 따라서 첫 번째 IIR 단계에서는 복잡한 산술적 계산이 필요하지 않다. 일반적으로 실제 값 산술에 대한 최적화는 변수에 적절한 실제 값 데이터 유형을 적용하는 것만큼 간단하다.

입력 용어 $x{\displaystyle }$[ ${\displaystyle N}$- ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle x[N-1$을 사용한 계산 후 필터 반복이 종료된 후 DFT 항을 평가하기 위해 방정식(11)을 적용해야 한다. 최종 계산은 복잡한 산수를 사용하지만, 이것은 실제와 가상의 용어를 구분하여 실제 가치 산술로 변환할 수 있다.

${\displaystyle {\begin{aligned}c_{r}&=\cos(2\pi {\tfrac {k}{N}}),\\c_{i}&=\sin(2\pi {\tfrac {k}{N}}),\\y[N]&=c_{r}s[N-1]-s[N-2]+jc_{i}s[N-1].\end{정렬}}}$

(13)

전력 스펙트럼 어플리케이션과 비교했을 때, 유일한 차이점은 다음과 같은 계산을 마칠 때 사용하는 것이다.

(신호 전력 구현 시와 동일한 IIR 필터 계산) XKreal = sprev * cr - sprev2; XKimag = sprev * ci; 

위상탐지

이 애플리케이션은 실제 값 또는 복합 값 입력 스트림을 사용하여 이전 섹션에서 설명한 것과 동일한 DFT 용어 $X{\displaystyle }$[${\displaystyle k}$ ${\displaystyle ]}$ ${\displaystyle$ X$[k$의 평가를 요구한다. 그러면 신호 위상은 다음과 같이 평가할 수 있다.

${\displaystyle \phi =\tan ^{-1}{\frac {\Im(X[k]))}}{\Re(X[k])}},}$

(14)

역 접선 함수를 계산할 때 특이점, 사분면 등에 대한 적절한 예방 조치를 취한다.

실제 산술에서의 복잡한 신호

복잡한 신호가 선형적으로 실제 부분과 가상 부분으로 분해되기 때문에 괴르첼 알고리즘은 실제 부분의 ${\displaystyle {순서}_{}}$에 따라 실제 산술적으로 계산될 수 있으며, $y{\displaystyle {}_{}}$ r${\displaystyle {}_{}}$[${\displaystyle n}$ ${\displaystyle ]}$ ${\displaystyle y_{\$$text$$\{$$r}}}$을(를) 산출하고, 가상 부분의 순서에 따라 ${\displaystyle {yi}_{}}$[$]{\displaystystystyle y_{i}$를 산출할 수 있다$.$ 즉, 두 가지 복합 값 부분 결과를 재결합할 수 있다.

${\displaystyle y[n]=y_{\text{r}[n]+datable_{\text{i}}[n]}$

(15)

계산 복잡성

이 섹션은 검증을 위해 추가 인용구가 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 비소싱 소재는 도전하여 제거할 수 있다. (2014년 2월) (이 템플릿 메시지 제거 방법 및 시기 학습)

• According to computational complexity theory, computing a set of ${\displaystyle M}$ DFT terms using ${\displaystyle M}$ applications of the Goertzel algorithm on a data set with ${\displaystyle N}$ values with a "cost per operation" of ${\displaystyle K}$ has complexity ${\displaystyle O(KNM)}$.

길이 $N{\displaystyle }$ ${\displaystyle N}$의 복잡한 입력 시퀀스에 대해$$ 단일 DFT bin $X{\displaystyle (f}$ ${\displaystyle )}$ ${\displaystyle X(f)}$을(를$)$ 계산하려면 Goertzel 알고리즘에는 루프 내에서 ${\displaystyle \mathrm{2N}}$ ${\displaystyle 2N}$ 곱과$$ ${\displaystyle \text{4N}}$ ${\displaystystyle$ 4\ N$}$의 추가/수축이 필요하다.이온, 총 ${\displaystyle \mathrm{2N}}$+ 4 ${\디스플레이$ 스타일 $2N+4}$의 승수와 ${\displaystyle \mathrm{4N}}$+ ${\displaystyle 4}$ ${\디스플레이$ 스타일 $4N+4}$의 추가$$/수축용. $이$는 각 M ${\displaystyle M}$ 주파수에서$$ 반복된다.

• 반대로, N $값$이$${\$displaystyle N}$인 데이터 집합에서 FFT를 사용하는 경우 $복잡도{\displaystyle }$O(${\displaystyle K}$ ${\displaystyle N}$ 로그${\displaystyle n}$N )$${\$displaystyle$ O$(KN\log$ N$)}$이(가) 있다$.$

This is harder to apply directly because it depends on the FFT algorithm used, but a typical example is a radix-2 FFT, which requires ${\displaystyle 2\log _{2}(N)}$ multiplications and ${\displaystyle 3\log _{2}(N)}$ additions/subtractions per DFT bin, for each of the ${\displaystyle N}$ 통에 담다

복잡도 순서 식에서 계산된 $용어{\displaystyle }$ M ${\displaystyle M}$이(가) ${\displaystyle \mathrm{로그}}$ ${\displaystyle }$ ${\displaystyle N}$ ${\displaystyle \log N}$보다 작을$$ 때 Goertzel 알고리즘의 이점은 분명하다$.$ 그러나 FFT 코드는 비교적 복잡하기 때문에 FFT의 경우 "작업 단위당 비용" $인자{\displaystyle }$ K ${\displaystyle K}$이($가)$ 더 큰 경우가 많으며, $실질적$인 이점은 ${\displaystyle {로그\mathrm{}}_{}}$ 2 $⁡$ ${\displaystyle (N})$보다$$몇 배$$ 더 큰 M {\$displaystystyle$ $M}$의 경우에도 Gaertzel 알고리즘을 $선호$한다.

radix-2 FFT 또는 Gaertzel 알고리즘이 더 효율적인지 여부를 결정하기 위한 규칙으로서, $이$ $N{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ $N}$을(를) 2의 가장 가까운 정확한 전력으로 상향 조정하고, 이 N 2 {\displaystyle $N_{2$}}$$로 부르면 Gaertzel 알고리즘이 더 빠를 것 같다.

${\displaystyle M\leq {\frac {5N_{2}}:{6N}\log _{2}(N_{2})}$

FFT 구현 및 처리 플랫폼은 상대적 성능에 상당한 영향을 미친다. 일부 FFTon-the-fly 계수를 발생할 것이"일의 단가 K."FFT그리고 DFT 알고리즘 증가하고 더 나은 수치는 효율을 위해서pre-computed 계수 값의 표를 사용할 수 있지만 이 계수 값 외부에 버퍼링 되기 위해 더 많은 액세스 하는 필요로 한다 내부complex-number 계산을 수행하 implementations[11].나mory, 수적 우위 중 일부에 대응하는 캐시 경합 증가로 이어질 수 있다.

두 알고리즘 모두 복잡한 값 입력 데이터가 아닌 실제 값을 사용할 때 대략 2개의 효율을 얻는다. 그러나 이러한 이득은 괴르첼 알고리즘에서는 당연한 것이지만 FFT에서는 실제 가치 데이터를 변환하는 데 특화된 특정 알고리즘 변형을^[which?] 사용하지 않으면 달성되지 않는다.

참고 항목

• 블루스타인의 FFT 알고리즘(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, Bibcode:1996dspp.book.....P

외부 링크

• 웨이백 머신의 괴르첼 알고리즘(2018-06-28)
• 주파수분석을 위한 DSP 알고리즘
• 케빈 뱅크스의 괴르첼 알고리즘