बिट-व्युत्क्रम क्रमपरिवर्तन
व्यावहारिक गणित में, बिट-रिवर्सल क्रमपरिवर्तन एक अनुक्रम का क्रमपरिवर्तन है आइटम, कहाँ दो की शक्ति है. इसे अनुक्रम के तत्वों को संख्याओं द्वारा अनुक्रमित करके परिभाषित किया गया है को , इनमें से प्रत्येक संख्या को उसके द्विआधारी प्रतिनिधित्व (बिल्कुल लंबाई के लिए गद्देदार) द्वारा दर्शाता है ), और प्रत्येक आइटम को उस आइटम पर मैप करना जिसके प्रतिनिधित्व में उल्टे क्रम में समान बिट्स हैं।
समान क्रमपरिवर्तन को दो बार दोहराने से वस्तुओं पर मूल क्रम वापस आ जाता है, इसलिए बिट उलट क्रमपरिवर्तन एक इनवोल्यूशन (गणित) है।
यह क्रमपरिवर्तन केवल सरल सूचकांक गणना करते समय रैखिक समय में किसी भी अनुक्रम पर लागू किया जा सकता है। इसमें कम-विसंगति अनुक्रमों की पीढ़ी और तेज़ फूरियर परिवर्तनों के मूल्यांकन में अनुप्रयोग हैं।
उदाहरण
आठ अक्षरों के क्रम पर विचार करेंabcdefgh. उनके सूचकांक बाइनरी नंबर 000, 001, 010, 011, 100, 101, 110 और 111 हैं, जिन्हें उलटने पर 000, 100, 010, 110, 001, 101, 011 और 111 हो जाते हैं। इस प्रकार, स्थिति 000 में अक्षर a को उसी स्थिति (000) पर मैप किया जाता है, स्थिति 001 में अक्षर b को पांचवें स्थान (जिसकी संख्या 100 है) आदि पर मैप किया जाता है, जिससे नया अनुक्रम मिलता है।aecgbfdh. इस नए अनुक्रम पर समान क्रमपरिवर्तन दोहराते हुए प्रारंभिक अनुक्रम पर लौट आता है।
सूचकांक संख्याओं को दशमलव में लिखना (लेकिन, जैसा कि ऊपर है, क्रमपरिवर्तन के लिए 1 की अधिक पारंपरिक शुरुआत के बजाय स्थिति 0 से शुरू करना), बिट-रिवर्सल क्रमपरिवर्तन आइटम, के लिए , हैं:[1]
| permutation | ||
|---|---|---|
| 0 | 1 | 0 |
| 1 | 2 | 0 1 |
| 2 | 4 | 0 2 1 3 |
| 3 | 8 | 0 4 2 6 1 5 3 7 |
| 4 | 16 | 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 |
इस अनुक्रम में प्रत्येक क्रमपरिवर्तन को संख्याओं के दो अनुक्रमों को जोड़कर उत्पन्न किया जा सकता है: पिछला क्रमपरिवर्तन, जिसके मान दोगुने हो जाते हैं, और वही क्रम जिसमें प्रत्येक मान में एक की वृद्धि होती है। इस प्रकार, उदाहरण के लिए लंबाई-4 क्रमपरिवर्तन को दोगुना करना 0 2 1 3 देता है 0 4 2 6, एक जोड़ने पर प्राप्त होता है 1 5 3 7, और इन दो अनुक्रमों को संयोजित करने से लंबाई-8 क्रमपरिवर्तन प्राप्त होता है 0 4 2 6 1 5 3 7.[2]
सामान्यीकरण
मूलांक का सामान्यीकरण अभ्यावेदन, के लिए , और करने के लिए , एक अंक-उलट क्रमपरिवर्तन है, जिसमें आधार- क्रमपरिवर्तित सूचकांक प्राप्त करने के लिए प्रत्येक तत्व के सूचकांक के अंकों को उलट दिया जाता है। इसी विचार को मिश्रित मूलांक संख्या प्रणालियों के लिए भी सामान्यीकृत किया जा सकता है। ऐसे मामलों में, अंक-उलट क्रमपरिवर्तन को एक साथ प्रत्येक आइटम के अंकों और संख्या प्रणाली के आधारों को उलट देना चाहिए, ताकि प्रत्येक उलटा अंक उसके आधार द्वारा परिभाषित सीमा के भीतर रहे।[3] क्रमपरिवर्तन जो उनके सूचकांकों के द्विआधारी प्रतिनिधित्व के भीतर बिट्स के सन्निहित ब्लॉकों को उलट कर बिट-रिवर्सल क्रमपरिवर्तन को सामान्यीकृत करते हैं, का उपयोग डेटा के दो समान-लंबाई अनुक्रमों को जगह में जोड़ने के लिए किया जा सकता है।[4] मनमानी लंबाई के अनुक्रमों के लिए बिट-रिवर्सल क्रमपरिवर्तन के दो विस्तार हैं। ये एक्सटेंशन उन अनुक्रमों के लिए बिट-रिवर्सल के साथ मेल खाते हैं जिनकी लंबाई 2 की शक्ति है, और उनका उद्देश्य कक्ज़मर्ज़ विधि के कुशल संचालन के लिए अनुक्रम में आसन्न वस्तुओं को अलग करना है। इनमें से पहला एक्सटेंशन, जिसे कुशल ऑर्डरिंग कहा जाता है,[5] मिश्रित संख्याओं पर कार्य करता है, और यह संख्या को उसके अभाज्य घटकों में विघटित करने पर आधारित है।
दूसरा एक्सटेंशन, जिसे ईबीआर (विस्तारित बिट-रिवर्सल) कहा जाता है, मूल रूप से बिट-रिवर्सल के समान है। आकार की एक श्रृंखला दी गई है , ईबीआर श्रेणी में संख्याओं के क्रमपरिवर्तन के साथ सरणी को भरता है रैखिक समय में. क्रमिक संख्याओं को क्रमपरिवर्तन में कम से कम से अलग किया जाता है पद.[6]
अनुप्रयोग
रेडिक्स-2 कूली-टुकी एफएफटी एल्गोरिदम के लिए बिट रिवर्सल सबसे महत्वपूर्ण है, जहां एल्गोरिदम के पुनरावर्ती चरण, जगह-जगह काम करते हुए, इनपुट या आउटपुट में थोड़ा उलटफेर करते हैं। इसी प्रकार, मिश्रित-मूलांक कूली-टुकी एफएफटी में मिश्रित-मूलांक अंक उत्क्रमण उत्पन्न होता है।[7] वितरित गणना में निचली सीमाएं तैयार करने के लिए बिट रिवर्सल क्रमपरिवर्तन का भी उपयोग किया गया है।[8] वैन डेर कॉरपुट अनुक्रम, इकाई अंतराल में संख्याओं का एक कम-विसंगति अनुक्रम, बिट-रिवर्सल क्रमपरिवर्तन के सूचकांकों को निश्चित-बिंदु अंकगणित | डायडिक तर्कसंगत संख्याओं के निश्चित-बिंदु बाइनरी प्रतिनिधित्व के रूप में पुन: व्याख्या करके बनाया गया है।
बिट-रिवर्सल क्रमपरिवर्तन का उपयोग अक्सर गतिशील डेटा संरचनाओं पर निचली सीमाएं खोजने में किया जाता है। उदाहरण के लिए, कुछ मान्यताओं के अधीन, बीच के पूर्णांकों को देखने की लागत और , समावेशी, उन मानों को धारण करने वाले किसी भी बाइनरी सर्च ट्री में है जब उन नंबरों को बिट-उलटे क्रम में पूछा जाता है। यह सीमा स्पले पेड़ों जैसे पेड़ों पर भी लागू होती है जिन्हें एक्सेस के बीच अपने नोड्स को पुनर्व्यवस्थित करने की अनुमति होती है।[9]
एल्गोरिदम
मुख्य रूप से फास्ट फूरियर ट्रांसफॉर्म एल्गोरिदम के महत्व के कारण, अनुक्रम में बिट-रिवर्सल क्रमपरिवर्तन लागू करने के लिए कई कुशल एल्गोरिदम तैयार किए गए हैं।[2] क्योंकि बिट-रिवर्सल क्रमपरिवर्तन एक इनवोल्यूशन है, इसे तत्वों के जोड़े को स्वैप करके इन-प्लेस एल्गोरिदम (डेटा को किसी अन्य सरणी में कॉपी किए बिना) आसानी से निष्पादित किया जा सकता है। आमतौर पर एल्गोरिथ्म विश्लेषण में उपयोग की जाने वाली रैंडम-एक्सेस मशीन में, एक सरल एल्गोरिदम जो इनपुट क्रम में इंडेक्स को स्कैन करता है और जब भी स्कैन एक इंडेक्स का सामना करता है जिसका रिवर्सल एक बड़ी संख्या है, तो स्वैप होता है जो डेटा चाल की एक रैखिक संख्या निष्पादित करेगा।[10]हालाँकि, प्रत्येक सूचकांक के उत्क्रमण की गणना करने के लिए गैर-स्थिर संख्या में कदम उठाने पड़ सकते हैं। वैकल्पिक एल्गोरिदम केवल सरल सूचकांक गणनाओं का उपयोग करते हुए रैखिक समय में थोड़ा उलट क्रमपरिवर्तन कर सकते हैं।[11] क्योंकि गणना के भाग के रूप में बिट-रिवर्सल क्रमपरिवर्तन को कई बार दोहराया जा सकता है, इसलिए एल्गोरिदम के चरणों को अलग करना सहायक हो सकता है जो क्रमपरिवर्तन का प्रतिनिधित्व करने के लिए उपयोग किए जाने वाले सूचकांक डेटा की गणना करते हैं (उदाहरण के लिए, दोहरीकरण और संयोजन विधि का उपयोग करके) वे चरण जो डेटा को क्रमबद्ध करने के लिए इस गणना के परिणामों का उपयोग करते हैं (उदाहरण के लिए, डेटा इंडेक्स को क्रम में स्कैन करके और जब भी स्वैप किया गया स्थान वर्तमान इंडेक्स से अधिक होता है, या अधिक परिष्कृत वेक्टर I/O|वेक्टर का उपयोग करके स्वैप निष्पादित करते हैं) बिखराव-इकट्ठा संचालन)।[2]
एक और विचार जो इन एल्गोरिदम के प्रदर्शन के लिए और भी महत्वपूर्ण है, वह है रनिंग टाइम पर मेमोरी पदानुक्रम का प्रभाव। इस प्रभाव के कारण, अधिक परिष्कृत एल्गोरिदम जो मेमोरी की ब्लॉक संरचना पर विचार करते हैं, इस अनुभवहीन स्कैन से तेज़ हो सकते हैं।[2][10] इन तकनीकों का एक विकल्प विशेष कंप्यूटर हार्डवेयर है जो मेमोरी को सामान्य और बिट-उलटे क्रम में एक्सेस करने की अनुमति देता है।[12] उच्च-प्रदर्शन कंप्यूटिंग क्षेत्रों में यूनिप्रोसेसर और मल्टीप्रोसेसर दोनों में बिट-रिवर्सल के प्रदर्शन सुधार पर गंभीरता से ध्यान दिया गया है। क्योंकि आर्किटेक्चर-अवेयर एल्गोरिदम विकास कैश, टीएलबी और मल्टीकोर सहित हार्डवेयर और सिस्टम सॉफ़्टवेयर संसाधनों का सर्वोत्तम उपयोग कर सकता है, जिससे गणना में काफी तेजी आती है।[13]
संदर्भ
- ↑ Sloane, N. J. A. (ed.), "Sequence A030109", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation
- ↑ 2.0 2.1 2.2 2.3 Karp, Alan H. (1996), "Bit reversal on uniprocessors", SIAM Review, 38 (1): 1–26, CiteSeerX 10.1.1.24.2913, doi:10.1137/1038001, MR 1379039. Karp surveys and compares 30 different algorithms for bit reversal, developed between 1965 and the 1996 publication of his survey.
- ↑ Elster, Anne C. (1989), "Fast bit-reversal algorithms", IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP '89, Glasgow, Scotland, May 23-26, 1989, pp. 1099–1102, doi:10.1109/ICASSP.1989.266624, S2CID 15028026
- ↑ Yang, Qingxuan; Ellis, John; Mamakani, Khalegh; Ruskey, Frank (2013), "In-place permuting and perfect shuffling using involutions", Information Processing Letters, 113 (10–11): 386–391, doi:10.1016/j.ipl.2013.02.017, MR 3037467, S2CID 14672841.
- ↑ Herman, Gabor T. (2009), Fundamentals of Computerized Tomography (2nd ed.), London: Springer, p. 209, ISBN 978-1-85233-617-2
- ↑ Gordon, Dan (June 2017), "A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates", Numerical Algorithms, 77 (4): 1141–1157, doi:10.1007/s11075-017-0356-3, S2CID 254889989
- ↑ B. Gold and C. M. Rader, Digital Processing of Signals (New York: McGraw–Hill, 1969).
- ↑ Frederickson, Greg N.; Lynch, Nancy A. (1984), "The impact of synchronous communication on the problem of electing a leader in a ring" (PDF), Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (STOC '84), pp. 493–503, doi:10.1145/800057.808719, ISBN 978-0897911337.
- ↑ Wilber, Robert (1989), "Lower Bounds for Accessing Binary Search Trees With Rotations", 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pp. 61–70, doi:10.1109/SFCS.1986.28, ISBN 0-8186-0740-8.
- ↑ 10.0 10.1 Carter, Larry; Gatlin, Kang Su (1998), "Towards an optimal bit-reversal permutation program", Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS), pp. 544–553, CiteSeerX 10.1.1.46.9319, doi:10.1109/SFCS.1998.743505, ISBN 978-0-8186-9172-0, S2CID 14307262.
- ↑ Jeong, Jechang; Williams, W.J. (1990), "A fast recursive bit-reversal algorithm", International Conference on Acoustics, Speech, and Signal Processing (ICASSP-90), vol. 3, pp. 1511–1514, doi:10.1109/ICASSP.1990.115695, S2CID 122373780.
- ↑ Harley, T. R.; Maheshwaramurthy, G. P. (2004), "Address generators for mapping arrays in bit-reversed order", IEEE Transactions on Signal Processing, 52 (6): 1693–1703, doi:10.1109/TSP.2004.827148, S2CID 10043478.
- ↑ Zhang, Zhao; Zhang, Xiaodong (2000), "Fast bit-reversals on uniprocessors and shared-memory multiprocessors", SIAM Journal on Scientific Computing, 22 (6): 2113–2134, doi:10.1137/S1064827599359709, MR 1856305
