تشخیص و تصحیح خطا

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

تشخیص و تصحیح خطا (به انگلیسی: Error detection and correction) در نظریه اطلاعات، نظریه کدگذاری، علوم رایانه، مخابرات تکنیک‌هایی هستند که تحویل امن داده‌ها در کانال‌های مخابراتی ناامن را ممکن می‌کنند بسیاری از کانال‌ها در معرض نویز هستند و ممکن است اطلاعات در حین فرستاده‌شدن میان مبداء ومقصد دچار خطا گردند. تشخیص و تصحیح خطا امکان شناسایی وساخت مجدد اطلاعات اولیه را ممکن می‌گرداند.

تعریف[ویرایش]

  • تشخیص خطا: تشخیص خطاهایی که با نویز یا با اختلالات‌هایی ایجادمی‌گردند و درهنگام انتقال میان فرستند ودریافت‌کننده به وجود می‌آیند.[۱]
  • تصحیح خطا: یافتن خطا و بازیابی اصل اطلاعات[۲]

تاریخچه[ویرایش]

معروف‌ترین استفاده قاعده‌دار از تشخیص خطا توسط کاتابان یهودی در هنگام کپی برداری از کتاب مقدسشان بود آن هاروش‌های مختلفی داشتند از قبیل جمع کلمات درهر خط یا جمع کلمات در هر صفحه یا چک کردن یک پاراگراف (معمولاً پاراگراف میانی). درهر صفحه اگر حتی یک خطا وجودداشت کل صفحه ازبین می‌رفت، امااگر ۳ خطا همزمان دریک صفحه رخ می‌داد؛ کل صفحه رانابود می‌کردند. این روش کار بودن خود را زمانی نشان داد که طومارهای دریای مرده کشف شدند.[۳]

معرفی[ویرایش]

ایده عمومی این است که چیزی به متن اصلی افزوده گردد که دریافت‌کننده بتواند درستی متن دریافتی را بررسی نماید، اگر خطایی محرز گشت آن را تصحیح کند. طرح‌های تشخیص وتصحیح خطا می‌تواند به صورت سیستماتیک یا غیرسیستماتیک باشد. در طرح سیستماتیک فرستنده داده‌های اصلی را همراه تعداد ثابتی عدد به عنوان بیت‌های بررسی می‌فرستد، که بیت‌های بررسی از الگوریتم قطعیای به دست می‌آیند که از داده‌های اصلی استفاده می‌کنند. اگر فقط تشخیص خطا مدنظر باشد گیرنده می‌تواند الگوریتم رادوباره برروی داده‌های اصلی اجرا ومقدار خروجی آن را با بیت‌های بررسی مقایسه کند اگر یکسان بودند خطایی رخ نداده است. در سامانه‌هایی که از کد غیر سیستماتیک استفاده می‌کنند، پیام اصلی تبدیل به یک پیام کد شده می‌شود. عملکرد مناسب زمانی حاصل می‌گردند که بر اساس ویژگی‌های کانال مخابراتی و طرح‌های انتقال داده انتخاب گردند. انواع معمول کانال‌های مخابراتی شامل مدل بدون حافظه که درآن خطا بصورت تصادفی و با احتمال قطعی اتفاق می‌افتد و مدل‌های پویا است. درنتیجه تشخیص وتصحیح خطا را می‌توان به (به انگلیسی: random-error-detecting/correcting) و (به انگلیسی: burst-error-detecting/correcting) تقسیم کرد. اگر ظرفیت کانال را نتوان معین کرد یا ظرفیت بیش از حد متغییر باشد می‌توان درخوات ارسال مجدد داده‌ها را داشت که آن را بعنوان درخواست بازفرستی خودکار، (به انگلیسی: automatic repeat request) می‌شناسند که بطورویژه دراینترنت کاربرد دارد.[۴]

اجرا[ویرایش]

تشخیص و تصحیح خطا به دو صورت زیر تحقق میابد:

  • درخواست بازفرستی خودکار، (به انگلیسی: automatic repeat request):داده‌ها به فرم بلوکی دریافت می‌گردند هر بلوک داده برای وجود خطا بررسی می‌شود اگر خطایی یافت شود، بصورت خودکار برای آن بلاک داده درخواست ارسال مجدد می‌شود این روند ادامه میابد تا زمانی که کل داده‌ها به صورت سالم دریافت گردند.[۵]
  • اصلاح خطا رو به جلو (به انگلیسی: Forward error correction): فرستنده اطلاعات را قبل فرستادن با کمک (به انگلیسی: error-correcting code (ECC)) کد می‌کند. اطلاعات اضافه شده توسط کد دریافت کننده برای بازیابی اطلاعات اصلی مورد استفاده قرار می‌گیرد.[۶]

این دو روش ممکن است ترکیب گردند وروش دیگری به نام درخواست تکرار اتوماتیک ترکیبی (به انگلیسی: Hybrid automatic repeat request) بسازند.

طرح‌های تشخیص خطا[ویرایش]

تشخیص خطا اغلب با یک تابع درهم‌سازی مناسب صورت می‌گیرد یک تابع هش برچسب‌هایی باطول ثابت را به پیام می‌افزاید و که گیرنده را قادر می‌سازد که پیام دریافتی را با بررسی برجسب صحت آن‌را تایید کند.طرح‎های بسیار زیادی برای تابع‌های هشی وجود دارد اما استفاده از آن‌ها بسته به سادگی یا مناسب بودن برای تشخیص نوع خاصی از خطاهست .

کدهای تکرار[ویرایش]

نوشتار اصلی: کدهای تکرار

اساس این طرح این است که کد ارسالی چندین بار ارسال گردد تا از صحت آن مطمئن شویم یک کد بزرگ به چندین بلاک تقسیم می‌گردد ، آنگاه هر کدام چند بار مثلاً ۳ بار ارسال می‌گردند. بنابراین اگر یکی از این بلاک‌ها متفاوت با دیگری باشد خطایی رخ داده هست. این طرح کارا نیست وزمان زیادی می‌گیرد ، اما مزیت آن سادگی آن است .

بیت توازن[ویرایش]

نوشتار اصلی: بیت توازن

دراین حالت یک بیت اضافه می‌شود به گونه‌ای که کل بیت‌های ارسالی دارای مجموع اعضای فرد یا زوج باشد.

چک‌سام[ویرایش]

نوشتار اصلی: چک‌سام

چک‌سام یک پیام عبارت است از هم‌نهشتی مجموع کلمات پیام

کد افرونگی چرخشی[ویرایش]

نوشتار اصلی: کد افزونگی چرخشی

یک تابع درهم‌ساز غیر ایمن هست که برای تشخیص خطاهایی تصادفی در شبکه ایجاد شده است.

تاریخ در همساز رمزنگارانه[ویرایش]

نوشتار اصلی: تابع درهم‌ساز رمزنگارانه

تابع درهم‌سازی هست که رشته‌ای را می‌گیرد ورشته‌ای ثابت برمی گرداند این طرح اطمینان بالایی از لحاظ یکپارچگی داده دارد. هرگونه تغییر در داده باعث تغییر مقدار تابع درهم‌ساز شده و خطا یافته می‌شود.

اصلاح خطا روبه جلو[ویرایش]

نوشتار اصلی: اصلاح خطا روبه جلو

(به انگلیسی: Forward error correction) ، با هر الگوی اصلاح خطا روبه جلو می توان خطاها را یافت. با کمترین فاصله همینگ d میتواندتاd-1 خطا را یافت . این طرح مناسب است اگر بتوان حداقل تعداد خطاها را قبل از ارسال پیش بینی نمود.

تصحیح خطا[ویرایش]

درخواست بازفرستی خودکار[ویرایش]

نوشتار اصلی: درخواست بازفرستی خودکار

یک روش کنترل خطا که از کدهای کشف خطا ، قبول یا عدم قبول پیام و وقفه برای انتقال مطمئن داده‌ها استفاده می‌کند ( قبول پیام یعنی گیرنده پیامی به فرستنده می‌فرستد که پیام به درستی دریافت شده است) .فرستنده به طور معمول در زمان وقفه اگر پیام قبولی دریافت نکند ، پیام را مجدداً می‌فرستد واینکار تا تعداد معینی بار صورت می‌پذیرد.این روش برای کانال‌های ارتباطی متغییر یا با ظرفیت ناشناخته مانند اینترنت مناسب هست .

اصلاح خطا روبه جلو[ویرایش]

نوشتار اصلی: اصلاح خطا روبه جلو

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

درخواست بازفرستی خودکار ترکیبی[ویرایش]

نوشتار اصلی: درخواست بازفرستی خودکار ترکیبی

از ترکیب دو روش قبل به دست می‌آید و دو روش اساسی دارد:

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

موارد غیر قابل استفاده[ویرایش]

برنامه‌هایی که احتیاج به زمان تاخیر کم دارند( مانند گفتگوی تلفنی ) نمی‌توان از درخواست بازفرستی خودکار استفاده کرد و باید از اصلاح خطا رو به جلواستفاده کرد .همچنین مانند مورد قبل برای برنامه‌هایی که وقتی اطلاعات را می‌فرستند دیگرآن را دردسترس برای ارسال مجدد ندارند نمی توان از درخواست باز فرستی خودکار استفاده کرد.

بعضی موارد کاربرد[ویرایش]

ارتباط تنگاتنگی میان توسعه اصلاح خطا رو به جلو و برنامه‌های فضایی بود. در فضا مسافت زیاد ، قدرت سیگنال کم و نیروی مورد نیاز محدود است ، پس احتیاج بود اطلاعات ارسالی اگر هم مشکل دارند در همان جا تصحیح و مورد استفاده قرار گیرند .برای همین هم برای مثال وویجر ۲ از تصحیح خطای رید-سالامون استفاده کرده است. [۷] همچنین از تشخیص و اصلاح خطا در بالابردن قابلیت اطمینان فضاهای ذخیره سازی داده‌ها استفاده می‌گردد برای مثال در هارد درایوهای جدید از کدافزونه‌ای چرخشی برای تشخیص و از تصحیح خطای رید-سالامون برای تصحیح خطاهای جزئی بهره می‌برند. سامانه‌های آرایه چندگانه دیسک‌های مستقل از تکنیک‌های مختلف تشخیص وتصحیح خطاها در زمانی که هاردرایو کاملاً قفل کرده است، استفاده می‌کنند . حافظه دسترسی تصادفی پویاها نیز ازکدهای تصحیح خطا استفاده می‌کنند ، تصحیح خطا دراین موارد معمولاً از کدهای همینگ استفاده می کنند. سامانه های کمی هم از شستشوی حافظه استفاده می کنند.

پانویس[ویرایش]

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

  • مشارکت‌کنندگان ویکی‌پدیا، «Error detection and correction»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲۲ مه ۲۰۱۴).