몇 가지 연구를 거친 후 일부 입력에서 DFT (이산 푸리에 변환)를 계산하는 작은 앱을 만들었습니다. 잘 작동하지만 꽤 느립니다.FFT가 DFT와 다른 점과 C++에서 FFT를 구현하는 방법은 무엇입니까?
FFT (Fast Fourier Transformations)를 사용하면 더 빨리 계산할 수 있지만 그 차이점은 무엇입니까? 그리고 더 중요하게, 어떻게 C++로 구현할 것인가?
수동으로 알고리즘을 구현 할 필요가없는 경우, 당신은 공식적합니다 (FAQ에서) ++ C에서 작동 심지어는 C에서 개발 된 것 알았는데 Fastest Fourier Transform in the West
을 살펴 수
질문 2.9. CFT에서 FFTW로 전화 할 수 있습니까?
가장 확실합니다. FFTW는 을 컴파일해야하며 C++ 컴파일러에서 링크해야합니다. 또한 C++ 템플릿 클래스는 FFTW의 복소수 형식과 비트 호환되는 입니다 (자세한 내용은 FFTW 설명서 참조).
흠 ... 언급 한 라이브러리는 비상업적 인 용도로 사용료가 필요합니다. –
아, 죄송합니다. 상업적 목적으로 사용했는지 알 수 없습니다. 이 경우 http://kissfft.sourceforge.net/을 시도 할 수 있습니다. 이것은 BSD 라이센스를 사용합니다. – XSL
몇 가지 설명 된 알고리즘을 통해이 멋진 설명을 발견했습니다. 구현에 대한
,
FFT는 n^2 인 DFT와 비교하여 n * log (n)의 compexity를가집니다.
많은 문학이 있습니다. 그 넓은 주제를 여기에서 충분히 설명 할 수 없기 때문에 먼저 확인하는 것이 좋습니다. http://en.wikipedia.org/wiki/Fast_Fourier_transform (외부 링크 확인)
라이브러리가 필요한 경우 예를 들어 라이브러리를 사용하는 것이 좋습니다. http://www.fftw.org/ 이 라이브러리는 FFT의 효율적 구현을 가지고 있으며, 또한 propariaretery 소프트웨어에 사용 (예 : MATLAB)
스티븐 스미스의 책 The Scientist and Engineer's Guide to Digital Signal Processing되고, 특히 Chapter 8 on the DFT 및 Chapter 12 on the FFT, 두 개의 변환을 설명 훨씬 더 나은 일을하는 내가 할 수 .
그건 그렇고, 전체 책은 무료로 제공됩니다 (위 링크). 이것은 신호 처리에 대한 아주 좋은 소개입니다.
C++ 코드 요청과 관련하여 서쪽에서 이미 가장 빠른 푸리에 변환 (superexsl에서 인용) 또는 TI 또는 Analog Devices의 DSP 라이브러리 만 사용했습니다.
올바르게 구현 된 DFT의 결과는 올바르게 구현 된 FFT의 결과와 본질적으로 동일하며 (반올림 오류 만 다름) 다른 사람들이 여기에서 지적했듯이, 주요 차이점은 성과입니다. DFT에는 O (n^2) 연산이 있고 FFT에는 O (nlogn) 연산이 있습니다.
내가 가장 많이 읽었던 출판물 (내가 아직 언급 한 책)은 E Oran Brigham의 The Fast Fourier Transform and its Applications입니다. 처음 몇 장에서는 푸리에 변환의 연속 및 이산 형태에 대한 전반적인 개요를 제공합니다. 그런 다음 radix-2 (n은 2의 거듭 제곱) 및 혼합 기수 (radix-2)에 대해 Cooley-Tukey Algorithm을 기반으로 한 DFT의 빠른 버전을 개발하기 위해이 코드를 사용합니다 (후자는 전보다 다소 얕은 논문 임).
입력 X에 대해 선형 시간 연산을 수행하고 결과를 반으로 반복적으로 분할하고 두 반쪽에서 유사한 선형 시간 연산을 수행하는 기수 2 알고리즘의 기본 접근법. 혼합 기수 경우는 비슷하지만, X를 매번 같은 부분으로 나눌 필요가 있기 때문에 n에 큰 소수 요소가 없으면 도움이됩니다.
FFT는 DFT를 빠르게 계산하는 알고리즘을 나타 내기위한 방법 일뿐입니다. 즉, FFT 알고리즘의 결과는 정의에 의해 DFT를 계산 한 결과와 동일해야합니다 (또는 매우 가깝습니다). –
FFT는 2의 거듭 제곱 인 샘플에서만 계산할 수 있습니다. DFT에는 이러한 제한이 없습니다. 나는 누구의 대답에서 그것을 보지 못했지만, 당신이 알아야 할 것이고 나는 그것이 분리 된 대답을 보증한다고 생각하지 않았다. –