کشف و تصحیح خطا مقاله شماره 1
زمانی که فرستنده اقدام به ارسال پیام به گیرنده می کند، پیام باید بدون خطا به گیرنده برسد. سوالی که مطرح می شود این است که اولا گیرنده چطور می تواند متوجه خطا شود و بفهمد که پیام دارای اشکال است؟ دوما گیرنده چطور باید پیام دریافتی را تصحیح کند؟
مینیمم فاصله همینگ
با وجودی که بحث فاصله همینگ، مفهومی کلیدی برای سر و کار داشتن با کدهای کشف و تصحیح خطا است، ارزیابی اصلی که برای طراحی هر کد صورت می پذیرد، مینیمم فاصله همینگ است. وقتی مجموعه ای از کدها راد اشته باشیم، مینیمم فاصله همینگ عبارت است از کوچکترین عدد همینگ میان همه زوج‌های موجود در مجموعه. این مفهوم با نماد dmin شناخته می شود. مینیمم فاصله همینگ تنها زمانی با فاصله همینگ برابر است که مجموعه کدها تنها دارای دو عضو باشد. به مثال زیر توجه کنید.
مثال: فاصله همینگ و مینیمم فاصله همینگ میان چهار کد 00000، 01011، 10101، 11110 را حساب کنید.
ابتدا فاصله همینگ میان تک تک زوج ها را محسابه میکنیم.
d (00000 , 01011) = 3
d (00000 , 10101) = 3
d (00000 , 11110) = 4
d (01011 , 10101) = 4
d (01011 , 11110) = 3
d (10101 , 11110) = 3
به این ترتیب، مینیمم فاصله همینگ برابر است با 3.
وقتی مجموعه ای از کدها راد اشته باشیم، مینیمم فاصله همینگ عبارت است از کوچکترین عدد همینگ میان همه زوج‌های موجود در مجموعه،
این مفهوم با نماد dmin شناخته می شود
ارتباط میان فاصله همینگ و خطا
این کمیت به ما تعداد بیت های معیوب در حین ارسال را نشان می دهد. به تعداد عدد همینگ، میان کد ارسالی و کد دریافتی بیت معیوب یافت می شود.
ارتباط میان مینیمم فاصله همینگ و کشف خطا
برای کشف n خطا در هنگام ارسال، باید مینیمم فاصله همینگ میان دو کد ارسالی برابر با عدد n+1 باشد تا کد دریافتی با کد ارسالی منطبق نگردد.
ارتباط میان مینیمم فاصله و تصحیح خطا
اگر بخواهیم n خطا را نه تنها کشف بلکه اصلاح هم کنیم، مینیمم فاصله همینگ میان دو کلمه کد باید برابر با 2n+1 باشد. به عنوان مثال، در مثال حل شده ی بالا، مینیمم فاصله همینگ 3 است پس تنها می توانیم خطاهای تک بیتی را تصحیح کنیم.
دو روش مشهور که برای کشف خطا وجود دارد:
PCC Parity Check Code و CRC Cyclic Redundancy Check است. روش سوم که مجموعه مقابله‌ای یا Checksum نام دارد، مکانیزمی است که در اینترنت جهانی کاربرد دارد و توسط چندین پروتکل مورد استفاده قرار می گیرید که در اینجا به شرح آن می پردازیم. ادامه در مقاله بعدی