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

[mehraboOon]

کشف و تصحیح خطا (2)



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

مینیمم فاصله همینگ


با وجودی که بحث فاصله همینگ، مفهومی کلیدی برای سر و کار داشتن با کدهای کشف و تصحیح خطا است، ارزیابی اصلی که برای طراحی هر کد صورت می پذیرد، مینیمم فاصله همینگ است. وقتی مجموعه ای از کدها راد اشته باشیم، مینیمم فاصله همینگ عبارت است از کوچکترین عدد همینگ میان همه زوج‌های موجود در مجموعه. این مفهوم با نماد 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 نام دارد، مکانیزمی است که در اینترنت جهانی کاربرد دارد و توسط چندین پروتکل مورد استفاده قرار می‌ گیرید که در اینجا به شرح آن می پردازیم. این مکانیز نیز مانند دو روش PCC و CRC بر اساس مفهوم افزونگی طراحی شده اند. این روش را با حل یک مثال ساده، به آسانی درک خواهید کرد.
مثال: مجموعه مقابله‌ای 8 بیتی را برای بلوک 16 بیتی 1010100100111001 محاسبه کنید و نشان دهید خطایی وجود ندارد.
قدم اول : کد 16 بیتی را به دو کد 8 بیتی تقسیم میکنیم.
قدم دوم : اعداد را در دسته های 8 بیتی جمع می کنیم.
10101001 + 00111001 = 11100010
قدم سوم : از عدد بدست آمده مکمل 1 میگیریم.
00011101
نتیجه بدست آمده را به انتهای کد اضافه می کنیم.
101010010011100100011101
برای نشان دادن عدم وجود خطا، کافیست گیرنده 24 بیت بدست آمده را به سه قسمت 8 تایی تقسیم کنیم و اعداد را با هم جمع کنیم و از آن مکمل 1 بگیریم. اگر نتیجه نهایی برابر با 0 شود، می توان نتیجه گرفت که خطایی رخ نداده است.
10101001 + 00111001 + 00011101 = 11111111
مکمل 1 = 00000000
مجموع مقابله‌ایکه اینترنت جهانی از آن استفاده می کند از نظر سنتی 16 بیتی است. قابلیت مجموع مقابله ای در وارسی خطا به توانایی CRC نیست. به عنوان مثال اگر مقدار یک کلمه کد افزایش یابد و مقدار کلمه کد دیگر به همان میزان کاهش، دو خطای پدید آمده قابل کشف نخواهد بود. زیرا حاصل جمع و مجموع مقابله ای یکسانی خواهند شد. مضافا چنانچه مقادیر چندین کلمه افزایش یابند اما تغییر کلی مضربی از 65535 باشد، حاصل جمع و مجموع مقابله ای تغیرر نخواهند کرد که به

معنای عدم کشف خطاهای پدید آمده است.

فاطمه مجدآبادی

بخش دانش و زندگی تبیان

منابع:

free-books-online

Data communications / F.Safaei

Data communication by William Stalling