दिलचस्प पोस्ट

असतत फूरियर की गणना कैसे करें?

मैं डीटीटी को बेहतर ढंग से समझने में मदद करने के लिए कुछ जगहों को खोजने की कोशिश कर रहा हूं और इसे कैसे गणना करना है लेकिन कोई फायदा नहीं हुआ। इसलिए मुझे डीएफटी को समझने में मदद की ज़रूरत है और यह जटिल संख्याओं की गणना है।

असल में, मैं सिर्फ उदाहरण के लिए देख रहा हूं कि डीटीटी की गणना कैसे की गई है, इस बारे में स्पष्टीकरण के साथ कि यह कैसे गणना की गई थी क्योंकि अंत में, मैं इसे गणना करने के लिए एक एल्गोरिथ्म बनाना चाहता हूं।

वेब के समाधान से एकत्रित समाधान "असतत फूरियर की गणना कैसे करें?"

मैं 1 डी डीएफटी / आईडीएफटी ग्रहण करता हूं …

सभी डीएफटी इस सूत्र का उपयोग करते हैं:

डीएफटी समीकरण

  • X(k) नमूना मूल्य (जटिल डोमेन) को बदल दिया है
  • x(n) इनपुट डेटा नमूना मान है (वास्तविक या जटिल डोमेन)
  • N आपके डेटासेट में नमूनों / मूल्यों की संख्या है

यह पूरी चीज सामान्यतः निरंतर c गुणा होती है। जैसा कि आप एक मूल्य के लिए देख सकते हैं आपको N कंप्यूटेशन की आवश्यकता होती है, इसलिए सभी नमूनों के लिए यह O(N^2) जो धीमा है।

यहाँ मेरा रियल <-> कॉम्प्लेक्स डोमेन डीएफटी / आईडीएफटी सी ++ में आप यह भी इंगित कर सकते हैं कि 1 डी रूपांतरण के साथ 2 डी रूपांतरण कैसे गणना करें और N-point डीसीटी, आईडीटीटी द्वारा N-point डीएफटी, आईडीएफटी की गणना कैसे करें।

फास्ट एल्गोरिदम

इस समीकरण को अजीब और अलग-अलग हिस्सों के बंटवारे के आधार पर अलग-अलग एल्गोरिदम भी हैं (जो 2x N/2 रकम देता है) जो भी एक O(N) प्रति एकल मान है, लेकिन 2 भाग समान समीकरण हैं +/- कुछ निरंतर चिमटा तो पहले से सीधे एक से आधा गणना की जा सकती है। यह O(N/2) प्रति एकल मान की ओर जाता है यदि आप इसे पुनरावर्तित करते हैं तो आपको O(log(N)) प्रति एकल मान मिलता है। तो पूरी चीज O(N.log(N)) बन गई जो कि बढ़िया है लेकिन यह प्रतिबंध भी जोड़ता है:

सभी डीएफएफटी को इनपुट डाटासेट की जरूरत है आकार दो के सत्ता के बराबर है !!!

इसलिए इसे फिर से विभाजित किया जा सकता है। 2 की निकटतम बड़ी शक्ति के लिए शून्य पैडिंग को अमान्य डेटासेट आकार (ऑडियो तकनीक में कभी-कभी भी चरण बदलाव) के लिए उपयोग किया जाता है। इधर देखो:

  • मेरा कॉम्प्लेक्स-> कॉम्प्लेक्स डोमेन डीएफटी, डीएफएफटी सी ++
  • एल्गोरिदम जैसे एफएफटी के निर्माण पर कुछ संकेत

जटिल आंकड़े

  • c = a + i*b
  • c जटिल संख्या है
  • a इसका वास्तविक हिस्सा है (पुनः)
  • b इसकी काल्पनिक भाग है (आईएम)
  • i*i=-1 काल्पनिक इकाई है

तो गणना इस तरह है

इसके अलावा:

 c0+c1=(a0+i.b0)+(a1+i.b1)=(a0+a1)+i.(b0+b1) 

गुणन:

 c0*c1=(a0+i.b0)*(a1+i.b1) =a0.a1+i.a0.b1+i.b0.a1+iib0.b1 =(a0.a1-b0.b1)+i.(a0.b1+b0.a1) 

वास्तविक -> जटिल रूपांतरण:

 complex = real+i.0 

[टिप्पणियाँ]

  • यह मत भूलो कि आपको डेटा को अलग सरणी में परिवर्तित करने की जरूरत है (जगह में नहीं)
  • FFT रिकर्सन पर सामान्यीकरण स्थिर है (आमतौर पर कुछ जैसे /=log2(N) पुनरावर्ती रोकथाम स्थिति पर भी निर्भर करता है)
  • अगर N=1 or 2 पुनरावृत्ति को रोकने के लिए मत भूलना …
  • सावधान रहें कि एफपीयू बड़े डेटासेट पर उगाही कर सकता है ( N बड़ा है)
  • यहां डीएफटी / डीएफएफटी के कुछ अंतर्दृष्टि हैं
  • यहां 2 डी एफएफटी और रैपिंग उदाहरण
  • आमतौर पर यूलर का सूत्र e^(ix)=cos(x)+i.sin(x) गणना करने के लिए उपयोग किया जाता है

मैं स्टीवन डब्ल्यू स्मिथ द्वारा डिजिटल सिग्नल प्रोसेसिंग के लिए वैज्ञानिक और अभियंता की मार्गदर्शिका पढ़ रहा हूं । यह एक मुफ्त पीडीएफ है अध्याय 12 में वह एफएफटी चरण-दर-चरण (एक वास्तविक संख्या इनपुट के साथ जटिल एफएफटी) के एक कार्यान्वयन के माध्यम से जाता है, और अंत में एक रियलएफएफटी प्रस्तुत करता है (जो कि एफएफटी को वास्तविक निविष्टियों के लिए विशेष रूप से संशोधित किया गया है)। एक अन्य अध्याय है जो जटिल एफएफटी के लिए समर्पित है। किताब का एक छोटा सा है, इसलिए बुनियादी और फोरट्रान में लिखा गया प्रोग्रामिंग उदाहरण प्राचीन लगते हैं, लेकिन अवधारणाओं को समझाया और सचित्र किया गया है।

यहां एक बहुत अच्छा उदाहरण है (आईएमएचओ): http://www.phpclasses.org/package/6193-PHP-Compute-the-Fast-Fourier-Transform-of-sampled-data.html

यह एक FFT एल्गोरिथ्म है जो PHP में लिखा गया है, और जटिल संख्या गणना भी है। आपके मामले में सहायक हो सकता है

जब मैंने अपने इंजीनियरिंग सम्मान परियोजना पर काम कर रहा था तो मुझे यह अविश्वसनीय रूप से उपयोगी मिला। वहाँ कुछ अच्छा लिंक भी हैं, लेकिन मेरे पास इस समय मेरे पास नहीं है (मैं वर्तमान में घर पर नहीं हूं।)