फूरियर रूपांतरण। व्रत और उग्र

अक्सर, जब एल्गोरिदम विकसित करते हैं, तो हम कम्प्यूटेशनल जटिलता की सीमा में भागते हैं, जो, ऐसा प्रतीत होता है, जिसे पार करना असंभव है। फूरियर रूपांतरण में जटिलता है $$$O (n ^ 2)$ , और एक त्वरित संस्करण, हाउस ¹ द्वारा 1805 के आसपास प्रस्तावित किया गया था (और 1965 में जेम्स कॉले और जॉन तुकी द्वारा पुनर्निर्मित किया गया था) $$$O (nlog (n))$ । इस लेख में मैं आपको दिखाना चाहता हूं कि आप रैखिक समय में रूपांतरण परिणाम प्राप्त कर सकते हैं $$$O (n)$ या यहां तक ​​कि निरंतर कठिनाई हासिल करते हैं $$$O (1)$ कुछ परिस्थितियों में जो वास्तविक समस्याओं में पाए जाते हैं।


जब मुझे वास्तविक समय में ध्वनि प्रणालियों के हस्तांतरण कार्यों के विश्लेषण के लिए एक कार्यक्रम लिखने के कार्य का सामना करना पड़ा, तो मैं, बाकी सभी की तरह, पहले त्वरित रूपांतरण में बदल गया। सब कुछ ठीक था, लेकिन समय विंडो के बड़े आकार के साथ, सीपीयू लोड अनिश्चित रूप से बड़ा हो गया और कुछ करना पड़ा। परिवर्तन को फिर से रोकने और उसका अध्ययन करने का निर्णय लिया गया, और साथ ही समस्या को हल करने के तरीके भी खोजे गए। आइए जोसेफ फूरियर ² के मूल परिवर्तन पर वापस जाएं:

$$

$$f (x) = \ योग \ सीमाएँ _ {- \ infty} ^ {+ \ infty} c_ke ^ {2 \ pi ikx / T} \\ c_k = \ frac {1} {T} \ int \ _ सीमाएँ_0 ^ Tf ( x) e ^ {- 2 \ pi ikx / T} dx$$

हम यहाँ क्या चल रहा है, इसे ध्यान से देखेंगे। फ़्रीक्वेंसी डोमेन में प्रत्येक आउटपुट वैल्यू $$$c_k$ संकेत के सभी इनपुट मूल्यों का योग है $$$च (x)$ द्वारा गुणा किया गया $$$e ^ {- 2 \ pi ikx / T}$ । गणना करने के लिए, हमें प्रत्येक आउटपुट मान के लिए सभी इनपुट डेटा से गुजरना होगा, अर्थात्। उन को पूरा करने के लिए $$$n ^ 2$ संचालन।

एन से छुटकारा पाएं

मुझे आपको याद दिलाना है कि शुरू में कार्य वास्तविक समय में ध्वनि डेटा का विश्लेषण करना था। ऐसा करने के लिए, आकार N का चयनित समय विंडो (अनिवार्य रूप से एक बफर) नमूना आवृत्ति के अनुरूप एक आवृत्ति f _{d के} साथ डेटा से भरा है। अवधि टी के साथ, इनपुट डेटा को टाइम विंडो से फ़्रीक्वेंसी विंडो में परिवर्तित किया जाता है। यदि आप वास्तविक संख्याओं को देखते हैं, तो एन 2 2 ¹⁴ (16 384) से 2 ¹⁶ (65 536) के नमूनों में भिन्न होता है (मान एफएफटी से विरासत में मिले हैं, जहां खिड़की का आकार दो की शक्ति होना चाहिए)। समय टी = 80ms (प्रति सेकंड 12.5 बार), जो आपको काफी आसानी से बदलाव देखने की अनुमति देता है और सीपीयू और जीपीयू को अधिभार नहीं देता है। नमूने की आवृत्ति f _d मानक है और 48 kHz है। आइए गणना करते हैं कि आयामों के बीच समय विंडो में कितना डेटा बदलता है। समय टी के दौरान, यह बफर में प्रवेश करता है $$$48000 * 0.08 = $ 384$ नमूने हैं। इस प्रकार, विंडो में केवल 5% से 23% डेटा अपडेट किया जाता है। सबसे खराब स्थिति में, 95% (और सबसे अच्छा 73%, जो भी बहुत कुछ है!) संसाधित नमूनों का बार-बार रूपांतरण में गिर जाएगा, इस तथ्य के बावजूद कि वे पहले से ही पुनरावृत्तियों में संसाधित हो चुके हैं।

उस पल में चौकस पाठक अपना हाथ उठाएगा और कहेगा: “रुको, लेकिन गुणांक के बारे में क्या $$$e ^ {- 2 \ pi ikx / T}$ ? आखिरकार, प्रत्येक नए परिवर्तन के साथ, एक ही डेटा श्रृंखला के नए पदों पर स्थित होगा, और परिणामस्वरूप, अलग-अलग गुणांक हैं? " उनकी देखभाल के लिए हर पांच के लिए, चलो उस परिवर्तन में एक महत्वपूर्ण विवरण याद करते हैं जो अक्सर भूल जाता है। फ़ंक्शन मानों के अध्ययन में $$$च (t)$ 0 से टी के अंतराल पर, फ़ंक्शन को आवधिक माना जाता है, जो आपको समय के साथ बाएं या दाएं फ़ंक्शन को दर्द रहित रूप से स्थानांतरित करने की अनुमति देता है। नतीजतन, हमारे पास अंत में एक नया मूल्य नहीं डालने और शुरुआत से पुराने मूल्य को हटाने का हर अधिकार है, लेकिन बफर में डेटा को चक्रीय रूप से बदलने के लिए।

स्पष्टता के लिए, आप सारणीबद्ध रूप में लिख सकते हैं कि बफर कैसे बदलेगा:

t = 0	च (0)	च (1)	एफ (2)	च (3)	च (4)	च (5)	च (6)	एफ (7)	एफ (8)	f (9)
टी = 1	च (10)	च (1)	एफ (2)	च (3)	च (4)	च (5)	च (6)	एफ (7)	एफ (8)	f (9)
t = 2	च (10)	एफ (11)	एफ (2)	च (3)	च (4)	च (5)	च (6)	एफ (7)	एफ (8)	f (9)
t = 3	च (10)	एफ (11)	एफ (12)	च (3)	च (4)	च (5)	च (6)	एफ (7)	एफ (8)	f (9)
t = 4	च (10)	एफ (11)	एफ (12)	एफ (13)	च (4)	च (5)	च (6)	एफ (7)	एफ (8)	f (9)

आप लिख सकते हैं कि समय में परिवर्तन कैसे t ₁ से t _{2 में बदल जाता है} :

$$

$$F_t = F_ {t-1} + \ Delta F \\ \ Delta F: \ Delta c_k = \ frac {1} {T} \ int \ limit_ {t_1} ^ {t_2} (f_t (x - f_ {) t-1} (x)) e ^ {- 2 \ pi ikx / T} dx$$

मूल्य $$$F_ {t-1} (x)$ पिछले रूपांतरण और गणना की जटिलता का परिणाम है $$$\ Delta f (x)$ समय विंडो के आकार पर निर्भर नहीं करता है और इसलिए, स्थिर है। नतीजतन, रूपांतरण की जटिलता होगी $$$O (n)$ ^* क्योंकि हमारे लिए जो कुछ भी है वह एक बार आवृत्ति खिड़की से गुजरना है और समय के दौरान बदल गए टी नमूनों के लिए परिवर्तनों को लागू करना है। मैं इस तथ्य पर भी आपका ध्यान आकर्षित करना चाहूंगा कि ऑड्स $$$e ^ {- 2 \ pi ikx / T}$ अग्रिम में गणना की जा सकती है, जो उत्पादकता में एक अतिरिक्त लाभ देता है, और केवल दो संचालन चक्र में रहते हैं: वास्तविक संख्या घटाना और एक वास्तविक संख्या को एक जटिल से गुणा करना, व्यवहार में ये दोनों ऑपरेशन सरल और सस्ते हैं।

तस्वीर को पूरा करने के लिए, यह केवल प्रारंभिक स्थिति को इंगित करने के लिए बनी हुई है, लेकिन यहां सब कुछ सरल है:

$$

$$F_0 (x) = 0$$

* - बेशक, पूरे परिवर्तन की अंतिम जटिलता इतनी ही रहेगी $$$O (n ^ 2)$ , लेकिन बफर को अपडेट करने के दौरान, इसे पुनरावृत्तियों पर धीरे-धीरे निष्पादित किया जाएगा। $$$O (n)$ - यह डेटा को अपडेट करने की जटिलता है, लेकिन यह ठीक वैसा ही है जिसकी हमें जरूरत है (एफएफटी का उपयोग करते समय, प्रत्येक परिवर्तन की जटिलता $$$O (nlog (n))$ )।

लेकिन अगर आप गहरी खुदाई करें तो क्या होगा। या दूसरी एन से छुटकारा पाएं

मैं तुरंत एक आरक्षण करना चाहता हूं कि अगले चरण केवल तभी लागू होते हैं जब आप परिणाम के लिए व्युत्क्रम परिवर्तन (संकेत को सही करने या आवेग प्रतिक्रिया प्राप्त करने के लिए) की योजना नहीं बनाते हैं। शुरू करने के लिए, मैं आपको याद दिलाना चाहता हूं कि रूपांतरण के परिणामस्वरूप हमें एक सममित डेटा सरणी मिलती है, जो हमें तुरंत रूपांतरणों की संख्या को आधे से कम करने की अनुमति देती है।

अब हम परिणामी डेटा सेट का विश्लेषण करते हैं, समस्या की स्थितियों को देखते हुए। हमारे पास जटिल संख्याओं का एक सेट है, जिनमें से प्रत्येक एक विशेष आवृत्ति पर दोलनों के आयाम और चरण का वर्णन करता है। आवृत्ति सूत्र द्वारा निर्धारित की जा सकती है: $$$f [j] = j \ frac {fd} {N}$ के लिए $$$j <\ _ frac {N} {2}$ । आइए अपने डेटा पर फ़्रीक्वेंसी विंडो के चरण का मूल्यांकन करें: $$$\ Delta f = \ frac {fd} {N}$ एन = 2 ^{14 के लिए} : 2.93 हर्ट्ज (और 2 ^{16 के लिए} : 0.73 हर्ट्ज)। इस प्रकार, 1 kHz से 2 kHz तक की सीमा में हमें 341 परिणाम मिलते हैं। स्वतंत्र रूप से मूल्यांकन करने की कोशिश करें कि एन = 65536 के लिए 8 kHz से 16 kHz तक की सीमा में कितना डेटा होगा। बहुत, सही? बहुत कुछ! क्या हमें इतना डेटा चाहिए? बेशक, ध्वनि प्रणालियों की आवृत्ति विशेषताओं को प्रदर्शित करने की समस्याओं में, उत्तर नहीं है। और दूसरी ओर, कम-आवृत्ति क्षेत्र में विश्लेषण के लिए, एक छोटा कदम बहुत उपयोगी है। मत भूलो कि अभी भी एक अनुसूची आगे है कि इन संस्करणों को करना चाहिए ( $$$\ frac {N} {2}$ ) एक मानव-पठनीय रूप में परिवर्तित करें (औसत, तड़क या चिकनाई) और उन्हें स्क्रीन पर प्रदर्शित करें। और उच्च आवृत्तियों पर, यहां तक ​​कि 4K स्क्रीन होने और लॉगरिदमिक फ़्रीक्वेंसी अक्ष के साथ पूर्ण स्क्रीन मोड में ग्राफ़ प्रदर्शित करने पर, चरण आकार जल्दी से 1 पिक्सेल से कम हो जाएगा।

अनुभव से, आप यह पता लगा सकते हैं कि यह केवल 48 अंक प्रति सप्तक के लिए पर्याप्त है, और डेटा को थोड़ा चिकना और अधिक औसतन रखने के लिए, मैं 96 पर रुकने का सुझाव देता हूं। ऑडियो आवृत्ति रेंज में 20 हर्ट्ज से 20 किलोहर्ट्ज़ तक, केवल 10 सप्तक: 20, 40, 80 को गिनना आसान है। , 160, 320, 640, 1280, 2560, 5120, 10240, 20480, जिनमें से प्रत्येक को दी गई संख्या में उपनगरों में विभाजित किया जा सकता है (यह मत भूलो कि विभाजन ज्यामितीय रूप से किया जाना चाहिए, और अंकगणितीय रूप से नहीं, इसलिए, यह केवल रूपांतरण करने के लिए पर्याप्त से अधिक है। 960 आवृत्तियों को प्राप्त करने के लिए Performan कि मूल संस्करण की तुलना में 16 में ... 65 गुना छोटे।

इस प्रकार, दोनों दृष्टिकोणों को मिलाकर, हम डेटा अपडेट एल्गोरिदम की निरंतर जटिलता प्राप्त करते हैं $$$O (1)$ ।

चुकंदर शहद और एक चम्मच टार

अब हम सुरक्षित रूप से यह कह सकते हैं कि जटिलता से $$$O (n ^ 2)$ हम जटिलता में आ गए $$$O (1)$ दो सरल जीवन हैक का उपयोग कर:

• समस्या का विश्लेषण करने के बाद, हमने देखा कि डेटा को धीरे-धीरे जोड़ा जाता है, और समय विंडो के पूर्ण अद्यतन की अवधि परिवर्तनों की अवधि की तुलना में बहुत अधिक है और फूरियर रूपांतरण के अंतर की गणना करने के लिए आगे बढ़ी।
• आवृत्ति विंडो में अंकगणितीय चरण से केवल निर्दिष्ट मूल्यों तक सीमित करने के लिए चला गया, जो नाटकीय रूप से रूपांतरणों की संख्या को कम कर सकता है।

लेकिन, निश्चित रूप से, जीवन वास्तव में एक परी कथा होगी, यदि कोई नहीं लेकिन। इन दो दृष्टिकोणों के अनुप्रयोग ने हमें वास्तव में सीपीयू को उतारने की अनुमति दी ताकि यह अनुमान लगाया जा सके कि यह फूरियर रूपांतरण की गणना करता है और स्क्रीन पर भी परिणाम प्रदर्शित करता है $$$N = 2 ^ {20}$ यह मुश्किल था। लेकिन सजा खुद को इंतजार नहीं कराती थी जब वास्तविकता में आपके संकेत आवधिक नहीं होते हैं (और यह सही रूपांतरण परिणाम प्राप्त करने के लिए आवश्यक है) और उपयुक्त विंडो आकार का चयन करना संभव नहीं है, विभिन्न विंडो फ़ंक्शंस का उपयोग करना आवश्यक हो जाता है, जो अब आपको पहले चरण का पूरी तरह से उपयोग करने की अनुमति नहीं देता है। अभ्यास से पता चला है कि संकेतों के अध्ययन में खिड़की के कार्यों का उपयोग कम आवृत्ति के साथ महत्वपूर्ण है $$$0,1f_d$ । उच्च आवृत्तियों पर, टाइम विंडो में गिरने वाली अवधियों की संख्या मूल कार्य में प्रथम-क्रम अंतराल (f (0) और f (N-1)) की उपस्थिति से उत्पन्न होने वाली विकृतियों को महत्वपूर्ण रूप से दर्शाती है।

अंत में, मैंने दूसरे चरण से भी इनकार कर दिया और एफएफटी पर वापस लौट आया, क्योंकि इस कार्य में लाभ पहले ही छोटा था।

निष्कर्ष में

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

काश, इस समस्या में मेरे लिए, यह केवल थोड़ा गणितीय मनोरंजन बना रहा, लेकिन मुझे आशा है कि यह आपको समय के साथ इनपुट डेटा में बदलाव के संदर्भ में छुट्टियों पर अन्य एल्गोरिदम का अध्ययन करने के लिए प्रेरित करता है :)

साहित्य

1. Cooley - Tukey FFT कलन विधि
2. ईए वलसोवा रो। MSTU के पब्लिशिंग हाउस का नाम N.E.Bauman रखा गया। मास्को। 2002

मिकियो शिबुया द्वारा मंगा से ली गई छवि। "उत्कृष्ट सामग्री। फूरियर विश्लेषण