쿨리-투키 FFT 알고리즘

쿨리-J. W. Cooley와 John Tukey의 이름을 딴 Tukey 알고리즘은 가장 흔한 빠른 FFT(Fast Fourier Transform) 알고리즘이다.N 크기의₂ N₁ 더 작은 DFT 단위로 임의$$ 복합 $크기{\displaystyle }$ N${\displaystyle }$= ${\displaystyle {}_{}}$ 1 ${\displaystyle {N\mathrm{}}_{}}$ ${\displaystyle {}_{}{}_{}}$ ${\$ N$=N_{1}N_{$2}}의 이산 푸리에 변환(DFT)을 반복적으로 추출하여 높은 복합 N(매끄러운 수)의 경우 계산 시간을 O(N 로그 N)로 줄인다.알고리즘의 중요성 때문에, 아래에 설명된 바와 같이 특정 변형과 구현 스타일은 그들 자신의 이름으로 알려지게 되었다.

왜냐하면 쿨리-Tukey 알고리즘은 DFT를 더 작은 DFT로 분해하며, DFT를 위한 다른 알고리즘과 임의로 결합할 수 있다.예를 들어, 래더나 블루스타인의 알고리즘은 쿨리-에 의해 분해될 수 없는 큰 주요 요소들을 처리하는 데 사용될 수 있다.Tukey 또는 prime-factor 알고리즘은 상대적으로 primary 요소를 분리하는 데 있어 더 큰 효율을 위해 이용될 수 있다.

이 알고리즘은 재귀적 응용과 함께 칼 프리드리히 가우스에 의해 발명되었다.쿨리와 투키는 160년 후에 독자적으로 재발견하여 대중화시켰다.

역사

재귀적 응용을 포함한 이 알고리즘은 1805년경 칼 프리드리히 가우스(Carl Friedrich Gauss)에 의해 발명되었는데, 그는 소행성 팔라스(Pallas)와 주노(Juno)의 궤적을 보간하는데 사용하였으나 그의 저작은 널리 인정되지 않았다(사후에만 출판되고 신라틴어로도 출판되었다).^[1][2]그러나 Gauss는 점증적 계산 시간을 분석하지 않았다.다양한 한정된 형태도 19세기와 20세기 초반에 걸쳐 여러 차례 재발견되었다.^[2]FFT는 1965년 IBM의 제임스 쿨리와 프린스턴의 존 터키가 알고리즘을 재창조하고 컴퓨터에서 편리하게 수행하는 방법을 설명하는 논문을 발표한 후 인기를 끌었다.^[3]

투키는 케네디 대통령의 과학자문위원회 회의에서 이 같은 생각을 떠올린 것으로 알려졌다.이 센서들은 지진학적 시계열을 생성할 것이다.그러나 이 데이터를 분석하려면 센서 수와 시간 길이로 인해 DFT를 계산하기 위한 빠른 알고리즘이 필요하다.이 과제는 소련의 시설을 방문하지 않고도 위반 사항이 감지될 수 있도록 제안된 핵실험 금지법의 비준을 위해 중요했다.^[4][5]그 모임의 또 다른 참가자, IBM의 Richard Garwin은 이 방법의 가능성을 인식하고 Tukey를 Cooley와 접촉시켰지만 Cooley가 원래 목적을 알지 못하는지 확실히 했다.대신에 Cooley는 헬륨-3의 3-D 결정에서 스핀 방향의 주기적인 결정을 위해 이것이 필요하다고 들었다.쿨리와 투키는 이후 공동 논문을 발표했고, 최대 300kHz의 속도로 샘플링이 가능한 아날로그-디지털 변환기가 동시 개발되면서 광범위한 채택이 빠르게 뒤따랐다.

가우스가 같은 알고리즘(증상증후군을 분석하지 않은 채)을 기술했다는 사실은 쿨리와 투키의 1965년 논문 이후 몇 년이 지나서야 실현되었다.^[2]그들의 논문은 I. J. Good의 알고리즘이 처음에는 Cooley-와 동등한 것으로 생각되었지만,^[3] 현재는 PFA(Prime-factor FFT 알고리즘)라고 불리는 것에 대한 I. Jood의 연구만을 영감으로 인용했다.Tukey 알고리즘은 PFA가 상당히 다른 알고리즘(Cooley–에서 어떤 복합적인 크기에 대한 지원과는 달리 비교적 주요한 요인이 있는 크기에 대해서만 작업하고 중국 잔여 정리에 의존함)이라는 것을 빠르게 깨달았다.투키(tukey).^[6]

Radix-2 DIT 케이스

라딕스-2 소멸시효(DIT) FFT는 쿨리의 가장 단순하고 가장 일반적인 형태다.Tukey 알고리즘(고도로 최적화된 Cooley-)Tukey 구현은 일반적으로 아래에 설명된 다른 형태의 알고리즘을 사용한다.Radix-2 DIT는 N 크기의 DFT를 각 재귀 단계와 함께 N/2 크기의 인터리브된 두 개의 DFT("radix-2"라는 이름)로 나눈다.

이산 푸리에 변환(DFT)은 다음 공식으로 정의된다.

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

여기서 $k{\displaystyle }$ ${\displaystyle k}$은(는) 0에서 $N{\displaystyle }$- ${\displaystyle 1}$까지$(\displaystyle N-1}$ 사이의 정수입니다$.$

Radix-2 DIT first computes the DFTs of the even-indexed inputs ${\displaystyle (x_{2m}=x_{0},x_{2},\ldots ,x_{N-2})}$ and of the odd-indexed inputs ${\displaystyle (x_{2m+1}=x_{1},x_{3},\ldots ,x_{N-1})}$, and then combines those전체 시퀀스의 DFT를 생성하는 두 개의 결과.이 아이디어는 전체 런타임을 O(N 로그 N)로 줄이기 위해 반복적으로 수행될 수 있다.이 단순화된 형태는 N이 2의 검정력이라고 가정한다. N 샘플 포인트의 수는 대개 응용 프로그램에 의해 자유롭게 선택될 수 있기 때문에(예: 샘플율이나 윈도우, 제로 패딩 등), 이것은 중요한 제한이 아니다.

radix-2 DIT 알고리즘은 함수 ${\displaystyle x_{}}$ $n{\displaystyle {}_{}}$ ${\$의 DFT를 짝수$$ $지수{\displaystyle }$ n${\displaystyle }$= ${\displaystyle \mathrm{2m}}$ ${\$$displaystyle$ n$={2m}$에 대한 합과$$ 홀수 지수 $n{\displaystyle }$= ${\displaystyle \mathrm{2m}}$+ $1$에 대한$$합으로 재구성한다$.$

${\displaystyle {\begin{matrix}X_{k}&=&\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N}}(2m)k}+\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N}}(2m+1)k}\end{matrix}}}$

아래 방정식에서와 같이 두 번째 합 중에서$$ 공통 $승수{\displaystyle {}^{}}$ e${\displaystyle {}^{}}$- 2 ${\displaystyle {\pi }^{}}$ i ${\$를 인수할 수 있다.It is then clear that the two sums are the DFT of the even-indexed part ${\displaystyle x_{2m}}$ and the DFT of odd-indexed part ${\displaystyle x_{2m+1}}$ of the function ${\displaystyle x_{n}}$. Denote the DFT of the Even-indexed inputs ${\displaystyle x_{2m}}$ by ${\$$displaystyle E_{k}}$ 및$$ ${\$에 의한 Oddisplay-indexed inputs x ${\displaystyle {\mathrm{2m}}_{}}$+ 1 ${\$의 DFT를 확인하면$$ 다음과 같은 결과를 얻을 수 있다.

${\displaystyle {\begin{matrix}X_{k}=\underbrace {\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}mk}} _{\mathrm {DFT\;of\;even-indexed\;part\;of\;} x_{n}}{}+e^{-{\frac {2\pi i}{N}}k}\underbrace {\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}mk}} _{\mathrm {DFT\;of\;odd-indexed\;part\;of\;} x_{n}}=E_{k}+e^{-{\frac {2\pi i}{N}}k}O_{k}\qquad {\text{{}}}{}k=0,\dots,{\frac{N}{2}}-1의 경우.\end{{11}}}$

Note that the equalities hold for ${\displaystyle k=0,\dots ,N-1}$ but the crux is that ${\displaystyle E_{k}}$ and ${\displaystyle O_{k}}$ are calculated in this way for ${\displaystyle k=0,\dots ,{\frac {N}{2}}-1}$ only.복합지수의 주기성 덕분에 ${\displaystyle {Xk}_{}}$+ ${\displaystyle {\frac{\mathrm{N}}{}}_{}}$ 2 ${\$ ${\$ 및$$ ${\displaystyle {Ok}_{}}$ ${\$

${\displaystyle{\begin{정렬}X_{k+{\frac{N}{2}}}&=\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac{2\pi 나는}{N/2}}m(k+{\frac{N}{2}})}+e^{-{\frac{2\pi 나는}{N}}(k+{\frac{N}{2}})}\sum \limits};=\sum \limits}mk미만}e^{mi-2\pi}+e^{-{\frac _{m=0}^{N/2-1}x_{2m}e^{-{\frac{2\pi 나는}{N/2}m(k+{\frac{N}{2}})}\\& _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac{2\pi 나는}{N/2}.{2\pi 나는}{N}}k}e^{-\pi i}\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}mk}e^{-2\pi mi}\\&=\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}mk}-e^{-{\frac {2\pi i}{N}}k}\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}mk}\\&=E_{k}-e^{-{\frac {2\pi i}{N}}k}O_{k}\end{aligned}}}$

$X{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$를 다음과$$ 같이 다시 쓸 수 있다.

${\displaystyle {\begin{matrix}X_{k}&=&E_{k}+e^{-{\frac {2\pi i}{N}}}{k}}}}}}}}O_{k}\\X_{k+{\frac {N}{2}}:}&=&E_{k}-e^{-{\frac {2\pi i}{{N}}}{k}}}}}:{k}}}}O_{k}\end{matrix}}$

이 결과는 길이 N의 DFT를 크기 N/2의 두 DFT로 재귀적으로 표현한 것으로, radix-2 DIT fast Fourier 변환의 핵심이다.알고리즘은 중간 계산 결과를 재사용하여 여러 DFT 출력을 계산함으로써 속도를 얻는다.Note that final outputs are obtained by a +/− combination of ${\displaystyle E_{k}}$ and ${\displaystyle O_{k}\exp(-2\pi ik/N)}$, which is simply a size-2 DFT (sometimes called a butterfly in this context); when this is generalized to larger radices below, the size-2 DFT is replaced by a larger DFT(그 자체는 FFT로 평가할 수 있다).

이 과정은 알고리즘을 분할하고 정복하는 일반적인 기법의 한 예다. 그러나 많은 전통적인 구현에서는 명시적인 재귀는 피하며, 그 대신 폭 우선 방식으로 계산 트리를 가로지른다.

위와 같은 크기 N DFT를 두 가지 크기 N/2 DFT로 재표현한 것을 다니엘슨-란크조스 보조정리라고 부르기도 하는데, 그 정체성이 1942년^[7] (룬지의 1903년 저작에^[2] 의해 영향을 받아) 그 두 저자에 의해 지적되었기 때문이다.그들은 그들의 보조마사를 "뒤로" 재귀적 방식으로 적용하여 변환 스펙트럼이 수렴될 때까지 DFT 크기를 반복적으로 두 배로 늘렸다(즉, 명령 N log N] 점증적 복잡성을 달성한 것은 분명하지 않지만).대니얼슨-란크조스는 기계 또는 전자 컴퓨터의 광범위한 가용성이 앞서며 수동 계산(아마도 기계 추가와 같은 기계적 보조장치가 있을 것이다)이 필요했다. 이들은 실제 입력으로 작동하는 64 DFT에 대해 140분의 계산 시간을 3-5개의 유의한 숫자로 보고했다.쿨리와 투키의 1965년 논문은 IBM 7094(아마도 36비트 단일한 정밀도 ~ 8자리)에서 크기 2048 복합 DFT의 가동 시간을 0.02분으로 보고했다.^[3]운행 횟수로 시간을 재조정하면 대략 80만분의 속도상승 인자에 해당한다.(손 계산 시간을 볼 때 64 사이즈의 140분은 부동소수 운전당 평균 16초에 해당하며, 이 중 약 20%가 곱셈이다.)

가성음

유사 부호드로 다음과 같은 절차를 작성할 수 있다.^[8]

X0,...,N−1← ditfft2(x, N, s):DFT(x0, xs, x2s,..., x(N-1)s의):N=1그때 X0←x0 사소한size-1 DFT 기본 다른 X0,...N/2−1에,N/2−1 ← ditfft2(x, N/2, 2초씩)DFT(x0, x2s, x4s,..., 음(N-2)s의)XN/2, k...,N−1 ← ditfft2(x+s, N/2, 2초씩)DFT(xs, xs+2s, xs+4s,..., x(N-1)s의)=0전체 DFT에:DFTs 2반쪽 p← Xk을 결합할까.q exp(-2πi/N k) Xk+N/2 Xk ← p + qk+N/2 X if p - q end for end if.

여기ditfft2 (x,N,1)은 X=DFT(x)를 radix-2 DIT FFT로 계산한다. 여기서 N은 2의 정수 전력이고 s=1은 입력 xarray의 보폭이다.x+s는 x로_s 시작하는 배열을 가리킨다.

(결과는 X의 순서가 올바르고 더 이상 비트 역순열이 필요하지 않다. 흔히 언급되는 별도의 비트 역순 단계의 필요성은 아래에 설명된 바와 같이 특정 인플레이스 알고리즘에 대해서만 발생한다.)

고성능 FFT 구현은 이러한 단순한 유사 코드와 비교하여 그러한 알고리즘의 구현에 많은 수정을 가한다.예를 들어, N=1보다 더 큰 베이스 케이스를 사용하여 재귀 오버헤드를 상각할 수 있으며, 트위들 ${\displaystyle \mathrm{요인}}$exp${\displaystyle [}$ - ${\displaystyle 2}$ ${\displaystyle i}$ i${\displaystyle k}$ / ${\displaystyle N}$]$${\$displaystyle \exp[-2\pi ik/N]}$을(를) 사전 계산할$$ 수 있으며, 캐시 이유로 더 큰 라디스를 사용하는 경우가 많다. 이러한 라디스와 기타 최적화는 함께 크기 또는 m의 순서로 성능을 개선할 수 있다.(^[8]많은 교과서 구현에서 깊이 우선의 재귀는 깊이 우선의 재귀가 더 나은 기억의 지역성을 가지고 있다고 주장되어 왔음에도 불구하고, 깊이 우선의 재귀는 비반복적 폭 우선 접근법에 전적으로 찬성하여 제거된다.)^[8][9]이러한 생각들 중 몇 가지는 아래에 자세히 설명되어 있다.

아이디어

더 일반적으로, 쿨리-Tukey 알고리즘은 다음과 같이 복합 크기 N₁₂ = NN의 DFT를 반복적으로 다시 추출한다.^[10]

1. N₂ 크기의 N DFT를 수행하십시오₁.
2. 통합의 복잡한 뿌리(흔히 트위들 인자라고 불림)에 곱한다.
3. N₁ 크기의 N DFT를 수행하십시오₂.

일반적으로 N이나₁ N은₂ 라딕스(재귀 단계마다 다를 수 있음)라고 하는 작은 요인(필수적으로 원시적인 것은 아님)이다.N이₁ 라딕스일 경우 시간(DIT) 알고리즘으로 불리는 반면, N이₂ 라딕스일 경우 주파수(DIF, Sande–)로 소멸한다.Tukey 알고리즘).위에 제시된 버전은 radix-2 DIT 알고리즘이었다.마지막 표현에서 홀수 변환을 곱한 위상은 twiddle factor이며, 짝수 변환과 홀수 변환의 +/- 조합(버터플라이)은 크기-2 dFT이다. (라딕스의 작은 DFT는 때때로 나비라고 하는데, 이를 위한 데이터 흐름도의 형태 때문에 소위 "나비"라고 한다.e radix-2 케이스)

변형

쿨리-에 다른 많은 변주곡들이 있다.Tukey 알고리즘.혼합 레이더 구현은 재귀의 주요 기본 사례에 대해 O(N²) 알고리즘을 채택한 2개 외에 다양한 (일반적으로 작은) 요인을 포함한 복합 크기를 처리한다(레이더 또는 블루스타인의 알고리즘과 같은 주요 기본 사례에 N 로그 N 알고리즘을 채택하는 것도 가능하다).분리 radix, 사실은 주문 비록 최근 변화는 더 낮은 수치를 달성하는 sizes,[10]power-of-two 무엇을 위한 것인지 긴 가장 낮은 알려진 산술 연산 횟수를 달성하기 위해서는 radix 2의 첫번째 변환, 빙빙 돌리다 요인이 필요한 악덕 업주 RADIX의 복수 2와 4 합쳐진다.[11][12](현대의 컴퓨터에서는 성능 캐시는 그 이상으로 결정된다.d CPU 파이프라인 고려사항(정확한 운용 횟수보다); 잘 최적화된 FFT 구현은 종종 상당한 크기의 더 큰 레이더 및/또는 하드 코딩된 베이스 케이스 변환을 채택한다).^[13]

쿨리를 바라보는 또 다른 방법Tukey 알고리즘은 출력 매트릭스가 전치되는 N의₂ 2차원 DFT(더하기 트위들)에 의해 N의 크기 N의 1차원 DFT를 다시 표현하는₁ 알고리즘이다.radix-2 알고리즘의 경우 이러한 모든 전이의 순 결과는 입력(DIF) 또는 출력(DIT) 지수의 비트 반전에 해당한다.만약 대신 작은 radix를 사용하는 한 대략 √N고 노골적/출력 매트릭스 transpositions의 radix을 고용합니다, 처음에는 기억 locality,[14][15]예를 개선할 것을 제안했다. 캐시 최적화 또는 노심 외부 운전을 위해 나중에 되기 위해 보여 준 4기분율 알고리즘(또는six-step, transpositions의 수에 따라)라고 불린다. 최적 값l 캐쉬-프로세서 알고리즘.^[16]

쿨리 장군Tukey factorization은 지수 k와_a n을 $각각{\displaystyle }$ k${\displaystyle }$= N ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}{}_{}{1\mathrm{}}_{}}$ + ${\displaystyle {k\mathrm{}}_{}}$ 2 ${\$2}$k_{1}+k_{2$}} $및$ n = ${\displaystyle {N\mathrm{}}_{}}$ 1 ${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$+ ${\displaystyle {n\mathrm{}}_{}}$ ${\displaystyle {}_{}}${\$displaystyle n=N_{1}n_${2$}+n_{$1}}}{$1}}}}}}}}$로 다시 씁니다$.$ 여기서 지수 k와_a n은 각각.N-1_a(1 또는 2의 a)즉, 입력(n)과 출력(k)을 각각 컬럼 주계열과 행 주계열 순서로 N에₂ 의한 N으로₁ 재색인한다. 이러한 색인 간의 차이는 위에서 언급한 바와 같이 전치형이다.이 재색인을 nk에 대한 DFT 공식으로 대체하면 ${\displaystyle {N1\mathrm{}}_{}}$ ${\displaystyle {}_{}{}_{}}$ 2 ${\displaystyle {N\mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ k ${\displaystyle {}_{}{}_{}}$ ${\$}:{1}}{1$}}}}}$ 교차$$ 항이 소멸되고 나머지 항은 단합성이 된다.

${\displaystyle X_{N_{2}k_{1}+k_{2}}}}=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}x_{N_{1}n_{2}+n_{1}{1}{1]2}}e^{-{-{\frac {2\pi i}{N_{1}N_{2}}:\cdot (N_{1}n_{2}+n_{1}}\cdot (N_{2}k_{1}+k_{2}}}}}}}}}}}}}}}}}}}}}}}}}}}{{{{{{2}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

${\displaystyle =\sum _{n_{1}=0}^{N_{1}-1}\left[e^{-{\frac {2\pi i}{N_{1}N_{2}}}n_{1}k_{2}}\right]\left(\sum _{n_{2}=0}^{N_{2}-1}x_{N_{1}n_{2}+n_{12}}e^{-{-{\frac {2\pi i}{N_{2}}n_{2}k_{2}}\\오른쪽)e^{-{-{\frac {2\pi i}{N_{1}n_{1}k_{1}}}}}{1}}}}}}}$

${\displaystyle =\sum _{n_{1}=0}^{N_{1}-1}\left(\sum _{n_{2}=0}^{N_{2}-1}x_{N_{1}n_{2}+n_{1$$}}e^{-{-{\frac {2\pi$ i$}{N_{2}}:n_{2}k_{2}}:\오른쪽)e^{-{{N_{1}N_{2$}}:$n_${1}{1}{1}}$n_{1}}{{1}k_{1$}+$k_{$2$\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}.$

여기서 각 내부 합은 크기 N의₂ DFT이고, 각 외부 합은₁ 크기 N의 DFT이며, [...] 괄호로 묶인 용어는 트위들 인자다.

Cooley와 Tukey^[3] 둘 다에서 보듯이 임의의 radix r (혼합된 radience뿐만 아니라)을 사용할 수 있으며, 가우스(radix-3와 radix-6 step의 예를 들었다)에서도 볼 수 있다.^[2]Cooley and Tukey originally assumed that the radix butterfly required O(r²) work and hence reckoned the complexity for a radix r to be O(r² N/r log_rN) = O(N log₂(N) r/log₂r); from calculation of values of r/log₂r for integer values of r from 2 to 12 the optimal radix is found to be 3 (the closest integer to e, which minimizes r/log₂r).^[3][17]그러나 이 분석은 잘못되었다. radix-butterfly도 DFT이며, O(r log r) 작업에서 FFT 알고리즘을 통해 수행될 수 있기 때문에 radix r은 실제로 복잡성 O(r log(r) N/r logN에서_r 상쇄되며, 최적의 r은 보다 복잡한 고려사항에 의해 결정된다.실제로 현대의 프로세서에 대한 프로세서 레지스터의 수가 많은 등, 예를 들어, 상당히 큰 r(32 또는 64)은 매우 중요하며,^[13] 심지어 무한의 r=sndN도 O(N log N) 복잡성을 달성하고 위에서 언급한 바와 같이 큰 N에 대한 이론적·실용적 장점을 가지고 있다.^[14][15][16]

데이터 순서 변경, 비트 반전 및 내부 알고리즘

비록 추상적인 쿨리-위의 DFT의 Tukey factorization은 알고리즘의 모든 구현에 어떤 형태로든 적용되며, FFT의 각 단계에서 데이터를 주문하고 액세스하는 기법에 훨씬 더 큰 다양성이 존재한다.특별한 관심사는 O(1) 보조 저장장치만을 사용하여 출력 데이터로 입력을 덮어쓰는 내부 알고리즘을 고안하는 문제다.

가장 잘 알려진 리오더링 기법은 내부 radix-2 알고리즘에 대한 명시적인 비트 반전을 포함한다.비트역전은 숫자 bbbb₄₃₂₁₀(예: N=32 입력의 경우 5자리)로 2진수로 작성된 색인 n의 데이터가 반전된 숫자 bbbb로₀₁₂₃₄ 색인으로 전송되는 순열이다.${\displaystyle {위}_{}}$에 제시된 것과 같은 radix-2 DIT 알고리즘의 마지막 단계를 고려해 보십시오. 입력을 통해 출력이 제자리에 기록되는 경우: $E{\displaystyle {}_{}}$ k ${\$ $및$ O ${\displaystyle k_{}}${\$displaystyle O_{k}$를 크기-2 DFT와 결합하면$$ 이 두 값이 출력에 의해 덮어쓰게 된다.그러나 두 출력 값은 출력 어레이의 첫 번째와 두 번째 절반으로 가장 유의한 비트 b₄(N=32의 경우)에 해당하는 값이어야 하는 반면, 두 입력 ${\displaystyle E_{}}$ k ${\$ 및 ${\displaystyle O_{}}$ $k{\displaystyle {}_{}}$ ${\$는 가장 유의하지 않은 비트 b에₀ 해당하는 짝수와 홀수 요소에 인터리브된다$$.따라서 정확한 위치에 출력을 얻기 위해서는 b가₀ b를₄ 대신해야 하고 지표가 bbbb가₀₄₃₂₁ 된다.그리고 다음 재귀 단계에서는, 그 4개의 최하위 비트가 bbbb가₁₄₃₂ 될 것이다. 만약 당신이 radix-2 DIT 알고리즘의 모든 재귀 단계를 포함한다면, 모든 비트는 역전되어야 하고, 따라서 사람들은 비트 반전으로 입력을 사전 처리해야만 한다(또는 출력을 후처리해야 한다).(각 size-N/2 보조양식이 연속적인 데이터에서 작동하려면 DIT 입력은 비트 역순으로 사전 처리된다.)이에 따라 모든 단계를 역순으로 수행하면 후처리(또는 전처리)에서 비트역전이 있는 radix-2 DIF 알고리즘을 얻게 된다.

이 알고리즘에서 사용되는 로그(log)는 베이스 2 로그다.

다음은 비트 역순열을 사용하여 구현된 반복적 radix-2 FFT 알고리즘에 대한 유사 코드다.^[18]

알고리즘 반복-ft 입력:n이 2. 출력의 검정력인 n개의 복잡한 값 배열:Array A the DFT of a.       bit-reverse-copy(a, A)     n ← a.length      for s = 1 to log(n) do m ← 2s ωm ← exp(−2πi/m)          for k = 0 to n-1 by m do ω ← 1             for j = 0 to m/2 – 1 do t ← ω A[k + j + m/2]                 u ← A[k + j]                 A[k + j] ← u + t A[k + j + m/2] ← u – t ω ← ω ωm return A

비트 역복사 절차는 다음과 같이 실시할 수 있다.

알고리즘 비트 역방향 복사본(A,A) 입력:n이 2. 출력의 검정력인 n개의 복잡한 값 배열:k = 0 ~ n – 1 do A[rev(k)] := a [k]의 크기 n n a.length a.length

또는 일부 애플리케이션(예: 콘볼루션)은 비트역전 데이터에서 동등하게 잘 작동하므로 비트역전 없이 모두 전진 변환, 처리, 역변환 등을 수행하여 자연적인 순서로 최종 결과를 도출할 수 있다.

그러나 많은 FFT 사용자들은 자연 순서 출력을 선호하며,^[13] 비트 반전이 O(N) 시간에 이루어질 수 있고 많은 연구의 대상이 되었지만, 별도의 명시적 비트 역전 단계는 계산 시간에 영향을 미칠 수 있다.^[19][20][21]또한 라딕스-2 사례에서는 순열화가 약간 역전되는 반면, 혼합라믹스 사례에서는 일반적으로 임의(혼합 베이스) 자릿수 역전이며, 순열 알고리즘은 구현이 더욱 복잡해진다.더욱이 많은 하드웨어 아키텍처에서는 연속적(또는 최소한 국부적) 데이터 요소에서 작동하도록 FFT 알고리즘의 중간 단계를 재주문하는 것이 바람직하다.이를 위해 쿨리-을 위한 여러 가지 대체 이행 방안이 마련되었다.별도의 비트 반전이 필요하지 않거나 중간 단계에서 추가 순열이 필요하지 않은 Tukey 알고리즘.

문제는 출력 배열이 입력 배열과 구별되거나 동등하게 동일한 크기의 보조 배열을 사용할 수 있는 경우에 크게 단순화된다.Stockham auto-sort^[22][23] 알고리즘은 FFT의 모든 스테이지를 아웃플레이스(out-out-place)^[23][24]로 수행하며, 일반적으로 두 어레이 사이를 왔다갔다 하며, 각 스테이지와 함께 지수의 "자리"를 한 자리씩 전치하며, 특히 SIMD 아키텍처에서 인기가 있었다.Pease 알고리즘에는 훨씬 더 큰 잠재적 SIMD 장점(더 연속적인 액세스)이 제안되어 ^[25]각 스테이지와 함께 아웃오더도 재주문하고 있지만, 이 방법은 별도의 비트/자리 반전 및 O(N log N) 저장장치가 필요하다.쿨리를 직접 적용할 수도 있다.명시적(심층 우선) 재귀와 작은 방사선을 이용한 투키 인자화 정의는 별도의 순열 단계(위의 유사 코드) 없이 자연적인 순서가 아닌 출력을 생성하며 계층적 메모리가 있는 시스템에서 캐시-불가역적 국소성 편익을 갖는다고 주장할 수 있다.^[9][13][26]

보조 저장장치와 별도의 숫자 역전 패스가 없는 인플레이스 알고리즘에 대한 일반적인 전략은 중간 단계에서 작은 매트릭스 전이(개별 자릿수 쌍을 교환하는 것)를 포함하며, 이는 데이터에 대한 패스 수를 줄이기 위해 라딕스 나비들과 결합할 수 있다.^{[13][27][28][29][30]}

참조

외부 링크

• "Fast Fourier transform - FFT". Cooley-Tukey technique. Article. 10. A simple, pedagogical radix-2 algorithm in C++
• "KISSFFT". GitHub. 11 February 2022. A simple mixed-radix Cooley–Tukey implementation in C
• 깃허브에 있는 Dsplib
• "Radix-2 Decimation in Time FFT Algorithm". Archived from the original on October 31, 2017. "Алгоритм БПФ по основанию два с прореживанием по времени" (in Russian).
• "Radix-2 Decimation in Frequency FFT Algorithm". Archived from the original on November 14, 2017. "Алгоритм БПФ по основанию два с прореживанием по частоте" (in Russian).