치프 Z-변환기

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "Chirp Z-transform" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2013년 1월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

처프 Z 변환(CZT)은 이산 푸리에 변환(DFT)의 일반화다.DFT가 단위 원을 따라 균일한 간격으로 Z 평면을 샘플링하는 동안, Z 평면의 나선 호를 따라 처프 Z-변환 샘플은 S 평면의 직선에 해당된다.^[1][2]DFT, 실제 DFT 및 줌 DFT는 CZT의 특별한 경우로 계산할 수 있다.

특히, 처프 Z 변환은 로그 나선형 등고선을 따라 z 점의 유한한_k 수로 Z 변환을 계산하며,^[1][3] 다음과 같이 정의된다.

${\displaystyle X_{k}=\sum _{n=0}^{{N-1}x(n)z_{k}^{-n}}}}$

${\displaystyle z_{k}=A\cdot W^{-k},k=0,1,\dots,M-1}$

여기서 A는 복합 출발점, W는 점 사이의 복합비, M은 계산할 점의 수입니다.

DFT와 마찬가지로, 처프 Z-변환기는 $최대n$ =$\max$ $(M$, N )$n=\max(M,N$) 연산으로 계산할 수 있다$.$ 역 처프 Z-변환(ICZT)에 대한 O(N 로그 N) 알고리즘은 2003년과 2019년에 설명되었다.^[4][5][6]

블루스타인의 알고리즘

블루스타인의 알고리즘은^[7][8] CZT를 콘볼루션으로 표현하고 FFT/IFT를 이용해 효율적으로 구현한다.

DFT는 CZT의 특수한 경우인 만큼, 이를 통해 프라임 사이즈를 포함한 임의 크기의 이산 푸리에 변환(DFT)을 효율적으로 계산할 수 있다. (프라임 사이즈의 FFT에 대한 다른 알고리즘인 레이더의 알고리즘도 DFT를 콘볼루션으로 다시 쓰는 방식으로 작동한다.)1968년 레오 블루스테인(Leo Bluestain)에 의해 잉태되었다.^[7]블루스타인의 알고리즘은 (단변형) z-변환에 기초하여 DFT보다 더 일반적인 변환을 계산하는 데 사용될 수 있다(Rabiner et al., 1969).

DFT가 공식에 의해 정의된다는 점을 상기

${\displaystyle X_{k}=\sum _{n=0}^{{N-1}x_{n}e^{-{\frac {2\pi i}{N}}{N}nk}\qquad k=0,\dots,N-1.}$

지수의 nk 제품을 아이덴티티로 대체하면

${\displaystyle nk={\frac {-(k-n)^{2}}:{2}}+{\frac {n^{2}}+{\frac {k^{2}}:}}$

따라서 다음을 얻는다.

${\displaystyle X_{k}=e^{-{\frac {\pi i}{N}}k^{2}}\sum _{n=0}^{N-1}\left(x_{n}e^{-{\frac {\pi i}{N}}n^{2}}\right)e^{{\frac {\pi i}{N}}(k-n)^{2}}\qquad k=0,\dots ,N-1.}$

이 합계는 정확히 다음과 같이 정의된 두 시퀀스 a와_n b의_n 합이다.

${\displaystyle a_{n}=x_{n}e^{-{\frac {\pi i}{N}n^{2}}}$

${\displaystyle b_{n}=e^{\frac {\pi i}{{N}n^{2}},}$

N 위상 계수 b를_k^* 곱한 콘볼루션의 출력과 함께.즉,

${\displaystyle X_{k}=b_{k}^{*}}\왼쪽(\sum _{n=0}^{N-1a_{n}b_{k-n}\오른쪽)\qquad k=0,\dots,N-1.}$

이 콘볼루션은 콘볼루션 정리를 통해 한 쌍의 FFT(복합 치프 b의_n 사전 계산된 FFT)로 수행할 수 있다.요점은 이러한 FFT가 같은 길이의 N이 아니라는 것이다: 그러한 경련은 FFT에서 정확히 2N–1보다 크거나 같은 길이로 제로패딩하여 계산할 수 있다.특히, 2개 또는 일부 다른 고복합 크기에 맞춰 패딩할 수 있으며, 이를 위해 FFT는 쿨리-에 의해 효율적으로 수행될 수 있다.O(N 로그 N) 시간의 Tukey 알고리즘.따라서, 블루스타인의 알고리즘은 쿨리보다 몇 배 느리지만 프라임 사이즈 DFT를 계산할 수 있는 O(N log N) 방법을 제공한다.복합 크기를 위한 Tukey 알고리즘.

블루스타인의 알고리즘에 있는 콘볼루션에 제로패딩의 사용은 약간의 추가적인 코멘트를 받을 만하다.길이 M ≥ 2N–1의 영패드를 사용한다고 가정합시다.즉_n, a는 길이 M의_n 배열 A로 확장되며, 여기서_n A = 0 < n < N에 대한 a와_n A = 0에 대한 다른_n 의미 - "제로 패딩"의 통상적인 의미.그러나, convolution의 b_k–n 용어 때문에, n의 양수 값과 음수 값 모두 b에_n 요구된다(그 b = b를_n 알린다_–n).무패딩 어레이의 DFT가 암시하는 주기적 경계는 –n이 M-n과 동일하다는 것을 의미한다.따라서 b는_n 길이 M의 배열 B로_n 확장되며, 여기서_n B₀ = b₀, B = B_M–n = 0 < n < N, B = 0은_n 그렇지_n 않다.그런 다음 A와 B를 FFT로 하고, 점으로 곱하여 역 FFT로 하여 일반적인 경동화 정리에 따라 a와 b의 경동화를 얻는다.

또한 DFT를 위한 블루스타인의 알고리즘에 어떤 종류의 콘볼루션이 필요한지에 대해서도 좀 더 정확하게 설명합시다.만일 시퀀스_n b가 주기 N과 n으로 주기적이라면, 길이 N의 주기적 경련이 될 것이고, 제로 패딩은 계산상의 편의만을 위한 것이 될 것이다.그러나 일반적으로는 그렇지 않다.

${\displaystyle b_{n+N}=e^{\frac {\pi i}{N}}{N}(n+N)^{2}}}=b_{n}\왼쪽[e^{\frac {\pi i}{{N}}}}{{N}}(2N+N^{2})\{N}}}\{N}}}}}\{N}}(우)=(-1)^{N}b_{n}.}$

따라서 N의 경우, 심지어 콘볼루션도 주기적이지만, 이 경우 N은 복합적이며 일반적으로 Cooley-와 같은 보다 효율적인 FFT 알고리즘을 사용한다.Tukey. 그러나 N 홀수에게 b는_n 반주기적이며 기술적으로 N 길이의 부정기적 경련을 가진다.그러나 위에서 설명한 대로 a를_n 최소 2N-1의 길이로 제로페이딩하면 그러한 구분이 사라진다.따라서, 단순한 선형 컨볼루션의 결과의 하위 집합(즉, 데이터의 개념적 "확장"은 주기적이든 그렇지 않든)이라고 생각하는 것이 아마도 가장 쉬울 것이다.

z-ray

블루스타인의 알고리즘은 (단변형) z-변환에 기반한 보다 일반적인 변환을 계산하는 데도 사용될 수 있다(Rabiner et al., 1969).특히 다음과 같은 형태의 변환을 계산할 수 있다.

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}z^{nk}\qquad k=0,\dots,M-1,}$

임의 콤플렉스 숫자 z 및 입력과 출력의 N과 M의 다른 숫자에 대해.블루스타인의 알고리즘을 고려할 때, 예를 들어 그러한 변환을 사용하여 스펙트럼의 일부에 대해 보다 미세한 간격을 두고 보간할 수 있다(주파수 분해능은 여전히 줌 FFT와 유사하게 총 샘플링 시간에 의해 제한되지만), 전송 기능 분석 등에서 임의 폴을 강화한다.

이 알고리즘은 푸리에-변환 사례(z = 1)의 경우 위의 시퀀스 b가_n 선형적으로 증가하는 주파수의 복잡한 사인파(syngoid)이기 때문에 chirp z-transform 알고리즘으로 불렸는데, 이를 레이더 시스템에서는 (선형) chirp라고 한다.

참고 항목

• 분수 푸리에 변환

참조

일반

• Leo I. Bluestain, "이연성 푸리에 변환의 연산에 대한 선형 필터링 접근법," 동북전자 연구 및 엔지니어링 회의 기록 10, 218-219 (1968년)
• Lawrence R. Rabiner, Ronald W. Schafer, Charles M. Rader, "The chirp z-transform 알고리즘과 그 적용" 벨 시스템. 기술자 J. 48, 1249-1292 (1969년).또한 Rabiner, Shafer, Rader, "The chirp z-transform 알고리즘," IEEE Transfer에서 출판되었다. 오디오 전자음향 17(2), 86–92(1969)
• D. H. 베일리와 P. N. 스와즈트라우버, "분수 푸리에 변환과 응용," SIAM 리뷰 33, 389-404 (1991년).(z-transform에 대한 이 용어는 비표준적이라는 점에 유의하십시오. 부분적인 푸리에 변환은 일반적으로 완전히 다른 연속적인 변환을 가리킨다.)
• Lawrence Rabiner, "The chirp z-transform algorithm—serendipity에 대한 교훈," IEEE 신호 처리 매거진 21, 118-119 (2004년 3월)(역사적 해설)
• 블라디미르 수코이와 알렉산더 스토이체프: "단위 원으로부터 역 FFT를 일반화" (2019년 10월)# 오픈 액세스.
• 블라디미르 수코이와 알렉산더 스토이체프(Alexander Sokhoy and Alexander Stoytchev): "단위 원의 처프 윤곽에 대한 ICZT 알고리즘의 수학적 오류 분석", Sci Rep 10, 4852(2020).

외부 링크

• 주파수분석을 위한 DSP 알고리즘 - Chirp-Z 변환(CZT)
• 신호 처리에서 50년 된 퍼즐 풀기, 2부