वृत्ताकार परिवर्तन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 8: Line 8:
  | footer = [[Permutation matrix|Matrices]] of 8-element circular shifts to the left and right
  | footer = [[Permutation matrix|Matrices]] of 8-element circular shifts to the left and right
}}
}}
[[साहचर्य]] गणित में, सर्कुलर शिफ्ट टुपल में प्रविष्टियों को पुनर्व्यवस्थित करने का ऑपरेशन है, या तो अंतिम प्रविष्टि को पहले स्थान पर ले जाकर, जबकि अन्य सभी प्रविष्टियों को अगले स्थान पर स्थानांतरित करके, या उलटा ऑपरेशन करके। वृत्ताकार बदलाव विशेष प्रकार का [[चक्रीय क्रम[[परिवर्तन]]]] है, जो बदले में विशेष प्रकार का क्रमपरिवर्तन है। औपचारिक रूप से, गोलाकार बदलाव टुपल में ''एन'' प्रविष्टियों का क्रमपरिवर्तन है जैसे कि या तो
[[साहचर्य]] गणित में, '''वृत्ताकार परिवर्तन''' टुपल में प्रविष्टियों को पुनर्व्यवस्थित करने का ऑपरेशन है, या तो अंतिम प्रविष्टि को पहले समिष्ट पर ले जाकर, जबकि अन्य सभी प्रविष्टियों को अगले समिष्ट पर स्थानांतरित करके, या प्रतिलोम ऑपरेशन करके प्राप्त करते है। वृत्ताकार परिवर्तन विशेष प्रकार का चक्रीय क्रम[[परिवर्तन]] है, जो बदले में विशेष प्रकार का क्रमपरिवर्तन है। औपचारिक रूप से, गोलाकार परिवर्तन टुपल में ''n'' प्रविष्टियों का क्रमपरिवर्तन है जैसे कि या तो
:<math>\sigma(i)\equiv (i+1)</math> [[मॉड्यूलर अंकगणित]] n, सभी प्रविष्टियों के लिए i = 1, ..., n
:<math>\sigma(i)\equiv (i+1)</math> [[मॉड्यूलर अंकगणित]] n, सभी प्रविष्टियों के लिए i = 1, ..., n
या
या
:<math>\sigma(i)\equiv (i-1)</math> मॉड्यूलर अंकगणित n, सभी प्रविष्टियों के लिए i = 1, ..., n।
:<math>\sigma(i)\equiv (i-1)</math> मॉड्यूलर अंकगणित n, सभी प्रविष्टियों के लिए i = 1, ..., n।


किसी दिए गए टुपल में बार-बार वृत्ताकार बदलाव लागू करने के परिणाम को ट्यूपल का 'वृत्ताकार बदलाव' भी कहा जाता है।
किसी दिए गए टुपल में बार-बार वृत्ताकार परिवर्तन प्रयुक्त करने के परिणाम को ट्यूपल का 'वृत्ताकार परिवर्तन' भी कहा जाता है।


उदाहरण के लिए, चार-टुपल (ए, बी, सी, डी) में बार-बार गोलाकार बदलाव लगाने से क्रमिक रूप से लाभ मिलता है
उदाहरण के लिए, चार-टुपल (''a'', ''b'', ''c'', ''d'') में बार-बार गोलाकार परिवर्तन लगाने से क्रमिक रूप से लाभ मिलता है
* (डी, ए, बी, सी),
* (''d'', ''a'', ''b'', ''c''),
* (सी, डी, ए, बी),
* (''c'', ''d'', ''a'', ''b''),
* (बी, सी, डी, ए),
* (''b'', ''c'', ''d'', ''a''),
* (ए, बी, सी, डी) (मूल चार-ट्यूपल),
* (''a'', ''b'', ''c'', ''d'') (मूल चार-ट्यूपल),
और फिर क्रम दोहराता है; इसलिए इस चार-टुपल में चार अलग-अलग गोलाकार बदलाव हैं। हालाँकि, सभी n-टुपल्स में n विशिष्ट वृत्ताकार बदलाव नहीं होते हैं। उदाहरण के लिए, 4-ट्यूपल (ए, बी, ए, बी) में केवल 2 अलग-अलग गोलाकार बदलाव हैं। n-ट्यूपल की अलग-अलग गोलाकार पारियों की संख्या है <math>\frac{n}{k}</math>, कहाँ {{mvar|k}} का [[भाजक]] है {{mvar|n}}, सभी उप-पैटर्न पर दोहराव की अधिकतम संख्या को दर्शाता है।
और फिर क्रम दोहराता है; इसलिए इस चार-टुपल में चार अलग-अलग गोलाकार परिवर्तन हैं। चूँकि, सभी n-टुपल्स में n विशिष्ट वृत्ताकार परिवर्तन नहीं होते हैं। उदाहरण के लिए, 4-ट्यूपल (a, b, a, b) में केवल 2 अलग-अलग गोलाकार परिवर्तन हैं। n-ट्यूपल की अलग-अलग गोलाकार परिवर्तन <math>\frac{n}{k}</math> की संख्या है , जहां {{mvar|k}} का [[भाजक]] है {{mvar|n}}, सभी उप-पैटर्न पर दोहराव की अधिकतम संख्या को दर्शाता है।


[[कंप्यूटर प्रोग्रामिंग]] में, [[बिटवाइज़ रोटेशन]], जिसे सर्कुलर शिफ्ट के रूप में भी जाना जाता है, बिटवाइज़ ऑपरेशन है जो इसके ऑपरेंड के सभी बिट्स को शिफ्ट करता है। [[अंकगणितीय बदलाव]] के विपरीत, गोलाकार बदलाव किसी संख्या के साइन बिट को संरक्षित नहीं करता है या [[चल बिन्दु संख्या]] के घातांक को उसके [[महत्व]] से अलग नहीं करता है। [[तार्किक बदलाव]] के विपरीत, रिक्त बिट स्थिति शून्य से नहीं भरी जाती है, बल्कि अनुक्रम से बाहर स्थानांतरित बिट्स से भरी जाती है।
[[कंप्यूटर प्रोग्रामिंग]] में, [[बिटवाइज़ रोटेशन]], जिसे वृत्ताकार परिवर्तन के रूप में भी जाना जाता है, बिटवाइज़ ऑपरेशन है जो इसके ऑपरेंड के सभी बिट्स को परिवर्तन करता है। इस प्रकार [[अंकगणितीय बदलाव|अंकगणितीय परिवर्तन]] के विपरीत, गोलाकार परिवर्तन किसी संख्या के साइन बिट को संरक्षित नहीं करता है या [[चल बिन्दु संख्या|फ़्लोटिंग-पॉइंट नंबर]] के घातांक को उसके [[महत्व]] से अलग नहीं करता है। [[तार्किक बदलाव|तार्किक परिवर्तन]] के विपरीत, रिक्त बिट स्थिति शून्य से नहीं भरी जाती है, किन्तु अनुक्रम से बाहर स्थानांतरित बिट्स से भरी जाती है।


== सर्कुलर शिफ्ट लागू करना ==
== वृत्ताकार परिवर्तन प्रयुक्त करना ==


बिट अनुक्रमों को व्यवस्थित करने के लिए [[क्रिप्टोग्राफी]] में अक्सर सर्कुलर शिफ्ट का उपयोग किया जाता है। दुर्भाग्य से, [[सी (प्रोग्रामिंग भाषा)]] सहित कई प्रोग्रामिंग भाषाओं में सर्कुलर शिफ्टिंग के लिए ऑपरेटर या मानक फ़ंक्शन नहीं हैं, भले ही लगभग सभी [[प्रोसेसर]] के पास इसके लिए [[बिटवाइज़ ऑपरेशन]] निर्देश हैं (उदाहरण के लिए [[इंटेल x86]] में आरओएल और आरओआर हैं)।
बिट अनुक्रमों को व्यवस्थित करने के लिए [[क्रिप्टोग्राफी]] में अधिकांशतः वृत्ताकार परिवर्तन का उपयोग किया जाता है। सामान्यतः, [[सी (प्रोग्रामिंग भाषा)]] सहित कई प्रोग्रामिंग भाषाओं में वृत्ताकार शिफ्टिंग के लिए ऑपरेटर या मानक फ़ंक्शन नहीं हैं, तथापि लगभग सभी [[प्रोसेसर]] के पास इसके लिए [[बिटवाइज़ ऑपरेशन]] निर्देश हैं (उदाहरण के लिए [[इंटेल x86]] में आरओएल और आरओआर हैं)। चूँकि, कुछ कंपाइलर [[आंतरिक कार्य]] के माध्यम से प्रोसेसर निर्देशों तक पहुंच प्रदान कर सकते हैं। इसके अतिरिक्त, मानक [[एएनएसआई सी]] कोड में कुछ निर्माणों को कंपाइलर द्वारा सीपीयू पर रोटेट असेंबली भाषा निर्देश के लिए अनुकूलित किया जा सकता है जिसमें ऐसा निर्देश होता है। अधिकांश सी कंपाइलर निम्नलिखित मुहावरे को पहचानते हैं, और इसे एकल 32-बिट रोटेट निर्देश में संकलित करते हैं।<ref>
हालाँकि, कुछ कंपाइलर [[आंतरिक कार्य]]ों के माध्यम से प्रोसेसर निर्देशों तक पहुंच प्रदान कर सकते हैं। इसके अलावा, मानक [[एएनएसआई सी]] कोड में कुछ निर्माणों को कंपाइलर द्वारा सीपीयू पर रोटेट असेंबली भाषा निर्देश के लिए अनुकूलित किया जा सकता है जिसमें ऐसा निर्देश होता है। अधिकांश सी कंपाइलर निम्नलिखित मुहावरे को पहचानते हैं, और इसे एकल 32-बिट रोटेट निर्देश में संकलित करते हैं।<ref>
[https://gcc.gnu.org/ml/gcc-patches/2007-11/msg01112.html GCC: "Optimize common rotate constructs"]
[https://gcc.gnu.org/ml/gcc-patches/2007-11/msg01112.html GCC: "Optimize common rotate constructs"]
</ref><ref>
</ref><ref>
Line 56: Line 55:
}
}
</syntaxhighlight>
</syntaxhighlight>
यह सुरक्षित और संकलक-अनुकूल कार्यान्वयन [[जॉन रेगेहर]] द्वारा विकसित किया गया था,<ref>[http://blog.regehr.org/archives/1063 Safe, Efficient, and Portable Rotate in C/C++]</ref> और इसे पीटर कॉर्डेस द्वारा और अधिक परिष्कृत किया गया।<ref>[https://stackoverflow.com/a/776523/224132 Stackoverflow: Best practices for rotates in C/C++]</ref><ref>[https://stackoverflow.com/a/31488147/224132 Near constant time rotate that does not violate the standards]</ref>
यह सुरक्षित और संकलक-अनुकूल कार्यान्वयन [[जॉन रेगेहर]] द्वारा विकसित किया गया था,<ref>[http://blog.regehr.org/archives/1063 Safe, Efficient, and Portable Rotate in C/C++]</ref> और इसे पीटर कॉर्डेस द्वारा और अधिक परिष्कृत किया गया था।<ref>[https://stackoverflow.com/a/776523/224132 Stackoverflow: Best practices for rotates in C/C++]</ref><ref>[https://stackoverflow.com/a/31488147/224132 Near constant time rotate that does not violate the standards]</ref> एक सरल संस्करण अधिकांशतः देखा जाता है जब <code>count</code> 1 से 31 बिट्स की सीमा तक सीमित है:
एक सरल संस्करण अक्सर देखा जाता है जब <code>count</code> 1 से 31 बिट्स की सीमा तक सीमित है:
<syntaxhighlight lang="C">
<syntaxhighlight lang="C">
uint32_t rotl32 (uint32_t value, unsigned int count) {
uint32_t rotl32 (uint32_t value, unsigned int count) {
Line 63: Line 61:
}
}
</syntaxhighlight>
</syntaxhighlight>
यह संस्करण खतरनाक है क्योंकि यदि <code>count</code> 0 या 32 है, तो यह 32-बिट शिफ्ट के लिए पूछता है, जो सी भाषा मानक में [[अपरिभाषित व्यवहार]] है। हालाँकि, यह वैसे भी काम करता है, क्योंकि अधिकांश माइक्रोप्रोसेसर इसे लागू करते हैं <code>value >> 32</code> या तो 32-बिट शिफ्ट (0 का उत्पादन) या 0-बिट शिफ्ट (मूल का उत्पादन) के रूप में <code>value</code>), और इनमें से कोई भी इस एप्लिकेशन में सही परिणाम देता है।
यह संस्करण खतरनाक है क्योंकि यदि <code>count</code> 0 या 32 है, तो यह 32-बिट परिवर्तन के लिए पूछता है, जो सी भाषा मानक में [[अपरिभाषित व्यवहार]] है। चूँकि, यह वैसे भी कार्य करता है, क्योंकि अधिकांश माइक्रोप्रोसेसर इसे प्रयुक्त करते हैं <code>value >> 32</code> या तो 32-बिट परिवर्तन (0 का उत्पादन) या 0-बिट परिवर्तन (मूल का उत्पादन) के रूप में <code>value</code>), और इनमें से कोई भी इस एप्लिकेशन में सही परिणाम देता है।


==उदाहरण==
==उदाहरण==
यदि बिट अनुक्रम 0001 0111 को बिट स्थिति के गोलाकार बदलाव के अधीन किया गया था... (नीचे चित्र देखें)
यदि बिट अनुक्रम 0001 0111 को बिट स्थिति के गोलाकार परिवर्तन के अधीन किया गया था... (नीचे चित्र देखें)
{|
{|
|
|
* to the left would yield: 0010 1110
* बायीं ओर उत्पन्न होगी: 0010 1110
[[Image:Rotate left.svg|thumb|left|300px|Left circular shift.]]
[[Image:Rotate left.svg|thumb|left|300px|वाम वृत्ताकार परिवर्तन.]]
|
|
* to the right would yield: 1000 1011.
* दांयी ओर उत्पन्न होगी: 1000 1011.
[[Image:Rotate right.svg|thumb|left|300px|Right circular shift.]]
[[Image:Rotate right.svg|thumb|left|300px|वाम वृत्ताकार परिवर्तन.]]
|}
|}
यदि बिट अनुक्रम 1001 0110 को निम्नलिखित परिचालनों के अधीन किया गया था:
यदि बिट अनुक्रम 1001 0110 को निम्नलिखित परिचालनों के अधीन किया गया था:
{| style="float:left;"
{| style="float:left;"
|-  
|-  
| left circular shift by 1 position:
| बायीं ओर वृत्ताकार 1 स्थिति से परिवर्तन:
| 0010 1101 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
| 0010 1101 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
|-  
|-  
| left circular shift by 2 positions:
| बाएं वृत्ताकार में 2 समिष्ट का परिवर्तन:
| 0101 1010
| 0101 1010
|-  
|-  
| left circular shift by 3 positions:
| बाएं वृत्ताकार में 3 समिष्ट का परिवर्तन:
| 1011 0100
| 1011 0100
|-  
|-  
| left circular shift by 4 positions:
| बाएं वृत्ताकार में 4 समिष्ट का परिवर्तन:
| 0110 1001
| 0110 1001
|-  
|-  
| left circular shift by 5 positions:
| बाएं वृत्ताकार में 5 समिष्ट का परिवर्तन:
| 1101 0010
| 1101 0010
|-  
|-  
| left circular shift by 6 positions:
| बाएं वृत्ताकार में 6 समिष्ट का परिवर्तन:
| 1010 0101
| 1010 0101
|-  
|-  
| left circular shift by 7 positions:
| बाएं वृत्ताकार में 7 समिष्ट का परिवर्तन:
| 0100 1011
| 0100 1011
|-  
|-  
| left circular shift by 8 positions:
| बाएं वृत्ताकार में 8 समिष्ट का परिवर्तन:
| 1001 0110
| 1001 0110
|}
|}
Line 105: Line 103:
{| style="float:left;"
{| style="float:left;"
|-  
|-  
| right circular shift by 1 position:
| दांयी ओर वृत्ताकार 1 स्थिति से परिवर्तन:
| 0100 1011
| 0100 1011
|-  
|-  
| right circular shift by 2 positions:
| दांयी वृत्ताकार में 2 समिष्ट का परिवर्तन:
| 1010 0101
| 1010 0101
|-  
|-  
| right circular shift by 3 positions:
| दांयी वृत्ताकार में 3 समिष्ट का परिवर्तन:
| 1101 0010
| 1101 0010
|-  
|-  
| right circular shift by 4 positions:
| दांयी वृत्ताकार में 4 समिष्ट का परिवर्तन:
| 0110 1001
| 0110 1001
|-  
|-  
| right circular shift by 5 positions:
| दांयी वृत्ताकार में 5 समिष्ट का परिवर्तन:
| 1011 0100
| 1011 0100
|-  
|-  
| right circular shift by 6 positions:
| दांयी वृत्ताकार में 6 समिष्ट का परिवर्तन:
| 0101 1010
| 0101 1010
|-  
|-  
| right circular shift by 7 positions:
| दांयी वृत्ताकार में 7 समिष्ट का परिवर्तन:
| 0010 1101
| 0010 1101
|-  
|-  
| right circular shift by 8 positions:
| दांयी वृत्ताकार में 8 समिष्ट का परिवर्तन:
| 1001 0110
| 1001 0110
|}
|}


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


[[चक्रीय कोड]] प्रकार का [[ब्लॉक कोड]] होता है, जिसमें यह गुण होता है कि कोडवर्ड का गोलाकार बदलाव हमेशा और कोडवर्ड उत्पन्न करेगा। यह निम्नलिखित सामान्य परिभाषा को प्रेरित करता है: वर्णमाला Σ पर [[स्ट्रिंग (कंप्यूटर विज्ञान)]] के लिए, शिफ्ट (ओं) को एस के परिपत्र शिफ्ट के [[सेट (गणित)]] को निरूपित करें,
और स्ट्रिंग्स के सेट L के लिए, शिफ्ट (L) को L में स्ट्रिंग्स के सभी गोलाकार शिफ्टों के सेट को निरूपित करें। यदि L चक्रीय कोड है, तो शिफ्ट (L) ⊆ L; L के [[चक्रीय भाषा]] होने के लिए यह आवश्यक शर्त है। [[औपचारिक भाषा सिद्धांत]] में ऑपरेशन शिफ्ट (एल) का अध्ययन किया गया है। उदाहरण के लिए, यदि L [[संदर्भ-मुक्त भाषा]] है, तो शिफ्ट(L) फिर से संदर्भ-मुक्त है।<ref>T. Oshiba, "Closure property of the family of context-free languages under the cyclic shift operation", Transactions of IECE, '''55D''':119–122, 1972.
</ref><ref>A. N. Maslov, "Cyclic shift operation for languages", Problems of Information Transmission '''9''':333–338, 1973.</ref> इसके अलावा, यदि एल को लंबाई एन की [[नियमित अभिव्यक्ति]] द्वारा वर्णित किया गया है, तो लंबाई [[ बिग ओ अंकन |बिग ओ अंकन]] (एन) की नियमित अभिव्यक्ति है<sup>3</sup>) शिफ्ट (एल) का वर्णन।<ref>{{cite journal | zbl=1176.68105 | last1=Gruber | first1=Hermann | last2=Holzer | first2=Markus | title=बहुपद आकार की नियमित अभिव्यक्तियों के साथ भाषा संचालन| url=http://www.hermann-gruber.com/data/derivatives-journal.pdf | journal=Theoretical Computer Science | volume=410 | number=35 | pages=3281–3289 | year=2009 | doi=10.1016/j.tcs.2009.04.009 | access-date=2012-09-06 | archive-url=https://web.archive.org/web/20170829023123/http://hermann-gruber.com/data/derivatives-journal.pdf | archive-date=2017-08-29 | url-status=dead | doi-access=free }}.</ref>




== अनुप्रयोग ==
[[चक्रीय कोड]] प्रकार का [[ब्लॉक कोड]] होता है, जिसमें यह गुण होता है कि कोडवर्ड का गोलाकार परिवर्तन सदैव और कोडवर्ड उत्पन्न करता है। यह निम्नलिखित सामान्य परिभाषा को प्रेरित करता है: इस प्रकार वर्णमाला Σ पर [[स्ट्रिंग (कंप्यूटर विज्ञान)]] के लिए, परिवर्तन (o) को एस के परिपत्र परिवर्तन के [[सेट (गणित)|फलन (गणित)]] को निरूपित करें, और स्ट्रिंग्स के फलन L के लिए, परिवर्तन (L) को L में स्ट्रिंग्स के सभी गोलाकार शिफ्टों के फलन को निरूपित करें। यदि L चक्रीय कोड है, तो परिवर्तन (L) ⊆ L; L के [[चक्रीय भाषा]] होने के लिए यह आवश्यक नियम है। इस प्रकार [[औपचारिक भाषा सिद्धांत]] में ऑपरेशन परिवर्तन (L) का अध्ययन किया गया है। उदाहरण के लिए, यदि L [[संदर्भ-मुक्त भाषा|संदर्भ-फ्री भाषा]] है, तो परिवर्तन(L) फिर से संदर्भ-फ्री है।<ref>T. Oshiba, "Closure property of the family of context-free languages under the cyclic shift operation", Transactions of IECE, '''55D''':119–122, 1972.
</ref><ref>A. N. Maslov, "Cyclic shift operation for languages", Problems of Information Transmission '''9''':333–338, 1973.</ref> इसके अलावा, यदि L को लंबाई n की [[नियमित अभिव्यक्ति]] द्वारा वर्णित किया गया है, तो शिफ्ट (L) का वर्णन करने वाली लंबाई O(n<sup>3</sup>) की एक नियमित अभिव्यक्ति है।<ref>{{cite journal | zbl=1176.68105 | last1=Gruber | first1=Hermann | last2=Holzer | first2=Markus | title=बहुपद आकार की नियमित अभिव्यक्तियों के साथ भाषा संचालन| url=http://www.hermann-gruber.com/data/derivatives-journal.pdf | journal=Theoretical Computer Science | volume=410 | number=35 | pages=3281–3289 | year=2009 | doi=10.1016/j.tcs.2009.04.009 | access-date=2012-09-06 | archive-url=https://web.archive.org/web/20170829023123/http://hermann-gruber.com/data/derivatives-journal.pdf | archive-date=2017-08-29 | url-status=dead | doi-access=free }}.</ref>
==यह भी देखें==
==यह भी देखें==
*[[बैरल शिफ्टर]]
*[[बैरल शिफ्टर]]
*[[परिसंचारी]]
*[[परिसंचारी|परिचालित]]
*[[लिंडन शब्द]]
*[[लिंडन शब्द]]
*नेकलेस (कॉम्बिनेटरिक्स) - टपल जैसी वस्तु लेकिन जिसके लिए गोलाकार बदलाव को समकक्ष माना जाता है।
*नेकलेस (कॉम्बिनेटरिक्स) - टपल जैसी वस्तु लेकिन जिसके लिए गोलाकार परिवर्तन को समकक्ष माना जाता है।


==संदर्भ==
==संदर्भ                                                                                                                                                                                                                                       ==
{{reflist}}
{{reflist}}


Revision as of 10:49, 19 July 2023

Matrices of 8-element circular shifts to the left and right

साहचर्य गणित में, वृत्ताकार परिवर्तन टुपल में प्रविष्टियों को पुनर्व्यवस्थित करने का ऑपरेशन है, या तो अंतिम प्रविष्टि को पहले समिष्ट पर ले जाकर, जबकि अन्य सभी प्रविष्टियों को अगले समिष्ट पर स्थानांतरित करके, या प्रतिलोम ऑपरेशन करके प्राप्त करते है। वृत्ताकार परिवर्तन विशेष प्रकार का चक्रीय क्रमपरिवर्तन है, जो बदले में विशेष प्रकार का क्रमपरिवर्तन है। औपचारिक रूप से, गोलाकार परिवर्तन टुपल में n प्रविष्टियों का क्रमपरिवर्तन है जैसे कि या तो

मॉड्यूलर अंकगणित n, सभी प्रविष्टियों के लिए i = 1, ..., n

या

मॉड्यूलर अंकगणित n, सभी प्रविष्टियों के लिए i = 1, ..., n।

किसी दिए गए टुपल में बार-बार वृत्ताकार परिवर्तन प्रयुक्त करने के परिणाम को ट्यूपल का 'वृत्ताकार परिवर्तन' भी कहा जाता है।

उदाहरण के लिए, चार-टुपल (a, b, c, d) में बार-बार गोलाकार परिवर्तन लगाने से क्रमिक रूप से लाभ मिलता है

  • (d, a, b, c),
  • (c, d, a, b),
  • (b, c, d, a),
  • (a, b, c, d) (मूल चार-ट्यूपल),

और फिर क्रम दोहराता है; इसलिए इस चार-टुपल में चार अलग-अलग गोलाकार परिवर्तन हैं। चूँकि, सभी n-टुपल्स में n विशिष्ट वृत्ताकार परिवर्तन नहीं होते हैं। उदाहरण के लिए, 4-ट्यूपल (a, b, a, b) में केवल 2 अलग-अलग गोलाकार परिवर्तन हैं। n-ट्यूपल की अलग-अलग गोलाकार परिवर्तन की संख्या है , जहां k का भाजक है n, सभी उप-पैटर्न पर दोहराव की अधिकतम संख्या को दर्शाता है।

कंप्यूटर प्रोग्रामिंग में, बिटवाइज़ रोटेशन, जिसे वृत्ताकार परिवर्तन के रूप में भी जाना जाता है, बिटवाइज़ ऑपरेशन है जो इसके ऑपरेंड के सभी बिट्स को परिवर्तन करता है। इस प्रकार अंकगणितीय परिवर्तन के विपरीत, गोलाकार परिवर्तन किसी संख्या के साइन बिट को संरक्षित नहीं करता है या फ़्लोटिंग-पॉइंट नंबर के घातांक को उसके महत्व से अलग नहीं करता है। तार्किक परिवर्तन के विपरीत, रिक्त बिट स्थिति शून्य से नहीं भरी जाती है, किन्तु अनुक्रम से बाहर स्थानांतरित बिट्स से भरी जाती है।

वृत्ताकार परिवर्तन प्रयुक्त करना

बिट अनुक्रमों को व्यवस्थित करने के लिए क्रिप्टोग्राफी में अधिकांशतः वृत्ताकार परिवर्तन का उपयोग किया जाता है। सामान्यतः, सी (प्रोग्रामिंग भाषा) सहित कई प्रोग्रामिंग भाषाओं में वृत्ताकार शिफ्टिंग के लिए ऑपरेटर या मानक फ़ंक्शन नहीं हैं, तथापि लगभग सभी प्रोसेसर के पास इसके लिए बिटवाइज़ ऑपरेशन निर्देश हैं (उदाहरण के लिए इंटेल x86 में आरओएल और आरओआर हैं)। चूँकि, कुछ कंपाइलर आंतरिक कार्य के माध्यम से प्रोसेसर निर्देशों तक पहुंच प्रदान कर सकते हैं। इसके अतिरिक्त, मानक एएनएसआई सी कोड में कुछ निर्माणों को कंपाइलर द्वारा सीपीयू पर रोटेट असेंबली भाषा निर्देश के लिए अनुकूलित किया जा सकता है जिसमें ऐसा निर्देश होता है। अधिकांश सी कंपाइलर निम्नलिखित मुहावरे को पहचानते हैं, और इसे एकल 32-बिट रोटेट निर्देश में संकलित करते हैं।[1][2] 

/*
 * Shift operations in C are only defined for shift values which are
 * not negative and smaller than sizeof(value) * CHAR_BIT.
 * The mask, used with bitwise-and (&), prevents undefined behaviour
 * when the shift count is 0 or >= the width of unsigned int.
 */

#include <stdint.h>  // for uint32_t, to get 32-bit-wide rotates, regardless of the size of int.
#include <limits.h>  // for CHAR_BIT

uint32_t rotl32 (uint32_t value, unsigned int count) {
    const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
    count &= mask;
    return (value << count) | (value >> (-count & mask));
}

uint32_t rotr32 (uint32_t value, unsigned int count) {
    const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
    count &= mask;
    return (value >> count) | (value << (-count & mask));
}

यह सुरक्षित और संकलक-अनुकूल कार्यान्वयन जॉन रेगेहर द्वारा विकसित किया गया था,[3] और इसे पीटर कॉर्डेस द्वारा और अधिक परिष्कृत किया गया था।[4][5] एक सरल संस्करण अधिकांशतः देखा जाता है जब count 1 से 31 बिट्स की सीमा तक सीमित है: 

uint32_t rotl32 (uint32_t value, unsigned int count) {
    return value << count | value >> (32 - count);
}

यह संस्करण खतरनाक है क्योंकि यदि count 0 या 32 है, तो यह 32-बिट परिवर्तन के लिए पूछता है, जो सी भाषा मानक में अपरिभाषित व्यवहार है। चूँकि, यह वैसे भी कार्य करता है, क्योंकि अधिकांश माइक्रोप्रोसेसर इसे प्रयुक्त करते हैं value >> 32 या तो 32-बिट परिवर्तन (0 का उत्पादन) या 0-बिट परिवर्तन (मूल का उत्पादन) के रूप में value), और इनमें से कोई भी इस एप्लिकेशन में सही परिणाम देता है।

उदाहरण

यदि बिट अनुक्रम 0001 0111 को बिट स्थिति के गोलाकार परिवर्तन के अधीन किया गया था... (नीचे चित्र देखें)

  • बायीं ओर उत्पन्न होगी: 0010 1110
वाम वृत्ताकार परिवर्तन.
  • दांयी ओर उत्पन्न होगी: 1000 1011.
वाम वृत्ताकार परिवर्तन.

यदि बिट अनुक्रम 1001 0110 को निम्नलिखित परिचालनों के अधीन किया गया था:

बायीं ओर वृत्ताकार 1 स्थिति से परिवर्तन: 0010 1101            
बाएं वृत्ताकार में 2 समिष्ट का परिवर्तन: 0101 1010
बाएं वृत्ताकार में 3 समिष्ट का परिवर्तन: 1011 0100
बाएं वृत्ताकार में 4 समिष्ट का परिवर्तन: 0110 1001
बाएं वृत्ताकार में 5 समिष्ट का परिवर्तन: 1101 0010
बाएं वृत्ताकार में 6 समिष्ट का परिवर्तन: 1010 0101
बाएं वृत्ताकार में 7 समिष्ट का परिवर्तन: 0100 1011
बाएं वृत्ताकार में 8 समिष्ट का परिवर्तन: 1001 0110
दांयी ओर वृत्ताकार 1 स्थिति से परिवर्तन: 0100 1011
दांयी वृत्ताकार में 2 समिष्ट का परिवर्तन: 1010 0101
दांयी वृत्ताकार में 3 समिष्ट का परिवर्तन: 1101 0010
दांयी वृत्ताकार में 4 समिष्ट का परिवर्तन: 0110 1001
दांयी वृत्ताकार में 5 समिष्ट का परिवर्तन: 1011 0100
दांयी वृत्ताकार में 6 समिष्ट का परिवर्तन: 0101 1010
दांयी वृत्ताकार में 7 समिष्ट का परिवर्तन: 0010 1101
दांयी वृत्ताकार में 8 समिष्ट का परिवर्तन: 1001 0110





अनुप्रयोग

चक्रीय कोड प्रकार का ब्लॉक कोड होता है, जिसमें यह गुण होता है कि कोडवर्ड का गोलाकार परिवर्तन सदैव और कोडवर्ड उत्पन्न करता है। यह निम्नलिखित सामान्य परिभाषा को प्रेरित करता है: इस प्रकार वर्णमाला Σ पर स्ट्रिंग (कंप्यूटर विज्ञान) के लिए, परिवर्तन (o) को एस के परिपत्र परिवर्तन के फलन (गणित) को निरूपित करें, और स्ट्रिंग्स के फलन L के लिए, परिवर्तन (L) को L में स्ट्रिंग्स के सभी गोलाकार शिफ्टों के फलन को निरूपित करें। यदि L चक्रीय कोड है, तो परिवर्तन (L) ⊆ L; L के चक्रीय भाषा होने के लिए यह आवश्यक नियम है। इस प्रकार औपचारिक भाषा सिद्धांत में ऑपरेशन परिवर्तन (L) का अध्ययन किया गया है। उदाहरण के लिए, यदि L संदर्भ-फ्री भाषा है, तो परिवर्तन(L) फिर से संदर्भ-फ्री है।[6][7] इसके अलावा, यदि L को लंबाई n की नियमित अभिव्यक्ति द्वारा वर्णित किया गया है, तो शिफ्ट (L) का वर्णन करने वाली लंबाई O(n3) की एक नियमित अभिव्यक्ति है।[8]

यह भी देखें

संदर्भ

  1. ↑ GCC: "Optimize common rotate constructs"
  2. ↑ "Cleanups in ROTL/ROTR DAG combiner code" mentions that this code supports the "rotate" instruction in the CellSPU
  3. ↑ Safe, Efficient, and Portable Rotate in C/C++
  4. ↑ Stackoverflow: Best practices for rotates in C/C++
  5. ↑ Near constant time rotate that does not violate the standards
  6. ↑ T. Oshiba, "Closure property of the family of context-free languages under the cyclic shift operation", Transactions of IECE, 55D:119–122, 1972.
  7. ↑ A. N. Maslov, "Cyclic shift operation for languages", Problems of Information Transmission 9:333–338, 1973.
  8. ↑ Gruber, Hermann; Holzer, Markus (2009). "बहुपद आकार की नियमित अभिव्यक्तियों के साथ भाषा संचालन" (PDF). Theoretical Computer Science. 410 (35): 3281–3289. doi:10.1016/j.tcs.2009.04.009. Zbl 1176.68105. Archived from the original (PDF) on 2017-08-29. Retrieved 2012-09-06..
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=वृत्ताकार_परिवर्तन&oldid=222950’