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

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

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

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

या

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

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

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

• (डी, ए, बी, सी),
• (सी, डी, ए, बी),
• (बी, सी, डी, ए),
• (ए, बी, सी, डी) (मूल चार-ट्यूपल),

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

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

सर्कुलर शिफ्ट लागू करना

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

/*
 * 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));
}

यह सुरक्षित और संकलक-अनुकूल कार्यान्वयन जॉन रेगेहर द्वारा विकसित किया गया था, और इसे पीटर कॉर्डेस द्वारा और अधिक परिष्कृत किया गया। एक सरल संस्करण अक्सर देखा जाता है जब 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 को बिट स्थिति के गोलाकार बदलाव के अधीन किया गया था... (नीचे चित्र देखें)

to the left would yield: 0010 1110 Left circular shift.

to the right would yield: 1000 1011. Right circular shift.

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

left circular shift by 1 position:	0010 1101
left circular shift by 2 positions:	0101 1010
left circular shift by 3 positions:	1011 0100
left circular shift by 4 positions:	0110 1001
left circular shift by 5 positions:	1101 0010
left circular shift by 6 positions:	1010 0101
left circular shift by 7 positions:	0100 1011
left circular shift by 8 positions:	1001 0110

right circular shift by 1 position:	0100 1011
right circular shift by 2 positions:	1010 0101
right circular shift by 3 positions:	1101 0010
right circular shift by 4 positions:	0110 1001
right circular shift by 5 positions:	1011 0100
right circular shift by 6 positions:	0101 1010
right circular shift by 7 positions:	0010 1101
right circular shift by 8 positions:	1001 0110

अनुप्रयोग

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

यह भी देखें

• बैरल शिफ्टर
• परिसंचारी
• लिंडन शब्द
• नेकलेस (कॉम्बिनेटरिक्स) - टपल जैसी वस्तु लेकिन जिसके लिए गोलाकार बदलाव को समकक्ष माना जाता है।