کد ال‌دی‌پی‌سی
در نظریهٔ اطلاعات، کد وارِسیِ پَریتهٔ کم‌چگال (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))
- کدهای توربو
منابع
[ویرایش]- ↑ Amin Shokrollahi (2003) LDPC Codes: An Introduction
- ↑ Hardesty, L. (January 21, 2010). "Explained: Gallager codes". MIT News. Retrieved August 7, 2013.
- ↑ Gallager, R.G. (January 1962). "Low density parity check codes". IRE Trans. Inf. Theory. 8 (1): 21–28. doi:10.1109/TIT.1962.1057683.
- ↑ ۴٫۰ ۴٫۱ Erico Guizzo (Mar 1, 2004). "CLOSING IN ON THE PERFECT CODE". IEEE Spectrum. "Another advantage, perhaps the biggest of all, is that the LDPC patents have expired, so companies can use them without having to pay for intellectual-property rights."
- ↑ Mackenzie, D. (9 July 2005). "Communication speed nears terminal velocity". New Scientist.
- ↑ Mosheiff, J.; Resch, N.; Ron-Zewi, N.; Silas, S.; Wootters, M. (2020). "Low-Density Parity-Check Codes Achieve List-Decoding Capacity". SIAM Journal on Computing (FOCS 2020): 38–73. doi:10.1137/20M1365934.
- ↑ David J.C. MacKay and Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes," Electronics Letters, July 1996
- ↑ Telemetry Data Decoding, Design Handbook
- ↑ Presentation by Hughes Systems بایگانی‌شده در ۲۰۰۶-۱۰-۰۸ توسط Wayback Machine
- ↑ HomePNA Blog: G.hn, a PHY For All Seasons
- ↑ IEEE Communications Magazine paper on G.hn بایگانی‌شده در ۲۰۰۹-۱۲-۱۳ توسط Wayback Machine
- ↑ IEEE Standard, section 20.3.11.6 "802.11n-2009", IEEE, October 29, 2009, accessed March 21, 2011.
- ↑ "IEEE SA - IEEE 802.11ax-2021". IEEE Standards Association (به انگلیسی). Archived from the original on 22 May 2022. Retrieved 22 May 2022.
- ↑ Chih-Yuan Yang, Mong-Kai Ku. http://123seminarsonly.com/Seminar-Reports/029/26540350-Ldpc-Coded-Ofdm-Modulation.pdf "LDPC coded OFDM modulation for high spectral efficiency transmission"
- ↑ Nick Wells. "DVB-T2 in relation to the DVB-x2 Family of Standards" بایگانی‌شده در ۲۰۱۳-۰۵-۲۶ توسط Wayback Machine
- ↑ "5G Channel Coding" (PDF). Archived from the original (PDF) on December 6, 2018. Retrieved January 6, 2019.
- ↑ Maunder, Robert (September 2016). "A Vision for 5G Channel Coding" (PDF). Archived from the original (PDF) on December 6, 2018. Retrieved January 6, 2019.
- ↑ "Soft-Decoding in LDPC based SSD Controllers". EE Times. 2015.
- ↑ "IEEE Spectrum: Does China Have the Best Digital Television Standard on the Planet?". spectrum.ieee.org. Archived from the original on 2009-12-12.
پیوند به بیرون
[ویرایش]- معرفی کدهای بررسی برابری با چگالی کم (توسط سارا جی جانسون، ۲۰۱۰)
- کدهای LDPC – یک آموزش مختصر (توسط برنهارد لینر، ۲۰۰۵)
- کدهای LDPC (TU Wien) بایگانی‌شده در فوریه ۲۸, ۲۰۱۹ توسط Wayback Machine </link>
- کدهای 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