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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

کدگذاری کانال (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) = 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[ویرایش]

این روش توسط ایروینگ اس رید و گوستاو سولومون ابداع شد، این نوع کدگذاری تنها روش غیرباینری در بین کدگذاری‌ها محسوب می‌شود. کدگذاری ریدسالامان روشی سیستماتیک برای ساختن کدهایی با قابلیت شناسایی چندین خطای نشانه تصادفی است که توانایی تشخیص هر ترکیب از 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= ۱۱

m= ۴

n=۱۵

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

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

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

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

حال داده را با یک خطا در بیت یازدهم ارسال می‌کنیم. داده ارسال شده به صورت زیر خواهد بود: ۰۱۱۱۰۱۰۱۱۰۰۰۰۰۱۰ 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, ۱۹۸۲