کدگذاری کانال

کدگذاری کانال (Channel Coding) به روشی در مخابرات برای انتقال اطلاعات گفته مي‌شود که شامل اضافه کردن بیتهای زائد (Redundant Bits) برای انتقال داده و جلوگیری از اختلالات مي‌شود و هدف از آن یافتن کدهایی است که سریع‌تر منتقل شوند و شامل تعداد زیادی از کدهای صحیح برای تصحیح خطا یا شناسایی آن باشند.

تعریف رمزگذاری

رمزگذاري فرآیند تغییر شکل اطلاعات الکترونیکی در یک فرم خاص است که تنها توسط یک شخص یا عده‌ای خاص قابل خواندن و ترجمه باشد.

دلایل استفاده از رمزگذاری ایجاد امنیت به منظور جلوگیری از سرقت و تحریف اطلاعات قابل انتقال در کانال‌های ارتباطی، جلوگیری از ایجاد خطا، تصحیح خطای ایجاد شده، ایجاد همزمانی در شناخت خطا و تصحیح آن از جمله دلایل رمزگذاری محسوب می‌شوند.

انواع کدگذاری

۱-کدگذاری منبع (Entropy Coding or Source Coding) شامل فشرده‌سازی داده‌ها برای انتقال مؤثر و کاهش ترافیک شبکه و کاهش طول پیام‌های ارسالی مي‌شود. ۲- کدگذاری کانال

کدگذاری جبری

کدگذاری جبری نوعي از کدگذاری است که با بررسی سه ویژگی طول کدواژه‌ها، تعداد کل کدواژه‌ها و حداقل فاصله میان دو کدواژه صورت می‌گیرد.

انواع کدگذاری جبری

۱-کدهای بلوكي خطي (Linear Block Codes) : در اين روش مجموعه هر دو کلمه رمز یک کلمه رمز جدید به صورت بلوكي از بيت‌ها در منبع را شکل می‌دهد. تبدیل رشته دودویی اصلی به یک رشته رمز شده با یک روش بلوک به بلوک، اضافه کردن r بیت اضافه به هر بلوک با n بیت اطلاعات، تولید بیت‌های کد از ترکیب خطی بیت‌های اطلاعات مراحل بلاک کد را تشکیل می‌دهند.

۲- کدهای حلقوی (Convolutional Codes): از اين روش در ماهواره‌ها، GSM (CDMA) و دستگاه‌های ارتباطی نظامی استفاده مي شود. عدم استفاده از هرگونه محافظت در برابر اختلالات (عیب در برابر کدهای خطی سدکننده)از جمله معايب و استفاده آسان (مزیت) و دارای یک چرخه بسیار ساده از مزایای این کدگذاری است.

روش BCH

خانواده‌ای از کدهای چرخشی با مقدار فاصلهٔ همینگ زیاد و الگوریتم‌های جبری تصحیح خطای بسیار مفید محسوب می‌شود، در اين روش هر کلمه کد مضربی از چند جمله‌ای مولد است. وجود qn − m کد واژه در یک کد چند جمله‌ای روی(GF(q، با طول کد n و چند جمله‌ای مولد(q(x از ویژگی‌های این نوع کدگذاری محسوب مي شود. در رمزگشایی، تشخیص خطا از طریق تقسیم چند جمله‌ای بر چند جمله‌ای مولد (باقیماندهٔ غیر صفر) صورت مي گيرد، حد اقل فاصلهٔ همینگ نيز باحداقل وزن(weight) کد واژه‌های غیر صفر آن برابري مي‌كند.

مثال:

{GF(۲) = {۰٬۱، m=2,n=۵ و چند جمله‌ای مولد g(x) = x۲ + x + ۱

x۲+x+۱, x۳+x۲+x, x۳+۱ ,۰ x۴+x۳+x2 , x۴+x۳+x+۱ ,x۴+x,x۴+x۲+۱

کد واژه‌ها:

۰۰۰۰۰٬۰۰۱۱۱٬۰۱۱۱۰٬۰۱۰۰۱ ۱۱۱۰۰٬۱۱۰۱۱٬۱۰۰۱۰٬۱۰۱۰۱

۰۰۰ ← ۰۰۰۰۰

۰۰۱ ← ۰۰۱۱۱

۰۱۰ ← ۰۱۰۰۱

۰۱۱ ← ۰۱۱۱۰

۱۰۰ ← ۱۰۰۱۰

۱۰۱ ← ۱۰۱۰۱

۱۱۰ ← ۱۱۰۱۱

۱۱۱ ← ۱۱۱۰۰

روش Reed-Solomon

اين روش توسط ایروینگ اس رید و گوستاو سولومون ابداع شد، اين نوع كدگذاري تنها روش غیرباینری در بين كدگذاري‌ها محسوب مي‌شود. كدگذاري ريدسالامان روشي سیستماتیک برای ساختن کدهایی با قابلیت شناسایی چندین خطای نشانه تصادفی است كه توانایی تشخیص هر ترکیب از t نشانه خطادار و تصحیح تا t/۲⌋ ⌊ نشانه را دارا است. كدگذاري ريد سالامان برای استفاده به صورت تصحیح خطای بیتی مسلسل‌وار مناسب است. نشانه‌های منبع به صورت ضرایب یک چندجمله‌ای p(x) بر روی یک طول محدود قرار دارند و n نشانه کد از k نشانه منبع با استفاده از فرانمونه‌برداری (p(x در n > k نقطه متفاوت توليد مي‌شود. کدهای RS به صورت کد BCH دوره‌ای است که نشانه‌های رمزکننده از روی ضرایب یک چندجمله‌ای به دست مي‌آيد که با استفاده از حاصلضرب p(x) و یک چندجمله‌ای مولد دوره‌ای ساخته می‌شود. این کار به یک الگوریتم رمزگشایی موثر منجر می‌شود که توسط Elwyn Berlekamp و James Massey کشف شد و به الگوریتم رمزگشایی Berlekamp-Massey معروف است.

کد همینگ

كد همينگ روشی برای مشخص کردن و اصلاح تغییرات ناخواسته در کانال نویزی است. اين كدگذاري از سه بیت توازن برای آشکارسازی و اصلاح خطا استفاده مي‌كند. کد همینگ يك كد خطی دودویی است که قابلیت تصحیح و تشخیص هر خطای منفرد در درون هر بلاک را دارد. این کد که در سال ۱۹۵۰ توسط ریچارد همینگ کشف گردید، در انتقال اطلاعات به خصوص سیستمهای Teletext و Telecommunication استفاده می‌شود. کد همینگ باعث می‌شود که درجه اطمینان داده در ارسال داده از راه دور زیاد شود. در کد همینگ رابطه ۲ ^ m >= n+۱برقرار است که: n= تعداد بیتهای موجود در یک بلاک m= تعداد بیتهای کنترلی در بلاک (m=n-k) k=تعداد بیتهای اطلاعاتی در بلاک

مثالی از کد همینگ:

Coding:

۰۱۱۱۱۱۰۱۰۰۰ داده اصلی

k= 11

m= 4

n=15

توازن بیتهایی را چک می‌کنیم که باقیمانده تقسیم شماره بیت آنها بر ۲، یک باشد

توازن بیتهایی را چک می‌کنیم که باقیمانده تقسیم شماره بیت آنها بر ۴، دو یا سه باشد

بیتهایی را چک می‌کنیم که باقیمانده تقسیم شماره بیت آنها بر ۸، چهار، پنج، شش یا هفت باشد

توازن بیتهایی را چک می‌کنیم که باقیمانده تقسیم شماره بیت آنها بر ۱۶، هشت، نه، ده، یازده، دوازده، سیزده، چهارده یا پانزده باشد

حال داده را با یک خطا در بیت یازدهم ارسال می‌کنیم. داده ارسال شده به صورت زیر خواهد بود : ۰۱۱۱۰۱۰۱۱۰۰۰۰۰۱۰ Decoding: توازن بیتهایی را محاسبه می‌کنیم که باقیمانده تقسیم شماره بیت آنها بر ۲، یک باشد:P1=۱

توازن بیتهایی را محاسبه می‌کنیم که باقیمانده تقسیم شماره بیت آنها بر ۴، دو یا سه باشد:P2=۱

توازن بیتهایی را محاسبه می‌کنیم که باقیمانده تقسیم شماره بیت آنها بر ۸، چهار، پنج، شش یا هفت باشد: P3=۰

توازن بیتهایی را محاسبه می‌کنیم که باقیمانده تقسیم شماره بیت آنها بر شانزده، هشت، نه، ده، یازده، دوازده، سیزده، چهارده یا پانزده باشد:P4=۱

توازنهای به دست آمده نشان می‌دهد که بیت یازدهم دارای خطا است: پس طبق الگوریتم بیت یازدهم را معکوس می‌کنیم در نتیجه خواهیم داشت: ۰۱۱۱۱۱۰۱۱۰۰۰۰۰۱۰ پس از حذف بیتهای کنترلی و بیت اضافه شده داده اصلی به دست خواهد آمد. ۰۱۱۱۱۱۰۱۰۰۰

جستارهای وابسته

• فشرده‌سازی داده‌ها

کتابشناسی

1. Clark, George C., Jr., and J. Bibb Cain, Error-Correction Coding for Digital Communications, New York, Plenum Press, 1981.
2. Lin, Shu, and Daniel J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ, Prentice-Hall, 1983.
3. Peterson, W. Wesley, and E. J. Weldon, Jr., Error-Correcting Codes, 2nd ed., Cambridge, MA, MIT Press, 1972.
4. van Lint, J. H., Introduction to Coding Theory, New York, Springer-Verlag, ۱۹۸۲