کشف و تصحیح خطا (لایه پیوند)
کشف و تصحیح خطا، بیتهای اضافی را که با دقت محاسبه شدهاند، به دادههای ارسالی اضافه میکند تا گیرنده بتواند خطاهای بیتی را که توسط یک پیوند ارتباطی نویزدار ایجاد شدهاند، شناسایی کرده و گاهی اوقات تصحیح کند.
Definition
کشف و تصحیح خطا، تکنیکهای کدگذاری هستند که بیتهای کنترلی اضافی را که از دادهها محاسبه شدهاند، اضافه میکنند تا گیرنده بتواند تشخیص دهد که آیا بیتها در حین انتقال خراب شدهاند (کشف) و با کدهای قویتر، دادههای اصلی را بازسازی کند (تصحیح).
Scope
این موضوع به تکنیکهای کدگذاری مورد استفاده در لایه پیوند برای مقابله با خطاهای بیتی میپردازد: بررسیهای توازن ساده، توازن دو بعدی، مجموع کنترل اینترنت (checksums) و بررسیهای افزونگی چرخهای (CRC) برای کشف، و کدهای تصحیح خطای پیشرو مانند کدهای همینگ برای تصحیح. این موضوع به مبادله بین سربار افزونگی و قدرت کشف یا تصحیح، و اینکه هر تکنیک در کجا استفاده میشود، میپردازد. این موضوع قابلیت اطمینان مبتنی بر ارسال مجدد که در لایههای بالاتر ساخته شده است را که مکمل کدگذاری است و جایگزین آن نیست، شامل نمیشود.
Core questions
- چگونه بیتهای کنترلی اضافی به گیرنده اجازه میدهند تا تشخیص دهد که یک انتقال خراب شده است؟
- توازن، مجموع کنترلها و بررسیهای افزونگی چرخهای از نظر قدرت و هزینه چه تفاوتی دارند؟
- چگونه کدهای تصحیح خطای پیشرو مانند کدهای همینگ خطاها را بدون ارسال مجدد تصحیح میکنند؟
- مبادله بین سربار کدگذاری و قابلیت مدیریت خطا چیست؟
- چه زمانی تصحیح خطا بر کشف به علاوه ارسال مجدد ترجیح داده میشود؟
Key concepts
- بررسی توازن
- توازن دو بعدی
- مجموع کنترل اینترنت
- بررسی افزونگی چرخهای (CRC)
- چندجملهای مولد
- تصحیح خطای پیشرو
- کدهای همینگ
- خطاهای انفجاری
- سربار کدگذاری
Key theories
- افزونگی برای کشف خطا
- با ارسال بیتهای اضافی که از دادهها محاسبه شدهاند — یک بیت توازن، یک مجموع کنترل، یا یک باقیمانده CRC — گیرنده میتواند برای تشخیص خرابی، مجدداً محاسبه و مقایسه کند؛ CRCهای مبتنی بر محاسبات چندجملهای تمام خطاهای انفجاری را تا درجه چندجملهای مولد تشخیص میدهند.
- تصحیح خطای پیشرو
- کدهای تصحیح خطا مانند کدهای همینگ به اندازه کافی افزونگی ساختاریافته اضافه میکنند که گیرنده نه تنها میتواند تعداد محدودی از خطاهای بیتی را تشخیص دهد، بلکه آنها را مکانیابی و رفع کند، و از ارسال مجدد به قیمت سربار بیشتر جلوگیری میکند.
- ظرفیت کانال و ارتباط قابل اعتماد
- نظریه اطلاعات بیان میکند که هر کانال نویزدار دارای ظرفیتی است که زیر آن ارتباط قابل اعتماد دلخواه با کدگذاری مناسب امکانپذیر است، و محدودیتهای اساسی را که کدهای کنترل خطای عملی به آن نزدیک میشوند، چارچوببندی میکند.
Clinical relevance
کنترل خطا نامرئی اما فراگیر است: CRCها از فریمهای اترنت و Wi-Fi محافظت میکنند، مجموع کنترلها از سربرگهای IP و انتقال محافظت میکنند، و تصحیح خطای پیشرو در مواردی که ارسال مجدد پرهزینه یا غیرممکن است، مانند پیوندهای فضای عمیق، رسانههای ذخیرهسازی، و پخش جریانی از طریق بیسیمهای پر اتلاف، ضروری است. تعادل صحیح بین کشف و تصحیح، قابلیت اطمینان و کارایی را در سیستمهای ارتباطی و ذخیرهسازی شکل میدهد.
History
نظریه اطلاعات کلود شانون در سال ۱۹۴۸ وجود کدگذاری قابل اعتماد را تا ظرفیت کانال اثبات کرد، و کدهای ریچارد همینگ در سال ۱۹۵۰ اولین طرح عملی تصحیح خطای تک بیتی را ارائه دادند. بررسیهای افزونگی چرخهای و کدهای قویتر به دنبال آن آمدند و در فریمبندی لایه پیوند استاندارد شدند، و این حوزه از آن زمان کدهای قدرتمندی (مانند کدهای توربو و LDPC) تولید کرده است که به حد شانون نزدیک میشوند.
Key figures
- Claude Shannon
- Richard Hamming
Related topics
Seminal works
- shannon1948
- hamming1950
- kurose2021
Frequently asked questions
- تفاوت بین کشف خطا و تصحیح خطا چیست؟
- کشف خطا فقط به گیرنده میگوید که دادهها خراب شدهاند، پس از آن میتواند دادهها را دور بیندازد یا درخواست ارسال مجدد کند. تصحیح خطا به اندازه کافی افزونگی اضافه میکند که گیرنده میتواند دادههای اصلی را بدون درخواست مجدد بازسازی کند، که در مواردی که ارسال مجدد کند یا غیرممکن است، ارزشمند است.
- چرا شبکهها به جای توازن ساده از CRC استفاده میکنند؟
- یک بیت توازن تنها هر تعداد زوجی از خطاهای بیتی را از دست میدهد، در حالی که یک بررسی افزونگی چرخهای، مبتنی بر تقسیم چندجملهای، تمام خطاهای تک بیتی، تمام خطاهای دو بیتی، و تمام خطاهای انفجاری کوتاهتر از بررسی را تشخیص میدهد، که آن را برای انواع خطاهایی که پیوندها واقعاً تولید میکنند، بسیار قویتر میکند.