बिट-व्युत्क्रम क्रमपरिवर्तन

एक हैमरस्ले सेट जिसके निर्देशांक 0 से 255 तक के पूर्णांक और उनके बिट-व्युत्क्रम हैं

व्यावहारिक गणित में, बिट-व्युत्क्रम क्रमपरिवर्तन $n$ वस्तुओं के अनुक्रम का क्रमपरिवर्तन है, जहां $n=2^{k}$ दो की शक्ति है। इसे अनुक्रम के तत्वों को $0$ से $n-1$ तक की संख्याओं द्वारा अनुक्रमित करके, इनमें से प्रत्येक संख्या को उसके द्विआधारी प्रतिनिधित्व (बिल्कुल लंबाई के लिए गद्देदार) द्वारा दर्शाया जाता है, और प्रत्येक आइटम को उस आइटम पर मैप करना जिसके प्रतिनिधित्व में उल्टे क्रम में समान बिट्स हैं।

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

यह क्रमपरिवर्तन केवल सरल सूचकांक गणना करते समय रैखिक समय में किसी भी अनुक्रम पर प्रयुक्त किया जा सकता है। इसमें कम-विसंगति अनुक्रमों की पीढ़ी और तेज़ फूरियर परिवर्तनों के मूल्यांकन में अनुप्रयोग हैं।

उदाहरण

आठ अक्षरों एबीसीडीईएफजीएच के अनुक्रम पर विचार करें। उनके सूचकांक बाइनरी नंबर 000, 001, 010, 011, 100, 101, 110 और 111 हैं, जिन्हें विपरीत करने पर 000, 100, 010, 110, 001, 101, 011 और 111 हो जाते हैं। इस प्रकार, अक्षर a स्थिति 000 को उसी स्थिति (000) पर मैप किया जाता है, स्थिति 001 में अक्षर b को पांचवें स्थान (जिसकी संख्या 100 है) पर मैप किया जाता है, आदि, जिससे नया अनुक्रम एईसीजीबीएफडीएच मिलता है। इस नए अनुक्रम पर समान क्रमपरिवर्तन दोहराते हुए प्रारंभिक अनुक्रम पर लौट आता है।

सूचकांक संख्याओं को दशमलव में लिखना (किन्तु, जैसा ऊपर बताया गया है, क्रमपरिवर्तन के लिए 1 की अधिक पारंपरिक प्रारंभ के अतिरिक्त स्थिति 0 से प्रारंभ करना), $n=2^{k}$ आइटम पर बिट-व्युत्क्रम क्रमपरिवर्तन, $k=0,1,2,3,\dots$ हैं:^[1]

$k$	$n=2^{k}$	क्रमपरिवर्तन
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]

सामान्यीकरण

$b>2$ और $n=b^{k}$ के लिए रेडिक्स $b$ अभ्यावेदन का सामान्यीकरण, एक अंक-व्युत्क्रम क्रमपरिवर्तन है, जिसमें क्रमबद्ध सूचकांक प्राप्त करने के लिए प्रत्येक तत्व के सूचकांक के आधार- $b$ अंकों को व्युत्क्रम दिया जाता है। इसी विचार को मिश्रित मूलांक संख्या प्रणालियों के लिए भी सामान्यीकृत किया जा सकता है। ऐसे स्थितियों में, अंक-व्युत्क्रम क्रमपरिवर्तन को एक साथ प्रत्येक आइटम के अंकों और संख्या प्रणाली के आधारों को व्युत्क्रम देना चाहिए, ताकि प्रत्येक उलटा अंक उसके आधार द्वारा परिभाषित सीमा के अंदर रहे।^[3]

क्रमपरिवर्तन जो उनके सूचकांकों के द्विआधारी प्रतिनिधित्व के अंदर बिट्स के सन्निहित ब्लॉकों को विपरीत कर बिट-व्युत्क्रम क्रमपरिवर्तन को सामान्यीकृत करते हैं, का उपयोग डेटा के दो समान-लंबाई अनुक्रमों को जगह में जोड़ने के लिए किया जा सकता है।^[4]

इच्छानुसार लंबाई के अनुक्रमों के लिए बिट-व्युत्क्रम क्रमपरिवर्तन के दो विस्तार हैं। ये विस्तार उन अनुक्रमों के लिए बिट-व्युत्क्रम के साथ मेल खाते हैं जिनकी लंबाई 2 की शक्ति है, और उनका उद्देश्य कक्ज़मर्ज़ विधि के कुशल संचालन के लिए अनुक्रम में आसन्न वस्तुओं को अलग करना है। इनमें से पहला विस्तार , जिसे कुशल ऑर्डरिंग कहा जाता है,^[5] मिश्रित संख्याओं पर कार्य करता है, और यह संख्या को उसके अभाज्य घटकों में विघटित करने पर आधारित है।

दूसरा विस्तार , जिसे ईबीआर (विस्तारित बिट-रिवर्सल) कहा जाता है, मूल रूप से बिट-व्युत्क्रम के समान है। आकार $n$ की एक सरणी को देखते हुए, ईबीआर रैखिक समय में श्रेणी $0\ldots n-1$ में संख्याओं के क्रमपरिवर्तन के साथ सरणी को भरता है। क्रमिक संख्याओं को क्रमपरिवर्तन में कम से कम $\lfloor n/4\rfloor$ स्थानों से अलग किया जाता है।^[6]

अनुप्रयोग

रेडिक्स-2 कूली-टुकी एफएफटी एल्गोरिदम के लिए बिट व्युत्क्रम सबसे महत्वपूर्ण है, जहां एल्गोरिदम के पुनरावर्ती चरण, जगह-जगह काम करते हुए, इनपुट या आउटपुट में थोड़ा उतार-चढ़ाव करते हैं। इसी प्रकार, मिश्रित-मूलांक कूली-टुकी एफएफटी में मिश्रित-मूलांक अंक उत्क्रमण उत्पन्न होता है।^[7]

वितरित गणना में निचली सीमाएं तैयार करने के लिए बिट व्युत्क्रम क्रमपरिवर्तन का भी उपयोग किया गया है।^[8]

वैन डेर कॉरपुट अनुक्रम, इकाई अंतराल में संख्याओं का एक कम-विसंगति अनुक्रम, बिट-व्युत्क्रम क्रमपरिवर्तन के सूचकांकों को निश्चित-बिंदु अंकगणित | डायडिक तर्कसंगत संख्याओं के निश्चित-बिंदु बाइनरी प्रतिनिधित्व के रूप में पुन: व्याख्या करके बनाया गया है।

बिट-व्युत्क्रम क्रमपरिवर्तन का उपयोग अक्सर गतिशील डेटा संरचनाओं पर निचली सीमाएं खोजने में किया जाता है। उदाहरण के लिए, कुछ मान्यताओं के अधीन, उन मानों को रखने वाले किसी भी बाइनरी सर्च ट्री में, $0$ और $n-1$ के बीच पूर्णांकों को देखने की निवेश, $\Omega (n\log n)$ है, जब उन संख्याओं के बारे में पूछताछ की जाती है बिट-विपरीत क्रम। यह सीमा छींटदार पेड़ों जैसे पेड़ों पर भी प्रयुक्त होती है जिन्हें एक्सेस के बीच अपने नोड्स को पुनर्व्यवस्थित करने की अनुमति होती है^[9]

एल्गोरिदम

मुख्य रूप से फास्ट फूरियर ट्रांसफॉर्म एल्गोरिदम के महत्व के कारण, अनुक्रम में बिट-व्युत्क्रम क्रमपरिवर्तन प्रयुक्त करने के लिए विभिन्न कुशल एल्गोरिदम तैयार किए गए हैं।^[2]

क्योंकि बिट-व्युत्क्रम क्रमपरिवर्तन एक इनवोल्यूशन है, इसे तत्वों के जोड़े को स्वैप करके इन-प्लेस एल्गोरिदम (डेटा को किसी अन्य सरणी में कॉपी किए बिना) सरलता से निष्पादित किया जा सकता है। समान्य रूप से एल्गोरिथ्म विश्लेषण में उपयोग की जाने वाली रैंडम-एक्सेस मशीन में, एक सरल एल्गोरिदम जो इनपुट क्रम में इंडेक्स को स्कैन करता है और जब भी स्कैन एक इंडेक्स का सामना करता है जिसका व्युत्क्रम एक बड़ी संख्या है, तो स्वैप होता है जो डेटा चाल की एक रैखिक संख्या निष्पादित करेगा।^[10] चूँकि , प्रत्येक सूचकांक के उत्क्रमण की गणना करने के लिए गैर-स्थिर संख्या में कदम उठाने पड़ सकते हैं। वैकल्पिक एल्गोरिदम केवल सरल सूचकांक गणनाओं का उपयोग करते हुए रैखिक समय में थोड़ा विपरीत क्रमपरिवर्तन कर सकते हैं।^[11] क्योंकि गणना के भाग के रूप में बिट-व्युत्क्रम क्रमपरिवर्तन को विभिन्न बार दोहराया जा सकता है, इसलिए एल्गोरिदम के चरणों को अलग करना सहायक हो सकता है जो क्रमपरिवर्तन का प्रतिनिधित्व करने के लिए उपयोग किए जाने वाले सूचकांक डेटा की गणना करते हैं (उदाहरण के लिए, दोहरीकरण और संयोजन विधि का उपयोग करके) वे चरण जो डेटा को क्रमबद्ध करने के लिए इस गणना के परिणामों का उपयोग करते हैं (उदाहरण के लिए, डेटा इंडेक्स को क्रम में स्कैन करके और जब भी स्वैप किया गया स्थान वर्तमान इंडेक्स से अधिक होता है, या अधिक परिष्कृत वेक्टर स्कैटर-संग्रह संचालन का उपयोग करके स्वैप निष्पादित करते हैं) .^[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

[1] Sloane, N. J. A. (ed.), "Sequence A030109", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation

[karp-2] 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.

[3] 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

[4] 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.

[5] Herman, Gabor T. (2009), Fundamentals of Computerized Tomography (2nd ed.), London: Springer, p. 209, ISBN 978-1-85233-617-2

[6] 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

[7] B. Gold and C. M. Rader, Digital Processing of Signals (New York: McGraw–Hill, 1969).

[8] 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.

[9] 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.

[cg98-10] 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.

[11] 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.

[12] 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.

[13] 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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

बिट-व्युत्क्रम क्रमपरिवर्तन

Contents

उदाहरण

सामान्यीकरण

अनुप्रयोग

एल्गोरिदम

संदर्भ

Navigation menu

Search