http://kin.naver.com/browse/db_detail.php?dir_id=1&docid=308694
수학자인 Fourier가 세운 가설에서 출발하는 이론입니다.
즉, 모든 상황에서 time domain의 값 n개는
frequency domain의 함수 n개의 합으로 나타낼 수 있을 것이라는
가설에서 출발합니다.
(배운지가 오래되어서 표현이 모호해도 이해하시길)
이것을 data domain에서 일정한 갯수의 데이터에 대하여
적용하는 것이 fast fourier transform입니다.
FFT 변환은 여러 분야에 사용되지만,
가장 널리 알려진 것은 MPEG 압축입니다.
MPEG에서는 FFT의 한 형태인 cosine을 기반으로 한
DCT(Discreate Cosine Transform) 함수를 사용하는데,
역시 앞에 나온 얘기가 반복됩니다.
MPEG은(MPEG1 기준입니다) 8x8 블럭으로 블럭화해서
블럭 단위로 인코딩을 하는데,
이 8x8 블럭 즉, 64개의 데이터를 DCT 변환을 해서
cosine 함수 64개의 합으로 변환합니다.
그러면, 뒤로 갈 수록 계수가 0에 가까워지거나 0이 되어버리는데,
이 값들을 제거함으로써 압축을 하는 것입니다.
(MPEG 에서는 이 외에도 수많은 압축 개념이 사용되는데,
FFT와 무관하므로 통과하겠습니다)
64개의 데이터를 8개의 cosine으로 표현할 수 있으면
무려 1/8의 데이터로 압축을 할 수 있는 것입니다.
다시 앞으로 돌아가서, FFT는 이러한 유한한 갯수의 데이터를
주파수 도메인의 함수들의 합으로 나타내는 변환입니다.
구체적인 알고리즘은 관련 서적을 뒤지면 나올 것입니다.
이 정도의 개념을 갖고 서적을 읽어보시면
쉽게 작성이 가능할 것입니다.
만들어진 알고리즘 자체는 무척 단순합니다.
도움이 되셨기를...
Posted by 눈빛마음