کدگذاری کانال
اصلاح خطای روبه جلو (FEC) یا کدگذاری کانال (Channel Coding) در مخابرات ، نظریه اطلاعات و نظریه کدگذاری به افزودن تعدادی بیت زائد (Redundant bits) به بیتهای اطلاعات برای مقابله با بروز خطا در خطوط نویز دار گفته می‌شود. این کار برای انتقال بدون خطای (یا کم‌خطا) اطلاعات لازم است.
یافتن کدهایی که بتوانند با کمترین تعداد بیتهای زائد، بیشترین تعداد خطا در بیتهای اطلاعات منتقل‌شده را تشخیص داده و تصحیح کنند، در کانون توجه کدگذاری (کدینگ) کانال است. از روش‌های کدینگ کانال به‌طور گسترده‌ای در انتقال داده‌ها (مثلاً در شبکه‌ها، مخابرات موبایل و ...)، و نیز ذخیره‌کردن داده‌ها (مثلاً بر روی هارددیسک، دی‌وی‌دی و ...) استفاده می‌شود.
کدگذاری جبری (Algebraic Coding)
کدگذاری جبری نوعی از کدگذاری کانال است که به بررسی و طراحی کدهایی با "طول کد" محدود می‌پردازد و سه ویژگی طول کدواژه‌ها، تعداد کل کدواژه‌ها و حداقل فاصله دو کدواژه را در نظر می‌گیرد.
انواع کدگذاری جبری
۱-کدهای بلوکی خطی (Linear Block Codes): در این کدها، هر کدواژه به صورت بلوکی از بیت‌هاست (طول بلوک ثابت است) و مجموع هر دو کدواژه، یک کدواژه دیگر همان کد است (به دلیل خطی بودن کد). تبدیل بیتهای اطلاعات دودویی به یک بلوک کد (کدواژه)، با تولید و اضافه‌کردن r بیت (بیتهای زائد) به هر بلوک k-بیتی اطلاعات صورت می گیرد. در واقع بیتهای زائد از ترکیب خطی بیتهای اطلاعات تولید می‌شوند. در نتیجه، هر کدواژه n=k+r بیت خواهد داشت.
۲- کدهای کانوُلوشِنال (Convolutional Codes): صرف‌نظر از چگونگی تولید این کد، ایده اصلی این کدها این است که هر بیت اطلاعات روی همۀ بیتهای زائد تأثیر بگذارد. این بر خلاف کدهای بلوکی خطی است که در آنها هر بیت اطلاعات، تنها روی تعداد محدودی از بیتهای زائد، تأثیرگذار است.
کد BCH
این کد، خانواده‌ای از کدهای دوره‌ای (Cyclic) با فاصلهٔ همینگ زیاد و الگوریتم‌های جبری تصحیح خطای بسیار مفید است. در این کد، هر کدواژه به‌صورت یک چندجمله‌ای در نظر گرفته می‌شود که مضربی از چندجمله‌ای مولد کد است. وجود qn−m کدواژه در یک کد چندجمله‌ای روی میدان محدود (GF(q، با طول کد n و چندجمله‌ای مولد (g(x از ویژگی‌های این نوع کد محسوب می‌شود. هنگام کدگشایی، تشخیص خطا از راه تقسیم چندجمله‌ای کد دریافت‌شده بر چندجمله‌ای مولد صورت می‌گیرد، حداقل فاصلهٔ همینگ در این کد، حداقل وزن (weight) کدواژه‌های غیرصفر آن است.
مثال:
{GF(۲) = {۰٬۱، m=2,n=۵ و چندجمله‌ای مولد g(x) = x2 + x + 1
x2+x+1, x3+x2+x, x3+1 ,0 x4+x3+x2 , x4+x3+x+1 ,x4+x,x4+x۲+۱
کد واژه‌ها:
۰۰۰۰۰٬۰۰۱۱۱٬۰۱۱۱۰٬۰۱۰۰۱ ۱۱۱۰۰٬۱۱۰۱۱٬۱۰۰۱۰٬۱۰۱۰۱
۰۰۰ ← ۰۰۰۰۰
۰۰۱ ← ۰۰۱۱۱
۰۱۰ ← ۰۱۰۰۱
۰۱۱ ← ۰۱۱۱۰
۱۰۰ ← ۱۰۰۱۰
۱۰۱ ← ۱۰۱۰۱
۱۱۰ ← ۱۱۰۱۱
۱۱۱ ← ۱۱۱۰۰
کد Reed-Solomon
این روش که توسط اِروینگ رید و گوستاو سولومون ابداع شد، تنها روش غیرباینری برای کدگذاری محسوب می‌شود.
این کدگذاری، روشی ساختاریافته برای تولید کدهایی با قابلیت شناسایی و تصحیح خطاهای مُمتد تصادفی (Burst errors) در سمبول‌های اطلاعات (هر سمبول (Symbol)، چندین بیت است) است، که توانایی تشخیص هر ترکیبی از t سمبول خطادار، و تصحیح تا ⌊t/۲⌋ سمبول را داراست. سمبول‌های منبع اطلاعات به‌صورت ضرایب یک چندجمله‌ای (p(x در نظر گرفته می‌شوند، و n سمبول کد از k سمبول منبع با استفاده از فرانمونه‌برداری (p(x در n> k نقطه متفاوت تولید می‌شود. کدهای RS به صورت کد BCH دوره‌ای است که سمبول‌های کدکننده از روی ضرایب یک چندجمله‌ای به‌دست می‌آید که با استفاده از حاصلضرب p(x) و یک چندجمله‌ای مولد دوره‌ای ساخته می‌شود. این کار به یک الگوریتم رمزگشایی مؤثر منجر می‌شود که توسط Elwyn Berlekamp و James Massey کشف شد و به الگوریتم رمزگشایی Berlekamp-Massey معروف است.
کد همینگ
کد همینگ از اولین کدهای باینری (دودویی) برای تشخیص و اصلاح خطا در کانال های نویزی است، و در نسخه اولیه خود سه بیت زائد دارد. این کد می‌تواند بروز یک خطا (یک بیت) را درون هر بلاک کد دریافت‌شده تشخیص داده و آن را تصحیح کند. این کد که در سال ۱۹۵۰ توسط ریچارد همینگ کشف شد، در انتقال اطلاعات به خصوص سیستمهای Teletext استفاده می‌شود. در کد همینگ رابطه ۲ ^ m>= n+۱برقرار است که n تعداد بیتهای موجود در یک بلاک، m تعداد بیتهای کنترلی در بلاک (m=n-k) k=تعداد بیتهای اطلاعاتی در بلاک
مثالی از کد همینگ:
Coding:
۰۱۱۱۱۱۰۱۰۰۰ داده اصلی
k= ۱۱
m= ۴
n=۱۵
توازن بیتهایی را چک می‌کنیم که باقیمانده تقسیم شماره بیت آنها بر ۲، یک باشد
توازن بیتهایی را چک می‌کنیم که باقیمانده تقسیم شماره بیت آنها بر ۴، دو یا سه باشد
بیتهایی را چک می‌کنیم که باقیمانده تقسیم شماره بیت آنها بر ۸، چهار، پنج، شش یا هفت باشد
توازن بیتهایی را چک می‌کنیم که باقیمانده تقسیم شماره بیت آنها بر ۱۶، هشت، نه، ده، یازده، دوازده، سیزده، چهارده یا پانزده باشد
حال داده را با یک خطا در بیت یازدهم ارسال می‌کنیم. داده ارسال شده به صورت زیر خواهد بود: ۰۱۱۱۰۱۰۱۱۰۰۰۰۰۱۰ Decoding: توازن بیتهایی را محاسبه می‌کنیم که باقیمانده تقسیم شماره بیت آنها بر ۲، یک باشد:P1=۱
توازن بیتهایی را محاسبه می‌کنیم که باقیمانده تقسیم شماره بیت آنها بر ۴، دو یا سه باشد:P2=۱
توازن بیتهایی را محاسبه می‌کنیم که باقیمانده تقسیم شماره بیت آنها بر ۸، چهار، پنج، شش یا هفت باشد: P3=۰
توازن بیتهایی را محاسبه می‌کنیم که باقیمانده تقسیم شماره بیت آنها بر شانزده، هشت، نه، ده، یازده، دوازده، سیزده، چهارده یا پانزده باشد:P4=۱
توازنهای به دست آمده نشان می‌دهد که بیت یازدهم دارای خطا است: پس طبق الگوریتم بیت یازدهم را معکوس می‌کنیم در نتیجه خواهیم داشت: ۰۱۱۱۱۱۰۱۱۰۰۰۰۰۱۰ پس از حذف بیتهای کنترلی و بیت اضافه شده داده اصلی به دست خواهد آمد. ۰۱۱۱۱۱۰۱۰۰۰
جستارهای وابسته
کتابشناسی
- Clark, George C. , Jr. , and J. Bibb Cain, Error-Correction Coding for Digital Communications, New York, Plenum Press, 1981.
- Lin, Shu, and Daniel J. Costello, Jr. , Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ, Prentice-Hall, 1983.
- Peterson, W. Wesley, and E. J. Weldon, Jr. , Error-Correcting Codes, 2nd ed. , Cambridge, MA, MIT Press, 1972.
- van Lint, J. H. , Introduction to Coding Theory, New York, Springer-Verlag, ۱۹۸۲
منابع
- ↑ Charles Wang; Dean Sklar; Diana Johnson (Winter 2001–2002). "Forward Error-Correction Coding". Crosslink — the Aerospace Corporation magazine of advances in aerospace technology. The Aerospace Corporation. 3 (1). Archived from the original on 25 February 2012. Retrieved 12 December 2018.
How Forward Error-Correcting Codes Work
- ↑ Maunder, Robert (2016). "Overview of Channel Coding".