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

गणित में, एक रिंग के ऊपर असतत फूरियर रूपांतरण एक फ़ंक्शन के असतत फूरियर ट्रांसफॉर्म (डीएफटी) को सामान्यीकृत करता है, जिसके मान आमतौर पर एक मनमानी रिंग (गणित) पर जटिल संख्याएं होते हैं।

परिभाषा

होने देना $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}}$

असतत फूरियर मानचित्रों को n-tuple|n-tuple रूपांतरित करता है $(v_{0},\ldots ,v_{n-1})$ के तत्वों का $R$ दूसरे एन-ट्यूपल के लिए $(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$ एकता की एक आदिम जड़ के रूप में, जो शर्त (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$ का गुणनात्मक व्युत्क्रम है $n$ में $R$ (यदि यह व्युत्क्रम मौजूद नहीं है, तो डीएफटी को उलटा नहीं किया जा सकता है)।

प्रमाण: (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}$ केवल बहुपद का मान है $p_{v}(x)$ के लिए $x=\alpha ^{k}$, अर्थात।,

$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}.$

जटिल संख्याओं पर, स्केलर कारक का उपयोग करके डीएफटी और व्युत्क्रम डीएफटी के लिए सूत्रों को सामान्य करना अक्सर प्रथागत होता है ${\frac {1}{\sqrt {n}}}$ दोनों सूत्रों में, बजाय $1$ डीएफटी के सूत्र में और ${\frac {1}{n}}$ व्युत्क्रम DFT के सूत्र में. इस सामान्यीकरण के साथ, डीएफटी मैट्रिक्स तब एकात्मक होता है। ध्यान दें कि ${\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एकता की जड़ें जब भी मौजूद होती हैं n बांटता है $p-1$, तो हमारे पास $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) एक समग्र मापांक का उपयोग करें।

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

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

गुण

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

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

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

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

यह भी देखें

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

बाहरी संबंध

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