[질문]2^n 이 아닌 FFT는 어떻게..
Kim Hyoung Joon
데이터의 수가 2^n 개 이어야 한다고 배웠습니다.
그런데 지금 제가 하려고 하는 일에서는
그 조건을 만족할 수가 없습니다.
인터넷을 뒤지다보니 어떤 사이트에서는
그 조건을 만족하도록 0으로 나머지를 채우라고 하던데(zero padding)
그래도 가능할까요?
matlab의 help를 보니 거기서는 뭔가 다른 알고리즘을 쓰고 있는거 같던데
혹시 다른 방법을 아시면 셜명을 해주십시오.
말로 설명한다기보다는 소스코드를 보여준다면 더 확실하겠죠....
혹시 FFT와 IFFT C source를 가지고 계시면
보내주세요... 부탁드립니다...
Min-Joon Kim
> 제가 배운바로는 FFT를 하기 위한 조건으로
> 데이터의 수가 2^n 개 이어야 한다고 배웠습니다.
> 그런데 지금 제가 하려고 하는 일에서는
> 그 조건을 만족할 수가 없습니다.
>
꼭 2^n일 필요는 없습니다. 제가 아는 어떤 FFT 프로그램에서는
2^n 3^m 5^l 의 데이터 수도 지원합니다.
단지 2^n의 경우가 가장 쉽죠.
그리고, 거의 대부분의 프로그램이 2^n을 취급할 수 있도록
되어 있구요.
> 인터넷을 뒤지다보니 어떤 사이트에서는
> 그 조건을 만족하도록 0으로 나머지를 채우라고 하던데(zero padding)
> 그래도 가능할까요?
>
보통 그렇게들 합니다.
> matlab의 help를 보니 거기서는 뭔가 다른 알고리즘을 쓰고 있는거 같던데
> 혹시 다른 방법을 아시면 셜명을 해주십시오.
> 말로 설명한다기보다는 소스코드를 보여준다면 더 확실하겠죠....
>
> 혹시 FFT와 IFFT C source를 가지고 계시면
> 보내주세요... 부탁드립니다...
서점에 가면 "Numerical Recipes in C"라는 책이 있습니다.
그 책에 보면 간단한 FFT의 C source code가
나와있을겁니다.
김민준.
--
Kim, Min-Joon, Dr.
KALIMER Sodium Experimental Technology Development
Korea Atomic Energy Research Institute
P. O. Box 105
Yusong, Taejon, 305-600
Republic of Korea
Phone: +82-42-868-2069
Fax: +82-42-868-8739
E-mail: ko...@hplmr01.kaeri.re.kr ko...@nanum.kaeri.re.kr
Sangwoo Choi
: Kim Hyoung Joon wrote:
: > 제가 배운바로는 FFT를 하기 위한 조건으로
: > 데이터의 수가 2^n 개 이어야 한다고 배웠습니다.
: > 그런데 지금 제가 하려고 하는 일에서는
: > 그 조건을 만족할 수가 없습니다.
: >
: 꼭 2^n일 필요는 없습니다. 제가 아는 어떤 FFT 프로그램에서는
: 2^n 3^m 5^l 의 데이터 수도 지원합니다.
: 단지 2^n의 경우가 가장 쉽죠.
: 그리고, 거의 대부분의 프로그램이 2^n을 취급할 수 있도록
: 되어 있구요.
: > 인터넷을 뒤지다보니 어떤 사이트에서는
: > 그 조건을 만족하도록 0으로 나머지를 채우라고 하던데(zero padding)
: > 그래도 가능할까요?
: >
: 보통 그렇게들 합니다.
0이 아니고. 앞에 나왔던 수들을 다시 반복해서 채우는 경우도 있는것 같더군요.
그러나 일반적으로 0을 채운다고 책에 나와 있습니다.
그렇게 2^n개의 데이타가 아니고. 임의 개수로.. 할려면..
DFT는 어떨까요?
FFT는 처리 속도가 빠르지만..일반적으로 데이타를 2^n개로 맞춰야 하죠.
하지만.. DFT의 경우는 임의 데이타 수로도.. 계산이 가능하잖아요.
단점은 시간이 많이 걸리지만..
하지만 계산해야할 데이타가 많지 않다던가
리얼 타임성을 요구하지 않는다면.. 요즘 computer들이 빠르니..
DFT도 편할것 같네요.
--
Material Strength And NonDestructive Evaluation Lab.
Mechanical Design Engineering
Pusan National University.
Phone : 051)510-3078 (Lab.) 051)555-0812 (Home)
PCS : 016-560-3807 (560...@sms.pcs016.co.kr)
http://www.pcs016.co.kr/htdocs/sms/index.html
E-Mail: woo...@hyowon.cc.pusan.ac.kr
woo...@metric.pusan.ac.kr
gun...@msnnde.me.pusan.ac.kr
Homepage http://hyowon.cc.pusan.ac.kr:8080/~woochoi
Sang-yong Suh
ftp.kigam.re.kr:pub/csm/cwpcodes/cwp.su.all.31.6.tar.gz를 가져 가셔서
풀으신 다음 src/cwp/lib/pfafft.c를 보시기 바랍니다.
소인수로 분해하여 FFT를 수행한답니다. 물론 소인수분해가 않되면
몇개의 0을 더해 소인수분해가 가능하도록 자료 길이를 조정하지요.
첨부한 것은 pfafft.c의 머릿글입니다.
--
sysuh
/* Copyright (c) Colorado School of Mines, 1996.*/
/* All rights reserved. */
/*********************** self documentation **********************/
/*****************************************************************************
PFAFFT - Functions to perform Prime Factor (PFA) FFT's, in place
npfa return valid n for complex-to-complex PFA
npfar return valid n for real-to-complex/complex-to-real PFA
npfao return optimal n for complex-to-complex PFA
npfaro return optimal n for real-to-complex/complex-to-real PFA
pfacc 1D PFA complex to complex
pfacr 1D PFA complex to real
pfarc 1D PFA real to complex
pfamcc multiple PFA complex to real
pfa2cc 2D PFA complex to complex
pfa2cr 2D PFA complex to real
pfa2rc 2D PFA real to complex