Soc FFT project 보고서

목차

1. FFT 란?
2. 설계할 Radix-2 DIF 32Point FFT

본문내용

고속 푸리에 변환(高速 푸리에 變換, Fast Fourier transform, FFT)은 이산 푸리에 변환(Discrete Fourier transform, DFT)과 그 역변환을 빠르게 수행하는 효율적인 알고리즘이다. FFT는 디지털 신호 처리에서 편미분 방정식의 근을 구하는 알고리즘에 이르기까지 많은 분야에서 사용한다.

x0,...,xn − 1이 복소수라고 가정할 때, DFT는 다음과 같이 정의한다.

이 식을 정의에 따라 계산하면 O(n2)의 연산이 필요하지만, FFT를 이용하면 O(n log n)의 연산만으로 가능하다. n이 합성수일 경우 그 소인수분해를 이용하여 연산 횟수를 줄일 수는 있지만, FFT를 사용하면 n이 소수일 경우에도 O(n log n)번의 연산 횟수를 보장한다.

쿨리-튜키 알고리즘
가장 일반적으로 사용되는 FFT 알고리즘은 쿨리-튜키 알고리즘(Cooley-Tukey algorithm)이다. 이 알고리즘은 분할 정복 알고리즘을 사용하며, 재귀적으로 n 크기의 DFT를 n = n1 n2가 성립하는 n1, n2 크기의 두 DFT로 나눈 뒤 그 결과를 O(n) 시간에 합치는 것이다.

참고 자료

없음