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

کدهای بررسی توازن با چگالی کم (LDPC)

معرفی‌شده توسط
Robert Gallager
سال
1962
نوع
linear error-correcting code
خانواده
Coding theory

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

اندازه قلم

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

کدهای LDPC که توسط رابرت گالاگر در سال ۱۹۶۲ ابداع و در دهه ۱۹۹۰ توسط مک‌کی بازکشف شدند، کدهای تصحیح خطای خطی هستند که توسط ماتریس‌های بررسی توازن تنک تعریف می‌شوند. این کدها با رمزگشایی تکراری انتشار باور، عملکردی در محدوده ۰.۴ دسی‌بل از حد شانون را به دست می‌آورند و به استاندارد برای شبکه‌های بی‌سیم مدرن (WiFi-6، 5G NR، پخش ویدیوی دیجیتال) تبدیل شده‌اند. برخلاف کدهای توربو، کدهای LDPC ساختار نظریه گرافی ظریف‌تر و تحلیل نظری بالغ‌تری دارند.

شهود پشت روش

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

تاریخ

گالاگر کدهای LDPC را در سال ۱۹۶۲ ابداع کرد، اما نظریه از پیاده‌سازی عملی عقب ماند. در سال ۱۹۹۵، مک‌کی آن‌ها را بازکشف کرد و عملکرد نزدیک به شانون آن‌ها را از طریق شبیه‌سازی‌ها نشان داد. تحقیقات گسترده در دهه ۲۰۰۰ الگوریتم‌های کارآمد کدگذاری، رمزگشایی و ساخت گراف را توسعه داد. کدهای LDPC در WiFi-6 (802.11ax, 2021) و استاندارد 5G NR (2018) پذیرفته شدند. آن‌ها به دلیل عملکرد بهتر و ساختار شفاف‌تر، در سیستم‌های جدید رایج‌تر از کدهای توربو شده‌اند.

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

کدهای LDPC به دلیل عملکرد بهتر و معماری ساده‌تر، در سیستم‌های مدرن بر کدهای توربو ترجیح داده می‌شوند. از LDPC برای طیف وسیعی از SNR (بدون آستانه ناگهانی) استفاده کنید؛ آن‌ها از SNR پایین تا بالا به خوبی کار می‌کنند. LDPC استاندارد برای WiFi-6، ماهواره و 5G NR است. تنها در صورتی از LDPC اجتناب کنید که سازگاری با سیستم‌های قدیمی به کدهای توربو نیاز داشته باشد. LDPC همچنین برای بسته‌های بسیار کوتاه (>30 بیت) مناسب است زیرا ساختار کد قابل تفکیک است.

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

  • ساخت گراف و ذخیره‌سازی ماتریس برای کدهای بسیار بلند (>10k بیت) پیچیده می‌شود
  • عملکرد حساس به ساختارهای گراف در مقیاس کوچک (دورها، مجموعه‌های جاذب)؛ نیاز به طراحی دقیق دارد
  • انتشار باور فرض می‌کند گراف بدون حلقه است، اما گراف‌ها دارای چرخه‌اند؛ همگرایی به راه‌حل بهینه تضمین نمی‌شود
  • تأخیر رمزگشایی (تکرارها) به صورت لگاریتمی با SNR رشد می‌کند؛ مانند برخی کدهای کلاسیک بدون تأخیر نیست
  • کوانتیزاسیون پیام‌ها (در سخت‌افزار با نقطه ثابت) بر عملکرد تأثیر می‌گذارد؛ نیاز به تخصیص دقیق بیت دارد

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

نقاط قوت

  • عملکرد در محدوده ۰.۴ دسی‌بل از حد شانون (کمی بهتر از کدهای توربو)
  • ساختار نظریه گرافی ساده‌تر؛ تحلیل نظری شفاف‌تر از کدهای توربو
  • رمزگشایی تکراری از رفتار آستانه‌ای ناگهانی جلوگیری می‌کند (برخلاف توربو)
  • طراحی کد انعطاف‌پذیر از طریق ساختار گراف؛ آسان برای سفارشی‌سازی برای کاربردهای خاص
  • سخت‌افزار رمزگشایی موازی کارآمد؛ پیام‌رسانی مناسب برای پیاده‌سازی VLSI/GPU
  • هم برای کلمات کد بلند و هم برای کلمات کد با طول متوسط به خوبی کار می‌کند

کاربردها

  • WiFi-6 (802.11ax): شبکه‌های محلی بی‌سیم با توان عملیاتی بالا که LDPC تحویل داده قابل اعتماد را فراهم می‌کند
  • 5G NR: کدگذاری کانال برای هر دو کانال داده و کنترل، جایگزین کدهای توربو از 4G
  • ارتباطات ماهواره‌ای: پخش ویدیوی دیجیتال (DVB-S2) و مأموریت‌های فضایی عمیق با استفاده از LDPC کلمات کد بلند
  • ارتباطات خطوط برق (PLC): انتقال داده قوی بر روی شبکه‌های الکتریکی نویزدار
  • سیستم‌های حافظه فلش: تصحیح خطا برای ذخیره‌سازی فلش NAND بدون فرسایش ناشی از بازسازی مکرر

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

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

1

بیت‌های اطلاعات با استفاده از یک ماتریس بررسی توازن تنک H کدگذاری می‌شوند؛ بیت‌های کدگذاری‌شده، جواب H*c = 0 (mod 2) هستند، که در آن c کلمه کد است.

2

ماتریس بررسی توازن H به گونه‌ای ساختار یافته است که تنک باشد (مثلاً هر سطر/ستون وزن کم ثابت ۳-۵ دارد). این ساختار برای کدگذاری کارآمد مورد بهره‌برداری قرار می‌گیرد.

3

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

4

یک گراف دوبخشی ساخته می‌شود: گره‌های چپ = گره‌های متغیر (بیت‌ها)، گره‌های راست = گره‌های بررسی (معادلات توازن). یال‌ها متغیرها را به بررسی‌هایی که در آن‌ها ظاهر می‌شوند، متصل می‌کنند.

5

انتشار باور تکراری: گره‌های متغیر پیام‌ها را از گره‌های بررسی جمع‌آوری می‌کنند، تخمین‌های بیت را به‌روزرسانی می‌کنند و پیام‌های اصلاح‌شده را بازمی‌گردانند. پس از تکرارها، تصمیمات سخت گرفته می‌شوند؛ اگر بررسی‌های توازن برآورده شوند، رمزگشایی موفقیت‌آمیز است.

دام‌های رایج

  • استفاده از یک گراف تنک با طراحی ضعیف و چرخه‌های کوتاه؛ چرخه‌های کوچک باعث نوسان انتشار باور می‌شوند
  • تکرار بیش از حد فراتر از همگرایی؛ تکرارهای غیرضروری بدون بهبود، انرژی را هدر می‌دهند
  • فرض اینکه رمزگشایی جمع-مین به خوبی جمع-ضرب است؛ تقریب‌ها دارای افت عملکرد هستند، به ویژه در SNR پایین
  • نادیده گرفتن اثرات طول محدود؛ گراف‌های طراحی شده برای تحلیل مجانبی ممکن است در بسته‌های کوتاه عملکرد ضعیفی داشته باشند
  • عدم در نظر گرفتن کوانتیزاسیون در پیاده‌سازی سخت‌افزاری؛ شبیه‌سازی با نقطه شناور با واقعیت نقطه ثابت متفاوت است

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

چه چیزی رمزگشایی LDPC را در مقایسه با کدهای خطی عمومی بسیار کارآمد می‌کند؟

تنکی ماتریس بررسی توازن به این معنی است که هر بیت تنها در چند بررسی توازن شرکت می‌کند. در رمزگشایی، پیام‌رسانی روی گراف دوبخشی خطی در تعداد یال‌ها است، نه طول کد. برای کدهای چگال، رمزگشایی به معکوس ماتریس نیاز دارد که مکعبی در طول کد است. تنکی، رمزگشایی را شبه‌خطی و عملی برای کدهای بلند می‌کند.

مجموعه جاذب چیست و چرا اهمیت دارد؟

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

LDPC چگونه با کدهای قطبی مقایسه می‌شود؟

هر دو به عملکرد نزدیک به شانون دست می‌یابند. کدهای قطبی دارای ساختار بازگشتی و بهینگی قابل اثبات تحت رمزگشایی حذف متوالی در طول کد بی‌نهایت هستند. کدهای LDPC انعطاف‌پذیرتر هستند و به صورت تجربی عملکرد طول محدود بهتری دارند. 5G NR از کدهای قطبی برای کانال‌های کنترل (بسته‌های کوتاه) و LDPC برای کانال‌های داده (بسته‌های بلند) استفاده می‌کند و از نقاط قوت هر کد بهره می‌برد.

چرا دور گراف در کدهای LDPC مهم است؟

دور، طول کوتاه‌ترین چرخه در گراف دوبخشی است. چرخه‌های کوتاه (دور < 6) باعث می‌شوند انتشار باور از اطلاعات همبسته استفاده کند (پیام‌ها به عقب برمی‌گردند) و عملکرد را کاهش می‌دهد. کدهای با دور بالا (دور ≥ 6) همبستگی‌ها را بهتر می‌شکنند. کدها اغلب برای حداکثر کردن دور با توجه به محدودیت‌های تنکی طراحی می‌شوند.

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

منابع

  1. Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.

    باز کردن مرجع DOI
    کپی شد.
  2. Richardson, T. J., & Urbanke, R. L. (2001). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.

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