FFT관련 논문은 어디다 발표하는게 나을까요?

kkb110의 이미지

FFT(Fast Fourier Transform)를 들여다보다가 우연히 연산량을 대폭 줄일수있는 구조를 창안해냈습니다.!! ㅋㅋ

기존에 FFT는 시간복잡도가 약 nLog[2,n] 정도인데 이번에 만든 FFT는 시간복잡도가 약 1/2nLog[2,n] + n-1 입니다.

n이 충분히 크다면 기존방법의 반정도의 연산량으로 FFT를 수행해낼 수 있죠. 256 point FFT의경우는 기존 FFT에 62.4%정도의 연산량으로 수행이 가능합니다. 대박이죠 ㅋㅋ

그것도 DIF나 DIT 든 상관없이, 그리고 Multi Radix FFT, Split Radix FFT등 거의 대부분의 방식의 FFT에 추가적으로 적용이 가능합니다. ㅋㅋ

그래서 논문을 써서 발표를 할라그러는데 어디다가 내야될지 모르겠네요.; 어디 학회가입한것도 없는데.. 어디다가 내보는게 좋을까요?? 논문쓴다음 IEEE가입하고 IEEE에다 내볼까요?

ed.netdiver의 이미지

부디 지도교수에게 먼저 문의해보시기 바랍니다.

앞서, 수십년묵은 그 기술들을 먼저 만들었다고 알려진 수많은 돌대가리들에게

예의상 묵념 한번 올려주시구요.ㅡ.ㅡ;

우.연.히....

--------------------------------------------------------------------------------
\(´∇`)ノ \(´∇`)ノ \(´∇`)ノ \(´∇`)ノ
def ed():neTdiVeR in range(thEeArTh)

hjfirst의 이미지

제가 잘 모르는 것일 수도 있지만

nLog[2,n]과 1/2nLog[2,n] + n-1는 결국 시간 복잡도가 같은 것 아닌가요 ??

여기서 FFT의 시간복잡도라 말하는 건 O(nLog[2,n]) 일 텐데 결국 1/2nLog[2,n] +n-1도 결국 O(nLog[2,n])인 데 말이죠.

결국 대세에 큰 영향을 미치는 건 아니지 않을까요?

kkb110의 이미지

아... 그부분에있어서 오해가 있을 수 있겠군요.
제가 만든 구조는 기존 FFT 알고리즘에 추가적으로 적용할수있는거라서요. 기존 알고리즘 에다가 제 구조를 거기다 적용하면 연산량이 정확히 반으로 줄어들고 거기다가 +n-1만큼의 연산량이 더 생깁니다.
시간복잡도라는것보다는 다른 말이 더 적합하겠네요.

다시 예를 들면 원본 알고리즘 연산 시간이 상수 k를 써서

k * nLog[2,n] 이라면 거기다가 제 구조를 적용하면
k * (1/2nLog[2,n] + n-1) 만큼의 시간이 걸립니다 ^^

fatman의 이미지

그전에 일단 이전에 나온 FFT 관련 논문들과 특허를 먼저 찾아보시고 생각하시는 알고리듬과 비슷한 주제로 나온 것이 있는지를 확인해 보시는 것이 좋을 듯 싶습니다. FFT가 신호처리 분야에서는 굉장히 중요한 알고리듬으로 알고 있기 때문에 속도를 빠르게 하거나 효율성을 높이는 논문이나 특허가 굉장히 많기 때문에 이전에 나왔을 가능성도 있다고 생각됩니다. 그렇게 찾아보신 후 새로운 것이나 굉장한 개선이 있다고 생각되면 당장 논문을 써서 제출하시면 되고, 제출할 학회는 지금까지 찾아보신 논문들이 어디서 발표되었는지를 확인하면 되겠지요.

...

cdpark의 이미지

kkb110 wrote:

제가 만든 구조는 기존 FFT 알고리즘에 추가적으로 적용할수있는거라서요. 기존 알고리즘 에다가 제 구조를 거기다 적용하면 연산량이 정확히 반으로 줄어들고 거기다가 +n-1만큼의 연산량이 더 생깁니다.

진짜라면 이걸 왜 논문으로 냅니까? 특허로 꽁꽁 묶은 후에 평생 특허료만 먹고 살아도 됩니다. :shock:

segfault의 이미지

수고하셨습니다 :)

이제 mp3나 ogg 인코딩하는 시간이 반으로 줄겠네요..

kkb110의 이미지

아! 특허로 내도 되는거였나요? -_-;;;;;;;;;;;;;;;;
특허쪽 한번 봐야겠네 *-_____-*;;;

사실 내용은 간단한거라 누가 먼저 발견했을거라는생각이 아주 강력하게 들기는 하는데;;;

일반적으로 가장 빠른 FFT알고리즘으로 인정받는 FFTW(fftw.org) 랑 djbfft(cr.yp.to/djbfft.html) 에 그런내용이 없다는것은 확인했습니다 히히힣힣힣 ^------------------------^

Prentice의 이미지

babjo87 wrote:
수고하셨습니다 :)

이제 mp3나 ogg 인코딩하는 시간이 반으로 줄겠네요..


특허로 출원하신다면 그렇기 힘들겠죠..

Creativity always builds on the past.
And you're building the past right now.

Share now. Shape tomorrow.

lifthrasiir의 이미지

hjfirst wrote:
제가 잘 모르는 것일 수도 있지만

nLog[2,n]과 1/2nLog[2,n] + n-1는 결국 시간 복잡도가 같은 것 아닌가요 ??

여기서 FFT의 시간복잡도라 말하는 건 O(nLog[2,n]) 일 텐데 결국 1/2nLog[2,n] +n-1도 결국 O(nLog[2,n])인 데 말이죠.

결국 대세에 큰 영향을 미치는 건 아니지 않을까요?

시간 복잡도가 같아도 계수가 다르다면 충분히 활용 가능합니다. 둘 다 O(n log n)인 건 마찬가지지만 계수가 반이니까요.

- 토끼군

fibonacci의 이미지

제가 전공이 달라서, 그 논문의 가치라던지 그쪽 저널의 순위라던지 그런건 잘 모르지만
http://epubs.siam.org/sam-bin/dbq/toclist/SIAP
이정도면 어떨까요?

No Pain, No Gain.

warpdory의 이미지

cdpark wrote:
kkb110 wrote:

제가 만든 구조는 기존 FFT 알고리즘에 추가적으로 적용할수있는거라서요. 기존 알고리즘 에다가 제 구조를 거기다 적용하면 연산량이 정확히 반으로 줄어들고 거기다가 +n-1만큼의 연산량이 더 생깁니다.

진짜라면 이걸 왜 논문으로 냅니까? 특허로 꽁꽁 묶은 후에 평생 특허료만 먹고 살아도 됩니다. :shock:

논문으로 낸 뒤에 6개월내에 보강해서 특허로 내면 됩니다.
거꾸로도 가능하지요. 특허낸 뒤에 '이런 게 있다. 특허 찾아봐라~~ ' 이런 식의 논문이죠.
IEEE 논문 보면 그런 게 꽤 많습니다.

그리고 FFT 는 ... 퓨리에 하고 별로 친하지 않아서 좋은 점수가 나오지 않아서 ... 수학적으로 뭐라 말씀드릴 내용은 없네요. - 복학하고 받은 유일한 F ...


---------
귓가에 햇살을 받으며 석양까지 행복한 여행을...
웃으며 떠나갔던 것처럼 미소를 띠고 돌아와 마침내 평안하기를...
- 엘프의 인사, 드래곤 라자, 이영도

즐겁게 놀아보자.

eddy_woody의 이미지

좋을 것 같은데요...

그러니까 개발하신 것이 새로운 FFT알고리듬이라기 보다는
무슨 알고리듬이든지 그것의 implementation의 계산 속도를 두 배 정도 향상시키는 (자료?)구조라는 말씀인 것 같은데 맞습니까?

벤치 마킹 결과 같은 것을 올려주시면 환상이겠습니다... :D

> It can take much longer than necessary to get rid of a problem professor...

I'm thinking duct tape and a trunk.

kkb110의 이미지

계속 검색해보고 있는데 tokigun님이 말씀해주신 SIAP정도면 괜찮은데 같습니다. IEEE, MAA, SIAP 이 3개정도가 적당할 것 같네요.

그리고 특허는 정보의 공유를 위해 만들어진 겁니다.
참고링크 : http://blog.naver.com/henuda/100000645708
새로운 발명을 하고 그것을 공유해서 우리모두가 혜택을 받을수있으면 발명자에게 그에 해당하는 보상을 해줘야 하는것 아니겠습니까? 전 보상과 공유는 동시에 양립할수있는 가치라고 생각합니다.

아 그리고 제가 만든것은 Cooley-Turkey 기반의 알고리즘구조를 약간 수정 한것입니다. 기존에 Cooley-Turkey 알고리즘이 있고 그에 기반한 변형인 Radix-4, Radix-8, Radix-16, Split Radix 이있는것처럼 제가 개발한것도 그런 성격입니다. 기존 것보다 복소수 곱셈과 덧셈이 좀 줄어드는거죠. ^^ 연산량이 가장 적다는 Split Radix에다가 중복적용도 가능하구요.

코딩하면 벤치마크도 올리겠습니다 ^^

macsaint의 이미지

혹시나 해서 말씀드리는데요..

wavelet에서 이용되던 lifting scheme이 아닌가 한번
확인해 보심이...

제 생각에도 같은 것이 아니었으면 좋겠습니다.

오늘 하루의 의미를 생각해 보자

urmajest의 이미지

kkb110 wrote:
아... 그부분에있어서 오해가 있을 수 있겠군요.
제가 만든 구조는 기존 FFT 알고리즘에 추가적으로 적용할수있는거라서요. 기존 알고리즘 에다가 제 구조를 거기다 적용하면 연산량이 정확히 반으로 줄어들고 거기다가 +n-1만큼의 연산량이 더 생깁니다.
시간복잡도라는것보다는 다른 말이 더 적합하겠네요.

다시 예를 들면 원본 알고리즘 연산 시간이 상수 k를 써서

k * nLog[2,n] 이라면 거기다가 제 구조를 적용하면
k * (1/2nLog[2,n] + n-1) 만큼의 시간이 걸립니다 ^^

딴지는 아니구요..

FFT의 time-complexity에 대해선 잘 모르지만,

O(nlogn) = O(1/2 nlogn + n-1) 이죠..

즉, asymtotic하게는 둘 다 동일한 것이죠.

실제 정확한 러닝타임이 향상되었다는 것을 보여주시는 거라면,

가장 최적화된 k를 찾고, 실제로 그 구조에 적용될 수가 있는지,

그리고 space-time tradeoff는 없는지를 알아보시면,

좋은 논문이 되겠네요 ^^

제가 말씀드리고 싶은건 만일 asymtotic running time을 줄이는

내용이라면 그건 알고리즘 디스크립션과 러닝 타임의 증명만으로도

훌륭한 논문이 될 수 있지만, 실제 러닝타임을 줄이는 내용이라면

그건 engineering이기 때문에 실제 application에서 n의 크기가

얼마나 되는지에 대한 조사(FFT는 그다지 크지 않죠?), 그리고 실제 구현했을 때의 성능 등이 포함이 되어야 좋은 논문이 될 수가 있습니다. 좋은 논문 쓰세요 ^^

최종호의 이미지

urmajest wrote:

딴지는 아니구요..
...
즉, asymtotic하게는 둘 다 동일한 것이죠.

제 답글은 딴지 맞구요.. ㅡ.ㅡ;;
p가 묵음이라도 있는 건 있는 거니까.. asymptotic 이 맞을 듯 합니다.. ㅡ.ㅡ;;
kjw2048의 이미지

교수님들께 상의 해보심이...

그리고 related work 을 꼭! 찾아보세요...

"아! 이건 기막힌 생각이다!" 라고 생각되서 논문 찾아보면 수십개씩 나옵니다 -_-;

(-_-)/

kcho의 이미지

혹시 논문 출판되면 여기에 다시 알려주세요. 아니면 개인적으로라도요. 관심이 많거든요.

나는 열정적인 사람이다. 열정은 내가 가지고 있는 에너지의 원동력이다.

s9204의 이미지

journal of computational physics는 어떤가요?

http://www.elsevier.com/locate/issn/00219991

skysign의 이미지

오래된 글이기는 하지만...
이후 어떻게 진행되었는지 아시는 분 있으신가요?

kkb110의 이미지

제가 알죠 ^^;
kjw2048님 말씀이 맞더군요 IEEE에서 정확히 같은 내용의 논문이 있더라구요 OTL

supaflow의 이미지

이글은 다시봐도 아까운듯..^^

=====
http://supaflow.tistory.com

kkb110의 이미지

게시판 왔다가 이글 올라와 있는거 보고 놀랬습니다 ^^;; 부끄럽기도하고~
거의 3년가까이 된 글인데.. 지금보니 그때생각이 모락모락~
지금보면 진짜 별 내용 아니였는데 -_-;;;

분석할 데이터가 실수일때 중복되는 연산을 뺀다는 내용입니다.
뭐 이건 사실 너무나 당연한건데 -_-;;
잘 포장해서 설명되어있는 논문은 이거구요.
http://user.chol.com/~kkb110/Real-valued_fast_Fourier_transform_algorithms.pdf

근데 최근에 FFT 연산 신기록이 갱신되었습니다.
2^n의 데이터에 대해선 Split-Radix 기법이 근 30년가까이 (곱셈횟수+덧셈횟수)최저연산량을 기록하고있었는데
이게 얼마전에 깨진거죠. 대단합니다. 여전히 NLogN인데 앞의 상수가 바뀌었습니다.
36/9 -> 34/9로..
그런데 얼마 차이 나지 않는데다가
알고리즘 구조복잡도라던지 사용하는 상수메모리가 증가해서 실용성이 있다고 보긴 힘들긴 합니다.
관련논문 두가지는 다음입니다.

http://www.fftw.org/newsplit.pdf
http://cr.yp.to/arith/tangentfft-20070809.pdf

전자가 그나마 이해하기 쉽게 설명해 둔 것 같구요.
후자는 다항식표기법이 신선하긴한데 알아보기는 더 힘든 것 같습니다.