FFT관련 논문은 어디다 발표하는게 나을까요?
글쓴이: kkb110 / 작성시간: 월, 2005/02/07 - 10:17오후
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에다 내볼까요?
Forums:
부디 지도교수에게 먼저 문의해보시기 바랍니다.앞서, 수십년묵은 그
부디 지도교수에게 먼저 문의해보시기 바랍니다.
앞서, 수십년묵은 그 기술들을 먼저 만들었다고 알려진 수많은 돌대가리들에게
예의상 묵념 한번 올려주시구요.ㅡ.ㅡ;
우.연.히....
--------------------------------------------------------------------------------
＼(´∇`)ノ ＼(´∇`)ノ ＼(´∇`)ノ ＼(´∇`)ノ
def ed():neTdiVeR in range(thEeArTh)
제가 잘 모르는 것일 수도 있지만nLog[2,n]과 1/2nLog
제가 잘 모르는 것일 수도 있지만
nLog[2,n]과 1/2nLog[2,n] + n-1는 결국 시간 복잡도가 같은 것 아닌가요 ??
여기서 FFT의 시간복잡도라 말하는 건 O(nLog[2,n]) 일 텐데 결국 1/2nLog[2,n] +n-1도 결국 O(nLog[2,n])인 데 말이죠.
결국 대세에 큰 영향을 미치는 건 아니지 않을까요?
아... 그부분2
아... 그부분에있어서 오해가 있을 수 있겠군요.
제가 만든 구조는 기존 FFT 알고리즘에 추가적으로 적용할수있는거라서요. 기존 알고리즘 에다가 제 구조를 거기다 적용하면 연산량이 정확히 반으로 줄어들고 거기다가 +n-1만큼의 연산량이 더 생깁니다.
시간복잡도라는것보다는 다른 말이 더 적합하겠네요.
다시 예를 들면 원본 알고리즘 연산 시간이 상수 k를 써서
k * nLog[2,n] 이라면 거기다가 제 구조를 적용하면
k * (1/2nLog[2,n] + n-1) 만큼의 시간이 걸립니다 ^^
그전에 일단 이전에 나온 FFT 관련 논문들과 특허를 먼저 찾아보시고 생
그전에 일단 이전에 나온 FFT 관련 논문들과 특허를 먼저 찾아보시고 생각하시는 알고리듬과 비슷한 주제로 나온 것이 있는지를 확인해 보시는 것이 좋을 듯 싶습니다. FFT가 신호처리 분야에서는 굉장히 중요한 알고리듬으로 알고 있기 때문에 속도를 빠르게 하거나 효율성을 높이는 논문이나 특허가 굉장히 많기 때문에 이전에 나왔을 가능성도 있다고 생각됩니다. 그렇게 찾아보신 후 새로운 것이나 굉장한 개선이 있다고 생각되면 당장 논문을 써서 제출하시면 되고, 제출할 학회는 지금까지 찾아보신 논문들이 어디서 발표되었는지를 확인하면 되겠지요.
...
[quote="kkb110"]제가 만든 구조는 기존 FFT 알고리즘에
진짜라면 이걸 왜 논문으로 냅니까? 특허로 꽁꽁 묶은 후에 평생 특허료만 먹고 살아도 됩니다. :shock:
Re: FFT관련 논문은 어디다 발표하는게 나을까요?
수고하셨습니다 :)
이제 mp3나 ogg 인코딩하는 시간이 반으로 줄겠네요..
----
http://www.planetmono.org
아! 특허로 DŽ
아! 특허로 내도 되는거였나요? -_-;;;;;;;;;;;;;;;;
특허쪽 한번 봐야겠네 *-_____-*;;;
사실 내용은 간단한거라 누가 먼저 발견했을거라는생각이 아주 강력하게 들기는 하는데;;;
일반적으로 가장 빠른 FFT알고리즘으로 인정받는 FFTW(fftw.org) 랑 djbfft(cr.yp.to/djbfft.html) 에 그런내용이 없다는것은 확인했습니다 히히힣힣힣 ^------------------------^
Re: FFT관련 논문은 어디다 발표하는게 나을까요?
특허로 출원하신다면 그렇기 힘들겠죠..
Creativity always builds on the past.
And you're building the past right now.
Share now. Shape tomorrow.
[quote="hjfirst"]제가 잘 모르는 것일 수도 있지만n
시간 복잡도가 같아도 계수가 다르다면 충분히 활용 가능합니다. 둘 다 O(n log n)인 건 마찬가지지만 계수가 반이니까요.
- 토끼군
...
제가 전공이 달라서, 그 논문의 가치라던지 그쪽 저널의 순위라던지 그런건 잘 모르지만
http://epubs.siam.org/sam-bin/dbq/toclist/SIAP
이정도면 어떨까요?
No Pain, No Gain.
[quote="cdpark"][quote="kkb110"]제가 만든
논문으로 낸 뒤에 6개월내에 보강해서 특허로 내면 됩니다.
거꾸로도 가능하지요. 특허낸 뒤에 '이런 게 있다. 특허 찾아봐라~~ ' 이런 식의 논문이죠.
IEEE 논문 보면 그런 게 꽤 많습니다.
그리고 FFT 는 ... 퓨리에 하고 별로 친하지 않아서 좋은 점수가 나오지 않아서 ... 수학적으로 뭐라 말씀드릴 내용은 없네요. - 복학하고 받은 유일한 F ...
---------
귓가에 햇살을 받으며 석양까지 행복한 여행을...
웃으며 떠나갔던 것처럼 미소를 띠고 돌아와 마침내 평안하기를...
- 엘프의 인사, 드래곤 라자, 이영도
즐겁게 놀아보자.
sci.math.num-analysis 같은데 올려봐도
좋을 것 같은데요...
그러니까 개발하신 것이 새로운 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.
계속 검색해보고 있는데 tokigun님이 말씀해주신 SIAP정도면 괜찮은
계속 검색해보고 있는데 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에다가 중복적용도 가능하구요.
코딩하면 벤치마크도 올리겠습니다 ^^
혹시나 해서 말씀드리는데요..wavelet에서 이용되던 lifti
혹시나 해서 말씀드리는데요..
wavelet에서 이용되던 lifting scheme이 아닌가 한번
확인해 보심이...
제 생각에도 같은 것이 아니었으면 좋겠습니다.
오늘 하루의 의미를 생각해 보자
[quote="kkb110"]아... 그부분에있어서 오해가 있을 수 있겠
딴지는 아니구요..
FFT의 time-complexity에 대해선 잘 모르지만,
O(nlogn) = O(1/2 nlogn + n-1) 이죠..
즉, asymtotic하게는 둘 다 동일한 것이죠.
실제 정확한 러닝타임이 향상되었다는 것을 보여주시는 거라면,
가장 최적화된 k를 찾고, 실제로 그 구조에 적용될 수가 있는지,
그리고 space-time tradeoff는 없는지를 알아보시면,
좋은 논문이 되겠네요 ^^
제가 말씀드리고 싶은건 만일 asymtotic running time을 줄이는
내용이라면 그건 알고리즘 디스크립션과 러닝 타임의 증명만으로도
훌륭한 논문이 될 수 있지만, 실제 러닝타임을 줄이는 내용이라면
그건 engineering이기 때문에 실제 application에서 n의 크기가
얼마나 되는지에 대한 조사(FFT는 그다지 크지 않죠?), 그리고 실제 구현했을 때의 성능 등이 포함이 되어야 좋은 논문이 될 수가 있습니다. 좋은 논문 쓰세요 ^^
[quote="urmajest"]딴지는 아니구요.....즉,
제 답글은 딴지 맞구요.. ㅡ.ㅡ;;
p가 묵음이라도 있는 건 있는 거니까.. asymptotic 이 맞을 듯 합니다.. ㅡ.ㅡ;;
교수님들께 상의 해보심이...그리고 related work 을 꼭
교수님들께 상의 해보심이...
그리고 related work 을 꼭! 찾아보세요...
"아! 이건 기막힌 생각이다!" 라고 생각되서 논문 찾아보면 수십개씩 나옵니다 -_-;
(-_-)/
혹시 논문 출판되면 여기에 다시 알려주세요. 아니면 개인적으로라도요. 관
혹시 논문 출판되면 여기에 다시 알려주세요. 아니면 개인적으로라도요. 관심이 많거든요.
나는 열정적인 사람이다. 열정은 내가 가지고 있는 에너지의 원동력이다.
journal of computational physics는 어떤가요?
journal of computational physics는 어떤가요?
http://www.elsevier.com/locate/issn/00219991
오래된 글이기는
오래된 글이기는 하지만...
이후 어떻게 진행되었는지 아시는 분 있으신가요?
제가 알죠 ^^; kjw2048님
제가 알죠 ^^;
kjw2048님 말씀이 맞더군요 IEEE에서 정확히 같은 내용의 논문이 있더라구요 OTL
이글은 다시봐도
이글은 다시봐도 아까운듯..^^
=====
http://supaflow.tistory.com
=====
http://supaflow.tistory.com
게시판 왔다가 이글
게시판 왔다가 이글 올라와 있는거 보고 놀랬습니다 ^^;; 부끄럽기도하고~
거의 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
전자가 그나마 이해하기 쉽게 설명해 둔 것 같구요.
후자는 다항식표기법이 신선하긴한데 알아보기는 더 힘든 것 같습니다.