موضوع مقاله: کد تصحیح خطای هم‌پیوسته | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # کد تصحیح خطای هم‌پیوسته | مقدمه: پیش‌زمینه کدگذاری کانال، به فرستادن رشته‌ای از داده‌ها - با بیشترین نرخ (سرعت) ممکن - روی یک کانال مخابراتی مشخص، و سپس کدگشایی قابل‌اطمینان داده‌ها در گیرنده و به‌کمک الگوریتم‌های قابل پیاده‌سازیِ کدگذاری و کدگشایی می‌پردازد. | ## بخش 1: کد تصحیح خطای هم‌پیوسته | قضیه کدگذاری کانال شانون نشان می‌دهد که برای بسیاری از کانال‌های رایج، می‌توان کدهایی یافت که داده‌ها را قابل‌اطمینان و با نرخ‌ دلخواه که کمتر از یک آستانه مشخص (ظرفیت کانال)، منتقل کنند. در واقع، احتمال خطای کدگشایی می‌تواند با افزایش طول کد ، به‌طور نمایی کاهش یابد. دیو فورنی در پایان نامه دکترایش نشان داد که می‌توان از کدهای هم‌پیوسته برای دست‌یابی به احتمالات خطایی که به‌ازای همۀ نرخ‌های دادۀ کمتر از ظرفیت کانال، به‌طور نمایی کاسته می‌شوند، و از سوی دیگر، پیچیدگیِ کدگشایی‌شان، تنها به‌طور چندجمله‌ای (polynomial-time) با طول کد افزایش می‌یابد، بهره برد. از این کانال N بار برای انتقال هر یک از N سمبل در یک کلمه کد Cout استفاده می‌کنیم. در تعمیم این هم‌پیوستگی، N کد درونی ممکن Cin, i وجود دارد و نماد i-ام در کلمه کد Cout با استفاده از کد درونی i-ام در کانال درونی منتقل می‌شود. کدهای یوستِسِن نمونه‌ای از کدهای هم‌پیوسته تعمیم‌یافته هستند که کد بیرونی آن‌ها یک کد رید-سولومون است. برای این جاها، که با i نشان داده‌شده‌اند داریم بنابراین، دست‌کم d⋅D جا در دنباله n⋅N سمبولِ برگرفته از الفبای A هستند که در آن‌ها دو کلمه کد با هم فرق دارند، و ازاین‌رو 2. این ویژگی را می‌توان به‌سادگی برپایۀ ایده تعریف یک ماتریس مولد برای کد هم‌پیوسته برحسب ماتریس‌های مولد Cout و Cin نشان داد. کدگشایی کد هم‌پیوسته یک راه طبیعی برای کدگشایی کد هم‌پیوسته این است که نخست کد درونی و سپس کد بیرونی را کدگشاییم. برای عملی بودن، پیچیدگی محاسباتی این الگوریتم باید برحسب طول بلوک نهایی، چندجمله‌ای باشد. | ## بخش 2: کد تصحیح خطای هم‌پیوسته | فرض کنید که یک الگوریتم کدگشایی منحصربه‌فرد چندجمله‌ای برای کد بیرونی در دست باشد. زمان اجرای چندجمله‌ای در اینجا به این معنی است که مدت زمان اجرای الگوریتم در طول بلوک نهایی، یک چندجمله‌ای از طول کد است. ایده اصلی این است که اگر طول بلوک درونی، لگاریتمی از طول کد بیرونی انتخاب شود، مدت زمان اجرای الگوریتم کدگشایی کد درونی ممکن است تابعی نمایی از طول بلوک درونی شود، و بنابراین می‌توانیم از کدگشایی درست‌نمایی بیشینه بهینه (MLD) برای کد درونی اما با پیچیدگی نمایی (Exponential time) بهره بریم. در مرحله دوم - که فرض می‌شود پیچیدگی الگوریتم کدگشایی بیرونی، چندجمله‌ای است - پیچیدگی الگوریتم کدگشایی کد هم‌پیوستۀ حاصل نیز چندجمله‌ای است. نکات الگوریتم کدگشایی بالا، می‌تواند برای تصحیح همۀ خطاهای کمتر از dD/4 از نظر تعداد، استفاده شود. با استفاده از کدگشایی کمترین فاصله، کدگشای بیرونی می‌تواند همۀ ورودی‌های 'y که کمتر از D/2 سمبل خطا دارند را تصحیح کند. همچنین، اگر کمتر از d/2 سمبل‌های درونی، نادرست باشند، کد درونی می‌تواند ورودی yi را قابل‌اعتماد تصحیح کند. بنابراین، برای نادرست بودن یک سمبل بیرونی y'i پس‌از رمزگشایی درونی، دست‌کم d/2 سمبل‌های درونی باید نادرست باشند، و برای اینکه کد بیرونی درست کار نکند، دست‌کم D/2 سمبل بیرونی باید نادرست باشند. بنابراین، شمار سمبل‌های درونی که باید نادرست دریافت شده‌باشند تا کد هم‌پیوسته از کار بیفتد، باید دست‌کم d/2⋅ D/2 = dD/4 باشد. همچنین این الگوریتم در صورتی کار می‌کند که کدهای درونی متفاوت باشند، برای نمونه، برای کدهای یوستسن. | ## بخش 3: کد تصحیح خطای هم‌پیوسته | الگوریتم کمترین فاصله تعمیم‌یافته، که فورنی پیش نهاد، می‌تواند برای تصحیح dD/2 خطا به کار رود. کاربردها اگرچه یک روش هم‌پیوستگی ساده برای مأموریت مدارگرد مارینر مریخ، پیشتر در 1971 پیاده شده‌بود، کاربرد مرتب کدهای هم‌پیوسته برای مخابرات فضای دوردست با برنامه وویجر، - که دو کاوشگر فضایی را در 1977 پرتاب کرد - آغاز شد.K. از آن زمان، این کدها، ابزار کدگذاری تصحیح خطای کارآمد شدند و کاربردشان دست‌کم تا اختراع کدهای توربو و کدهای ال‌دی‌پی‌سی ادامه یافت. اندازۀ سمبل بزرگتر باعث می‌شود کد بیرونی در برابر خطاهای رگباری (burst error) - که ممکن است در اثر اختلالات کانال رخ دهند یا در اثر اینکه خروجی کد کانولوشنال، پیاپی خطا دارد، قوی‌تر شود. هم‌پیوستگی کد کانولوشنال ویتربی درونی و کد رید-سولومون بیرونی (معروف به کد RSV)، نخستین‌‌بار در وویجر 2 به‌کار رفت R. امروزه در مخابرات ماهواره‌ای، مانند استاندارد تلویزیون دیجیتال DVB-Sاز این کد استفاده می‌شود. در نگاهی فراخ‌تر، هر ترکیب (سریالی) دو یا چند کد، ممکن است یک کد هم‌پیوسته نامیده شود. برای نمونه، در استاندارد DVB-S2، از راه هم‌پیوستگی یک کد ال‌دی‌پی‌سی بسیار کارآمد و یک کد بیرونی جبری، هرگونه خطای بازمانده از کد ال‌دی‌پی‌سی درونی در اثر کف خطای ذاتی این کد، تصحیح شود. یک کد هم‌پیوستۀ ساده نیز در لوح فشرده (CD) به‌کار می‌رود، که در آن یک درهم‌کنندۀ میان دو کد رید-سولومون مختلف، خطاها را در بلوک‌ها پخش می‌کند. کدگشایی تکرارشونده، اکنون برای هم‌پیوستگی سریال و با هدف دست‌یابی به بهرۀ (gain) کدگذاری بیشتر هم به‌کار می‌روند، برای نمونه، در کدهای کانولوشنال هم‌پیوسته سریالی. | ## جمع‌بندی | یک نسخه ابتدائی کدگشایی تکرارشونده با دو تا پنج تکرار، در "کد گالیله" کاوشگر فضایی گالیله پیاده شد.