🔢 mathematics

Polar Complexity: A New Descriptive Complexity with Applications to Source and Joint Source-Channel Coding

यह शोध पत्र परिमित-लंबाई वाले बाइनरी अनुक्रमों का वर्णन करने के लिए एक नए मीट्रिक के रूप में "पोलर कॉम्प्लेक्सिटी" (polar complexity) को प्रस्तुत करता है और एक पूर्णतः लॉसलेस (lossless), एडेप्टिव सोर्स कोडिंग योजना और एक संयुक्त स्रोत-चैनल कोडिंग ढांचे को विकसित करने के लिए इसका लाभ उठाता है, जो स्रोत सांख्यिकी के पूर्व ज्ञान के बिना निकट-इष्टतम प्रदर्शन प्राप्त करते हैं और त्रुटि प्रदर्शन एवं डिकोडिंग जटिलता के बीच लचीले ट्रेडऑफ़ प्रदान करते हैं।

मूल लेखक: Xinyuanmeng Yao, Xiao Ma

प्रकाशित 2026-05-13

📖 7 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Xinyuanmeng Yao, Xiao Ma

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

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

यह शोध पत्र एक नया तरीका पेश करता है जिससे यह मापा जा सके कि कोई विशिष्ट कहानी कितनी "कंप्रेसिबल" (संकुचित करने योग्य) है, और फिर इस माप का उपयोग करके डेटा भेजने का एक स्मार्ट और अधिक लचीला तरीका बनाता है। यहाँ सरल उपमाओं का उपयोग करके इसका विवरण दिया गया है:

1. नया पैमाना: "पोलर कॉम्प्लेक्सिटी" (Polar Complexity)

पारंपरिक रूप से, डेटा संपीड़न (जैसे ZIP फ़ाइलें) कहानियों के पूरे पुस्तकालय के औसत व्यवहार को देखकर काम करता है। यह मान लेता है कि सभी कहानियाँ एक ही रैंडम प्रक्रिया द्वारा उत्पन्न होती हैं। लेकिन क्या होगा यदि आपके पास केवल एक विशिष्ट कहानी हो, और आप उन नियमों को नहीं जानते जो इसे बनाने के लिए उपयोग किए गए थे?

लेखक एक नई अवधारणा पेश करते हैं जिसे पोलर कॉम्प्लेक्सिटी कहा जाता है। इसे एक "कठिनाई स्कोर" के रूप में सोचें।

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

2. स्कोर को मापना: "बाइसेक्शन सर्च" (Bisection Search)

इस स्कोर की सटीक गणना करना कठिन है। यह एक पत्थर का सटीक वजन अनुमान लगाने की तरह है।

पुराना तरीका: 1 टुकड़ा अनुमान लगाएँ, फिर से बनाने की कोशिश करें। विफल। 2 टुकड़े अनुमान लगाएँ, फिर से प्रयास करें। विफल। इसमें बहुत समय लगता है।
नया तरीका (बाइसेक्शन सर्च): लेखकों ने एक स्मार्ट "अनुमान और जाँच" वाला खेल बनाया है। आप बीच की संख्या का अनुमान लगाते हैं। यदि यह काम करता है, तो आप जानते हैं कि उत्तर कम है; यदि यह विफल होता है, तो आप जानते हैं कि यह अधिक है। आप हर बार खोज क्षेत्र को आधा कर देते हैं। यह अविश्वसनीय रूप से तेज़ है।
शॉर्टकट: उन्होंने एक "क्रिस्टल बॉल" (एक लो-कॉम्प्लेक्सिटी एस्टीमेशन विधि) भी बनाई है। यह कहानी को देखती है और भविष्यवाणी करती है, "यह पेचीदा लग रहा है; आपको शायद 50 टुकड़ों की आवश्यकता होगी।" यह हमेशा 100% सटीक नहीं होती है, लेकिन यह एक बहुत ही सुरक्षित ऊपरी सीमा है जो समय बचाती है।

3. दो-चरणीय संपीड़न प्रणाली (Two-Stage Compression System)

अब जब वे किसी भी विशिष्ट कहानी की "कठिनाई" को माप सकते हैं, तो उन्होंने एक नई संपीड़न प्रणाली बनाई है।

उपमा: कल्पना कीजिए कि आप एक पैकेज भेज रहे हैं। वस्तु को बॉक्स में भरने के बजाय, आप पहले एक लेबल लगाते हैं जिसमें लिखा होता है, "इस वस्तु को आकार 5 के बॉक्स की आवश्यकता है।" फिर आप उस विशिष्ट बॉक्स में वस्तु रखते हैं।
यह कैसे काम करता है:
1. चरण 1: कंप्यूटर डेटा की "पोलर कॉम्प्लेक्सिटी" (कठिनाई स्कोर) की गणना करता है। वह इस संख्या को एक छोटे हेडर (लेबल की तरह) के रूप में लिख देता है।
2. चरण 2: यह डेटा को ठीक उतने ही बिट्स (पुनर्निर्माण के लिए आवश्यक "टुकड़े") तक संकुचित करता है।
परिणाम: अंतिम संदेश "लेबल" + "संकुचित डेटा" है।
- यह क्यों महान है: यह बिना पूर्व नियमों को जाने किसी भी प्रकार के डेटा के लिए काम करता है। यदि डेटा सरल है, तो लेबल कहता है "छोटा बॉक्स", और पैकेज बहुत छोटा होता है। यदि डेटा अव्यवस्थित है, तो लेबल कहता है "बड़ा बॉक्स", और आपका पैकेज बड़ा होता है। यह सामग्री के अनुसार खुद को ढाल लेता है।
- गारंटी: शोध पत्र सिद्ध करता है कि पर्याप्त लंबे डेटा के लिए, यह विधि सैद्धांतिक संपीड़न सीमा (जिसे एंट्रॉपी कहा जाता है) के जितना संभव हो सके उतना करीब पहुँच जाती है।

4. "एडेप्टिव डबल-पोलर" प्रणाली (शोर वाली लाइन पर डेटा भेजना)

अंतिम भाग में, यह शोध पत्र इस नए संपीड़न को एक विधि के साथ जोड़ता है जिसका उपयोग शोर वाले चैनल (जैसे खराब वाई-फाई कनेक्शन) पर डेटा भेजने के लिए किया जाता है। इसे जॉइंट सोर्स-चैनल कोडिंग (JSCC) कहा जाता है।

समस्या: आमतौर पर, आप पहले डेटा को कंप्रेस करते हैं, फिर त्रुटि सुरक्षा (error protection) जोड़ते हैं। लेकिन यदि चैनल बहुत शोर वाला है, तो आपको डेटा को सुरक्षित करने के लिए अधिक बिट्स भेजने की आवश्यकता हो सकती है। यदि चैनल स्पष्ट है, तो आपको कम बिट्स की आवश्यकता होगी।
समाधान: लेखकों ने एक "बॉक्स आकारों का मेनू" बनाया है।
- भेजने वाला और प्राप्त करने वाला संभावित "कठिनाई स्कोर" (जैसे छोटा, मध्यम, बड़ा) की एक सूची पर सहमत होते हैं।
- भेजने वाला (Sender): डेटा को देखता है, उसकी जटिलता की गणना करता है, मेनू में से सबसे छोटा "बॉक्स आकार" चुनता जो डेटा को रखने के लिए पर्याप्त बड़ा हो, और उसे भेजता है।
- प्राप्त करने वाला (Receiver): उसे नहीं पता होता कि कौन सा बॉक्स आकार चुना गया था! इसलिए, वह यह मानकर संदेश को डिकोड करने का प्रयास करता है कि यह एक "छोटा बॉक्स" था। यदि यह विफल हो जाता है, तो वह "मध्यम" का प्रयास करता है, फिर "बड़ा"। वह यह देखने के लिए एक स्मार्ट टेस्ट (जैसे चेकसम) का उपयोग करता है कि कौन सा अनुमान काम करता है।
अनुकूलन (Optimization): लेखकों ने यह निर्धारित करने के लिए कि इस "मेनू" को डिज़ाइन करने का सबसे अच्छा तरीका क्या है, एक गणितीय रणनीति (डायनामिक प्रोग्रामिंग) का उपयोग किया ताकि सिस्टम तेज़ हो लेकिन गलतियाँ कम से कम करे।

दावों का सारांश

नया मीट्रिक: उन्होंने "पोलर कॉम्प्लेक्सिटी" को एक विशिष्ट अनुक्रम को पूरी तरह से पुनर्गठित करने के लिए आवश्यक न्यूनतम बिट्स के रूप में परिभाषित किया।
दक्षता: उन्होंने दिखाया कि कैसे "आधे-आधे" खोज पद्धति का उपयोग करके इसे तेज़ी से कैलकुलेट किया जा सकता है।
संपीड़न: उन्होंने एक ऐसी प्रणाली बनाई जो डेटा को उसकी जटिलता के आधार पर कंप्रेस करती है, और यह सिद्ध किया कि यह लंबे डेटा के लिए सर्वोत्तम सैद्धांतिक सीमाओं के समान काम करती है।
ट्रांसमिशन: उन्होंने इसे एरर करेक्शन के साथ जोड़कर एक ऐसा सिस्टम बनाया है जो स्वचालित रूप से डेटा की "कठिनाई" और चैनल के "शोर" के अनुसार खुद को ढाल लेता है, जो मौजूदा तरीकों से बेहतर प्रदर्शन करता है।

यह शोध पत्र दावा करता है कि यह डेटा को संभालने का एक स्व-निहित, गणितीय रूप से सिद्ध तरीका है जो कुशल और मजबूत दोनों है, और इसके लिए डेटा के सांख्यिकीय नियमों को पहले से जानने की आवश्यकता नहीं है।

तकनीकी सारांश: पोलर जटिलता और एडेप्टिव डबल-पोलर कोडिंग

समस्या विवरण
व्यक्तिगत परिमित-लंबाई वाले बाइनरी अनुक्रमों (binary sequences) का कुशलतापूर्वक वर्णन करना सूचना सिद्धांत (information theory) में एक मौलिक चुनौती बनी हुई है। जबकि शैनन का ढांचा ज्ञात सांख्यिकी वाले स्टोकेस्टिक स्रोतों के लिए औसत विवरण लंबाई को अनुकूलित करता है, यह उन व्यक्तिगत अनुक्रमों पर सीधे लागू नहीं होता जिनमें कोई संभाव्यता मॉडल (probabilistic model) नहीं होता। इसके विपरीत, कोलमोगोरोव जटिलता (Kolmogorov complexity), जो किसी अनुक्रम की जटिलता को उसे उत्पन्न करने वाले सबसे छोटे प्रोग्राम की लंबाई द्वारा परिभाषित करती है, सैद्धांतिक रूप से सार्वभौमिक है लेकिन गणना योग्य (uncomputable) नहीं है। मौजूदा गणना योग्य दृष्टिकोण, जैसे कि लेम्पेल-ज़िव (LZ) जटिलता या रैखिक जटिलता (linear complexity), विशिष्ट संरचनात्मक धारणाओं (जैसे दोहराए गए पैटर्न या रैखिक पुनरावृत्ति) पर निर्भर करते हैं जो किसी भी मनमाने अनुक्रम की पूर्ण नियमितता को पकड़ने में सक्षम नहीं हो सकते हैं। इसके अलावा, पारंपरिक निश्चित-लंबाई वाले पोलर स्रोत कोडिंग, जो स्टोकेस्टिक स्रोतों के लिए एंट्रॉपी प्राप्त करते हैं, स्वाभाविक रूप से यह निर्धारित करने का तंत्र प्रदान नहीं करते कि किसी विशिष्ट व्यक्तिगत अनुक्रम के सटीक पुनर्निर्माण के लिए न्यूनतम संपीड़न लंबाई क्या होनी चाहिए।

कार्यप्रणाली
यह शोध पत्र एक नया वर्णनात्मक जटिलता मीट्रिक प्रस्तुत करता जिसे पोलर जटिलता (Polar Complexity) कहा गया है, जिसे न्यूनतम पोलर-संपीड़न लंबाई (PCL) के रूप में परिभाषित किया गया है जो सक्सेसिव कैंसलेशन डिकोडिंग (SCD) का उपयोग करके एक विशिष्ट बाइनरी अनुक्रम के सटीक पुनर्निर्माण की गारंटी देता है। यह कार्यप्रणाली बाइनरी बैलेंस्ड ट्री (BBT) पोलर कोडिंग ढांचे पर आधारित है, जो मनमाने ब्लॉक लंबाई के लिए पोलर ट्रांसफॉर्म का सामान्यीकरण करती है।

पोलर जटिलता की परिभाषा और गणना:
- लेखक एक अनुक्रम $\mathbf{s}$ की पोलर जटिलता $L^\star(\mathbf{s})$ को न्यूनतम PCL $L$ के रूप में परिभाषित करते हैं, जिससे यह सुनिश्चित होता है कि अनुक्रम को एक मानक विन्यास (फ्रोज़न-नोड चयन के लिए पोलराइजेशन-वेट पद्धति और एक नियतक SCD पैरामीटर $\tau=0$ का उपयोग करते हुए) के तहत उसके पोलर-संपीड़ित प्रतिनिधित्व से पूरी तरह से पुनः प्राप्त किया जा सके।
- सटीक गणना: रिकवरेबिलिटी (पुनर्प्राप्ति क्षमता) की मोनोटोनिसिटी (monotonicity) का लाभ उठाते हुए (यदि एक अनुक्रम लंबाई $L$ पर रिकवरेबल है, तो वह किसी भी $L' > L$ पर रिकवरेबल होगा), यह शोध पत्र $L^\star(\mathbf{s})$ को कुशलतापूर्वक गणना करने के लिए एक बाइसेक्शन-सर्च एल्गोरिदम (bisection-search algorithm) प्रस्तावित करता है, जो SCD परीक्षणों की संख्या को अनुक्रम की लंबाई के रैखिक के बजाय लघुगणकीय (logarithmic) में कम कर देता है।
- कम-जटिलता अनुमान: बार-बार डिकोडिंग परीक्षणों से बचने के लिए, एक अनुमानित पोलर जटिलता (predicted polar complexity) पेश की गई है। यह विधि स्थानीय रूप से संदिग्ध या त्रुटि के प्रति संवेदनशील लीफ नोड्स के "क्रिटिकल सेट" की पहचान करने के लिए जीन-एडेड SCD (GA-SCD) का उपयोग करती है। अनुमानित जटिलता इस क्रिटिकल सेट के उच्चतम-प्राथमिकता वाले नोड के चयन प्राथमिकता द्वारा निर्धारित की जाती है, जो वास्तविक पोलर जटिलता के लिए एक रूढ़िवादी ऊपरी सीमा (conservative upper bound) प्रदान करती है।
पोलर-आधारित दो-चरणीय स्रोत कोडिंग:
- एक नया स्रोत कोडिंग तंत्र प्रस्तावित किया गया है जहाँ प्रत्येक स्रोत अनुक्रम को एक जोड़ी के रूप में एनकोड किया जाता है: एक निश्चित-लंबाई वाला हेडर जिसमें इसकी पोलर जटिलता का बाइनरी प्रतिनिधित्व होता है, उसके बाद परिवर्तनीय-लंबाई वाला पोलर-संपीड़ित अनुक्रम।
- यह योजना पूर्णतः लॉसलेस (lossless) और प्रीफिक्स-फ्री (prefix-free) है।
- सैद्धांतिक विश्लेषण सिद्ध करता है कि बाइनरी मेमोरीलेस स्रोतों (BMS) के लिए, जिनका ब्लॉक लेंथ दो की घात (power of two) है, इस योजना की सामान्यीकृत औसत संपीड़न लंबाई स्रोत एंट्रॉपी के सर्वसम्य (asymptotically) रूप से करीब पहुँच जाती है, बशर्ते कि फ्रोज़न-नोड चयन और SCD पैरामीटर स्रोत वितरण के लिए अनुकूलित हों।
एडेप्टिव डबल-पोलर जॉइंट सोर्स-चैनल कोडिंग (JSCC):
- लेखक प्रस्तावित स्रोत कोडिंग को पोलर चैनल कोडिंग के साथ एकीकृत करके एक एडेप्टिव JSCC योजना बनाते हैं।
- तंत्र: एनकोडर और डिकोडर उम्मीदवार PCL का एक पूर्व-निर्धारित परिमित सेट साझा करते हैं। किसी दिए गए स्रोत अनुक्रम के लिए, एनकोडर सबसे छोटा उम्मीदवार PCL चुनता है जो अनुक्रम की अनुमानित पोलर जटिलता के बराबर या उससे अधिक हो। चुना गया PCL चैनल एनकोडर में सक्रिय और फ्रोज़न नोड्स के आवंटन को निर्धारित करता है।
- डिकोडिंग: डिकोडर उम्मीदवार PCL सेट पर परिकल्पना परीक्षण (hypothesis testing) करता है। यह प्रत्येक परिकल्पना के लिए उम्मीदवार स्रोत अनुक्रमों का पुनर्निर्माण करता है और अमान्य उम्मीदवारों को फ़िल्टर करने के लिए CRC चेक का उपयोग करते हुए अंतिम अनुमान का चयन करता है।
- अनुकूलन (Optimization): प्रस्तावित उम्मीदवार PCL सेट के डिज़ाइन को फ्रेम एरर रेट (FER) को कम करने के लिए एक अनुकूलन समस्या के रूप में तैयार किया गया है। इसे प्रदर्शन-जटिलता ट्रेड-ऑफ के लिए डायनेमिक प्रोग्रामिंग का उपयोग करके कुशलतापूर्वक हल किया जाता है।

प्रमुख योगदान

पोलर जटिलता: एक नया, गणना योग्य वर्णनात्मक जटिलता मीट्रिक का परिचय जो सटीक SCD पुनर्निर्माण के लिए न्यूनतम PCL पर आधारित है।
कुशल एल्गोरिदम: सटीक गणना के लिए एक बाइसेक्शन-सर्च एल्गोरिदम और पोलर जटिलता का अनुमान लगाने के लिए एक कम-जटिलता वाले GA-SCD-आधारित अनुमान विधि का विकास।
दो-चरणीय स्रोत कोडिंग: एक पूर्णतः लॉसलेस, प्रीफिक्स-फ्री कोडिंग योजना जो बिना किसी पूर्व सांख्यिकीय ज्ञान के संचालन के लिए एंट्रॉपी प्राप्त करती है (हालांकि एंट्रॉपी-अचीविंग प्रमाण पैरामीटर ट्यूनिंग के लिए सांख्यिकी के ज्ञान को मानते हैं)।
एडेप्टिव JSCC: एक एकीकृत डबल-पोलर JSCC ढांचा जो व्यक्तिगत स्रोत यथार्थवादन (realizations) की संपीड़ितता के आधार पर चैनल कोड दर को अनुकूलित करता है। इस योजना में प्रदर्शन-जटिलता ट्रेड-ऑफ के लिए डायनेमिक प्रोग्रामिंग-आधारित विधि शामिल है।

परिणाम

स्रोत कोडिंग प्रदर्शन: सिमुलेशन दर्शाते हैं कि प्रस्तावित दो-चरणीय योजना छोटे ब्लॉक लेंथ ( $K=64$ ) के लिए एन्यूमरेटिव कोडिंग के समान संपीड़न प्रदर्शन प्राप्त करती है, लेकिन काफी कम कम्प्यूटेशनल जटिलता ( $O(K \log K)$ बनाम $O(K^2)$ ) के साथ। यह योजना विभिन्न स्रोत वितरणों में मजबूत बनी रहती है और इसे संचालन के लिए पूर्व सांख्यिकीय ज्ञान की आवश्यकता नहीं होती है।
जटिलता अनुमान: बाइसेक्शन सर्च विधि, अनुक्रमिक खोज की तुलना में पोलर जटिलता निर्धारित करने की कम्प्यूटेशनल लागत को काफी कम कर देती है। अनुमानित पोलर जटिलता लगातार वास्तविक जटिलता को एक छोटे अंतर के साथ ऊपरी सीमा (upper bound) के रूप में बनाए रखती है, जो इसके JSCC डिजाइन के लिए उपयोगिता को प्रमाणित करती है।
JSCC प्रदर्शन: एडेप्टिव डबल-पोलर JSCC सिमुलेशन में (ब्लॉक लेंथ $N=128$ और $N=1024$ के लिए), प्रस्तावित योजना मौजूदा पोलर-कोड-आधारित JSCC बेसलाइन (डबल-CRC-पोलर और जॉइंट SCLD योजनाओं सहित) से बेहतर प्रदर्शन करती है। फ्रेम एरर रेट (FER) उम्मीदवार PCL सेट की कार्डिनैलिटी (cardinality) बढ़ने के साथ निरंतर घटता है, और उस सैद्धांतिक निचली सीमा के करीब पहुँच जाता है जहाँ वास्तविक PCL डिकोडर को ज्ञात होता है।

महत्व
यह शोध पत्र दावा करता है कि स्टोकेस्टिक स्रोत गुणों के बजाय व्यक्तिगत अनुक्रमों के रिकवरी व्यवहार पर ध्यान केंद्रित करके, यह वर्णनात्मक जटिलता का एक व्यावहारिक और गणना योग्य माप प्रदान करता है। यह "पोलर जटिलता" कोडिंग योजनाओं की एक नई श्रेणी को सक्षम बनाती है जो पूर्णतः लॉसलेस और एडेप्टिव हैं। प्रस्तावित एडेप्टिव डबल-पोलर JSCC योजना एक लचीला प्रदर्शन-जटिलता ट्रेड-ऑफ प्रदान करती है, जो यह प्रदर्शित करती है कि व्यक्तिगत स्रोत यथार्थवादन की संपीड़ितता के साथ चैनल सुरक्षा को मिलाना, स्थिर या गैर-एडेप्टिव जॉइंट कोडिंग दृष्टिकोणों की तुलना में बेहतर एरर-रेट प्रदर्शन दे सकता है। यह कार्य एल्गोरिथमिक जटिलता अवधारणाओं और व्यावहारिक, क्षमता-निकट (capacity-approaching) कोडिंग तकनीकों के बीच के अंतर को पाटता है।

1. नया पैमाना: "पोलर कॉम्प्लेक्सिटी" (Polar Complexity)

2. स्कोर को मापना: "बाइसेक्शन सर्च" (Bisection Search)

3. दो-चरणीय संपीड़न प्रणाली (Two-Stage Compression System)

4. "एडेप्टिव डबल-पोलर" प्रणाली (शोर वाली लाइन पर डेटा भेजना)

दावों का सारांश

इसी तरह के और पेपर