हैडामर्ड परिवर्तन

"Walsh transform" redirects here. Not to be confused with Walsh matrix.

बूलियन कार्य और वॉल्श मैट्रिक्स का मैट्रिक्स गुणन इसका वॉल्श स्पेक्ट्रम है:
(1, 0, 1, 0, 0, 1, 1, 0) × एच(8) = (4, 2, 0, −2, 0, 2, 0, 2)

फास्ट वॉल्श-हैडमार्ड परिवर्तन, (1, 0, 1, 0, 0, 1, 1, 0) के वॉल्श स्पेक्ट्रम की गणना करने का एक तेज़ तरीका।

मूल कार्य को इसके वॉल्श स्पेक्ट्रम के माध्यम से अंकगणितीय बहुपद के रूप में व्यक्त किया जा सकता है।

हैडामर्ड परिवर्तन (जिसे वाल्श-हैडामर्ड परिवर्तन, हैडामर्ड-रेडमाकर-वॉल्श परिवर्तन, वॉल्श परिवर्तन या वॉल्श-फूरियर परिवर्तन के रूप में भी जाना जाता है) फूरियर परिवर्तन के सामान्यीकृत वर्ग का एक उदाहरण है। यह 2m वास्तविक संख्याओं (या समष्टि, या हाइपरकॉम्प्लेक्स संख्याओं, चूंकि हैडामर्ड मैट्रिक्स स्वयं पूरी तरह से वास्तविक हैं) पर एक ऑर्थोगोनल, सममित, अव्यवस्थित, रैखिक संचालन करता है।

हैडामर्ड परिवर्तन को माप-2 असतत फूरियर रूपांतरण (डीएफटी) से निर्मित माना जा सकता है, और वास्तव में यह माप के बहुआयामी डीएफटी के समकक्ष है 2 × 2 × ⋯ × 2 × 2. यह वाल्श समारोह के सुपरपोज़िशन में एक एकपक्षीय इनपुट सदिश को विघटित करता है।

इस परिवर्तन का नाम फ्रांस के गणितज्ञ जैक्स हैडामर्ड के नाम पर रखा गया है (French: [adamaʁ]), जर्मन-अमेरिकी गणितज्ञ हंस रेडेमाकर, और अमेरिकी गणितज्ञ जोसेफ एल. वॉल्श।

परिभाषा

हैडामर्ड परिवर्तन Hm एक 2m × 2m मैट्रिक्स है, हैडामर्ड मैट्रिक्स (एक सामान्यीकरण कारक द्वारा स्केल किया गया), जो 2m वास्तविक संख्या xn को 2m वास्तविक संख्या Xk में बदल देता है। हैडामर्ड परिवर्तन को दो तरीकों से परिभाषित किया जा सकता है: पुनरावर्ती रूप से, या सूचकांक n और k के बाइनरी (बेस -2) प्रतिनिधित्व का उपयोग करके।

पुनरावर्ती रूप से, हम 1 × 1 हैडामर्ड रूपांतरण H0 को पहचान H0 = 1 द्वारा परिभाषित करते हैं, और फिर H_m for m > 0 को परिभाषित करते हैं:

$$H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}$$

जहां 1/√2 एक सामान्यीकरण है जिसे कभी-कभी छोड़ दिया जाता है।

m > 1 के लिए, Hm को इस प्रकार भी परिभाषित कर सकते हैं:

$$H_{m}=H_{1}\otimes H_{m-1}$$

कहाँ $\otimes$ क्रोनकर उत्पाद का प्रतिनिधित्व करता है। इस प्रकार, इस सामान्यीकरण कारक के अतिरिक्त, हैडामर्ड मैट्रिक्स पूरी तरह से 1 और -1 से बने होते हैं।

समान रूप से, हम हैडामर्ड मैट्रिक्स को इसकी (k,n)-वीं प्रविष्टि द्वारा लिखकर परिभाषित कर सकते हैं

$${\begin{aligned}k&=\sum _{i=0}^{m-1}{k_{i}2^{i}}=k_{m-1}2^{m-1}+k_{m-2}2^{m-2}+\dots +k_{1}2+k_{0}\\n&=\sum _{i=0}^{m-1}{n_{i}2^{i}}=n_{m-1}2^{m-1}+n_{m-2}2^{m-2}+\dots +n_{1}2+n_{0}\end{aligned}}$$

जहां के_j और n_j क्रमशः k और n के बिट तत्व (0 या 1) हैं। ध्यान दें कि ऊपरी बाएँ कोने में तत्व के लिए, हम परिभाषित करते हैं: $k=n=0$. इस स्थितियों में, हमारे पास है:

$$(H_{m})_{k,n}={\frac {1}{2^{m/2}}}(-1)^{\sum _{j}k_{j}n_{j}}$$

यह बिल्कुल बहुआयामी है ${\textstyle 2\times 2\times \cdots \times 2\times 2}$ यदि इनपुट और आउटपुट को n द्वारा अनुक्रमित बहुआयामी सरणियों के रूप में माना जाता है, तो DFT को एकात्मक प्रचालक के रूप में सामान्यीकृत किया जाता है_j और के_j, क्रमश।

हैडामर्ड मैट्रिसेस के कुछ उदाहरण इस प्रकार हैं।

कहाँ $i\cdot j$ संख्याओं i और j के द्विआधारी निरूपण का बिटवाइज़ डॉट उत्पाद है। उदाहरण के लिए, यदि ${\textstyle n\;\geq \;2}$, तब

$$(H_{n})_{3,2}\;=\;(-1)^{3\cdot 2}\;=\;(-1)^{(1,1)\cdot (1,0)}\;=\;(-1)^{1+0}\;=\;(-1)^{1}\;=\;-1$$

उपरोक्त से सहमत (समग्र स्थिरांक की अनदेखी)। ध्यान दें कि मैट्रिक्स की पहली पंक्ति, पहला कॉलम तत्व द्वारा दर्शाया गया है ${\textstyle (H_{n})_{0,0}}$.

H₁ बिल्कुल माप-2 DFT है। इसे 'Z'/(2) के दो-तत्व योगात्मक समूह पर फूरियर रूपांतरण के रूप में भी माना जा सकता है।

हैडामर्ड मैट्रिसेस की पंक्तियाँ वॉल्श कार्य हैं।

वॉल्श-हैडमार्ड परिवर्तन के लाभ

वास्तविक

मैट्रिक्स H की उपरोक्त परिभाषा के अनुसार, यहां हम H = H[m,n] देते हैं

$$H[m,n]={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}$$

वॉल्श परिवर्तन में, मैट्रिक्स में केवल 1 और −1 दिखाई देंगे। संख्याएँ 1 और −1 वास्तविक संख्याएँ हैं इसलिए समष्टि संख्या गणना करने की कोई आवश्यकता नहीं है।

कोई गुणा आवश्यक नहीं है

DFT को अतार्किक गुणन की आवश्यकता है, जबकि हैडामर्ड परिवर्तन को नहीं। यहाँ तक कि तर्कसंगत गुणन की भी आवश्यकता नहीं है, क्योंकि केवल संकेत फ़्लिप की ही आवश्यकता होती है।

कुछ गुण डीएफटी के समान हैं

वॉल्श परिवर्तन मैट्रिक्स में, पहली पंक्ति (और कॉलम) में सभी प्रविष्टियाँ 1 के समकक्ष हैं।

$$H[m,n]=\left({\begin{array}{rrrrrrrr}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&-1&-1&1&-1&1&1&-1\\1&-1&1&-1&-1&1&-1&1\\1&-1&1&-1&1&-1&1&-1\end{array}}\right)$$

असतत फूरियर रूपांतरण：

$$e^{-j2\pi mn/N}$$

असतत फूरियर रूपांतरण में, जब m शून्य (अर्थ पहली पंक्ति) के समकक्ष होता है, तो DFT का परिणाम भी 1 होता है।

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

यदि हम शून्य क्रॉसिंग की गणना करते हैं:

पहली पंक्ति = 0 शून्य क्रॉसिंग
दूसरी पंक्ति = 1 शून्य क्रॉसिंग
तीसरी पंक्ति = 2 शून्य क्रॉसिंग
           ⋮
आठवीं पंक्ति = 7 शून्य क्रॉसिंग

फूरियर रूपांतरण से संबंध

हैडामर्ड परिवर्तन वास्तव में माप के बहुआयामी डीएफटी के समकक्ष है 2 × 2 × ⋯ × 2 × 2.

एक अन्य दृष्टिकोण हैडामर्ड परिवर्तन को बूलियन समूह पर फूरियर परिवर्तन के रूप में देखना है $(\mathbb {Z} /2\mathbb {Z} )^{n}$. परिमित समूहों पर फूरियर रूपांतरण का उपयोग करना | परिमित (एबेलियन) समूहों पर फूरियर रूपांतरण, एक कार्य का फूरियर रूपांतरण $f\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C}$ कार्य है ${\widehat {f}}$ द्वारा परिभाषित

$${\widehat {f}}(\chi )=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a){\bar {\chi }}(a)$$

कहाँ $\chi$ का एक चरित्र (गणित) है $(\mathbb {Z} /2\mathbb {Z} )^{n}$. प्रत्येक अक्षर का एक रूप होता है $\chi _{r}(a)=(-1)^{a\cdot r}$ कुछ के लिए $r\in (\mathbb {Z} /2\mathbb {Z} )^{n}$, जहां गुणन बिट स्ट्रिंग्स पर बूलियन डॉट उत्पाद है, इसलिए हम इनपुट की पहचान कर सकते हैं ${\widehat {f}}$ साथ $r\in (\mathbb {Z} /2\mathbb {Z} )^{n}$ (पोंट्रीगिन द्वंद्व) और परिभाषित करें ${\widehat {f}}\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C}$ द्वारा

$${\widehat {f}}(r)=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a)(-1)^{r\cdot a}$$

यह हैडामर्ड रूपांतरण है $f$, इनपुट पर विचार करते हुए $f$ और ${\widehat {f}}$ बूलियन स्ट्रिंग के रूप में.

उपरोक्त सूत्रीकरण के संदर्भ में जहां हैडामर्ड परिवर्तन एक सदिश को गुणा करता है $2^{n}$ समष्टि आंकड़े $v$ बाईं ओर हैडामर्ड मैट्रिक्स द्वारा $H_{n}$ लेकर समतुल्यता देखी जाती है $f$ किसी तत्व के सूचकांक के अनुरूप बिट स्ट्रिंग को इनपुट के रूप में लेना $v$, और होना $f$ के संगत तत्व को आउटपुट करें $v$.

इसकी तुलना सामान्य असतत फूरियर रूपांतरण से करें, जिसे एक सदिश पर प्रयुक्त किया जाता है $v$ का $2^{n}$ समष्टि संख्याएँ के अतिरिक्त चक्रीय समूह के वर्णों का उपयोग करती हैं $\mathbb {Z} /2^{n}\mathbb {Z}$.

कम्प्यूटेशनल समष्टिता

शास्त्रीय क्षेत्र में, हैडमार्ड परिवर्तन की गणना की जा सकती है $n\log n$ संचालन ($n=2^{m}$), तेजी से हैडामर्ड परिवर्तन एल्गोरिदम का उपयोग करना।

क्वांटम डोमेन में, हैडमार्ड परिवर्तन की गणना की जा सकती है $O(1)$ समय, क्योंकि यह एक क्वांटम लॉजिक गेट है जो क्वांटम लॉजिक गेट समानांतर गेट हो सकता है।

क्वांटम कम्प्यूटिंग अनुप्रयोग

हेडमार्ड परिवर्तन का उपयोग क्वांटम कंप्यूटिंग में बड़े पैमाने पर किया जाता है। 2×2 हैडामार्ड रूपांतरित होता है $H_{1}$ क्वांटम लॉजिक गेट हैडामर्ड गेट के रूप में जाना जाता है, और समानांतर में n-क्विबिट रजिस्टर के प्रत्येक क्यूबिट के लिए हैडामर्ड गेट का अनुप्रयोग हैडामर्ड परिवर्तन के समकक्ष है। $H_{n}$.

हैडमार्ड गेट

Further information: क्वांटम गेट § हैडमर्ड गेट

क्वांटम कंप्यूटिंग में, हैडामर्ड गेट एक-क्विबिट वर्तन है, जो क्विबिट-आधार राज्यों को मैप करता है $|0\rangle$ और $|1\rangle$ कम्प्यूटेशनल बेसिस (रैखिक बीजगणित) राज्यों के समकक्ष वजन वाले दो सुपरपोजिशन राज्यों में $|0\rangle$ और $|1\rangle$. सामान्यतः चरणों को इसलिए चुना जाता है

$$H={\frac {|0\rangle +|1\rangle }{\sqrt {2}}}\langle 0|+{\frac {|0\rangle -|1\rangle }{\sqrt {2}}}\langle 1|$$

डिराक संकेतन में. यह परिवर्तन मैट्रिक्स से मेल खाता है

$$H_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}$$

में $|0\rangle ,|1\rangle$ आधार, जिसे कम्प्यूटेशनल आधार भी कहा जाता है। राज्य ${\textstyle {\frac {\left|0\right\rangle +\left|1\right\rangle }{\sqrt {2}}}}$ और ${\textstyle {\frac {\left|0\right\rangle -\left|1\right\rangle }{\sqrt {2}}}}$ के रूप में जाने जाते हैं $\left|{\boldsymbol {+}}\right\rangle$ और $\left|{\boldsymbol {-}}\right\rangle$ क्रमशः, और साथ में क्वांटम कंप्यूटिंग में ध्रुवीय आधार का गठन करते हैं।

हैडमर्ड गेट संचालन

$${\begin{aligned}H(|0\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle =:|+\rangle \\H(|1\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle =:|-\rangle \\H(|+\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}+{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|0\rangle \\H(|-\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}-{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|1\rangle \end{aligned}}$$

हैडामर्ड गेट का 0 या 1 क्वबिट पर एक अनुप्रयोग एक क्वांटम स्थिति उत्पन्न करेगा, जो यदि देखा जाए, तो समान संभावना के साथ 0 या 1 होगा (जैसा कि पहले दो संचालनो में देखा गया है)। यह बिल्कुल मानक संभाव्य ट्यूरिंग मशीन में सिक्का उछालने जैसा है। चूंकि, यदि हैडामर्ड गेट को लगातार दो बार प्रयुक्त किया जाता है (जैसा कि पिछले दो संचालनो में प्रभावी ढंग से किया जा रहा है), तो अंतिम स्थिति सदैव प्रारंभिक स्थिति के समान होती है।

हैडामर्ड क्वांटम एल्गोरिथ्म में परिवर्तन

क्वांटम हैडामर्ड परिवर्तन की गणना करना हैडामर्ड परिवर्तन की टेंसर उत्पाद संरचना के कारण व्यक्तिगत रूप से प्रत्येक क्विबिट के लिए हैडामर्ड गेट का अनुप्रयोग है। इस सरल परिणाम का अर्थ है कि क्वांटम हैडामर्ड परिवर्तन को n लॉग n परिचालन के शास्त्रीय स्थितियों की तुलना में लॉग n परिचालन की आवश्यकता होती है।

कई क्वांटम एल्गोरिदम प्रारंभिक चरण के रूप में हैडामर्ड परिवर्तन का उपयोग करते हैं, क्योंकि यह आरंभिक रूप से m क्यूबिट को मैप करता है $|0\rangle$ सभी 2^m के सुपरपोजिशन के लिए ओर्थोगोनल अवस्थाएँ $|0\rangle ,|1\rangle$ समान वजन के साथ आधार. उदाहरण के लिए, इसका उपयोग डॉयचे-जोज़सा एल्गोरिदम, साइमन के एल्गोरिदम, बर्नस्टीन-वज़ीरानी एल्गोरिदम और ग्रोवर के एल्गोरिदम में किया जाता है। ध्यान दें कि रव का एल्गोरिदम प्रारंभिक हैडामर्ड परिवर्तन के साथ-साथ क्वांटम फूरियर रूपांतरण दोनों का उपयोग करता है, जो परिमित समूहों पर दोनों प्रकार के फूरियर परिवर्तन हैं; सबसे पहले $(\mathbb {Z} /2\mathbb {Z} )^{n}$ और दूसरा प्रारंभ $\mathbb {Z} /2^{n}\mathbb {Z}$.

आण्विक फ़ाइलोजेनेटिक वृक्षविकासवादी जीव विज्ञान) अनुप्रयोग

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

फ़ाइलोजेनेटिक हैडामर्ड परिवर्तन की यांत्रिकी में सदिश की गणना सम्मलित होती है $\gamma (T)$ जो ट्री के लिए टोपोलॉजी और शाखा की लंबाई के बारे में जानकारी प्रदान करता है $T$ साइट पैटर्न सदिश या मैट्रिक्स का उपयोग करना $s(T)$.

$$\gamma (T)=H^{-1}(\ln(Hs(T)))$$

कहाँ $H$ उचित माप का हैडामर्ड मैट्रिक्स है। इसकी व्याख्या को सरल बनाने के लिए इस समीकरण को तीन समीकरणों की श्रृंखला के रूप में पुनः लिखा जा सकता है:

$${\begin{aligned}r&=Hs(T)\\\rho &=\ln r\\\gamma (T)&=H^{-1}\rho \end{aligned}}$$

इस समीकरण की व्युत्क्रमणीय प्रकृति किसी को अपेक्षित साइट पैटर्न सदिश (या मैट्रिक्स) की गणना निम्नानुसार करने की अनुमति देती है:

$$s(T)=H^{-1}(\exp(H\gamma (T)))$$

हम न्यूक्लियोटाइड को बाइनरी स्वरूप के रूप में एन्कोड करके DNA के लिए कैवेंडर-फैरिस-जेरज़ी नेमैन (सीएफएन) दो-राज्य प्रतिस्थापन मॉडल का उपयोग कर सकते हैं (प्यूरीन ए और जी को आर के रूप में एन्कोड किया गया है और पाइरीमिडीन सी और टी को वाई के रूप में एन्कोड किया गया है)। इससे साइट पैटर्न सदिश के रूप में एकाधिक अनुक्रम संरेखण को एन्कोड करना संभव हो जाता है $s(T)$ जिसे ट्री सदिश में बदला जा सकता है $\gamma (T)$, जैसा कि निम्नलिखित उदाहरण में दिखाया गया है:

एक विशिष्ट ट्री के लिए हैडामर्ड परिवर्तन दिखाने वाला उदाहरण (वाडेल एट अल से अनुकूलित कार्य उदाहरण के लिए मान। 1997))

अनुक्रमणिका	बाइनरी पैटर्न	संरेखण पैटर्न	$\gamma (T)$	$\rho =H^{-1}\gamma (T)$	$r=\exp(\rho )$	$s(T)=H^{-1}\rho$
0	0000	RRRR and YYYY	−0.475	0	1	0.6479
1	0001	RRRY and YYYR	0.2	−0.5	0.6065	0.1283
2	0010	RRYR and YYRY	0.025	−0.15	0.8607	0.02
3*	0011	RRYY and YYRR	0.025	−0.45	0.6376	0.0226
4	0100	RYRR and YRYY	0.2	−0.45	0.6376	0.1283
5*	0101	RYRY and YRYR	0	−0.85	0.4274	0.0258
6*	0110	RYYR and YRRY	0	−0.5	0.6065	0.0070
7	0111	RYYY and YRRR	0.025	−0.9	0.4066	0.02

इस तालिका में दिखाया गया उदाहरण सरलीकृत तीन समीकरण योजना का उपयोग करता है और यह चार टैक्सोन ट्री के लिए है जिसे ((A,B),(C,D)) के रूप में लिखा जा सकता है; न्यूविक प्रारूप में। साइट पैटर्न ABCD क्रम में लिखे गए हैं। इस विशेष ट्री की दो दीर्घ टर्मिनल शाखाएँ (प्रति साइट 0.2 अनुप्रस्थ प्रतिस्थापन), दो छोटी टर्मिनल शाखाएँ (प्रति साइट 0.025 अनुप्रस्थ प्रतिस्थापन), और लघु आंतरिक शाखा (प्रति साइट 0.025 अनुप्रस्थ प्रतिस्थापन) हैं; इस प्रकार, इसे ((A:0.025,B:0.2):0.025,(C:0.025,D:0.2)) के रूप में लिखा जाएगा; न्यूविक प्रारूप में। यदि अधिकतम पारसीमोनी (फ़ाइलोजेनेटिक्स) मानदंड का उपयोग करके डेटा का विश्लेषण किया जाता है तो यह ट्री दीर्घ शाखा आकर्षण प्रदर्शित करेगा (यह मानते हुए कि विश्लेषण किया गया अनुक्रम प्रेक्षित साइट पैटर्न आवृत्तियों के लिए पर्याप्त लंबा है जो दिखाए गए अपेक्षित आवृत्तियों के करीब है) $s(T)=H^{-1}\rho$ कॉलम)। दीर्घ शाखा का आकर्षण इस तथ्य को दर्शाता है कि सूचकांक 6 के साथ साइट पैटर्न की अपेक्षित संख्या - जो ट्री का समर्थन करती है ((A,C),(B,D)); -- सच्चे ट्री (सूचकांक 4) का समर्थन करने वाले साइट पैटर्न की अपेक्षित संख्या से अधिक। जाहिर है, फाइलोजेनेटिक हैडामर्ड परिवर्तन की उलटी प्रकृति का अर्थ है कि ट्री सदिश का अर्थ है कि ट्री सदिश $\gamma (T)$ सही ट्री से मेल खाता है. परिवर्तन के बाद पारसीमोनी विश्लेषण इसलिए सुसंगत अनुमानक है, जैसा कि सही मॉडल (इस स्थितियों में CFN मॉडल) का उपयोग करके एक मानक अधिकतम संभावना विश्लेषण होगा।

ध्यान दें कि 0 वाला साइट पैटर्न उन साइटों से मेल खाता है जो नहीं बदले हैं (न्यूक्लियोटाइड्स को प्यूरीन या पाइरीमिडीन के रूप में एन्कोड करने के बाद)। तारांकन (3, 5, और 6) वाले सूचकांक पारसीमोनी-जानकारीपूर्ण हैं, और। शेष सूचकांक साइट पैटर्न का प्रतिनिधित्व करते हैं जहां एक एकल टैक्सोन अन्य तीन टैक्सों से भिन्न होता है (इसलिए वे एक मानक अधिकतम संभावना फ़ाइलोजेनेटिक ट्री में टर्मिनल शाखा की लंबाई के समकक्ष हैं)।

यदि कोई न्यूक्लियोटाइड डेटा को आर और वाई (और अंततः 0 और 1 के रूप में) के रूप में रिकोड किए बिना उपयोग करना चाहता है, तो साइट पैटर्न को मैट्रिक्स के रूप में एनकोड करना संभव है। यदि हम चार-टैक्सन वृक्ष पर विचार करें तो कुल 256 साइट पैटर्न (चौथी शक्ति के चार न्यूक्लियोटाइड) हैं। चूंकि, डीएनए विकास के मॉडल की समरूपता | किमुरा तीन-पैरामीटर (या K81) मॉडल हमें डीएनए के लिए 256 संभावित साइट पैटर्न को 64 पैटर्न तक कम करने की अनुमति देता है, जिससे चार-टैक्सन ट्री के लिए न्यूक्लियोटाइड डेटा को एनकोड करना संभव हो जाता है। 8 × 8 मैट्रिक्स ट्रांसवर्जन (आरवाई) साइट पैटर्न के लिए ऊपर उपयोग किए गए 8 तत्वों के सदिश के समान। यह क्लेन चार-समूह का उपयोग करके डेटा को रीकोड करके पूरा किया जाता है:

फ़ाइलोजेनेटिक हैडामर्ड परिवर्तन के लिए क्लेन चार-समूह कोडिंग

न्यूक्लियोटाइड 1	न्यूक्लियोटाइड 2	न्यूक्लियोटाइड 3	न्यूक्लियोटाइड 4
A (0,0)	G (1,0)	C (0,1)	T (1,1)
C (0,0)	T (1,0)	A (0,1)	G (1,1)
G (0,0)	A (1,0)	T (0,1)	C (1,1)
T (0,0)	C (1,0)	G (0,1)	A (1,1)

RY डेटा की तरह, साइट पैटर्न को मनमाने ढंग से चुने गए पहले टैक्सन में आधार के सापेक्ष अनुक्रमित किया जाता है, जिसके बाद उस पहले आधार के सापेक्ष एन्कोडेड टैक्सा में आधार होते हैं। इस प्रकार, पहला टैक्सन बिट जोड़ी (0,0) प्राप्त करता है। उन बिट युग्मों का उपयोग करके कोई व्यक्ति RY सदिश के समान दो सदिश उत्पन्न कर सकता है और फिर उन सदिश का उपयोग करके मैट्रिक्स को पॉप्युलेट कर सकता है। इसे हेंडी एट अल के उदाहरण का उपयोग करके चित्रित किया जा सकता है। (1994), जो चार प्राइमेट हीमोग्लोबिन स्यूडोजेन के एकाधिक अनुक्रम संरेखण पर आधारित है:

एन्कोडेड अनुक्रम संरेखण का उदाहरण (हेंडी एट अल. 1994 से)। ) (मान 9879 साइटों में से गिने जाते हैं)

	0	8	16	24	32	40	48	56
0	8988	9	10	12	24			90
1	41	9		**
2	45		13
3	54*			14				3
4	94				20
5			1
6	2				2
7	356		1		1			75

कॉलम 0 में साइट पैटर्न की बहुत बड़ी संख्या इस तथ्य को दर्शाती है कि कॉलम 0 संक्रमण (आनुवांशिकी) अंतर से मेल खाता है, जो जीनोमिक क्षेत्रों की लगभग सभी तुलनाओं में अनुप्रस्थ अंतर की तुलना में अधिक तेजी से जमा होता है (और निश्चित रूप से उपयोग किए जाने वाले हीमोग्लोबिन स्यूडोजेन में अधिक तेजी से जमा होता है) यह उदाहरण काम आया ). यदि हम साइट पैटर्न AAGG पर विचार करते हैं तो यह क्लेन समूह बिट जोड़ी के दूसरे तत्व के लिए बाइनरी पैटर्न 0000 और पहले तत्व के लिए 0011 होगा। इस स्थितियों में पहले तत्व पर आधारित बाइनरी पैटर्न पहला तत्व सूचकांक 3 से मेल खाता है (इसलिए कॉलम 0 में पंक्ति 3; तालिका में एकल तारांकन के साथ दर्शाया गया है)। साइट पैटर्न GGAA, CCTT, और TTCC को बिल्कुल उसी तरह से एन्कोड किया जाएगा। साइट पैटर्न AACT को दूसरे तत्व के आधार पर बाइनरी पैटर्न 0011 और पहले तत्व के आधार पर 0001 के साथ एन्कोड किया जाएगा; इससे पहले तत्व के लिए सूचकांक 1 और दूसरे के लिए सूचकांक 3 प्राप्त होता है। दूसरे क्लेन समूह बिट जोड़ी पर आधारित सूचकांक को कॉलम इंडेक्स प्राप्त करने के लिए 8 से गुणा किया जाता है (इस स्थितियों में यह कॉलम 24 होगा) वह सेल जिसमें AACT साइट पैटर्न की गिनती सम्मलित होगी, दो तारांकन के साथ इंगित किया गया है; चूंकि, उदाहरण में किसी संख्या की अनुपस्थिति इंगित करती है कि अनुक्रम संरेखण में कोई AACT साइट पैटर्न सम्मलित नहीं है (इसी तरह, CCAG, GGTC, और TTGA साइट पैटर्न, जो उसी तरह से एन्कोड किए जाएंगे, अनुपस्थित हैं)।

अन्य अनुप्रयोग

हैडामर्ड परिवर्तन का उपयोग डेटा एन्क्रिप्शन के साथ-साथ कई संकेत आगे बढ़ाना और डेटा संपीड़न एल्गोरिदम, जैसे JPEG XR और H.264/MPEG-4 AVC|MPEG-4 AVC में भी किया जाता है। वीडियो संपीड़न अनुप्रयोगों में, इसका उपयोग सामान्यतः पूर्ण रूपांतरित अंतरों के योग के रूप में किया जाता है। यह क्वांटम कंप्यूटिंग में महत्वपूर्ण संख्या में एल्गोरिदम का भी महत्वपूर्ण हिस्सा है। हैडामर्ड परिवर्तन को NMR, मास स्पेक्ट्रोमेट्री और क्रिस्टलोग्राफी जैसी प्रायोगिक तकनीकों में भी प्रयुक्त किया जाता है। छद्म-यादृच्छिक मैट्रिक्स वर्तन प्राप्त करने के लिए, स्थानीय-संवेदनशील हैशिंग के कुछ संस्करणों में इसका अतिरिक्त उपयोग किया जाता है।

यह भी देखें

• फास्ट वॉल्श-हैडमार्ड परिवर्तन
• छद्म-हैडामर्ड परिवर्तन
• हार परिवर्तन
• सामान्यीकृत वितरणात्मक कानून

बाहरी संबंध

• Ritter, Terry (August 1996). "Walsh–Hadamard Transforms: A Literature Survey".
• Akansu, A.N.; Poluri, R. (July 2007). "Walsh-Like Nonlinear Phase Orthogonal Codes for Direct Sequence CDMA Communications" (PDF). IEEE Transactions on Signal Processing. 55 (7): 3800–6. Bibcode:2007ITSP...55.3800A. doi:10.1109/TSP.2007.894229. S2CID 6830633.
• Pan, Jeng-shyang Data Encryption Method Using Discrete Fractional Hadamard Transformation (May 28, 2009)
• Lachowicz, Dr. Pawel. Walsh–Hadamard Transform and Tests for Randomness of Financial Return-Series (April 7, 2015)
• Beddard, Godfrey; Yorke, Briony A. (January 2011). "Pump-probe Spectroscopy using Hadamard Transforms" (PDF).
• Yorke, Briony A.; Beddard, Godfrey; Owen, Robin L.; Pearson, Arwen R. (September 2014). "Time-resolved crystallography using the Hadamard transform". Nature Methods. 11 (11): 1131–1134. doi:10.1038/nmeth.3139. PMC 4216935. PMID 25282611.

संदर्भ