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

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

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

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

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

## شرح
بندانگشتی| نمایش طرح‌واره از کد هم‌پیوسته که برپایۀ یک کد درونی و یک کد بیرونی ساخته شده‌است.
[بندانگشتی|400x400پیکسل| این یک نمایش تصویری از به هم پیوستن دو کد است،به‌ویژه، [تصحیح خطای رید-سالامون|کد Reed–Solomon با n=q=4 و k=2 به‌عنوان کد بیرونی و کد آدامار با n=q و k=log q استفاده می‌شود. به عنوان کد درونی استفاده می شود. به طور کلی، کد هم‌پیوسته است [q^2,k \log q] -کد]]
فرض کنید *C<sub>in</sub>* یک کد [*n*، *k*، *d*] *باشد*، یعنی یک کد بلوکی به طول *n* ، بعد *k* ، حداقل فاصله همینگ *d* ، و نرخ *r* = *k*/*n* ، روی الفبای *A* :

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

و *C<sub>out</sub>* یک کد [ *N*، *K*، *D*] روی الفبای *B* با تعداد سمبول‌های *B|* =*|*|*A*|*k**|*  باشد:

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

کد درونی *C<sub>in</sub>*، یکی از |*A*|*k* = |*B*| ورودی‌های ممکن را می‌پذیرد، آن را به یک *n*-تایی روی *A* کد میکند، روی کانال می‌فرستد، و به یکی از |*B*| خروجی‌های ممکن کدگشایی می‌کند. این را می‌توان به‌عنوان یک فراکانال (super channel) در نظر گرفت که یک سمبل را از الفبای *B* منتقل می‌کند. از این کانال *N* بار برای انتقال هر یک از *N* سمبل در یک کلمه کد *C**out* استفاده می‌کنیم. بنابراین، هم‌پیوستگی *C**out* (کد بیرونی) با Cin (کد درونی)، که با *C<sub>out</sub>*∘*C<sub>in</sub>* نشان داده می‌شود، کدی به طول *Nn* روی الفبای *A* است: 

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

هر پیام ورودی *m* = (*m*1, *m*2, ..., *m*K) را به یک کلمه کد (*C<sub>in</sub>*(*m*1), *C<sub>in</sub>*(*m*2), ..., *C<sub>in</sub>*(*m*N)) می‌نگارد، که (*m*1, *m*2, ..., *m*N) = *C<sub>out</sub>*(*m*1, *m*2, ..., *m*K)

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

در تعمیم این هم‌پیوستگی، *N* کد درونی ممکن *C<sub>in</sub>*, *i* وجود دارد و نماد *i-*ام در کلمه کد *C**out* با استفاده از کد درونی *i-*ام در کانال درونی منتقل می‌شود. کدهای یوستِسِن نمونه‌ای از کدهای هم‌پیوسته تعمیم‌یافته هستند که کد بیرونی آن‌ها یک کد رید-سولومون است.

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

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

: \Delta(C_{out}(m^1), C_{out}(m^2)) \ge D.

بنابراین، دست‌کم *D* جا در دنباله‌ای از *N* سمبول کلمات کد *C**out*(*m*1) و *C**out*(*m*2) می‌توان یافت که یکسان نباشند. برای این جاها، که با *i* نشان داده‌شده‌اند داریم

: \Delta(C_{in}(C_{out}(m^1)_i), C_{in}(C_{out}(m^2)_i)) \ge d.

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

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

**2.** اگر *C**out* و *C**in* کدهای بلوک خطی باشند، *C**out* ∘ *C**in* نیز یک کد بلوک خطی است.

این ویژگی را می‌توان به‌سادگی برپایۀ ایده تعریف یک ماتریس مولد برای کد هم‌پیوسته برحسب ماتریس‌های مولد *C**out* و *C<sub>in</sub>* نشان داد.

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

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

# از MLD کد درونیِ *C*in برای بازسازی مجموعه‌ای از کلمات کد درونی استفاده کنید *y* = (*y*1, ..., *y**N*) که *y**i* = MLD*C*in (*y*i), 1 ≤ *i* ≤ *N.*
# الگوریتم کدگشایی یگانه برای *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
رده:نظریه اطلاعات
رده:میدان‌های متناهی
رده:نظریه کدگذاری
رده:آشکارسازی و اصلاح خطا