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

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

کدگذاری کانال (Channel Coding)[۱][۲] در مخابرات دیجیتال، به افزودن تعدادی بیت زائد (Redundant bits) به بیت های اطلاعات (دیتا) به منظور مقابله با بروز خطا هنگام انتقال این اطلاعات در اثر نویز کانال مخابراتی گفته میشود. این کار برای انتقال بدون خطای (یا کم خطای) اطلاعات لازم است. یافتن کدهایی که بتوانند با کمترین تعداد بیت های زائد، بیشترین تعداد خطا در رشته بیت های اطلاعات منتقل شده را تشخیص داده و تصحیح کنند، در کانون توجه مبحث کدگذاری (کدینگ) کانال است. از روش های کدینگ کانال به طور گسترده ای در مبحث انتقال داده ها (مثلا در شبکه ها، مخابرات موبایل و ...) و نیز ذخیره سازی داده ها (مثلا بر روی هارد دیسک، دی وی دی و ...) استفاده می شود.

کدگذاری جبری (Algebraic Coding)[ویرایش]

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

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

۱-کدهای بلوکی خطی (Linear Block Codes): در این نوع از کدها، هر کدواژه به صورت بلوکی از بیت‌هاست (طول بلوک ثابت است) و مجموع هر دو کدواژه، یک کدواژه دیگر همان کد است (به دلیل خطی بودن کد). تبدیل داده های (اطلاعات) دودویی به یک بلوک کد (کدواژه)، با تولید و اضافه کردن r بیت (بیت های زائد) به هر بلوک n بیتی اطلاعات صورت می گیرد. در واقع بیت های زائد از ترکیب خطی بیت‌های اطلاعات تولید می‌شوند. در نتیجه، هر کدواژه n+r بیت خواهد داشت.

۲- کدهای کانولوشنال (Convolutional Codes): ایده اصلی این کدها این است که هر بیت اطلاعات بر روی همه بیت های کدواژه حاصل تأثیر می گذارد. این بر خلاف کدهای بلوکی خطی است که در آنها هر بیت اطلاعات، تنها بر روی تعداد محدودی از بیت های کدواژه (در واقع، بیت های زائد) تأثیرگذار است.

کد BCH[ویرایش]

خانواده‌ای از کدهای دوره ای (Cyclic) با فاصلهٔ همینگ زیاد و الگوریتم‌های جبری تصحیح خطای بسیار مفید محسوب می‌شود، در این کدها هر کدواژه (کلمه کد) مضربی از چندجمله‌ای مولد است. وجود 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 استفاده می‌شود. در کد همینگ رابطه ۲ ^ 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, ۱۹۸۲

منابع[ویرایش]

  1. 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). How Forward Error-Correcting Codes Work 
  2. Maunder, Robert (2016). "Overview of Channel Coding".