वलय पर असतत फूरियर रूपांतरित

गणित में, एक वलय के ऊपर असतत फूरियर रूपांतरण एक फलन के असतत फूरियर रूपांतरण (डीएफटी) को सामान्यीकृत करता है, जिसके मान सामान्यतः एक इच्छानुसार वलय (गणित) पर जटिल संख्याएं होते हैं।

का एक अनुप्रयोग कोडिंग सिद्धांत में रीड-सोलोमन कोड को बीसीएच कोड में कम करना है। इस तरह के परिवर्तन को उचित तेज एल्गोरिदम के सा

परिभाषा

होने देना $R$ कोई भी वलय हो (गणित), चलो $n\geq 1$ एक पूर्णांक हो, और चलो $\alpha \in R$ एकता का एक प्रमुख मूल बनें और एकता की मूल जड़ बनें, इसे निम्न द्वारा परिभाषित किया गया है:

${\begin{aligned}&\alpha ^{n}=1\\&\sum _{j=0}^{n-1}\alpha ^{jk}=0{\text{ for }}1\leq k<n\qquad (1)\end{aligned}}$

असतत फूरियर R के तत्वों के n-टपल $(v_{0},\ldots ,v_{n-1})$ को दूसरे n-टपल $(f_{0},\ldots ,f_{n-1})$ में बदल देता है। R के तत्वों का निम्नलिखित सूत्र के अनुसार:

$f_{k}=\sum _{j=0}^{n-1}v_{j}\alpha ^{jk}.\qquad (2)$

परंपरा के अनुसार, टुपल $(v_{0},\ldots ,v_{n-1})$को समय डोमेन में कहा जाता है और सूचकांक j को समय कहा जाता है। टपल$(f_{0},\ldots ,f_{n-1})$ को आवृत्ति डोमेन में कहा जाता है और सूचकांक $k$ को आवृत्ति कहा जाता है। टपल $(f_{0},\ldots ,f_{n-1})$ को $(v_{0},\ldots ,v_{n-1})$ का स्पेक्ट्रम भी कहा जाता है। यह शब्दावली सिग्नल प्रोसेसिंग में फूरियर रूपांतरण के अनुप्रयोगों से ली गई है।

यदि R एक अभिन्न डोमेन है (जिसमें क्षेत्र सम्मिलित हैं), तो $\alpha$ को एकता की आदिम nवीं जड़ के रूप में चुनना पर्याप्त है, जो नियम (1) को प्रतिस्थापित करता है:

$\alpha ^{k}\neq 1$ के लिए $1\leq k<n$

प्रमाण: लो $\beta =\alpha ^{k}$ साथ $1\leq k<n$. तब से $\alpha ^{n}=1$, $\beta ^{n}=(\alpha ^{n})^{k}=1$, देना:

$\beta ^{n}-1=(\beta -1)\left(\sum _{j=0}^{n-1}\beta ^{j}\right)=0$

जहां योग (1) से मेल खाता है। तब से $\alpha$ एकता की आदिम जड़ है, $\beta -1\neq 0$. तब से $R$ एक अभिन्न डोमेन है, योग शून्य होना चाहिए। ∎

एक और सरल नियम उस स्थिति में प्रयुक्त होती है जहां n दो की घात है: (1) को $\alpha ^{n/2}=-1$ से प्रतिस्थापित किया जा सकता है।

उलटा

असतत फूरियर रूपांतरण का व्युत्क्रम इस प्रकार दिया गया है:

$v_{j}={\frac {1}{n}}\sum _{k=0}^{n-1}f_{k}\alpha ^{-jk}.\qquad (3)$

जहाँ $1/n$, R में n का गुणात्मक व्युत्क्रम है (यदि यह व्युत्क्रम उपस्थित नहीं है, तो डीएफटी को विपरीत नहीं किया जा सकता है)।

प्रमाण: (3) के दाईं ओर (2) रखने पर, हमें प्राप्त होता है

${\begin{aligned}&{\frac {1}{n}}\sum _{k=0}^{n-1}f_{k}\alpha ^{-jk}\\={}&{\frac {1}{n}}\sum _{k=0}^{n-1}\sum _{j'=0}^{n-1}v_{j'}\alpha ^{j'k}\alpha ^{-jk}\\={}&{\frac {1}{n}}\sum _{j'=0}^{n-1}v_{j'}\sum _{k=0}^{n-1}\alpha ^{(j'-j)k}.\end{aligned}}$

ये बिल्कुल समान है $v_{j}$, क्योंकि

$\sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=0$ जब $j'\neq j$ (द्वारा (1) के साथ $k=j'-j$), और
$\sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=n$ जब $j'=j$. ∎

आव्यूह सूत्रीकरण

चूंकि असतत फूरियर रूपांतरण एक रैखिक ऑपरेटर है, इसलिए इसे आव्यूह गुणन द्वारा वर्णित किया जा सकता है। आव्यूह नोटेशन में असतत फूरियर रूपांतरण निम्नानुसार व्यक्त किया गया है:

${\begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{n-1}\end{bmatrix}}={\begin{bmatrix}1&1&1&\cdots &1\\1&\alpha &\alpha ^{2}&\cdots &\alpha ^{n-1}\\1&\alpha ^{2}&\alpha ^{4}&\cdots &\alpha ^{2(n-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha ^{n-1}&\alpha ^{2(n-1)}&\cdots &\alpha ^{(n-1)(n-1)}\\\end{bmatrix}}{\begin{bmatrix}v_{0}\\v_{1}\\\vdots \\v_{n-1}\end{bmatrix}}.$

इस परिवर्तन के आव्यूह को डीएफटी आव्यूह कहा जाता है।

इसी प्रकार, व्युत्क्रम फूरियर रूपांतरण के लिए आव्यूह नोटेशन है

${\begin{bmatrix}v_{0}\\v_{1}\\\vdots \\v_{n-1}\end{bmatrix}}={\frac {1}{n}}{\begin{bmatrix}1&1&1&\cdots &1\\1&\alpha ^{-1}&\alpha ^{-2}&\cdots &\alpha ^{-(n-1)}\\1&\alpha ^{-2}&\alpha ^{-4}&\cdots &\alpha ^{-2(n-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha ^{-(n-1)}&\alpha ^{-2(n-1)}&\cdots &\alpha ^{-(n-1)(n-1)}\end{bmatrix}}{\begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{n-1}\end{bmatrix}}.$

बहुपद सूत्रीकरण

कभी-कभी औपचारिक बहुपद के साथ $n$-ट्यूपल $(v_{0},\ldots ,v_{n-1})$की पहचान करना सुविधाजनक होता है

$p_{v}(x)=v_{0}+v_{1}x+v_{2}x^{2}+\cdots +v_{n-1}x^{n-1}.\,$

असतत फूरियर रूपांतरण (2) की परिभाषा में सारांश लिखकर, हम प्राप्त करते हैं:

$f_{k}=v_{0}+v_{1}\alpha ^{k}+v_{2}\alpha ^{2k}+\cdots +v_{n-1}\alpha ^{(n-1)k}.\,$

इसका अर्थ यह है कि$f_{k}$ , $x=\alpha ^{k}$ के लिए बहुपद $p_{v}(x)$ का मान मात्र है।

$f_{k}=p_{v}(\alpha ^{k}).\,$

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

इसी प्रकार, व्युत्क्रम फूरियर रूपांतरण (3) की परिभाषा लिखी जा सकती है:

$v_{j}={\frac {1}{n}}(f_{0}+f_{1}\alpha ^{-j}+f_{2}\alpha ^{-2j}+\cdots +f_{n-1}\alpha ^{-(n-1)j}).\qquad (5)$

साथ

$p_{f}(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots +f_{n-1}x^{n-1},$

इस का अर्थ है कि

$v_{j}={\frac {1}{n}}p_{f}(\alpha ^{-j}).$

हम इसे इस प्रकार संक्षेप में प्रस्तुत कर सकते हैं: यदि $p(x)$ का मान $q(x)$ का गुणांक है तो $q(x)$ का मान एक अदिश कारक और पुनर्क्रमण तक $p(x)$ का गुणांक है।

विशेष स्थिति

सम्मिश्र संख्याएँ

यदि $F={\mathbb {C} }$ सम्मिश्र संख्याओं का क्षेत्र है, तो $n$एकता की जड़ों को जटिल तल के इकाई वृत्त पर बिंदुओं के रूप में देखा जा सकता है। इस स्थिति में, सामान्यतः कोई लेता है

$\alpha =e^{\frac {-2\pi i}{n}},$

जो असतत फूरियर रूपांतरण के लिए सामान्य सूत्र उत्पन्न करता है:

$f_{k}=\sum _{j=0}^{n-1}v_{j}e^{{\frac {-2\pi i}{n}}jk}.$

जटिल संख्याओं पर अधिकांशतः डीएफटी के लिए सूत्र में 1 और व्युत्क्रम के लिए सूत्र में ${\frac {1}{n}}$ के अतिरिक्त दोनों सूत्रों में अदिश कारक ${\frac {1}{\sqrt {n}}}$ का उपयोग करके डीएफटी और व्युत्क्रम डीएफटी के लिए सूत्रों को सामान्य करने की प्रथा है। डीएफटी. इस सामान्यीकरण के साथ, डीएफटी आव्यूह तब एकात्मक होता है। ध्यान दें कि किसी इच्छानुसार क्षेत्र में ${\sqrt {n}}$ का कोई अर्थ नहीं है।

परिमित क्षेत्र

यदि $F=GF(q)$ एक सीमित क्षेत्र है, जहां $q$ एक अभाज्य संख्या शक्ति है, तो एक आदिम का अस्तित्व $n$मूल स्वतः ही इसका तात्पर्य करता है कि $n$ $q-1$ को विभाजित करता है, क्योंकि प्रत्येक तत्व के गुणक क्रम को गुणक समूह के आकार को विभाजित करना होगा $F$, जो $q-1$ है यह विशेष रूप से यह सुनिश्चित करता है $n=\underbrace {1+1+\cdots +1} _{n\ {\rm {times}}}$ विपरीत है, जिससे अंकन ${\frac {1}{n}}$ (3) में समझ में आता है।

$GF(q)$ पर असतत फूरियर रूपांतरण का एक अनुप्रयोग कोडिंग सिद्धांत में रीड-सोलोमन कोड को बीसीएच कोड में कम करना है। इस तरह के परिवर्तन को उचित तेज एल्गोरिदम के साथ कुशलतापूर्वक किया जा सकता है, उदाहरण के लिए साइक्लोटोमिक फास्ट फूरियर रूपांतरण होता है।

संख्या-सैद्धांतिक परिवर्तन

संख्या-सैद्धांतिक परिवर्तन (एनटीटी) असतत फूरियर रूपांतरण को $F={\mathbb {Z} }/p$ में विशेषज्ञता द्वारा प्राप्त किया जाता है, पूर्णांक मॉड्यूल एक अभाज्य p यह एक परिमित क्षेत्र है, और जब भी n, $p-1$ को विभाजित करता है तो एकता की आदिम nवीं जड़ें उपस्थित होती हैं, इसलिए हमारे पास एक सकारात्मक पूर्णांक ξ के लिए $p=\xi n+1$ है। विशेष रूप से, मान लीजिए कि $\omega$ एकता का एक आदिम $(p-1)$वाँ मूल है, तो एकता का nवाँ मूल $\alpha$ ,$\alpha =\omega ^{\xi }$मानकर पाया जा सकता है।

जैसे के लिए $p=5$, $\alpha =2$ :${\begin{aligned}2^{1}&=2{\pmod {5}}\\2^{2}&=4{\pmod {5}}\\2^{3}&=3{\pmod {5}}\\2^{4}&=1{\pmod {5}}\end{aligned}}$ जब $N=4$

${\begin{bmatrix}F(0)\\F(1)\\F(2)\\F(3)\end{bmatrix}}={\begin{bmatrix}1&1&1&1\\1&2&4&3\\1&4&1&4\\1&3&4&2\end{bmatrix}}{\begin{bmatrix}f(0)\\f(1)\\f(2)\\f(3)\end{bmatrix}}$

संख्या सैद्धांतिक परिवर्तन वलय $\mathbb {Z} /m$ में सार्थक हो सकता है, तब भी जब मापांक m अभाज्य नहीं है, परन्तु क्रम n का एक प्रमुख मूल उपस्थित हो। संख्या सैद्धांतिक परिवर्तन के विशेष स्थिति जैसे कि फ़र्मेट नंबर रूपांतरण (m = 2^k+1), जो शॉनहेज-स्ट्रैसेन एल्गोरिदम द्वारा उपयोग किया जाता है, या मेर्सन नंबर रूपांतरण (m = 2^k − 1) एक समग्र मापांक का उपयोग करते हैं।

असतत भारित परिवर्तन

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

गुण

व्युत्क्रम परिवर्तन, कनवल्शन प्रमेय और सबसे तेज फूरियर रूपांतरण (एफएफटी) एल्गोरिदम सहित जटिल डीएफटी की अधिकांश महत्वपूर्ण विशेषताएं, केवल इस संपत्ति पर निर्भर करती हैं कि रूपांतरण का कर्नेल एकता की प्रमुख जड़ है। ये गुण, समान प्रमाणों के साथ, इच्छानुसार छल्लों पर भी लागू होते हैं। क्षेत्र के मामले में, इस सादृश्य को एक तत्व के साथ क्षेत्र द्वारा औपचारिक रूप दिया जा सकता है, विस्तार क्षेत्र $\mathbf {F} _{1^{n}}.$ पर बीजगणित के रूप में एकता की आदिम nवीं जड़ वाले किसी भी क्षेत्र पर विचार किया जा सकता है।

विशेष रूप से, एनटीटी की गणना करने के लिए $O(n\log n)$ फास्ट फूरियर रूपांतरण एल्गोरिदम की प्रयोज्यता, कनवल्शन प्रमेय के साथ मिलकर, इसका अर्थ है कि संख्या-सैद्धांतिक परिवर्तन पूर्णांक अनुक्रमों के स्पष्ट कनवल्शन की गणना करने का एक कुशल विधि देता है। जबकि जटिल डीएफटी समान कार्य कर सकता है, यह परिमित-परिशुद्धता फ़्लोटिंग पॉइंट अंकगणित में राउंड-ऑफ त्रुटि के लिए अतिसंवेदनशील है; एनटीटी का कोई राउंड-ऑफ नहीं है क्योंकि यह पूरी तरह से निश्चित आकार के पूर्णांकों से संबंधित है जिन्हें स्पष्ट रूप से दर्शाया जा सकता है।

तेज़ एल्गोरिदम

एक तेज एल्गोरिदम के कार्यान्वयन के लिए (फूरियर रूपांतरण कितनी तेजी से असतत फूरियर रूपांतरण की गणना करता है) यह अधिकांशतः वांछनीय होता है कि रूपांतरण लंबाई भी अत्यधिक समग्र हो, उदाहरण के लिए, दो की शक्ति। चूँकि परिमित क्षेत्रों के लिए विशेष तेज़ फूरियर रूपांतरण एल्गोरिदम हैं, जैसे वांग और झू का एल्गोरिदम, जो परिवर्तन लंबाई कारकों की परवाह किए बिना कुशल हैं।

यह भी देखें

• असतत फूरियर रूपांतरण|असतत फूरियर रूपांतरण (जटिल)
• परिमित समूहों पर फूरियर रूपांतरण
• गॉस राशि
• संकल्प
• न्यूनतम-वर्ग वर्णक्रमीय विश्लेषण
• गुणा एल्गोरिथ्म

बाहरी संबंध

• http://www.apfloat.org/ntt.html