고속 푸리에 변환

고속 푸리에 변환(FFT)은 시퀀스의 이산 푸리에 변환(DFT) 또는 그 역(IDFT)을 계산하는 알고리즘입니다.푸리에 분석은 원래 영역(종종 시간 또는 공간)의 신호를 주파수 영역의 표현으로 변환하고 그 반대도 마찬가지입니다.DFT는 일련의 값을 다른 ^[1]주파수의 성분으로 분해하여 얻습니다.이 연산은 많은 분야에서 유용하지만 정의에서 직접 계산하는 것이 너무 느려서 실용적이지 못할 때가 많습니다.FFT는 DFT 행렬을 스파스(^[2]대부분 0) 인자의 곱으로 인수분해함으로써 이러한 변환을 신속하게 계산한다.$그{\displaystyle }$ 결과 DFT의 정의를 적용하기만 하면 발생하는 O$($$N$2)에서 $(N log$$N$$)$로 DFT의 계산 복잡성을 줄일 수 있다.특히 N이 수천 또는 수백만 개에 이르는 긴 데이터 세트의 경우 속도 차이가 클 수 있습니다.반올림 오류가 있는 경우 많은 FFT 알고리즘이 DFT 정의를 직간접적으로 평가하는 것보다 훨씬 정확합니다.단순한 복소수 산술에서 군 이론 및 수 이론까지 광범위한 공개 이론을 기반으로 하는 많은 다른 FFT 알고리즘이 있습니다.

고속 푸리에 변환은 공학, 음악, 과학 및 수학 분야에서 널리 사용됩니다.기본 아이디어는 1965년에 대중화되었지만, 일부 알고리즘은 1805년에 ^[1]이미 개발되었습니다.1994년, Gilbert Stren은 FFT를 ^[3][4]"우리 생애에서 가장 중요한 수치 알고리즘"이라고 표현했으며, 이는 IEEE 잡지 Computing in Science ^[5]& Engineering에 의해 20세기의 상위 10개의 알고리즘에 포함되었습니다.

가장 잘 알려진 FFT 알고리즘은 N의 인수 분해에 따라 다르지만, 모든 N에 대해, 심지어 소수 N에 대해서도 O(N log N) 복잡도를 갖는 FFT가 있습니다.많은 FFT 알고리즘은 e${\displaystyle {}^{}}$- 2 ${\displaystyle {\mu }^{}}$i /$$({$displaystyle$ e$^{-2\pi$ i$/N})$이 N번째 기본 통합 루트이므로 수이론 변환과 같은 유한 필드에 걸쳐 유사한 변환에 적용할 수 있다는 $사실$에만 의존합니다.역DFT는 DFT와 동일하지만, 지수의 반대 기호와 1/N 계수를 사용하여 FFT 알고리즘을 쉽게 적용할 수 있습니다.

역사

DFT를 위한 빠른 알고리즘의 개발은 1805년 칼 프리드리히 가우스가 표본 ^[6][7]관찰을 통해 팔라스와 주노의 궤도를 보간하기 위해 그것이 필요했던 미발표 작업으로 거슬러 올라갈 수 있다.그의 방법은 James Cooly와 John Tukey가 1965년에 발표한 방법과 매우 유사했으며, 이들은 일반적으로 현대의 일반 FFT 알고리즘의 발명에 기여한 것으로 알려져 있다.가우스의 연구는 1822년 조제프 푸리에의 결과보다 앞서 있었지만, 그는 계산 시간을 분석하지 않았고 결국 그의 목표를 달성하기 위해 다른 방법을 사용했다.

1805년과 1965년 사이에 FFT의 일부 버전이 다른 저자들에 의해 출판되었다.1932년 프랭크 예이츠는 상호작용 알고리즘이라고 불리는 그의 버전을 발표했는데, 이것은 하다마드와 월시 ^[8]변환의 효율적인 계산을 제공했다.예이츠의 알고리즘은 여전히 실험의 통계 설계와 분석 분야에서 사용되고 있다.1942년, G. C. 다니엘슨과 코넬리우스 랭조스는 푸리에 변환 계산에서 엄청난 ^[9][10]병목 현상을 보이는 분야인 X선 결정학을 위한 DFT를 계산하는 버전을 발표했다.과거 많은 방법들이 "대칭성"을 ${\displaystyle {}^{}}$하여 O$displaystyle O\left(N^{2$}\right$)$ 연산의$$ $상수{\displaystyle }$ 계수를 줄이는 데 초점을 맞췄지만, Danielson과 Lanczos는 "주기성"을 사용할 수 있다는 것을 깨닫고 "두 배 이상의 노동력"으로 "두 배[N]만 "두 배"를 적용할 수 있다는 것을 깨달았다.Gauss와 마찬가지로 O${\displaystyle (N}$ log${\displaystyle n}$N $)(\displaystyle$ O$(N\log$ N$))$^[11] 스케일링으로$$ $이어진다고{\displaystyle }$ 분석하지 않았습니다.

James Cooly와 John Tukey는 이러한 초기 알고리즘을^[7] 독립적으로 재발견하여 1965년에 N이 반드시 2의 거듭제곱이 아닌 복합일 때 적용할 수 있는 보다 일반적인 FFT를 발표하였으며${\displaystyle ,}$ O ( ${\displaystyle N}$ ${\displaystyle \log n}$N$$$$) ^[12]( \ $display style O$( N \ $log$N ) $스케일링$을 분석하였습니다.투키는 케네디 대통령의 과학 자문 위원회 회의에서 이 아이디어를 생각해 냈는데, 이 회의에서 외부로부터 이 나라를 포위하기 위한 센서를 설치해 소련의 핵실험을 탐지하는 것이 논의 주제였다.이러한 센서의 출력을 분석하려면 FFT 알고리즘이 필요합니다.Tukey와의 논의에서 Richard Garwin은 이 알고리즘이 국가 안보 문제뿐만 ^[13]아니라 헬륨-3의 3D 결정에서 스핀 방향의 주기성을 결정하는 즉시 관심을 갖는 문제를 포함한 광범위한 문제에 대해서도 일반적인 적용 가능성을 인식했습니다.Garwin은 구현을 위해 Cooly(^[14]둘 다 IBM의 Watson 연구소에서 근무)에게 Tukey의 아이디어를 제공했습니다.Cooly와 Tukey는 6개월이라는 ^[15]비교적 짧은 시간 안에 논문을 발표했다.Tukey는 IBM에서 일하지 않았기 때문에 아이디어의 특허성이 의심되었고 알고리즘은 공공 영역에 들어갔으며, 이후 10년의 컴퓨팅 혁명을 통해 FFT는 디지털 신호 처리에서 없어서는 안 될 알고리즘 중 하나가 되었습니다.

정의.

${\displaystyle {x\mathrm{}}_{}}$ 0$(\$ …, $x{\displaystyle {}_{}}$ ${\displaystyle N_{}}$- $(\$을 복소수로 합니다.DFT는 다음 공식으로 정의됩니다.

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-i2\pi kn/N}\qquad k=0,\ldots,N-1,}$

${\displaystyle {여기}^{}}$서 e ${\displaystyle {\mathrm{i}}^{}}$ 2 ${\displaystyle {/}^{}}$ /$$ { $style$ e$^{i2\pi /N}$은 1의 원시 N번째 루트입니다.

이 정의를 직접 평가하려면 O${\displaystyle }$( ${\displaystyle {N\mathrm{}}^{}}$ 2)$${ $displaystyle O\left$(N^{$2}\right)}$ 연산이$$ $필요$합니다.N개의 출력_k X가 있으며 각 출력에는 N개의 항의 합계가 필요합니다.FFT는 O${\displaystyle (N}$ log${\displaystyle n}$N$$) {$displaystyle$ O$(N\log$ N$)}$ 연산에서$$ $동일$한 결과를 계산하는 방법입니다.알려진 모든 FFT 알고리즘에는${\displaystyle }\delta {\displaystyle \mathrm{}}$ ( ${\displaystyle N}$ ${\displaystyle \log }$ ${\displaystyle †N}$) {$displaystyle \Theta (N\log$ N$)}$ 연산이 필요하지만, 복잡성을 낮출 ^[16]수 없다는 증거는 없습니다.

FFT의 절감 효과를 설명하기 위해 N=4096 데이터 포인트에 대한 복소 곱셈 및 덧셈 카운트를 고려합니다.DFT의 합계를 직접 평가하려면 N개의 복소수 곱셈과 N(N - 1)개의 복소수 덧셈이 포함되며², $그{\displaystyle }$ 중 1의 곱셈과 같은 사소한 연산을 제거하여 약 3000만 개의 연산을 남김으로써 O$(N)의$연산을$$ 절약할 수 있다.반대로 기수 2 쿨리는-Tukey 알고리즘은 N의 거듭제곱에 대해 (N/2)log₂(N)의 복소수 곱셈(1과 유사한 곱셈의 단순화는 무시) 및 Nlog₂(N)의 복소수 덧셈만으로 동일한 결과를 계산할 수 있습니다.이것은 직접 평가의 약 30,000회입니다.실제로, 현대 컴퓨터에 대한 실제적인 공연은 요인 산술 연산자의 속도와 그 분석은 복잡한 주제(예를 들어, 참조하십시오 Frigo&존슨, 2005년)[17]한 것은 다름 아니지만 O(N2){O\left(N^{2}\right)\displaystyle}에서 O(N로그 ⁡ N)에 필요한 전반적인 개선{\displays 지배된다.tyle O($N\log$ N$)}$이 남습니다.

알고리즘

쿨리-투키 알고리즘

지금까지 가장 일반적으로 사용되는 FFT는 쿨리입니다.Tukey 알고리즘이는 콤포지트 $사이즈{\displaystyle }$ N ${\displaystyle =}$ ${\displaystyle {}_{}{}_{}}$$$$({$ N$=N_{$1}$N_{2})$의 DFT를 $O스타일$${\displaystyle (\backslash }$$displaystyle$ N_${1$}})과 $함께{\displaystyle }$ N1(\$displaystyle N_{$1}}) $및{\displaystyle {}_{}}$ $(\$ N_2$\}\})$의 다수의 작은 DFT로 재귀적으로 분해하는 분할 알고리즘입니다$.$ 전통적으로 트위들 계수(Gentleman and Sande, 1966년^[18] 이후).

이 방법(그리고 FFT의 일반적인 아이디어)은 1965년 ^[12]Coolley와 Tukey의 출판물에 의해 대중화되었지만, 나중에^[1] 그 두 저자가 1805년^[19] 경에 Carl Friedrich Gauss에게 알려진 알고리즘을 독립적으로 재발명했다는 것이 밝혀졌다(그리고 이후 제한된 형태로 여러 번 재발명되었다).

Cooly의 가장 잘 알려진 용도는 다음과 같습니다.Tukey 알고리즘은 변환을 각 단계에서 N/2 크기의 두 조각으로 나누는 것으로, 따라서 두 가지 크기의 거듭제곱으로 제한되지만 일반적으로 모든 인수분해를 사용할 수 있습니다(가우스와^[1] Cooly/Tukey 양쪽에 알려져 있음).이것들은 각각 기수-2 및 혼합 기수 케이스라고 불립니다(또한 분할 기수 FFT와 같은 다른 변형도 고유의 이름을 가지고 있습니다).기본 아이디어는 재귀적이지만 대부분의 기존 구현에서는 명시적 재귀가 발생하지 않도록 알고리즘을 재정렬합니다.그리고 쿨리가...Tukey 알고리즘은 DFT를 보다 작은 DFT로 분할합니다.다음과 같이 DFT의 다른 알고리즘과 임의로 조합할 수 있습니다.

기타 FFT 알고리즘

에는 FFT알고리즘 Cooley–보다 다른 있다.터키.

N)N1N2coprime N1과 N2를 들어, 누군가는 prime-factor(Good– 사용할 수 있다.토마스)알고리즘(PFA), 중국인의 나머지 정리에 따라, 이와 비슷하게 Cooley–에 DFT 인수 분해를 하다.터키지만 물결 무늬적 요인 없이.그 Rader–Brenner 알고리즘(1976년)[20]은 Cooley–.Tukey-like 인수 분해지만 순전히 상상의 돌리기 요소들과, 증가된 증보와 줄어든 수치 안정성의 대가를 치르면 이후에 Cooley–의split-radix 변형으로 대체되었습니다 multiplications을 줄이는 방법이다.터키(그러나 같은 곱셈 횟수를 달성한다면 적은 수를 가질 증보와 없이 희생시키는 정확도).는 재귀적으로 작은 작전 DFTs보다 다른으로 DFT 인수 분해를 하다 알고리즘.(그 Rader–Brenner[20]과 QFT 알고리즘 2의 제곱수 크기에 대하지만, 그들이 일반적인 복합 NBruun의 알고리즘 임의의 심지어 복합 크기에 적용된다에 적응할 것이 가능하다 제안했다.)은 Bruun과 QFT 알고리즘을 포함한다.Bruun의 알고리즘은 다항 zN − 1의 재귀적 분해로 FFT해석하기에, 폼의real-coefficient 다항식 여기로 zM − 1과 z2M+azM+1기반을 두고 있다.

또 다른 다항 관점는 모양체근 절개술의 polynomials—these에 zN − 1factorizes은 Winograd FFTalgorithm,[21][22]으로 이용된다 자주, 그리고 따라서 몇( 있는 경우)multiplications를 필요로 하면, 그래서 Winograd minimal-multiplication FFTs를 얻고 종종 작은을 위한 효율적인 알고리즘을 찾는데 사용될 수 있1,0, 또는 −1의 계수다. 요인들.실제로, Winograd은 DFT 유일한 O(N)비이성적인 multiplications로 증명된 achievable에 multiplications의 수에 2의 제곱수의 크기에 하한을 이끌고 계산할 수 있;불행히도 이 많은 더 많은 추가 사항과 절충은 더 이상 현대 프로세서에 대해 유리한 하드웨어 multipliers의 비용을 보여 주었다.특히 Winograd 또한 아시아 신문 재단 PFA의 레이더에 의해 FFTs 크기의 용도뿐만 아니라 알고리즘을 만든다.

Rader의 알고리즘은 곱셈군 모듈로 소수 N의 발생기의 존재를 이용하여 소수 크기 N의 DFT를 (복합) 크기 N - 1의 주기적 회전으로 표현하며, 이는 (Winograd는 다른 회전 방법을 사용하지만) 일반 FFT 쌍으로 계산할 수 있다.또 다른 프라임 사이즈의 FFT는 L. I. Bluestein에 의한 것으로, 때때로 chirp-z 알고리즘이라고 불리기도 합니다.이것은 DFT를 컨볼루션으로서 재표현하기도 하지만, 이번에는 같은 사이즈의 (2의 거듭제곱에 제로 패드가 적용되어 radix-2 Coolley에 의해 평가될 수 있습니다)예를 들어, Tukey FFT)의 ID를 통해

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

육각 고속 푸리에 변환(HFFT)은 ASA(Array Set Addressing)라고 하는 육각 그리드에 대한 새로운 어드레싱 체계를 사용하여 육각 샘플링 데이터에 대한 효율적인 FFT를 계산하는 것을 목표로 합니다.

실제 또는 대칭 데이터에 특화된 FFT 알고리즘

많은 애플리케이션에서 DFT의 입력 데이터는 순수하게 실재하며, 이 경우 출력은 대칭을 충족합니다.

${\displaystyle X_{N-k}=X_{k}^{*}$

효율적인 FFT 알고리즘이 이러한 상황에 맞게 설계되었습니다(예:Sorensen, 1987).^[23][24]하나의 접근방식은 일반적인 알고리즘(예: Cooly-)을 취하는 것으로 구성된다.Tukey)를 사용하여 계산의 중복 부분을 제거함으로써 시간과 메모리를 약 2배 절약할 수 있습니다.혹은 짝수 길이의 실입력 DFT를 (실수 및 허수 부분이 원래의 실데이터의 짝수/홀수 요소인) 길이의 절반의 복소 DFT로 표현한 후 O(N) 후처리 연산을 할 수 있다.

한때 실제 입력 DFT는 이산 하틀리 변환(DHT)에 의해 보다 효율적으로 계산될 수 있다고 생각되었지만, 그 후 동일한 수의 ^[23]입력에 대응하는 DHT 알고리즘(FHT)보다 적은 연산을 필요로 하는 특수한 실제 입력 DFT 알고리즘(FFT)이 일반적으로 발견될 수 있다는 주장이 제기되었다.브루운의 알고리즘(위)은 실제 입력을 활용하기 위해 처음에 제안된 또 다른 방법이지만, 아직 널리 보급되지는 않았다.

짝수/홀수 대칭을 갖는 실제 데이터의 경우 FFT 전문화가 더 있습니다. 이 경우 시간과 메모리에서 약 2개의 다른 계수를 얻을 수 있으며 DFT는 이산 코사인/사인 변환(DCT/DST)이 됩니다.이러한 경우 FFT 알고리즘을 직접 수정하는 대신, DCT/DST는 O(N) 사전 및 후 처리와 결합된 실제 데이터의 FFT를 통해 계산할 수도 있습니다.

계산상의 문제

복잡성 및 작업 수 제한

오랜 이론적 관심의 근본적인 문제는 고속 푸리에 변환의 복잡성과 정확한 연산 카운트에 대한 하한을 증명하는 것이며, 많은 미해결 문제가 남아 있다.복잡도가 낮은 알고리즘은 알려져 있지 않지만, 두 가지 크기의 단순한 검정력의 경우에도 DFT가 진정으로 δ(N log N) 이상의 연산을 필요로 하는지 여부는 엄격하게 증명되지 않는다.특히, 현대의 컴퓨터에서의 실제 성능은 캐시나 CPU 파이프라인 최적화와 같은 많은 다른 요인에 의해 결정되지만, 산술 연산의 개수는 보통 이러한 질문의 초점이 됩니다.

Shmuel Winograd(1978)^[21]의 연구에 이어 FFT에 필요한 실제 곱셈 수에 대해 엄격한 δ(N) 하한이 알려져 있다.겨우 4N− 2로그 22⁡(N)− 2로그 2⁡(N)− 4{4N-2\log_{2\displaystyle}(N)-2\log _ᆮ(N)-4}비이성적인 진짜 multiplications=}는 DFTpower-of-two 길이의 N2m{\displaystyle N=2^{m}를 계산하기 위해 필요하다. 더구나 이 사건을 달성하는 것을 노골적인 알고리즘(Heideman &am 것으로 알려지고 있다고 보여질 수 있다.p/&Burrus, 1986;^[25] Duhamel, 1990^[26]).그러나 이러한 알고리즘은 적어도 하드웨어 멀티플라이어가 있는 최신 컴퓨터에서는 실용화되기 위해서는 너무 많은 추가가 필요합니다(Duhamel, 1990;^[26] Frigo & Johnson, 2005).^[17]

알고리즘에 대한 일부 제한적인 가정 하에서 하한이 입증되었지만, 필요한 추가 수에 대해서는 엄격한 하한이 알려져 있지 않다.1973년 Morgenstern은^[27] 곱셈 상수가 경계 크기를 갖는 알고리즘의 가산 카운트에 대한 δ(N log N) 하한을 증명했다(이것은 대부분의 FFT 알고리즘에 해당하지만 모든 FFT 알고리즘에 해당되지는 않는다).Pan(1986)^[28]은 FFT 알고리즘의 "비동기성" 측정값에 대한 경계를 가정하여 δ(N log N) 하한을 증명했지만, 이 가정의 일반성은 불명확하다.2N의 거듭제곱의 경우, Papadimitriou(1979)^[29]는 Cooly에 의해 달성된 복소수 ${\displaystyle {\mathrm{추가}}_{}}$의 N ${\displaystyle {로그\mathrm{}}_{}}$ 2${\displaystyle {}_{}\mu }$N(\$displaystyle N\log _{2$}N$$$)$이 다음과 같이 주장했다.Tukey 알고리즘은 알고리즘 그래프상의 특정 가정 하에서 최적입니다(그의 가정은 무엇보다도 통합의 근원에는 어떠한 부가적 동일성도 이용되지 않음을 의미합니다).(이 인수는 복소수 곱셈의 일부로 추가가 필요하기 때문에 엄격한 경계가 아니지만 $최소{\displaystyle \mathrm{}}$ ${\displaystyle {\mathrm{2개}}_{}}$의 N ${\displaystyle {로그2\mathrm{}}_{}}$ ${\displaystyle n{}_{}}$N $(\displaystyle 2N\log$ _${2}N)$의 실제 추가가 필요하다는 것을 의미합니다).지금까지 공개된 FFT 알고리즘 중 2의 거듭제곱에 대해 N ${\displaystyle {로그\mathrm{}}_{}}$ 2 ${\displaystyle {}_{}}$ {\$displaystyle$ N$\log$ _${2}N}$ 미만의 복소수 추가(또는 이에 상당하는 값)를 달성한 것은 없습니다.

세 번째 문제는 때때로 "산술 복잡도"라고 불리는 실제 곱셈과 덧셈의 총 수를 최소화하는 것입니다(이 문맥에서는 고려되고 있는 점근 복잡도가 아니라 정확한 카운트입니다).다시 말씀드리지만, 엄격한 하한선은 증명되지 않았습니다.그러나 1968년 이후 N의 거듭제곱에 대한 가장 낮은 공개 카운트는 분할 기수 FFT 알고리즘에 의해 오랫동안 달성되었습니다. 이 알고리즘에는 4 ${\displaystyle N}$ ${\displaystyle {로그\mathrm{}}_{}}$ 2${\displaystyle }$µ (${\displaystyle N)}$ - ${\displaystyle 6}$N +$$ { $displaystyle 4N\log$ _${2}$ ($N)-6N+8}$의 실제 곱셈과 N > 1에 대한 $추가$가 필요합니다.이 값은 최근 ${\displaystyle {\mathrm{349N}}_{}}$ ${\displaystyle {log\mathrm{}}_{}}$ 2 ${\displaystyle {}_{}}$ $(\displaystyle \sim {34}{9}N\log$ _${2}N}($Johnson and Frigo,^[16] 2007; Lundy and Van Buskirk^[30], 2007)으로${\displaystyle }$감소했습니다.약간 더 큰 계수( 하지만 아직도 더 나은 N의 값 분할 radix보다 ≥ 256)입증할 수 있게. N≤ 512에 최적화 되어에 대해 알고리즘(unit-modulus 복합적 요인들과split-radix-like flowgraphs)에 추가적인 제한 하에 만족시킬 수 있음에 감소로 공개되었다 나머지를 이론 문제 폭력으로(Haynal & 풀 수 있는;Haynal, 2.011를 참조해 주세요.^[31]

FFT 알고리즘의 복잡성을 낮추거나 증명하려는 대부분의 시도는 가장 단순하기 때문에 일반적인 복합 데이터 사례에 초점을 맞췄다.그러나, 복소 데이터 FFT는 실제 데이터 FFT, 이산 코사인 변환, 이산 하틀리 변환 등과 같은 관련 문제에 대한 알고리즘과 매우 밀접하게 관련되어 있기 때문에, 이들 중 하나를 개선하면 다른 것을 즉시 개선할 수 있다(Duhamel & Vetterli, 1990).^[32]

근사치

위에서 설명한 모든 FFT 알고리즘은 DFT를 정확하게 계산합니다(즉, 부동 소수점 오류 무시).그러나 DFT를 대략적으로 계산하는 몇 가지 "FFT" 알고리즘이 제안되었으며, 오차는 증가된 계산을 희생하여 임의로 작게 만들 수 있습니다.이러한 알고리즘은 근사 오차를 증가된 속도 또는 기타 특성과 교환합니다.예를 들어 Edelman 등(1999)^[33]에 의한 대략적인 FFT 알고리즘은 고속 멀티폴 방법의 도움으로 병렬 컴퓨팅에 대한 통신 요건을 낮춘다.Guo 및 Burrus(1996)^[34]에 의한 웨이브릿 기반의 근사 FFT는 정확한 FFT로 가능한 것보다 더 효율적으로 희박한 입력/출력(시간/주파수 현지화)을 고려한다.DFT 출력의 서브셋의 대략적인 계산을 위한 또 다른 알고리즘은 Shentov 등(1995년)^[35]에 기인한다.Edelman 알고리즘은 데이터의 압축성(희박성)이 아니라 푸리에 행렬 자체의 압축성(랭크 결핍성)에 기초하기 때문에 희소 데이터와 비희박 데이터에 대해서도 동일하게 작동합니다.만약 자료가 sparse—that만 한다면, KN푸리에 계수에서nonzero—then은 반대로, 복합 O(K일지(N)log(N/K))그리고 이것은 하나의 평범한 FFTN/K 을에 비해 실용적인 speedups로 이어질 것으로 입증되었다;32large-N 예(N=222)은 확률론적 대략적인 알고리즘(는 estimat의 사용을 줄일 수 있다.동부 표준시소수점 이하 ^[36]몇 자리까지 K 계수를 최대화합니다.)

정확성.

FFT 알고리즘은 유한 정밀도 부동 소수점 산술 사용 시 오류가 발생하지만, 이러한 오류는 일반적으로 매우 작습니다. 대부분의 FFT 알고리즘(예: Cooly-)Tukey는 알고리즘의 쌍별 합산 구조의 결과로 우수한 수치 특성을 가집니다.Cooly의 상대 오차에 대한 상한-네이브 DFT ^[18]공식의 O('N^3/2')에 비해 Tukey 알고리즘은 O('log N)입니다.여기서 '는 머신의 부동 소수점 상대 정밀도입니다.실제로 루트 평균 제곱(rms) 오차는 Cooly의 경우 O(ε "log N")에 불과하여 이러한 상한보다 훨씬 우수합니다.순진한 DFT의 Tukey 및 O('N') (Schatzman, 1996).^[37]그러나 이러한 결과는 FFT에 사용되는 트위들 계수(즉, 삼각 함수 값)의 정확도에 매우 민감하며, 부정확한 삼각 반복 공식을 사용하는 경우처럼 부주의한 FFT 구현이 정확도가 훨씬 떨어지는 것은 드문 일이 아닙니다.쿨리 이외의 일부 FFT-Rader-Brenner 알고리즘 등의 Tukey는 본질적으로 안정성이 떨어집니다.

고정 소수점 산술에서 FFT 알고리즘에 의해 누적된 유한 정밀도 오차는 더 심하며, RMS 오차는 쿨리의 경우 O(δN)로 증가합니다.Tukey 알고리즘(Welch, 1969).^[38]이 정확도를 달성하려면 정밀도 손실을 최소화하기 위해 스케일링에 세심한 주의를 기울여야 하며, 고정점 FFT 알고리즘은 Cooly와 같은 분해의 각 중간 단계에서 스케일링을 수행해야 합니다.터키.

FFT 구현의 정확성을 검증하기 위해, O(N log N) 시간 내에 랜덤 입력에 대한 변환의 선형성, 임펄스-응답 및 시간 이동 특성을 확인하는 간단한 절차를 통해 엄격한 보증을 얻을 수 있습니다(Ergün, 1995).^[39]

다차원 FFT

다차원 DFT 문서에 정의된 대로 다차원 DFT

${\displaystyle X_{\mathbf {k} =\sum _{\mathbf {n} =0}^{\mathbf {N} -1} e^{-2\pi i\mathbf {k} \cdot (\mathbf {n} /\mathbf {N} ) x_{\mathbf {n} } } }$

지수 n의d-dimensional 벡터로)d중첩 summations(nj에)0쭉 펼쳐져 Nj=0\ldots N_{j}-1}각 j1{\displaystyle n_{j}−)의 분열 n/N는 n/N으로 정의됨=에 의해(n1,…, nd){\displaystyle \mathbf{n}=\left(n_{1},\ldots,n_{d}\right)}(n. 배열 xn으로 변환합니다. ${\displaystyle 1_{}}$/ ${\displaystyle {N\mathrm{}}_{}}$1 , ${\displaystyle ...}$ , n${\displaystyle {}_{}{d}_{}}$ / ${\displaystyle N_{}}$d $){$ $displaystyle \mathbf {n}$/\$mathbf {N} =\left(n_{1}/N_{1},\ldots,n_{d}/N_{d}\right}$가 요소별로 수행됩니다.동등하게, 1차원의 DFT의 d세트 시퀀스의 구성이며, 한 번에 1차원의 DFT를 따라(임의의 순서로) 실행된다.

이 구성 관점은 행-열 알고리즘으로 알려진 가장 단순하고 일반적인 다차원 DFT 알고리즘을 즉시 제공합니다(2차원 케이스 이후).즉, 단순히 d개의 1차원 FFT 시퀀스를 수행할 수 있습니다(위의 알고리즘 중 하나를 사용). 먼저 n차원을₁ 따라 변환한 다음 n차원을₂ 따라 변환하는 등(또는 실제로 모든 순서가 작동합니다).이 방법은 일반적인 O(N log N) 복잡도를 가지고 있음을 쉽게 알 수 있습니다. $여기$서 N ${\displaystyle =}$ ${\displaystyle {N\mathrm{}}_{}}$ ${\displaystyle {}_{}{}_{}}$⋅ ${\displaystyle N_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle \cdot }$N d$$ N d \ $displaystyle$ N =$N_{1}\cdot$ \ $cdot$\ cdots \ $cdot$ N_${d}$는 변환된 데이터 포인트의 총 수입니다.특히 크기 N₁ 등의 N/N₁ 변환이 있으므로 FFT 시퀀스의 복잡성은 다음과 같습니다.

${\displaystyle {narged}&{\frac {N}{N_{1}+\cdots +{\frac {N}{N_{d}}O(N_{d}\log N_{d}}\\\\[6]\Leg N_{1}\cdots + {N}O(왼쪽)\end { aligned}}$

2차원, xk n1×n2{\displaystyle n_{1}\times n_{2}로}, 이 알고리즘 먼저(resp. 기둥), 또 다른 n1n2{\displaystyle n_{1}\times n_{2}}matrix,×(resp. 기둥)함께 결과 변환된 행 그룹은 FFT모든 행의 수행에 부합하는 행렬 볼 수 있다. and 이 두 번째 행렬의 각 열(응답 행)에 대해 FFT를 수행하고 결과를 최종 결과 행렬로 그룹화합니다.

2개 이상의 차원에서는 종종 캐시 로컬리티가 차원을 재귀적으로 그룹화하는 것이 유리합니다.예를 들어, 3차원 FFT는 먼저 각 고정₁ n에 대해 각 평면 "슬라이스"의 2차원 FFT를 수행한 다음 n 방향을₁ 따라 1차원 FFT를 수행할 수 있습니다.보다 일반적으로 점근적으로 최적의 캐시 오블리뷰스 알고리즘은 2개의 그룹$n$ 1,${\displaystyle \dots ,}$ ${\displaystyle {}_d}$ /${\displaystyle {}_{}}$2$)($2})과${\displaystyle }$(${\displaystyle {nd\mathrm{}}_{}}$ /${\displaystyle {}_{}}$2 +${\displaystyle {}_{}{1}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle n_{}}$d $)(display$style ($n_{d/2},\ldots$ transformed, $n)$로 재귀적으로 분할됩니다.(Frigo and Johnson, 2005 ^[17]참조)그러나 이는 행-열 알고리즘의 단순한 변형으로 남아 있어 최종적으로 1차원 FFT 알고리즘만 기본 케이스로 필요로 하며 여전히 O(N log N) 복잡성이 존재한다.또 다른 변형은 변환이 연속된 데이터 상에서 동작하도록 변환 사이의 매트릭스 트랜스포지션을 실행하는 것입니다.이는 비연속적인 데이터에 액세스하는 데 시간이 많이 걸리는 코어 외 및 분산 메모리 상황에서 특히 중요합니다.

행-열 알고리즘과는 다른 다른 다차원 FFT 알고리즘이 있지만 모두 O(N log N) 복잡성이 있습니다.아마도 가장 단순한 비행-컬럼 FFT는 벡터-기수 FFT 알고리즘으로, 이는 일반적인 쿨리의 일반화이다.각 단계에서 변환 치수를 r $=$ ( r ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}{2\mathrm{}}_{}}$,${\displaystyle }$… , ${\displaystyle r_{}}$d $){$ $displaystyle \mathbf {r}$ =\$left(r_{1},r_{2},\ldots,r_{d}\right)$로 나누는 Tukey 알고리즘.(캐시의 이점도 있습니다).벡터 기수의 가장 단순한 경우는 모든 반지름이 동일한 경우(예: 벡터 기수-2는 모든 차원을 2로 나눈다)입니다. 그러나 이것은 필요하지 않습니다.$한{\displaystyle \mathbf{}}$ 번에 하나의 단위 기수만 갖는 벡터 기수(예:${\displaystyle r\mathrm{}}$ $=$ ( 1,${\displaystyle }$…,${\displaystyle 1}$, ${\displaystyle r,}$ ${\displaystyle 1}$,$…,$ 1$)$ ${displaystyle \mathbf$ {$r} =\left(1,\ldots,$1,\ldots$,$1,\ldots,$1\right$는 기본적으로 행-열 알고리즘입니다.더 복잡한 다른 방법에는 Nussbaumer(1977)^[40]에 의한 다항식 변환 알고리즘이 포함되어 있으며, 이들은 변환을 컨볼루션 및 다항식 곱의 관점에서 본다.자세한 내용과 참고 자료는 Duhamel and Vetterli(1990)^[32]를 참조하십시오.

기타 일반화

Mohlenkamp는^{2 [41]}O(N²² log(N)의 복잡성을 갖는 것으로 추측되는 알고리즘(그러나 증명되지 않음)과 함께 S구상의² 구형 고조파에 대한^5/2 O(Nlog N)의 일반화를 기술했다.Mohlenkamp는 libftsh ^[42]라이브러리에서도 구현을 제공한다.O(Nlog² N) 복잡도의 구면 고조파 알고리즘은 Rokhlin과 Tygert에 의해 ^[43]기술된다.

고속 폴딩 알고리즘은 일련의 실제 또는 복잡한 스칼라 값이 아닌 일련의 빈 파형에서 작동한다는 점을 제외하면 FFT와 유사합니다.회전(FFT에서는 복소 위상에 의한 곱셈)은 성분 파형의 원형 이동입니다.

다양한 그룹은 또한 포츠 등에서 검토한 바와 같이 비등축 데이터에 대한 "FFT" 알고리즘을 발표했다.(^[44]2001년).이러한 알고리즘은 DFT(등가 데이터에 대해서만 정의됨)를 엄밀하게 계산하는 것이 아니라 오히려 그 근사치(흔히 그 자체가 대략적으로만 계산되는 NDFT)를 계산합니다. Uniform Discrete Fourier Transform))를 계산한다.보다 일반적으로 스펙트럼 추정에는 다양한 방법이 있다.

적용들

FFT는 디지털 기록,^[45] 샘플링, 적층 합성 및 피치 보정 소프트웨어에 사용됩니다.

FFT의 중요성은 주파수 영역에서의 작업이 시간 또는 공간 영역에서의 작업과 동일하게 계산적으로 실현 가능하도록 만들었다는 사실에서 비롯됩니다.FFT의 중요한 응용 프로그램에는 다음이 포함됩니다.^[15][46]

• 고속 대승법 및 다항식 곱셈,
• 토플리츠, 순환 및 기타 구조화된 행렬에 대한 효율적인 행렬-벡터 곱셈,
• 필터링 알고리즘(오버랩 추가 및 오버랩 저장 방식 참조),
• 이산 코사인 또는 사인 변환을 위한 고속 알고리즘(예: JPEG 및 MPEG/MP3 인코딩 및 디코딩에 사용되는 고속 DCT),
• 빠른 체비셰프 근사,
• 차분 방정식을 풀고
• 동위원소 ^[47]분포의 계산.
• 5G, LTE, Wi-Fi, DSL 및 기타 최신 통신 시스템을 위한 OFDM(직교 주파수 분할 다중화)을 사용하여 복잡한 데이터 기호를 변조 및 복조합니다.

연구 분야

빅 FFT

천문학과 같은 분야의 빅데이터가 폭발적으로 증가함에 따라 특정 간섭계 계산에 512K FFT의 필요성이 대두되고 있습니다.WMAP 및 LIGO와 같은 프로젝트에서 수집된 데이터는 수백억 포인트의 FFT를 필요로 합니다.이 크기는 메인 메모리에 맞지 않기 때문에 이른바 코어 외 FFT가 활발한 ^[48]연구 영역입니다.

근사 FFT

MRI와 같은 애플리케이션의 경우 간격이 일정하지 않은 그리드 포인트 및/또는 주파수에 대한 DFT를 계산해야 합니다.다중극 기반 접근법은 런타임 증가 ^[49]계수를 사용하여 대략적인 수량을 계산할 수 있습니다.

그룹 FFT

FFT는 추가적인 일반화를 위해 그룹 표현 이론을 사용하여 설명하고 해석할 수도 있습니다.비사이클릭을 포함한 콤팩트군의 함수는 환원 불가능한 매트릭스 요소의 기초에 관해 팽창을 가진다.이러한 기본 변경을 수행하기 위한 효율적인 알고리즘을 찾는 것은 여전히 활발한 연구 영역이다.효율적인 구면 고조파 확장, 특정 마르코프 과정 분석, 로봇 공학 ^[50]등을 포함한 응용 분야.

양자 FFT

양자 컴퓨터에서 정수 인수분해를 위한 쇼어의 빠른 알고리즘은 이진 벡터의 DFT를 계산하는 서브루틴을 가지고 있습니다.이는 현재 양자 FFT로 알려진 1비트 또는 2비트 양자 게이트의 시퀀스로 구현되며, 이는 사실상 쿨리(Cooly-Tukey FFT는 푸리에 행렬의 특정 인수분해로 실현되었습니다.이러한 아이디어의 확장이 현재 ^[51]검토되고 있다.

언어 레퍼런스

언어	명령어/방법	전제 조건
R	통계:: syslog(x)	없음.
옥타브/MATLAB	FFT(x)	없음.
파이썬	FFT.2011(x)	수치 삐걱거리다
매스매티카	푸리에[x]	없음.
포트란	fftw_one(계획, 입력, 출력)	FFTW
줄리아.	FFT(A [,dims])	FFTW
녹	fft.process(&mut x);	녹슨
해스켈	dft)	fft

참고 항목

FFT-related 알고리즘:

• Goertzel 알고리즘 – 이산 푸리에 변환의 개별 조건을 계산합니다.

FFT구현:

• ALGLIB,real/complex FFT구현과dual/GPL-licensed C++및 C#도서관(또한 다른 언어 지원)–.
• FFTPACK 다른 포트란 FFT도서관(공공 도메인)–.
• 아키텍처 고유:
  • 암 퍼포먼스^[52] 라이브러리
  • 인텔 인테그레이티드 퍼포먼스 프리미티브
  • 인텔(R) 마스 라이브러리
• CPU나 GPU(Pocket 등)에는 더 많은 구현이 ^[53]있습니다.C++용 FFT

기타 링크:

• Odlyzko-Schönhage 알고리즘은 FFT를 유한 디리클레 시리즈에 적용한다.
• Schönhage-Strassen 알고리즘 – 큰 정수에 대한 점근 고속 곱셈 알고리즘
• 나비 다이어그램 – FFT를 설명하는 데 사용되는 다이어그램
• 스펙트럼 음악(음악 작곡에 DFT 분석 적용 포함)
• 스펙트럼 분석기 – 스펙트럼 분석을 수행하는 여러 장치 중 하나(대부분 DFT 경유)
• 시계열
• Fast Walsh-Hadamard 변환
• 일반화 분포 법칙
• 최소 제곱 스펙트럼 분석
• 다차원 변환
• 다차원 이산 컨볼루션
• 고속 푸리에 변환 망원경

레퍼런스

추가 정보

• Brigham, E. Oran (2002). The Fast Fourier Transform. New York: Prentice-Hall.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Chapter 30: Polynomials and the FFT". Introduction to Algorithms (2 ed.). MIT Press / McGraw-Hill. ISBN 0-262-03293-7.
• Elliott, Douglas F.; Rao, K. Ramamohan (1982). Fast transforms: Algorithms, analyses, applications. New York, USA: Academic Press.
• Guo, Haitao; Sitton, Gary A.; Burrus, Charles Sidney (1994). "The Quick Discrete Fourier Transform". Proceedings of ICASSP '94. IEEE International Conference on Acoustics, Speech and Signal Processing. Proceedings on the IEEE Conference on Acoustics, Speech, and Signal Processing (ICASSP). Vol. 3. pp. 445–448. doi:10.1109/ICASSP.1994.389994. ISBN 978-0-7803-1775-8. S2CID 42639206.
• Johnson, Steven G.; Frigo, Matteo (2007). "A modified split-radix FFT with fewer arithmetic operations" (PDF). IEEE Transactions on Signal Processing. 55 (1): 111–119. Bibcode:2007ITSP...55..111J. CiteSeerX 10.1.1.582.5497. doi:10.1109/tsp.2006.882087. S2CID 14772428.
• Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (2007). "Chapter 12. Fast Fourier Transform". Numerical Recipes: The Art of Scientific Computing (3 ed.). New York, USA: Cambridge University Press. ISBN 978-0-521-88068-8.
• Singleton, Richard Collom (June 1969). "A Short Bibliography on the Fast Fourier Transform". Special Issue on Fast Fourier Transform. IEEE Transactions on Audio and Electroacoustics. Vol. AU-17. IEEE Audio and Electroacoustics Group. pp. 166–169. doi:10.1109/TAU.1969.1162029. (NB. 광범위한 참고 문헌 목록을 포함합니다.)
• 엘레나 프레스티니: "응용 고조파 해석의 진화", 스프링거, ISBN 978-0-8176-4125-2(2004), 3.10항 "가우스와 소행성: FFT의 역사"

외부 링크

• 다항식 곱셈을 위한 고속 푸리에 변환 – 고속 푸리에 알고리즘
• Fast Fourier Transforms, Charles Sidney Burrus, Ivan Selesnick, Markus Pueschel, Matteo Frigo 및 Steven G. Johnson(2008)이 편집한 Connexions 온라인 책
• Fast Fourier 변환 — FFT – FFT 프로그래밍(C++) – Cooly –터키 알고리즘
• 온라인 문서, 링크, 책 및 코드
• Sri Welaratna, "FFT 분석기 30년", 소리와 진동(1997년 1월호, 30주년호) – 하드웨어 FFT 디바이스의 역사적 리뷰
• ALGLIB FFT 코드– 듀얼/GPL 라이선스 다국어(VBA, C++, Pascal 등) 수치 분석 및 데이터 처리 라이브러리
• SFFT: Sparse Fast Fourier Transform – MIT의 Sparse(sub-linear time) FFT 알고리즘, sFFT 및 구현
• VB6 FFT – 소스 코드를 사용한 VB6 최적화 라이브러리 구현
• 대화형 FFT 자습서 – 푸리에 변환 및 FFT 방법에 대한 시각적 대화형 소개