کد ال‌دی‌پی‌سی

در نظریهٔ اطلاعات، **کد** **وارِسیِ پَریتهٔ کم‌چگال** (Low-density parity-check code, LDPC) - یا به‌اختصار، **کد اِل‌دی‌پی‌سی** - یک کد تصحیح‌کنندهٔ خطای خطی بلوکی است؛ روشی برای انتقال پیام از راه یک کانال نویزی. یک کد ال‌دی‌پی‌سی، به‌کمک یک گراف تانِر (Tanner graph) پراکنده (یک زیرکلاس گراف دوبخشی) ساخته می‌شود. کدهای ال‌دی‌پی‌سی، کدهای نزدیک‌شونده به ظرفیت کانال هستند، یعنی آستانهٔ نویز آنها، در عمل، به بیشینهٔ نظری (حد شانون) کانال بی‌حافظهٔ متقارن، بسیار نزدیک است. آستانهٔ نویز، حد بالای نویز کانال است که تا پیش‌از آن، احتمال از دست رفتن اطلاعات را می‌توان با کد کردن پیام، دلخواه کوچک کرد. با استفاده از روش انتشار باور تکرارشونده (iterative)، شمار محاسبات لازم برای کدگشایی ال‌دی‌پی‌سی، رابطهٔ خطی با طول کد دارد.

کدهای ال‌دی‌پی‌سی، به‌افتخار رابرت گالاگِر - که مفهوم ال‌دی‌پی‌سی را سال ۱۹۶۰ در پایان‌نامهٔ دکترایش در مؤسسه فناوری ماساچوست پیش نهاد و گسترد - به‌نام *کدهای گالاگر* هم شناخته می‌شوند. ازآنجاکه کدهای ال‌دی‌پی‌سی به کدگشایی تکرارشوندهٔ پُرمحاسبات نیاز داشتند، چندین دهه بی‌کاربرد ماندند. در ۱۹۹۳، کدهای توربو اختراع شدند که به‌کمک کدگشایی تکرارشونده، عملکرد بسیار بهتری از کدهای دیگر تا آن زمان داشتند. اما کدهای توربو، ثبت اختراع شده‌بودند و برای استفاده نیاز به پرداخت هزینه داشتند؛ بنابراین، کدهای ال‌دی‌پی‌سی با اقبال روبه‌رو شدند، چراکه نشان داده شده‌بود که عملکرد مشابهی با کدهای توربو دارند و ثبت اختراع هم نشده‌بودند. حتی اکنون هم که دیگر حق ثبت اختراع کدهای توربو برداشته شده‌است (از ۲۹ اوت ۲۰۱۳)، کدهای ال‌دی‌پی‌سی، به‌سبب برتری‌های فنی‌شان، همچنان به‌کار می‌روند.

کدهای ال‌دی‌پی‌سی، ویژگی‌های ترکیبی ایدئال دارند. گالاگر در پایان‌نامه‌اش نشان داد که این کدها، با احتمال زیاد به حد گیلبرت-وارشاموف (Gilbert-Varshamov bound) برای کدهای خطیِ در میدان باینری (binary field) دست می‌یابند. در سال ۲۰۲۰ هم نشان داده‌شد که کدهای ال‌دی‌پی‌سی گالاگر به ظرفیت کدگشایی لیستی، همچنین به حد گیلبرت-وارشاموف برای کدهای خطی در هر میدانی دست می‌یابند.

## تاریخچه
ازآنجاکه کدهای ال‌دی‌پی‌سی - که نخستین بار در ۱۹۶۳ از سوی گالاگر پیشنهاد شدند - عملی نبوند، تا ۱۹۹۶ - که کار او دوباره مورد توجه قرار گرفت - فراموش شدند. کدهای توربو - دستهٔ دیگری از کدهای نزدیک‌شونده به ظرفیت کانال که ۱۹۹۳ کشف شدند - در سال‌های پایانی دههٔ ۹۰ میلادی، روش کدگذاریِ برگزیده شده‌بودند و از آنها در کاربردهایی مانند شبکهٔ فضای دوردست ناسا و مخابرات ماهواره‌ای بهره گرفته‌می‌شد. از آن پس بود که کدهای ال‌دی‌پی‌سی، به‌عنوان جایگزینی که عملکرد مشابه داشتند و از طرفی مشکل حق ثبت اختراع هم نداشتند، با اقبال روبه‌رو شدند. از آن زمان، با پیشرفت‌هایی که کدهای ال‌دی‌پی‌سی از نظر *[[کف خطا|کفِ خطا]]* و عملکرد در نرخ کدهای بزرگتر کردند، از کدهای توربو پیشی گرفتند. کدهای توربو تنها برای نرخ کدهای کوچکتر مناسب‌ترند.

## کاربردها
در سال ۲۰۰۳، یک کد ال‌دی‌پی‌سی به سبک تکرار-انباشت بی‌قاعده (irregular repeat accumulate, IRA)، بر شش کد توربو چیره شد و به‌عنوان کد تصحیح‌کننده خطا در استاندارد جدید DVB-S2 برای تلویزیون دیجیتال برگزیده شد. کمیته گزینش DVB-S2، برای برآورد پیچیدگی کدگشایی کدهای توربو پیشنهادشده، از یک روش کدگشایی سریالی - که در مقایسه با کدگشایی موازی، ناکارآمدتر بود - بهره گرفت. این، کدهای توربوی پیشنهادشده را واداشت تا از فریم‌هایی که طولشان نصف فریم‌های کدهای ال‌دی‌پی‌سی پیشنهادشده بود، استفاده کنند.

در سال ۲۰۰۸، کد ال‌دی‌پی‌سی، کدهای توربو کانولوشنال را به عنوان سیستم تصحیح خطای پیش‌رو (FEC) برای استاندارد ITU-T G.hn شکست داد. G.hn، کدهای ال‌دی‌پی‌سی را به‌جای کدهای توربو برگزید، زیرا پیچیدگی کدگشایی کمتری داشتند (به‌ویژه وقتی با سرعت داده نزدیک به ۱٫۰ گیگابیت‌برثانیه کار می‌کنند)، نیز برای‌این‌که کدهای توربو پیشنهادشده، کفِ خطای (error floor) قابل توجهی در محدوده عملکرد موردنظر دارند.

کدهای ال‌دی‌پی‌سی همچنین برای اِتِرنت 10GBASE-T استفاده می‌شوند که داده‌ها را با سرعت ۱۰ گیگابیت‌درثانیه از راه کابل زوجِ به‌هم‌تابیده منتقل می‌کند. از ۲۰۰۹، کدهای ال‌دی‌پی‌سی نیز بخشی از استاندارد Wi-Fi 802.11 به‌عنوان بخشی اختیاری از 802.11n و 802.11ac، در مشخصات لایهٔ فیزیکی شبکه (PHY) با گذرداد زیاد (high throughput) هستند. ال‌دی‌پی‌سی، همچنین بخش اجباری 802.11ax (Wi-Fi ۶) است.

برخی از سیستم‌های OFDM، یک کد تصحیح خطای بیرونی هم دارند که خطاهای گاه‌به‌گاه را که از تصحیح خطای ال‌دی‌پی‌سی درونی به‌جا مانده‌اند (در اثر کف خطا) - حتی در نرخ‌های خطای بیت کم - برطرف می‌کند (کدهای هم‌پیوسته را ببینید).

برای نمونه، کد رید-سولومون با *کُدمدولاسیون* (coded modulation) ال‌دی‌پی‌سی (RS-LCM)، از یک کد بیرونی رید-سولومون بهره می‌برد. استانداردهای DVB-S2، DVB-T2 و DVB-C2، همگی از کد بیرونی بی‌سی‌اچ برای برطرف کردن خطاهای به‌جامانده از کدگشایی ال‌دی‌پی‌سی بهره می‌برند.

سیستم 5G NR، از کد قطبی برای کانال‌های کنترل و از کد ال‌دی‌پی‌سی برای کانال‌های انتقال داده استفاده می‌کند.

اگرچه کاربرد کد ال‌دی‌پی‌سی برای تصحیح خطا در درایوهای هارددیسک موفق بوده‌است، برای بهره‌گیری کامل از قابلیت تصحیح خطای این کد در درایوهای حالت جامد، سنجش ولتاژ دقیق سلول‌های حافظهٔ این درایوها لازم است، که به افزایش تأخیرِ خواندن از حافظه می‌انجامد. LDPC-in-SSD یک رویکرد برای بهره‌گیری از کد ال‌دی‌پی‌سی و با افزایش اندک تأخیر در این حافظه‌هاست.

:

:

:

:،

## جستارهای وابسته
### اشخاص
* ریچارد همینگ
* کلود شانون
* دیوید مک کی
* اروینگ رید
* مایکل لوبی

### تئوری
* نظریه گراف
* کد همینگ
* کد گراف اسپارس (Sparse graph code)
* کد گسترنده (Expander code)

### کاربردها
* G.hn/G.9960 (استاندارد ITU-T برای شبکه سازی از طریق خطوط برق، خطوط تلفن و کابل کواکسیال)
* 802.3an یا 10GBASE-T (اترنت ۱۰ گیگابیت بر ثانیه روی جفت پیچ خورده)
* CMMB (پخش چند رسانه ای موبایل چین)
* DVB-S2 / DVB-T2 / DVB-C2 (پخش ویدئو دیجیتال، نسل دوم)
* DMB-T/H (پخش ویدئوی دیجیتال)
* وایمکس (استاندارد IEEE 802.16e برای ارتباطات مایکروویو)
* IEEE 802.11n-2009 (استاندارد Wi-Fi)
* DOCSIS 3.1
* ATSC 3.0 (نسل بعدی پخش زمینی دیجیتال آمریکای شمالی)
* 3GPP (کانال داده 5G-NR)

### کدهای دیگر نزدیک‌شونده به ظرفیت کانال
* کدهای آب‌نما (fountain codes)
* کدهای LT
* کدهای آنلاین
* کدهای قطبی
* کدهای رپتور (raptor codes)
* کدهای تکرار-انباشت (repeat-accumulate، دسته‌ای از کدهای توربو ساده)
* کدهای کانولوشنال هم‌پیوستۀ سریال (serial concatenated convolutional codes)
* کدهای تورنادو (کدهای ال‌دی‌پی‌سی برای کدگشایی کانال مخدوش (erasure channel))
* کدهای توربو

## منابع

## پیوند به بیرون
* معرفی کدهای بررسی برابری با چگالی کم (توسط سارا جی جانسون، ۲۰۱۰)
* کدهای LDPC – یک آموزش مختصر (توسط برنهارد لینر، ۲۰۰۵)
* کدهای LDPC (TU Wien)  
* کدهای LDPC: مقدمه (توسط امین شکراللهی، ۱۳۸۲)
* رمزگشایی باور-انتشار کدهای LDPC (توسط امیر بناتان، دانشگاه پرینستون)
* کدهای توربو و LDPC: پیاده‌سازی، شبیه‌سازی و استانداردسازی (دانشگاه ویرجینیای غربی)
* نظریه اطلاعات و کدگذاری (Marko Hennhöfer، ۲۰۱۱، TU Ilmenau) - کدهای LDPC را در صفحات ۷۴–۷۸ مورد بحث قرار می‌دهد.
* کدهای LDPC و نتایج عملکرد
* پیوند DVB-S.2، از جمله کدگذاری LDPC (MatLab)
* کد منبع برای رمزگذاری، رمزگشایی و شبیه‌سازی کدهای LDPC از مکان‌های مختلفی در دسترس است:
** کدهای باینری LDPC در C
** کدهای باینری LDPC برای پایتون (الگوریتم هسته به زبان C)
** رمزگذار LDPC و رمزگشای LDPC در متلب
** جعبه ابزار تصحیح خطا به جلو سریع (AFF3CT) در C++11 برای شبیه‌سازی سریع LDPC

رده:آشکارسازی و اصلاح خطا
رده:نظریه کدگذاری