کشف و تصحیح خطا (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.

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

ارتباط میان مینیمم فاصله همینگ و کشف خطا

برای کشف 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

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

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

منابع:

free-books-online

Data communications / F.Safaei

Data communication by William Stalling