고속 푸리에 변환
고속 푸리에 변환은 이산 푸리에 변환(DFT)을 직접 계산보다 적은 연산으로 수행하는 알고리즘 계열이다 수치·신호 처리 알고리즘 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로...
| 분류 | 알고리즘 · 수치·신호 처리 알고리즘 |
|---|---|
| 핵심 문제 | 이산 푸리에 변환(DFT)을 직접 계산보다 적은 연산으로 수행하는 알고리즘 계열이다 |
| 방법 | Cooley–Tukey 분할 방식은 입력을 짝수·홀수 인덱스로 나누고 작은 변환 결과를 회전 인자와 결합한다 |
| 계산 비용 | 보통 O(N log N), 직접 DFT는 O(N²) |
| 적용 조건 | 부동소수점 오차, 변환 길이와 복소수 정규화·역변환 규약을 정의해야 한다 |
| 관련 활용 | 신호 분석·컨볼루션·다항식 곱셈에 사용한다 |
| 관련 이론 | 자료구조, 계산 복잡도 |
| 참고 자료 | CP-Algorithms |
고속 푸리에 변환은 이산 푸리에 변환(DFT)을 직접 계산보다 적은 연산으로 수행하는 알고리즘 계열이다 수치·신호 처리 알고리즘 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별된다.[1]
계산 절차는 Cooley–Tukey 분할 방식은 입력을 짝수·홀수 인덱스로 나누고 작은 변환 결과를 회전 인자와 결합한다. 다양한 길이·기수·실수 입력에 대한 구현이 존재한다. 각 단계의 상태가 무엇을 의미하는지 정의하고 초기값과 경계 입력을 검사하면 결과의 정확성을 증명하거나 테스트할 수 있다.
복잡도는 보통 O(N log N), 직접 DFT는 O(N²) 적용 전제는 부동소수점 오차, 변환 길이와 복소수 정규화·역변환 규약을 정의해야 한다 실제 연산량·메모리 사용은 구현의 자료구조와 정수·실수 표현, 전처리 및 입력 크기에 따라 달라진다.
응용과 관련 기법을 보면 신호 분석·컨볼루션·다항식 곱셈에 사용한다. 유한체에서 정확한 정수 컨볼루션을 얻는 별도 방법으로 수론적 변환이 있다. 같은 문제라도 최악 시간 보장, 메모리 요구 사항과 정밀도·확률적인 실패 가능성에 따라 적합한 알고리즘이 달라진다.[2]