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

হার-সামঞ্জস্যপূর্ণ পোলার কোডের ওজন বর্ণালী সম্পর্কে

মৌলিক তথ্য

  • পেপার আইডি: 2410.19242
  • শিরোনাম: On the Weight Spectrum of Rate-Compatible Polar Codes
  • লেখক: Zicheng Ye, Yuan Li, Zhichao Liu, Huazi Zhang, Jun Wang, Guiying Yan, Zhiming Ma
  • শ্রেণীবিভাগ: cs.IT math.IT
  • প্রকাশনার সময়: ২০২৪ সালের অক্টোবর
  • পেপার লিঙ্ক: https://arxiv.org/abs/2410.19242

সারসংক্ষেপ

ওজন বর্ণালী ত্রুটি সংশোধনকারী কোডের কর্মক্ষমতায় গুরুত্বপূর্ণ ভূমিকা পালন করে। যদিও মাতৃ কোড দৈর্ঘ্যের পোলার কোডের উপর ব্যাপক তাত্ত্বিক অনুসন্ধান করা হয়েছে, তবুও হার-সামঞ্জস্যপূর্ণ পোলার কোডের ওজন বর্ণালী কাঠামো এখনও অধরা রয়েছে। এই নিবন্ধটি আধা-সমান বিলোপন, ওয়াং-লিউ সংক্ষিপ্তকরণ এবং বিট-বিপরীত সংক্ষিপ্তকরণ হ্রাসকারী পোলার কোডের ন্যূনতম ওজন কোডওয়ার্ড সংখ্যা গণনার তাত্ত্বিক ফলাফল উপস্থাপন করে এই ফাঁক পূরণ করে। অতিরিক্তভাবে, আমরা এলোমেলো উপরের ত্রিভুজাকার পূর্ব-রূপান্তর সংক্ষিপ্তকরণ এবং বিলোপন পোলার কোডের গড় বর্ণালী গণনার জন্য একটি দক্ষ অ্যালগরিদম প্রস্তাব করি। উল্লেখযোগ্যভাবে, আমাদের অ্যালগরিদম কোড দৈর্ঘ্যের সাপেক্ষে বহুপদী জটিলতা রয়েছে। সিমুলেশন ফলাফল আমাদের আবিষ্কারগুলি হার-সামঞ্জস্যপূর্ণ পোলার কোডের কর্মক্ষমতার জন্য নির্ভুল অনুমান প্রদান করে তা নিশ্চিত করে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার পটভূমি

  1. পোলার কোডের সীমাবদ্ধতা: পোলার কোড তার ক্রোনেকার পণ্যের অন্তর্নিহিত কাঠামোর কারণে, মূল কোড দৈর্ঘ্য ২ এর শক্তিতে সীমাবদ্ধ। তবে, ব্যবহারিক প্রয়োগে সাধারণত বিভিন্ন কোড দৈর্ঘ্যের বার্তা প্রেরণের প্রয়োজন হয়, যা প্রয়োজনীয় কোড দৈর্ঘ্যের নমনীয়তা প্রদানের জন্য বিলোপন (puncturing) এবং সংক্ষিপ্তকরণ (shortening) কৌশল প্রয়োজন।
  2. ওজন বর্ণালীর গুরুত্ব: ওজন বর্ণালী সর্বোচ্চ সম্ভাবনা (ML) ডিকোডিং কর্মক্ষমতায় উল্লেখযোগ্য প্রভাব ফেলে এবং নিম্ন ওজন কোডওয়ার্ড সংখ্যার উপর ভিত্তি করে সংযুক্ত সীমানার মাধ্যমে অনুমান করা যায়। তবে, নির্ভুল ওজন বর্ণালী গণনার জটিলতা সাধারণত কোড দৈর্ঘ্যের সাথে সূচকীয়ভাবে বৃদ্ধি পায়।
  3. বিদ্যমান গবেষণার অপর্যাপ্ততা: যদিও মাতৃ কোড দৈর্ঘ্যের পোলার কোডের ওজন বর্ণালী সম্পর্কে ব্যাপক গবেষণা রয়েছে, তবুও হার-সামঞ্জস্যপূর্ণ পোলার কোডের ওজন বর্ণালীর একটি সুসংগত কাঠামো এখনও অনুপস্থিত। বিদ্যমান পদ্ধতিগুলি হয় অত্যধিক জটিল বা সীমিত প্রয়োগযোগ্যতা রয়েছে।

গবেষণা প্রেরণা

এই নিবন্ধটির লক্ষ্য হার-সামঞ্জস্যপূর্ণ পোলার কোডের ওজন বর্ণালী তত্ত্বের ফাঁক পূরণ করা এবং আধা-সমান বিলোপন (QUP), ওয়াং-লিউ সংক্ষিপ্তকরণ এবং বিট-বিপরীত সংক্ষিপ্তকরণ পোলার কোডের জন্য একটি সুসংগত ওজন বর্ণালী বিশ্লেষণ কাঠামো প্রদান করা।

মূল অবদান

  1. তাত্ত্বিক অবদান: QUP, ওয়াং-লিউ সংক্ষিপ্তকরণ এবং বিট-বিপরীত সংক্ষিপ্তকরণ হ্রাসকারী পোলার কোডের ন্যূনতম ওজন কোডওয়ার্ড সংখ্যা গণনার জন্য একটি সম্পূর্ণ তাত্ত্বিক কাঠামো এবং সূত্র প্রস্তাব করা।
  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। এখানে ≼ মনোমিয়ালের আংশিক ক্রম সম্পর্ক নির্দেশ করে।

মূল অ্যালগরিদম

১. বিট-বিপরীত সংক্ষিপ্তকরণ পোলার কোড

উপপাদ্য ২: ধরুন 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 এর ফ্যাক্টর সংখ্যা।

অ্যালগরিদম ১ গণনা প্রক্রিয়া বর্ণনা করে:

  • জটিলতা: O(|Y'||Iᵣ|) = O(N²)
  • প্রতিটি r ডিগ্রির মনোমিয়াল f এর জন্য, এর সংক্ষিপ্তকৃত ফ্যাক্টর সংখ্যা গণনা করুন
  • অবশিষ্ট কোডওয়ার্ড সংখ্যা পুনরাবৃত্তিমূলকভাবে আপডেট করুন

২. QUP পোলার কোড

লেম্মা ৫ এর মাধ্যমে 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)

৩. পূর্ব-রূপান্তরিত পোলার কোডের গড় ওজন বর্ণালী

উপপাদ্য ৭ পূর্ব-রূপান্তরিত পোলার কোডের গড় ওজন বর্ণালী প্রদান করে:

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

অ্যালগরিদম ৩ এর মাধ্যমে বাস্তবায়িত, জটিলতা O(N³)।

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

  1. একীভূত কাঠামো: প্রথমবারের মতো একাধিক হার-মিলান প্যাটার্নের জন্য একীভূত ওজন বর্ণালী বিশ্লেষণ কাঠামো প্রদান করা।
  2. বহুপদী জটিলতা: সমস্ত অ্যালগরিদম বহুপদী জটিলতা অর্জন করে, ঐতিহ্যবাহী সূচকীয় জটিলতার সীমাবদ্ধতা অতিক্রম করে।
  3. প্রতিসাম্য ব্যবহার: কোডওয়ার্ডের প্রতিসাম্য বৈশিষ্ট্য কৌশলগতভাবে ব্যবহার করে গণনা সরল করা, যেমন ওয়াং-লিউ সংক্ষিপ্তকরণ QUP এর প্রতিসাম্যের মাধ্যমে পাওয়া যায়।
  4. পুনরাবৃত্তিমূলক বিয়োজন: দৈর্ঘ্য N এর কোডকে দুটি দৈর্ঘ্য N/2 এর সাব-কোডে বিয়োজন করে গণনা জটিলতা হ্রাস করা।

পরীক্ষামূলক সেটআপ

ডেটাসেট এবং পরামিতি

  • কোড দৈর্ঘ্য: N = 32, 96, 768, 896 ইত্যাদি
  • তথ্য বিট সংখ্যা: K = 24, 48, 72, 192, 384, 576 ইত্যাদি
  • তথ্য সেট নির্বাচন: গাউসিয়ান অনুমান (GA) পদ্ধতির উপর ভিত্তি করে
  • পূর্ব-রূপান্তর: PC-polar কোড (৫ দৈর্ঘ্যের চক্রীয় শিফট রেজিস্টার ব্যবহার করে)

মূল্যায়ন মেট্রিক্স

  • ন্যূনতম ওজন dₘᵢₙ এবং ন্যূনতম ওজন কোডওয়ার্ড সংখ্যা Aₘᵢₙ
  • সংযুক্ত সীমানা (Union Bound) গণনার ব্লক ত্রুটি হার (BLER)
  • SCL ডিকোডিং (তালিকা আকার ৩২) এর প্রকৃত কর্মক্ষমতা

তুলনামূলক পদ্ধতি

  • SCL ডিকোডিং সংগ্রহ করা ওজন বর্ণালী
  • ঐতিহ্যবাহী সূচকীয় জটিলতা নির্ভুল গণনা পদ্ধতি
  • সম্ভাব্যতামূলক পদ্ধতির আনুমানিক ফলাফল

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

সারণী ২ তাত্ত্বিক গণনা এবং SCL ডিকোডিং সংগ্রহ ফলাফলের তুলনা প্রদর্শন করে:

  • বিলোপন বিট সংখ্যা কম হলে, তাত্ত্বিক নিম্ন সীমা এবং প্রকৃত মান সম্পূর্ণভাবে সামঞ্জস্যপূর্ণ
  • বিলোপন বিট সংখ্যা বৃদ্ধি পেলে, নিম্ন সীমা প্রকৃত মানের চেয়ে উল্লেখযোগ্যভাবে ছোট হতে পারে, কারণ উচ্চ ওজন কোডওয়ার্ড বিলোপনের পরে নিম্ন ওজনে পরিণত হতে পারে

সারণী ৩ বিভিন্ন কোডের ন্যূনতম ওজন এবং ন্যূনতম ওজন কোডওয়ার্ড সংখ্যা প্রদর্শন করে:

  • QUP: dₘᵢₙ = 12, Aₘᵢₙ = 56 (96,24 কোড)
  • ওয়াং-লিউ সংক্ষিপ্তকরণ: dₘᵢₙ = 16, Aₘᵢₙ = 292
  • বিট-বিপরীত সংক্ষিপ্তকরণ: dₘᵢₙ = 16, Aₘᵢₙ = 490

কর্মক্ষমতা যাচাইকরণ

চিত্র ১-৮ সংযুক্ত সীমানা এবং SCL ডিকোডিং কর্মক্ষমতার তুলনা প্রদর্শন করে:

  • উচ্চ সংকেত-থেকে-শব্দ অনুপাতে, তাত্ত্বিক সংযুক্ত সীমানা এবং প্রকৃত SCL কর্মক্ষমতা অত্যন্ত সামঞ্জস্যপূর্ণ
  • পূর্ব-রূপান্তরিত পোলার কোডের জন্য, গড় ওজন বর্ণালী একইভাবে কর্মক্ষমতা নির্ভুলভাবে পূর্বাভাস দিতে পারে
  • প্রস্তাবিত পদ্ধতির নির্ভুলতা এবং ব্যবহারিকতা যাচাই করে

জটিলতা বিশ্লেষণ

  • অ্যালগরিদম ১ (বিট-বিপরীত সংক্ষিপ্তকরণ): O(N²)
  • অ্যালগরিদম ২ (QUP): O(N³)
  • অ্যালগরিদম ৩ (পূর্ব-রূপান্তর গড় বর্ণালী): O(N³)

সম্পর্কিত কাজ

পোলার কোড ওজন বর্ণালী গবেষণা

  • Bardet এবং অন্যরা পোলার কোডকে হ্রাসকারী মনোমিয়াল কোড হিসাবে বিবেচনা করে, ন্যূনতম ওজন কোডওয়ার্ড সংখ্যা নির্ধারণের জন্য LTA স্বয়ংরূপতা প্রয়োগ করেন
  • পরবর্তী গবেষণা 1.5wₘᵢₙ এবং 2wₘᵢₙ এর নিচে ওজনের কোডওয়ার্ড সংখ্যা পরিমাণ করে

অ্যালগরিদমিক পদ্ধতি

  • SCL ডিকোডিং সংগ্রহ নিম্ন ওজন কোডওয়ার্ডের পদ্ধতি
  • বহুপদী জটিলতার সম্ভাব্যতামূলক আনুমানিক পদ্ধতি
  • গণনা জটিলতা হ্রাস করার জন্য গাছ ছেদ পদ্ধতি

পূর্ব-রূপান্তরিত পোলার কোড

  • CRC সহায়তা, প্যারিটি চেক, PAC কোড ইত্যাদি পূর্ব-রূপান্তর পদ্ধতি
  • উপরের ত্রিভুজাকার পূর্ব-রূপান্তর কোড দূরত্ব হ্রাস না করার তাত্ত্বিক প্রমাণ
  • গড় ওজন বর্ণালীর পুনরাবৃত্তিমূলক সূত্র

উপসংহার এবং আলোচনা

প্রধান উপসংহার

১. হার-সামঞ্জস্যপূর্ণ পোলার কোডের ওজন বর্ণালীর সম্পূর্ণ তাত্ত্বিক কাঠামো প্রতিষ্ঠা করা २. বহুপদী জটিলতার দক্ষ অ্যালগরিদম প্রদান করা ३. তাত্ত্বিক পূর্বাভাস এবং প্রকৃত কর্মক্ষমতা অত্যন্ত সামঞ্জস্যপূর্ণ, বিশেষত উচ্চ সংকেত-থেকে-শব্দ অনুপাতে

সীমাবদ্ধতা

१. বৃহৎ পরিমাণ বিলোপনের ক্ষেত্রে, ন্যূনতম ওজন কোডওয়ার্ড সংখ্যার নিম্ন সীমা যথেষ্ট কঠোর নাও হতে পারে २. অ্যালগরিদম জটিলতা বহুপদী হলেও, অত্যন্ত দীর্ঘ কোডের জন্য এখনও গণনা চ্যালেঞ্জের সম্মুখীন হতে পারে ३. প্রধানত হ্রাসকারী পোলার কোডের উপর ফোকাস করে, অ-হ্রাসকারী কোডের প্রতি প্রয়োগযোগ্যতা সীমিত

ভবিষ্যত দিকনির্দেশনা

१. বিলোপন কোডের ওজন বর্ণালীর কঠোর সীমানা অনুমান উন্নত করা २. আরও সাধারণ পোলার কোড নির্মাণ পদ্ধতিতে সম্প্রসারণ করা ३. ওজন বর্ণালী এবং অন্যান্য কর্মক্ষমতা সূচকের মধ্যে সম্পর্ক গবেষণা করা

গভীর মূল্যায়ন

সুবিধা

१. তাত্ত্বিক সম্পূর্ণতা: প্রথমবারের মতো একাধিক হার-মিলান প্যাটার্নের জন্য একীভূত তাত্ত্বিক কাঠামো প্রদান করে, গুরুত্বপূর্ণ তাত্ত্বিক ফাঁক পূরণ করে २. অ্যালগরিদমিক দক্ষতা: বহুপদী জটিলতা অর্জন একটি প্রধান অগ্রগতি, যা বড় কোড দৈর্ঘ্যের ওজন বর্ণালী গণনা সম্ভব করে ३. পরীক্ষামূলক যাচাইকরণ: পর্যাপ্ত সিমুলেশন যাচাইকরণ তত্ত্বের নির্ভুলতা নিশ্চিত করে, বিশেষত সংযুক্ত সীমানা এবং প্রকৃত কর্মক্ষমতার সামঞ্জস্যতা ४. ব্যবহারিক মূল্য: পদ্ধতি সরাসরি পোলার কোড কর্মক্ষমতা পূর্বাভাস এবং অপ্টিমাইজেশন ডিজাইনে ব্যবহার করা যায়

অপূর্ণতা

१. নিম্ন সীমানা শিথিলতা: উচ্চ বিলোপন হার ক্ষেত্রে, তাত্ত্বিক নিম্ন সীমা প্রকৃত মান উল্লেখযোগ্যভাবে কম অনুমান করতে পারে २. প্রয়োগযোগ্যতার পরিসীমা: প্রধানত হ্রাসকারী পোলার কোডে প্রয়োগযোগ্য, সর্বজনীনতা সীমিত করে ३. জটিলতা: যদিও বহুপদী, তবুও O(N³) অতি-দীর্ঘ কোডের জন্য চ্যালেঞ্জ উপস্থাপন করে

প্রভাব

१. একাডেমিক অবদান: পোলার কোড তত্ত্বের জন্য গুরুত্বপূর্ণ বিশ্লেষণ সরঞ্জাম প্রদান করে, এই ক্ষেত্রের তাত্ত্বিক উন্নয়ন অগ্রসর করে २. ব্যবহারিক মূল্য: ৫G/৬G যোগাযোগ ব্যবস্থায় পোলার কোডের ডিজাইন এবং অপ্টিমাইজেশনের জন্য তাত্ত্বিক সমর্থন প্রদান করে ३. পদ্ধতিবিদ্যা: বহুপদী জটিলতা অ্যালগরিদম ডিজাইনের চিন্তাভাবনা অন্যান্য কোডিং তত্ত্ব সমস্যার জন্য শিক্ষামূলক মূল্য রাখে

প্রযোজ্য পরিস্থিতি

१. যোগাযোগ ব্যবস্থা ডিজাইন: ৫G NR, স্যাটেলাইট যোগাযোগ ইত্যাদি হার-সামঞ্জস্যপূর্ণ পোলার কোডের প্রয়োজনীয় পরিস্থিতি २. কর্মক্ষমতা বিশ্লেষণ: পোলার কোড কর্মক্ষমতা দ্রুত এবং নির্ভুলভাবে পূর্বাভাস দেওয়ার প্রয়োজনীয় প্রয়োগ ३. কোডওয়ার্ড অপ্টিমাইজেশন: ওজন বর্ণালীর উপর ভিত্তি করে পোলার কোড নির্মাণ এবং পরামিতি অপ্টিমাইজেশন

সংদর্ভ

নিবন্ধটি ৪০টি গুরুত্বপূর্ণ সংদর্ভ উদ্ধৃত করে, যা পোলার কোড মৌলিক তত্ত্ব, ওজন বর্ণালী বিশ্লেষণ, পূর্ব-রূপান্তর প্রযুক্তি এবং হার-মিলান সহ মূল ক্ষেত্রগুলি অন্তর্ভুক্ত করে, গবেষণার জন্য একটি দৃঢ় তাত্ত্বিক ভিত্তি প্রদান করে।