2025-11-20T14:55:15.130233

On the Weight Spectrum of Rate-Compatible Polar Codes

Ye, Li, Liu et al.
The weight spectrum plays a crucial role in the performance of error-correcting codes. Despite substantial theoretical exploration of polar codes with mother code length, a framework for the weight spectrum of rate-compatible polar codes remains elusive. In this paper, we address this gap by presenting the theoretical results for enumerating the number of minimum-weight codewords for quasi-uniform punctured, Wang-Liu shortened, and bit-reversal shortened decreasing polar codes. Additionally, we propose efficient algorithms for computing the average spectrum of random upper-triangular pre-transformed shortened and punctured polar codes. Notably, our algorithms operate with polynomial complexity relative to the code length. Simulation results affirm that our findings yield a precise estimation of the performance of rate-compatible polar codes.
academic

दर-संगत ध्रुवीय कोड के भार स्पेक्ट्रम पर

मूल जानकारी

  • पेपर ID: 2410.19242
  • शीर्षक: दर-संगत ध्रुवीय कोड के भार स्पेक्ट्रम पर
  • लेखक: Zicheng Ye, Yuan Li, Zhichao Liu, Huazi Zhang, Jun Wang, Guiying Yan, Zhiming Ma
  • वर्गीकरण: cs.IT math.IT
  • प्रकाशन समय: अक्टूबर 2024
  • पेपर लिंक: https://arxiv.org/abs/2410.19242

सारांश

भार स्पेक्ट्रम त्रुटि सुधार कोड के प्रदर्शन में महत्वपूर्ण भूमिका निभाता है। यद्यपि मातृ कोड लंबाई के ध्रुवीय कोड पर व्यापक सैद्धांतिक अन्वेषण किए गए हैं, दर-संगत ध्रुवीय कोड के भार स्पेक्ट्रम की रूपरेखा अभी भी दुर्लभ है। यह पेपर अर्ध-समान विलोपन, Wang-Liu संक्षिप्तकरण और बिट-प्रतिलोमन संक्षिप्तकरण ह्रासमान ध्रुवीय कोड के न्यूनतम भार कोडवर्ड संख्या गणना के सैद्धांतिक परिणाम प्रस्तुत करके इस अंतराल को संबोधित करता है। इसके अतिरिक्त, हम यादृच्छिक ऊपरी त्रिकोणीय पूर्व-परिवर्तन संक्षिप्तकरण और विलोपन ध्रुवीय कोड के औसत स्पेक्ट्रम की गणना के लिए एक कुशल एल्गोरिथ्म प्रस्तुत करते हैं। उल्लेखनीय रूप से, हमारा एल्गोरिथ्म कोड लंबाई के संबंध में बहुपद जटिलता रखता है। सिमुलेशन परिणाम पुष्टि करते हैं कि हमारे निष्कर्ष दर-संगत ध्रुवीय कोड के प्रदर्शन का सटीक अनुमान प्रदान करते हैं।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या पृष्ठभूमि

  1. ध्रुवीय कोड की सीमाएं: ध्रुवीय कोड अपनी Kronecker उत्पाद की अंतर्निहित संरचना के कारण, मूल कोड लंबाई 2 की घातों तक सीमित है। हालांकि, व्यावहारिक अनुप्रयोग आमतौर पर विभिन्न कोड लंबाई के संदेश प्रसारित करने की आवश्यकता होती है, जिसके लिए विलोपन (puncturing) और संक्षिप्तकरण (shortening) तकनीकों की आवश्यकता होती है।
  2. भार स्पेक्ट्रम का महत्व: भार स्पेक्ट्रम अधिकतम संभावना (ML) विकोडन प्रदर्शन पर महत्वपूर्ण प्रभाव डालता है, जिसे निम्न भार कोडवर्ड संख्या के आधार पर संघ सीमा के माध्यम से अनुमानित किया जा सकता है। हालांकि, सटीक भार स्पेक्ट्रम की गणना की जटिलता आमतौर पर कोड लंबाई के साथ घातीय रूप से बढ़ती है।
  3. मौजूदा अनुसंधान की कमियां: यद्यपि मातृ कोड लंबाई के ध्रुवीय कोड के भार स्पेक्ट्रम पर व्यापक अनुसंधान है, दर-संगत ध्रुवीय कोड के भार स्पेक्ट्रम के लिए एक व्यवस्थित रूपरेखा अभी भी अनुपस्थित है।

अनुसंधान प्रेरणा

यह पेपर दर-संगत ध्रुवीय कोड के भार स्पेक्ट्रम सिद्धांत में अंतराल को भरने का लक्ष्य रखता है, अर्ध-समान विलोपन (QUP), Wang-Liu संक्षिप्तकरण और बिट-प्रतिलोमन संक्षिप्तकरण ध्रुवीय कोड के लिए एक व्यवस्थित भार स्पेक्ट्रम विश्लेषण रूपरेखा प्रदान करता है।

मुख्य योगदान

  1. सैद्धांतिक योगदान: QUP, Wang-Liu संक्षिप्तकरण और बिट-प्रतिलोमन संक्षिप्तकरण ह्रासमान ध्रुवीय कोड के न्यूनतम भार कोडवर्ड संख्या की गणना के लिए एक संपूर्ण सैद्धांतिक रूपरेखा और सूत्र प्रस्तुत करता है।
  2. एल्गोरिथ्मिक नवाचार: यादृच्छिक ऊपरी त्रिकोणीय पूर्व-परिवर्तन संक्षिप्तकरण और विलोपन ध्रुवीय कोड के औसत भार स्पेक्ट्रम की गणना के लिए बहुपद जटिलता एल्गोरिथ्म विकसित करता है।
  3. प्रदर्शन मूल्यांकन: सिमुलेशन के माध्यम से सत्यापित करता है कि प्रस्तावित विधि दर-संगत ध्रुवीय कोड के प्रदर्शन का सटीक अनुमान लगा सकती है, विशेष रूप से उच्च संकेत-से-शोर अनुपात स्थितियों में।
  4. जटिलता अनुकूलन: सभी प्रस्तावित एल्गोरिथ्म कोड लंबाई के संबंध में बहुपद जटिलता रखते हैं, जो विधि की स्केलेबिलिटी और व्यावहारिकता सुनिश्चित करता है।

विधि विवरण

कार्य परिभाषा

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

सैद्धांतिक आधार

ध्रुवीय कोड का एकपदीय प्रतिनिधित्व

ध्रुवीय कोड को वलय F₂x₁,...,xₘ/(x₁²-x₁,...,xₘ²-xₘ) में एकपदीय कोड के रूप में वर्णित किया जा सकता है। एकपदीय समुच्चय को परिभाषित किया जाता है:

M ≜ {x₁^(a₁)...xₘ^(aₘ) | (a₁,...,aₘ) ∈ F₂ᵐ}

ह्रासमान एकपदीय कोड

सूचना समुच्चय I⊆M ह्रासमान है, यदि ∀f≼g और g∈I, तो f∈I। यहाँ ≼ एकपदीय के आंशिक क्रम संबंध को दर्शाता है।

मुख्य एल्गोरिथ्म

1. बिट-प्रतिलोमन संक्षिप्तकरण ध्रुवीय कोड

प्रमेय 2: मान लीजिए C(I,Y'ᵢ) लंबाई N=2ᵐ का संक्षिप्तकरण ह्रासमान r-क्रम ध्रुवीय कोड है, संक्षिप्तकरण पैटर्न Y'ᵢ के साथ। r डिग्री के एकपदीय f के लिए, न्यूनतम भार d=2^(m-r) के कोडवर्ड की संख्या है:

|Tf(d,Y'ᵢ)| = λf(1 - βf(i)/2ʳ)

जहाँ βf(i) Y'ᵢ में f के कारकों की संख्या है।

एल्गोरिथ्म 1 प्रक्रिया का वर्णन करता है:

  • जटिलता: O(|Y'||Iᵣ|) = O(N²)
  • प्रत्येक r डिग्री के एकपदीय f के लिए, इसके संक्षिप्तकृत कारकों की संख्या की गणना करें
  • शेष कोडवर्ड संख्या को पुनरावृत्तिपूर्वक अद्यतन करें

2. QUP ध्रुवीय कोड

लेम्मा 5 के माध्यम से Pf(d,a) की गणना के लिए पुनरावृत्त समीकरण स्थापित करता है:

एकपदीय f = xᵢ₁...xᵢₜ के लिए, Nf(w,a) को पहले a बिट्स में भार w के कोडवर्ड की संख्या के रूप में परिभाषित करें, तो:

  • जब a ≤ 2^(it-1), w≠0: Nf(w,a) = Σₛ∈B(f,t) 2^αf(s)Nf(s)(w,a) + Nf(0)(w,a)
  • जब 2^(it-1) < a ≤ 2^it: Nf(w,a) = Nf(2^(it-t) - w, 2^it - a)
  • जब a > 2^it: Nf(w,a) = Nf(w - 2^(it-t), a - 2^it)

3. पूर्व-परिवर्तन ध्रुवीय कोड औसत भार स्पेक्ट्रम

प्रमेय 7 पूर्व-परिवर्तन ध्रुवीय कोड का औसत भार स्पेक्ट्रम देता है:

E[N(d,T,X)] = Σ₁≤j≤K 2^(K-j)Ad(m,(0₁^(Ij-1),1),X) / 2^(N-Ij)

एल्गोरिथ्म 3 के माध्यम से कार्यान्वित, जटिलता O(N³) है।

तकनीकी नवाचार बिंदु

  1. एकीकृत रूपरेखा: पहली बार कई दर मिलान पैटर्न के लिए एकीकृत भार स्पेक्ट्रम विश्लेषण रूपरेखा प्रदान करता है।
  2. बहुपद जटिलता: सभी एल्गोरिथ्म बहुपद जटिलता प्राप्त करते हैं, पारंपरिक घातीय जटिलता की सीमा को तोड़ते हैं।
  3. समरूपता का उपयोग: कोडवर्ड की समरूपता गुणों का कुशलतापूर्वक उपयोग करके गणना को सरल बनाता है, जैसे Wang-Liu संक्षिप्तकरण QUP की समरूपता के माध्यम से प्राप्त किया जा सकता है।
  4. पुनरावृत्ति अपघटन: लंबाई N के कोड को दो लंबाई N/2 के उप-कोड में विघटित करके गणना जटिलता को कम करता है।

प्रायोगिक सेटअप

डेटासेट और पैरामीटर

  • कोड लंबाई: N = 32, 96, 768, 896 आदि
  • सूचना बिट्स: K = 24, 48, 72, 192, 384, 576 आदि
  • सूचना समुच्चय चयन: गॉसियन सन्निकटन (GA) विधि पर आधारित
  • पूर्व-परिवर्तन: PC-polar कोड (5 लंबाई चक्रीय शिफ्ट रजिस्टर का उपयोग)

मूल्यांकन मेट्रिक्स

  • न्यूनतम भार dₘᵢₙ और न्यूनतम भार कोडवर्ड संख्या Aₘᵢₙ
  • संघ सीमा (Union Bound) गणना से त्रुटि ब्लॉक दर (BLER)
  • SCL विकोडन (सूची आकार 32) का वास्तविक प्रदर्शन

तुलना विधियां

  • SCL विकोडन द्वारा एकत्रित भार स्पेक्ट्रम
  • पारंपरिक घातीय जटिलता सटीक गणना विधि
  • संभाव्य विधि के अनुमानित परिणाम

प्रायोगिक परिणाम

मुख्य परिणाम

तालिका 2 सैद्धांतिक गणना और SCL विकोडन एकत्र परिणामों की तुलना दिखाती है:

  • जब विलोपन बिट्स कम होते हैं, तो सैद्धांतिक निचली सीमा वास्तविक मान के साथ पूरी तरह मेल खाती है
  • विलोपन बिट्स बढ़ने पर, निचली सीमा वास्तविक मान से काफी कम हो सकती है, क्योंकि उच्च भार कोडवर्ड विलोपन के बाद निम्न भार में बदल सकते हैं

तालिका 3 विभिन्न कोड के न्यूनतम भार और न्यूनतम भार कोडवर्ड संख्या प्रदर्शित करती है:

  • QUP: dₘᵢₙ = 12, Aₘᵢₙ = 56 (96,24 कोड)
  • Wang-Liu संक्षिप्तकरण: dₘᵢₙ = 16, Aₘᵢₙ = 292
  • बिट-प्रतिलोमन संक्षिप्तकरण: dₘᵢₙ = 16, Aₘᵢₙ = 490

प्रदर्शन सत्यापन

चित्र 1-8 संघ सीमा और SCL विकोडन प्रदर्शन की तुलना दिखाते हैं:

  • उच्च संकेत-से-शोर अनुपात पर, सैद्धांतिक संघ सीमा वास्तविक SCL प्रदर्शन के साथ उच्च रूप से मेल खाती है
  • पूर्व-परिवर्तन ध्रुवीय कोड के लिए, औसत भार स्पेक्ट्रम समान रूप से प्रदर्शन की सटीक भविष्यवाणी कर सकता है
  • प्रस्तावित विधि की सटीकता और व्यावहारिकता को सत्यापित करता है

जटिलता विश्लेषण

  • एल्गोरिथ्म 1 (बिट-प्रतिलोमन संक्षिप्तकरण): O(N²)
  • एल्गोरिथ्म 2 (QUP): O(N³)
  • एल्गोरिथ्म 3 (पूर्व-परिवर्तन औसत स्पेक्ट्रम): O(N³)

संबंधित कार्य

ध्रुवीय कोड भार स्पेक्ट्रम अनुसंधान

  • Bardet आदि ने ध्रुवीय कोड को ह्रासमान एकपदीय कोड के रूप में माना, LTA स्वसंरूपता लागू करके न्यूनतम भार कोडवर्ड संख्या निर्धारित की
  • बाद के अनुसंधान ने 1.5wₘᵢₙ और 2wₘᵢₙ से नीचे भार के कोडवर्ड संख्या को परिमाणित किया

एल्गोरिथ्मिक विधियां

  • SCL विकोडन द्वारा निम्न भार कोडवर्ड एकत्र करने की विधि
  • बहुपद जटिलता की संभाव्य सन्निकटन विधि
  • गणना जटिलता को कम करने के लिए वृक्ष प्रतिच्छेदन विधि

पूर्व-परिवर्तन ध्रुवीय कोड

  • CRC-सहायक, समता जांच, PAC कोड आदि पूर्व-परिवर्तन विधियां
  • ऊपरी त्रिकोणीय पूर्व-परिवर्तन कोड दूरी को कम न करने का सैद्धांतिक प्रमाण
  • औसत भार स्पेक्ट्रम के पुनरावृत्ति सूत्र

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. दर-संगत ध्रुवीय कोड के भार स्पेक्ट्रम की संपूर्ण सैद्धांतिक रूपरेखा स्थापित करता है
  2. बहुपद जटिलता के कुशल एल्गोरिथ्म प्रदान करता है
  3. सैद्धांतिक भविष्यवाणी वास्तविक प्रदर्शन के साथ उच्च रूप से मेल खाती है, विशेष रूप से उच्च संकेत-से-शोर अनुपात पर

सीमाएं

  1. बड़ी मात्रा में विलोपन की स्थिति में, न्यूनतम भार कोडवर्ड संख्या की निचली सीमा पर्याप्त रूप से तंग नहीं हो सकती है
  2. एल्गोरिथ्म जटिलता यद्यपि बहुपद है, अत्यंत लंबे कोड के लिए अभी भी गणना चुनौतियों का सामना कर सकती है
  3. मुख्य रूप से ह्रासमान ध्रुवीय कोड पर केंद्रित है, गैर-ह्रासमान कोड के लिए प्रयोज्यता सीमित है

भविष्य की दिशाएं

  1. विलोपन कोड भार स्पेक्ट्रम के तंग सीमा अनुमान में सुधार करना
  2. अधिक सामान्य ध्रुवीय कोड निर्माण विधियों तक विस्तार करना
  3. भार स्पेक्ट्रम और अन्य प्रदर्शन संकेतकों के बीच संबंध का अध्ययन करना

गहन मूल्यांकन

शक्तियां

  1. सैद्धांतिक पूर्णता: पहली बार कई दर मिलान पैटर्न के लिए एकीकृत सैद्धांतिक रूपरेखा प्रदान करता है, महत्वपूर्ण सैद्धांतिक अंतराल को भरता है
  2. एल्गोरिथ्मिक दक्षता: बहुपद जटिलता का कार्यान्वयन एक बड़ी सफलता है, जो बड़े कोड लंबाई के भार स्पेक्ट्रम गणना को संभव बनाता है
  3. प्रायोगिक सत्यापन: पर्याप्त सिमुलेशन सत्यापन सिद्धांत की सटीकता की पुष्टि करता है, विशेष रूप से संघ सीमा और वास्तविक प्रदर्शन के मेल की डिग्री
  4. व्यावहारिक मूल्य: विधि ध्रुवीय कोड प्रदर्शन भविष्यवाणी और अनुकूलन डिजाइन के लिए सीधे लागू की जा सकती है

कमियां

  1. निचली सीमा शिथिलता: उच्च विलोपन दर स्थितियों के लिए, सैद्धांतिक निचली सीमा वास्तविक मान को काफी कम आंक सकती है
  2. प्रयोज्यता श्रेणी: मुख्य रूप से ह्रासमान ध्रुवीय कोड पर लागू होता है, सार्वभौमिकता को सीमित करता है
  3. जटिलता: यद्यपि बहुपद है, O(N³) अति-लंबे कोड के लिए अभी भी चुनौतीपूर्ण हो सकता है

प्रभाव

  1. शैक्षणिक योगदान: ध्रुवीय कोड सिद्धांत के लिए महत्वपूर्ण विश्लेषण उपकरण प्रदान करता है, इस क्षेत्र के सैद्धांतिक विकास को आगे बढ़ाता है
  2. व्यावहारिक मूल्य: 5G/6G संचार प्रणाली में ध्रुवीय कोड के डिजाइन और अनुकूलन के लिए सैद्धांतिक समर्थन प्रदान करता है
  3. पद्धतिविज्ञान: बहुपद जटिलता एल्गोरिथ्म डिजाइन के विचार अन्य कोडिंग सिद्धांत समस्याओं के लिए संदर्भ मूल्य रखते हैं

प्रयोज्य परिदृश्य

  1. संचार प्रणाली डिजाइन: 5G NR, उपग्रह संचार आदि जहां दर-संगत ध्रुवीय कोड की आवश्यकता होती है
  2. प्रदर्शन विश्लेषण: ध्रुवीय कोड प्रदर्शन की तीव्र और सटीक भविष्यवाणी की आवश्यकता वाले अनुप्रयोग
  3. कोडवर्ड अनुकूलन: भार स्पेक्ट्रम के आधार पर ध्रुवीय कोड निर्माण और पैरामीटर अनुकूलन

संदर्भ

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