کد تصحیح خطای هم‌پیوسته

در تئوری کدگذاری کانال مخابراتی، کدهای هم‌پیوسته (Concatenated codes)، دسته‌ای از کدهای تصحیح‌کننده خطا هستند که از به‌هم‎‌پیوستن یک کد درونی (inner code) و یک کد بیرونی (outer code) به‌دست می‌آیند. این کدها را دیو فورنی در سال 1966، در جست‌وجوی کدی که هم احتمال خطای آن با افزایش طول کد، به‌طور نمایی (Exponential) کاهش یابد و هم دارای پیچیدگیِ کدگشاییِ چندجمله‌ای برحسب طول کد (Polynomial-time) باشد، پیش نهاد. کدهای هم‌پیوسته در دهۀ هفتاد میلادی در مخابرات فضایی، استفاده شد.

پیش‌زمینه

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

قضیه کدگذاری کانال شانون نشان می‌دهد که برای بسیاری از کانال‌های رایج، می‌توان کدهایی یافت که داده‌ها را قابل‌اطمینان و با نرخ‌ دلخواه $R$ که کمتر از یک آستانه مشخص $C$ (ظرفیت کانال)، منتقل کنند. در واقع، احتمال خطای کدگشایی می‌تواند با افزایش طول کد ($N$)، به‌طور نمایی کاهش یابد. اما، پیچیدگی یک کدگشایی بهینۀ ساده‌لوحانه هم - که تنها بر محاسبۀ درست‌نمایی (likelihood) هر کلمۀ کدِ فرستاده‌شدۀ ممکن، استوار است - به‌طور نمایی (exponentially) با طول کد ($N$) افزایش می یابد. بنابراین چنین کدگشایی بهینه‌ای، به‌سرعت ناممکن می‌شود.

دیو فورنی در پایان نامه دکترایش نشان داد که می‌توان از کدهای هم‌پیوسته برای دست‌یابی به احتمالات خطایی که به‌ازای همۀ نرخ‌های دادۀ کمتر از ظرفیت کانال، به‌طور نمایی کاسته می‌شوند، و از سوی دیگر، پیچیدگیِ کدگشایی‌شان، تنها به‌طور چندجمله‌ای (polynomial-time) با طول کد افزایش می‌یابد، بهره برد.

شرح

نمایش طرح‌واره از کد هم‌پیوسته که برپایۀ یک کد درونی و یک کد بیرونی ساخته شده‌است.

این یک نمایش تصویری از به هم پیوستن دو کد است،به‌ویژه، کد Reed–Solomon با n=q=4 و k=2 به‌عنوان کد بیرونی و کد آدامار با n=q و k=log q استفاده می‌شود. به عنوان کد درونی استفاده می شود. به طور کلی، کد هم‌پیوسته است $[q^{2},k\log q]$ -کد

فرض کنید C_in یک کد [n، k، d] باشد، یعنی یک کد بلوکی به طول n ، بعد k ، حداقل فاصله همینگ d ، و نرخ r = k/n ، روی الفبای A :

$C_{in}:A^{k}\rightarrow A^{n}$

و C_out یک کد [ N، K، D] روی الفبای B با تعداد سمبول‌های B| =||A|^k| باشد:

$C_{out}:B^{K}\rightarrow B^{N}$

کد درونی C_in، یکی از |A|^k = |B| ورودی‌های ممکن را می‌پذیرد، آن را به یک n-تایی روی A کد میکند، روی کانال می‌فرستد، و به یکی از |B| خروجی‌های ممکن کدگشایی می‌کند. این را می‌توان به‌عنوان یک فراکانال (super channel) در نظر گرفت که یک سمبل را از الفبای B منتقل می‌کند. از این کانال N بار برای انتقال هر یک از N سمبل در یک کلمه کد C_out استفاده می‌کنیم. بنابراین، هم‌پیوستگی C_out (کد بیرونی) با C_in (کد درونی)، که با C_out∘C_in نشان داده می‌شود، کدی به طول Nn روی الفبای A است:

$C_{out}\circ C_{in}:A^{kK}\rightarrow A^{nN}$

هر پیام ورودی m = (m₁, m₂, ..., m_K) را به یک کلمه کد (C_in(m'₁), C_in(m'₂), ..., C_in(m'_N)) می‌نگارد، که (m'₁, m'₂, ..., m'_N) = C_out(m₁, m₂, ..., m_K)

نکتۀ کلیدی در این رویکرد این است که اگر C_in به روش درست‌نمایی بیشینه (Maximum likelihood)، کدگشایی شود (که احتمال خطای نمایی‌ِ کم‌شونده با افزایش طول کد دارد)، و C_out یک کد با طول N = 2^nr باشد که می‌تواند با پیچیدگی محاسباتی چندجمله‌ای (Polynomial time) بر حسب N کدگشایی شود. سپس کد هم‌پیوسته را می‌توان با پیچیدگی محاسباتی چندجمله‌ای n2^nr = O(N⋅log(N)) کدگشایی کرد، که احتمال خطای نمایی‌کم‌شونده (Exponentially decreasing) دارد، حتی اگر کدگشایی C_in، دارای پیچیدگی نمایی (Exponential time) باشد.

در تعمیم این هم‌پیوستگی، N کد درونی ممکن C_{in, i} وجود دارد و نماد i-ام در کلمه کد C_out با استفاده از کد درونی i-ام در کانال درونی منتقل می‌شود. کدهای یوستِسِن نمونه‌ای از کدهای هم‌پیوسته تعمیم‌یافته هستند که کد بیرونی آن‌ها یک کد رید-سولومون است.

ویژگی‌ها

1. فاصله کد هم‌پیوسته C_out∘C، دست‌کم dD است، یعنی یک کد [nN، kK، D'] با D' ≥ dD است.

اثبات: دو پیام m¹ ≠ m² ∈ B^K را در نظر بگیرید. اگر Δ نشان‌دهنده فاصلۀ دو کلمه کد باشد، پس

$\Delta (C_{out}(m^{1}),C_{out}(m^{2}))\geq D.$

بنابراین، دست‌کم D جا در دنباله‌ای از N سمبول کلمات کد C_out(m¹) و C_out(m²) می‌توان یافت که یکسان نباشند. برای این جاها، که با i نشان داده‌شده‌اند داریم

$\Delta (C_{in}(C_{out}(m^{1})_{i}),C_{in}(C_{out}(m^{2})_{i}))\geq d.$

بنابراین، دست‌کم d⋅D جا در دنباله n⋅N سمبولِ برگرفته از الفبای A هستند که در آن‌ها دو کلمه کد با هم فرق دارند، و ازاین‌رو

$\Delta (C_{in}(C_{out}(m^{1})),C_{in}(C_{out}(m^{2})))\geq dD.$

2. اگر C_out و C_in کدهای بلوک خطی باشند، C_out ∘ C_in نیز یک کد بلوک خطی است.

این ویژگی را می‌توان به‌سادگی برپایۀ ایده تعریف یک ماتریس مولد برای کد هم‌پیوسته برحسب ماتریس‌های مولد C_out و C_in نشان داد.

کدگشایی کد هم‌پیوسته

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

فرض کنید ورودی کدگشا، بردار y = (y₁, ..., y_N) ∈ (Aⁿ)^N باشد. الگوریتم کدگشایی یک فرآیند دو مرحله‌ای‌ست:

1. از MLD کد درونیِ C_in برای بازسازی مجموعه‌ای از کلمات کد درونی استفاده کنید y' = (y'₁, ..., y'_N) که y'_i = MLD_Cin (y_i), 1 ≤ i ≤ N.
2. الگوریتم کدگشایی یگانه برای C_out را روی y پیاده کنید.

اکنون، پیچیدگی اجرای مرحله اول O(N⋅exp(n)) است، که در آن n = O (log( N )) طول بلوک درونی است. به عبارت دیگر، N^O(1) (یعنی چندجمله‌ای) بر حسب طول بلوک بیرونی N است. در مرحله دوم - که فرض می‌شود پیچیدگی الگوریتم کدگشایی بیرونی، چندجمله‌ای است - پیچیدگی الگوریتم کدگشایی کد هم‌پیوستۀ حاصل نیز چندجمله‌ای است.

نکات

الگوریتم کدگشایی بالا، می‌تواند برای تصحیح همۀ خطاهای کمتر از dD/4 از نظر تعداد، استفاده شود. با استفاده از کدگشایی کمترین فاصله، کدگشای بیرونی می‌تواند همۀ ورودی‌های 'y که کمتر از D/2 سمبل خطا دارند را تصحیح کند. همچنین، اگر کمتر از d/2 سمبل‌های درونی، نادرست باشند، کد درونی می‌تواند ورودی y_i را قابل‌اعتماد تصحیح کند. بنابراین، برای نادرست بودن یک سمبل بیرونی y'_i پس‌از رمزگشایی درونی، دست‌کم d/2 سمبل‌های درونی باید نادرست باشند، و برای اینکه کد بیرونی درست کار نکند، دست‌کم D/2 سمبل بیرونی باید نادرست باشند. بنابراین، شمار سمبل‌های درونی که باید نادرست دریافت شده‌باشند تا کد هم‌پیوسته از کار بیفتد، باید دست‌کم d/2⋅ D/2 = dD/4 باشد.

همچنین این الگوریتم در صورتی کار می‌کند که کدهای درونی متفاوت باشند، برای نمونه، برای کدهای یوستسن. الگوریتم کمترین فاصله تعمیم‌یافته، که فورنی پیش نهاد، می‌تواند برای تصحیح dD/2 خطا به کار رود. این الگوریتم، از اطلاعات مخدوش (erasure) کد درونی برای بهبود عملکرد کد بیرونی بهره می‌گیرد و نخستین الگوریتمی بود که از کدگشایی با تصمیم‌گیری نرم (Soft decision) استفاده می‌کرد.

کاربردها

اگرچه یک روش هم‌پیوستگی ساده برای مأموریت مدارگرد مارینر مریخ، پیشتر در 1971 پیاده شده‌بود، کاربرد مرتب کدهای هم‌پیوسته برای مخابرات فضای دوردست با برنامه وویجر، - که دو کاوشگر فضایی را در 1977 پرتاب کرد - آغاز شد. از آن زمان، این کدها، ابزار کدگذاری تصحیح خطای کارآمد شدند و کاربردشان دست‌کم تا اختراع کدهای توربو و کدهای ال‌دی‌پی‌سی ادامه یافت.

معمولا، کد درونی، یک کد بلوکی نیست، بلکه یک کد کانولوشنال کدگشایی‌شده به روش ویتربی نرم با طول قید (constraint length) کوتاه است. کد بیرونی هم، یک کد بلوکی درازتر با تصمیم‌گیری سخت (hard decision) - اغلب یک کد رید-سولومون با سمبل‌های هشت‌بیتی - است. اندازۀ سمبل بزرگتر باعث می‌شود کد بیرونی در برابر خطاهای رگباری (burst error) - که ممکن است در اثر اختلالات کانال رخ دهند یا در اثر اینکه خروجی کد کانولوشنال، پیاپی خطا دارد، قوی‌تر شود. معمولاً میان دو کد، یک درهم‌کننده (interleaver) هم می‌گذارند تا خطاهای رگباری را پخش کند.

هم‌پیوستگی کد کانولوشنال ویتربی درونی و کد رید-سولومون بیرونی (معروف به کد RSV)، نخستین‌‌بار در وویجر 2 به‌کار رفت و یک ساختار محبوب شد. امروزه در مخابرات ماهواره‌ای، مانند استاندارد تلویزیون دیجیتال DVB-Sاز این کد استفاده می‌شود.

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

یک کد هم‌پیوستۀ ساده نیز در لوح فشرده (CD) به‌کار می‌رود، که در آن یک درهم‌کنندۀ میان دو کد رید-سولومون مختلف، خطاها را در بلوک‌ها پخش می‌کند.

کدهای توربو: رویکرد هم‌پیوستگی موازی

کدهای توربو را می‌توان یک هم‌پیوستگی موازی از دو کد کانولوشنال دانست که یک درهم‌کننده (interleaver)، میان آن دو قرار گرفته و تکرارشونده (iterative) کدگشایی می‌شوند. این طرح، عملکرد بهتری نسبت به کدهای هم‌پیوسته پیشین دارد.

اما، یک جنبه کلیدی کدهای توربو، کدگشایی تکرارشوندۀ آنهاست. کدگشایی تکرارشونده، اکنون برای هم‌پیوستگی سریال و با هدف دست‌یابی به بهرۀ (gain) کدگذاری بیشتر هم به‌کار می‌روند، برای نمونه، در کدهای کانولوشنال هم‌پیوسته سریالی. یک نسخه ابتدائی کدگشایی تکرارشونده با دو تا پنج تکرار، در "کد گالیله" کاوشگر فضایی گالیله پیاده شد.

همچنین ببینید

• قید گیلبرت – ورشاموف
• کد یوستِسِن
• قید سینگلتون
• قید زیابلوف

•  

لینک‌های بیرونی

• University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra