Skip to content
بازگشت به نتایج جست‌وجو

کدهای قطبی با کدگشایی حذف متوالی

معرفی‌شده توسط
Erdal Arikan
سال
2009
نوع
recursive error-correcting code
خانواده
Coding theory

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

کدهای قطبی که توسط اردال آریکان در سال ۲۰۰۹ معرفی شدند، اولین خانواده سازنده کدها هستند که اثبات شده است به ظرفیت شانون کانال‌های بدون حافظه با ورودی باینری متقارن دست می‌یابند. این کدها از ساختار بازگشتی و کدگشایی حذف متوالی استفاده می‌کنند، که یک الگوریتم حریصانه ساده با تضمین‌های نظری است. کدهای قطبی در 5G NR برای کدگذاری کانال کنترل پذیرفته شدند و برای سیستم‌های 6G آینده مورد مطالعه قرار می‌گیرند. برخلاف کدهای توربو و LDPC (که تجربی هستند)، کدهای قطبی مبانی نظری دقیق ارائه می‌دهند.

شهود پشت روش

کدهای قطبی بر اساس مفهوم قطبش کانال بنا شده‌اند: اعمال یک تبدیل بازگشتی خاص به مجموعه‌ای از کانال‌های مستقل و یکسان، مجموعه‌ای جدید ایجاد می‌کند که در آن برخی کانال‌ها عملاً بدون نویز (ظرفیت ۱) و برخی دیگر عملاً بی‌فایده (ظرفیت ۰) می‌شوند. بیت‌های اطلاعاتی روی کانال‌های بدون نویز قرار می‌گیرند؛ بیت‌های فریز شده (که برای گیرنده شناخته شده‌اند) کانال‌های بی‌فایده را پر می‌کنند. کدگشایی از حذف متوالی استفاده می‌کند: بیت به بیت به ترتیب کدگشایی می‌شود و از بیت‌های قبلاً کدگشایی شده برای بهبود تخمین‌های بیت‌های باقی‌مانده استفاده می‌شود. ساختار بازگشتی تضمین می‌کند که پیچیدگی کدگشایی خطی با طول کد است و ویژگی قطبش عملکرد دستیابی به ظرفیت مجانبی را تضمین می‌کند.

تاریخ

مقاله آریکان در سال ۲۰۰۹ در مورد قطبش کانال تحول‌آفرین بود: برای اولین بار، یک خانواده کد سازنده با پیچیدگی چندجمله‌ای اثبات شد که به ظرفیت دست می‌یابد. تحقیقات بعدی کدگشاهای عملی (انتشار باور، کدگشایی لیستی) را برای رفع کف خطا در SNR متوسط توسعه دادند. کدهای قطبی در 3GPP 5G NR Release 15 برای کانال‌های کنترل (مانند PBCH، DCI) پذیرفته شدند و جایگزین کدهای توربو شدند. برای کانال‌های داده، LDPC به دلیل عملکرد تجربی بهتر در طول بلوک‌های متوسط انتخاب شد. آریکان جایزه مقاله IEEE Information Theory Society را دریافت کرد و کدهای قطبی همچنان یک زمینه تحقیقاتی فعال هستند.

چه زمانی استفاده شود

کدهای قطبی برای طول بسته‌های کوتاه تا متوسط (۱۰۰-۱۰۰۰ بیت) و الزامات تأخیر سخت‌گیرانه (بدون کدگشایی تکراری) ایده‌آل هستند. از کدهای قطبی برای کانال‌های کنترل در 5G/6G یا هر سناریویی که تضمین‌های اثبات‌پذیر دستیابی به ظرفیت را در اولویت قرار می‌دهد، استفاده کنید. از کدهای قطبی برای کلمات کد بسیار طولانی (>10k بیت) که انعطاف‌پذیری LDPC ترجیح داده می‌شود، اجتناب کنید. کدهای قطبی در کانال‌های محو شوندگی بلوکی برتری دارند؛ در محو شوندگی مسطح، مزیت خاصی نسبت به LDPC ندارند.

محدودیت‌ها و ملاحظات

  • حذف متوالی در SNR پایین دارای انتشار خطای نمایی است (کف خطا)
  • طراحی بیت فریز شده نیاز به دانستن SNR کانال از قبل دارد؛ سازگاری لازم است
  • عملکرد در طول بلوک‌های کوتاه بدون اصلاحات هوشمندانه، پایین‌تر از LDPC/توربو است
  • انتشار باور یا کدگشایی لیستی (برای کاهش کف خطا) پیچیدگی را افزایش می‌دهد و به LDPC نزدیک می‌شود
  • اکوسیستم پیاده‌سازی کمتر بالغ در مقایسه با کدهای توربو و LDPC

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • اولین خانواده کد با اثبات سازنده دستیابی به ظرفیت شانون
  • کدگشایی حذف متوالی ساده؛ پیچیدگی زمانی خطی O(N log N)
  • ساختار بازگشتی امکان پیاده‌سازی کارآمد سخت‌افزاری را فراهم می‌کند
  • بدون پردازش تکراری؛ تأخیر قطعی (مهم برای سیستم‌های بلادرنگ)
  • چارچوب نظری برای تحلیل عملکرد و بهینه‌سازی ساختار کد
  • سازگاری ذاتی از طریق انتخاب بیت فریز شده برای SNR و طول بلوک‌های مختلف

کاربردها

  • کانال‌های کنترل 5G NR (PBCH, DCI): انتقال قابل اعتماد بسته کوتاه با محدودیت‌های تأخیر سخت‌گیرانه
  • ارتباطات ماهواره‌ای: کدگذاری ساختاریافته با تأخیر کدگشایی قطعی برای لینک‌های حیاتی
  • توزیع کلید کوانتومی: امنیت نظری ترکیب شده با تصحیح خطای عملی
  • تله‌متری هوافضا: ارتباطات فضاپیما با قابلیت اطمینان فوق‌العاده بالا و تأخیر کدگشایی محدود
  • ارتباطات نوری: لینک‌های با برد کوتاه اما سرعت بالا که در آن‌ها کدگشایی سریع و قطعی ضروری است

چگونه کار می‌کند

چگونه کار می‌کند

1

بیت‌های اطلاعاتی (به علاوه بیت‌های فریز شده) از طریق یک ماتریس مولد که به صورت بازگشتی ساخته شده است (ساختار حاصل‌ضرب کرونکر)، کلمه کد را تشکیل می‌دهند.

2

ماتریس مولد G با حاصل‌ضرب‌های کرونکر مکرر [[1,0],[1,1]] ساخته می‌شود؛ این کار ساختار قطبش بازگشتی را ایجاد می‌کند.

3

بیت‌های کدگذاری شده ارسال می‌شوند؛ بیت‌های دریافتی مقادیر نرم (نسبت‌های لگاریتمی درست‌نمایی از کانال) هستند.

4

کدگشای حذف متوالی بیت‌ها را به صورت متوالی پردازش می‌کند: برای بیت i، نسبت لگاریتمی درست‌نمایی شرطی را با توجه به تمام بیت‌های قبلاً کدگشایی شده و مشاهده کانال محاسبه می‌کند.

5

هر بیت با برش LLR آن (مثبت -> ۱، منفی -> ۰) کدگشایی می‌شود. اگر بیت i فریز شده باشد، از مقدار شناخته شده استفاده می‌شود. بیت‌های کدگشایی شده به جلو تغذیه می‌شوند تا تخمین‌های LLR برای بیت‌های باقی‌مانده را بهبود بخشند.

دام‌های رایج

  • استفاده از حذف متوالی پایه در SNR پایین؛ انتشار باور یا کدگشایی لیستی برای BER معقول ضروری است
  • طراحی مجموعه بیت فریز شده برای شرایط کانال اشتباه؛ اگر SNR واقعی با SNR طراحی متفاوت باشد، عملکرد کاهش می‌یابد
  • فرض پیچیدگی کدگشایی خطی به معنای کدگشایی سریع است؛ هر بیت همچنان نیاز به محاسبه LLR دارد که در مجموع به O(N log N) می‌رسد
  • نادیده گرفتن اثرات کوانتیزاسیون؛ کوانتیزاسیون LLR با نقطه ثابت (به ویژه تصمیمات شاخه‌ای) بر کف خطا تأثیر می‌گذارد
  • عدم بهره‌برداری از سازگاری؛ انتخاب مجدد بیت فریز شده بر اساس بازخورد CSI می‌تواند عملکرد را به طور قابل توجهی بهبود بخشد

پرسش‌های متداول

قطبش کانال چیست و چگونه کدهای دستیابی به ظرفیت را ممکن می‌سازد؟

قطبش کانال N کانال یکسان را به N کانال با ظرفیت‌های قطبی شده تبدیل می‌کند: برخی به ۱ (بدون نویز) و برخی دیگر به ۰ (بی‌فایده) نزدیک می‌شوند. بیت‌های اطلاعاتی روی کانال‌های با ظرفیت بالا محافظت می‌شوند؛ کانال‌های با ظرفیت پایین فریز می‌شوند. با افزایش N، کسر کانال‌های با ظرفیت بالا به ظرفیت شانون نزدیک می‌شود. این ساختار امکان کدگشایی حذف متوالی ساده را برای دستیابی به ظرفیت فراهم می‌کند.

چرا حذف متوالی در SNR پایین دارای کف خطا است؟

حذف متوالی به صورت حریصانه یک بیت را در هر زمان با استفاده از تخمین‌های بیت قبلی کدگشایی می‌کند. اگر یک بیت اولیه به اشتباه کدگشایی شود، خطا به تمام بیت‌های بعدی منتشر می‌شود و باعث آبشار خطاها می‌شود. این کف خطا از وابستگی به تصمیمات گذشته ناشی می‌شود. انتشار باور یا کدگشایی لیستی با بررسی جایگزین‌ها و به تعویق انداختن تصمیمات سخت، این مشکل را کاهش می‌دهد.

بیت‌های فریز شده چگونه انتخاب می‌شوند؟

بیت‌های فریز شده روی کانال‌هایی با اطلاعات متقابل تخمین زده شده پایین (ظرفیت پایین) قرار می‌گیرند. یک روش این است که فرآیند قطبش را برای SNR و طول بلوک هدف شبیه‌سازی کنیم، کانال‌ها را بر اساس ظرفیتشان رتبه‌بندی کنیم، سپس K کانال با کمترین ظرفیت را فریز کنیم. این کار نیاز به دانستن SNR از قبل دارد. کدهای قطبی تطبیقی می‌توانند مجموعه بیت فریز شده را بر اساس بازخورد یا تخمین CSI به‌روزرسانی کنند.

کدگشایی لیستی برای کدهای قطبی چیست؟

به جای اتخاذ یک تصمیم سخت در هر مرحله، کدگشایی لیستی فهرستی از کلمات کد جزئی کاندید را حفظ می‌کند و مسیرهای متعدد را بررسی می‌کند. پس از پردازش تمام بیت‌ها، بهترین مسیر (بر اساس درست‌نمایی) انتخاب می‌شود. این کار کف خطا را به طور قابل توجهی کاهش می‌دهد اما پیچیدگی را به O(L N log N) افزایش می‌دهد که در آن L اندازه لیست است. اندازه لیست ۸-۳۲ معمول است؛ تعادلی خوب بین عملکرد و پیچیدگی.

روش‌های مرتبط

منابع

  1. Arikan, E. (2009). Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Transactions on Information Theory, 55(7), 3051-3073.

    باز کردن مرجع DOI
    کپی شد.
  2. Sasoglu, E., Telatar, I., & Yildirim, E. (2011). Polarization for arbitrary discrete memoryless channels. In Proceedings of the IEEE Information Theory Workshop (ITW), 144-148.

    باز کردن مرجع انتشار
    کپی شد.