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

[mehraboOon]

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


زمانی که فرستنده اقدام به ارسال پیام به گیرنده می‌ کند، پیام باید بدون خطا به گیرنده برسد. سوالی که مطرح می شود این است که اولا گیرنده چطور می تواند متوجه خطا شود و بفهمد که پیام دارای اشکال است؟ دوما گیرنده چطور باید پیام دریافتی را تصحیح کند؟ برای پاسخ دادن به این پرسش ها ابتدا لازم است با انواع خطا آشنا شویم.http://img.tebyan.net/big/1390/05/124250913219894101142214215310611513385151.jpg
به دلیل وجود نویز ( برای اطلاعات بیشتر رجوع شود به نویز در رسانه انتقال (http://www.tebyan.net/science_technology/computermagazine/network_security/2011/7/20/172931.html) ) در محیط و رسانه انتقال، زمانی که امواج الکترومغناطیس از نقطه‌ ای به نقطه ی دیگر منتقل می شوند دچار اختلال می شوند. این اختلال گاهی موجب می شود که مفهوم صفر و یک انتقالی در گیرنده تغییر کند و در نتیجه پیام دچار خطا شود.

انواع خطاهایی که می توانند رخ دهند عبارت اند از :


*خطای تک بیتی یا Single bit error*خطای رگباری یا Burst error
*خطای تک بیتی

همان طور که از اسمش پیداست این خطا تنها در یک بیت انتقالی رخ می دهد. در واقع در یک بایت یا بسته ارسالی تنها یک بیت از صفر به یک یا از یک به صفر تغییر می کند.
http://img.tebyan.net/big/1390/05/20110809160029927_1-1.jpg
خطای رگباری


در این حالت، دو یا چند بیت به صورت متوالی با خطا به گیرنده می رسند. طول خطا لزوما به انندازه بیت های معیوب نیست، بدین معنا که اگر خط بیت معیوب و سپس یک بیت سالم و دوباره چند بیت معیوب داشته باشیم، طول خطای رگباری از اولین بیت معیوب آغاز و تا آخرین بیت معیوب ادامه دارد.http://img.tebyan.net/big/1390/05/20110809160029958_2.jpg
خطاهای تک بیتی را به آسانی می توان کشف یا اصلاح کرد. ولی در شرایط واقعی، خطاها به صورت پشت سر هم و رگباری رخ می دهند. یعنی به صورت رگباری از بین می روند. فرض کنید نویز ضربه ای به مدت 0.1 میلی ثانیه بر روی کانال انتقال قرار بگیرد. تمامی بیت هایی که در این فاصله ارسال شده اند، از بین خواهند رفت.

اگر نرخ انتقال یک مگابیت بر ثانیه باشد، در هر میکرو ثانیه، یک بیت ارسال می شود و در نتیجه 100 بیت خراب می شوند. چنان چه نرخ انتقال بیشتر باشد، تعداد بیت های معیوب بیشتر خواهد شد


زیرا در مدت زمان کمتری، بیت های بیشتری ارسال می شوند. پس در فاصله اثر نویز، بیت های بیشتری خراب می شوند. برای مثال اگر نرخ انتقال 10 مگابیت بر ثانیه باشد، 1000 بیت پشت سر هم خراب می شوند. به طور کلی زمان اعمال نویز، خطای رگباری را مشخص می کند.ب
افزونگی


برای آنکه گیرنده بتواند خطای ایجاد شده در پیام را بفهمد، با مفهومی به نام افزونگی رو به رو هستیم. افزونگی بدین معناست که برای رسیدن به منظور فوق، نیازمند اضافه کردن چند بیت کنترلی بر سر پیام هستیم تا توسط آنها قادر به کشف و یا تصحیح بیت های معیوب باشیم.به طور کلی کشف خطا از تصحیح آن آسان تر است.
دو تکنیک اصلی برای تصحیح خطا داریم:
اولین روش به ارسال مجدد یا Retransmission معروف است. در این روش گیرنده با استفاده از بیت های کنترلی و افزونگی متوجه وجود خطا در پیام می شود و پیغامی برای فرستنده ارسال می کند و از فرستنده می خواهد که دوباره همان پیام را ارسال کند.
روش دوم تصحیح خطای پیش رو یا Forward Error Correction نام دارد. در این روش گیرنده نه تنها کشف می کند که پیام دارای خطا است بلکه با کمک بیت های افزونه و با تکنیک های خاصی سعی در حدس زدن پیام مورد نظر می کند.
فاصله همینگ


یکی از مفاهیم اصلی برای کنترل خطا، ایده فاصله همینگ ( Hamming Distance ) است. فاصله همینگ بین دو کلمه ی هم اندازه عبارتست از تعداد بیت های متفاوت در دو کلمه کد. به عبارت دیگر، اگر دو کلمه کد با فاصله همینگ D موجود باشند، در این صورت برای تبدیل یک کلمه کد به کلمه کد دیگری، بایستی D خطا روی دهد. چنانچه، x و y دو کلمه کد باشند، فاصله همینگ با نماد d(x,y) نشان داده می شود. فاصله همینگ به آسانی با به کار بستن عملگر XOR بر روی دو کلمه کد و شمارش تعداد یک های حاصل به دست می آید. دقت داشته باشید که فاصله همینگ بزرگتر یا مساوی صفر است.برای مثال فاصله همینگ دو کد 01110011 و 11101101 برابر است با 5. زیرا حاصل XOR این دو کد عبارت است از 10011110.

ادامه دارد...


فاطمه مجدآبادی
بخش دانش و زندگی تبیان
منابع:

free-books-online
Data communications / F.Safaei
Data communication by William Stalling

[mehraboOon]

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



زمانی که فرستنده اقدام به ارسال پیام به گیرنده می‌ کند، پیام باید بدون خطا به گیرنده برسد. سوالی که مطرح می شود این است که اولا گیرنده چطور می تواند متوجه خطا شود و بفهمد که پیام دارای اشکال است؟ دوما گیرنده چطور باید پیام دریافتی را تصحیح کند؟ برای پاسخ دادن به این پرسش ها ابتدا لازم است با انواع خطا آشنا شویم. http://img.tebyan.net/big/1390/05/1157116134147182511624111042182495101234.jpg (http://www.tebyan.net/bigimage.aspx?img=http://img.tebyan.net/big/1390/05/239852291782191451891339136331211902439694.jpg)
در قسمت اول مطلب کشف و تصحیح خطا (http://forums.azardl.com/showthread.php?p=151167#post151167) گفتیم که برای رسیدن به پاسخ دو پرسش فوق، به ابتدای کدهای ارسالی، بیت هایی را تحت عنوان افزونگی ارسال می‌کنیم. همچنین مفهوم فاصله همینگ را شرح داده و روش محاسبه آن را توضیح دادیم. اینک به بیان چند مفهوم دیگر و ارتباط آنها با کشف و تصحیح خطا می‌ پردازیم.

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


با وجودی که بحث فاصله همینگ، مفهومی کلیدی برای سر و کار داشتن با کدهای کشف و تصحیح خطا است، ارزیابی اصلی که برای طراحی هر کد صورت می پذیرد، مینیمم فاصله همینگ است. وقتی مجموعه ای از کدها راد اشته باشیم، مینیمم فاصله همینگ عبارت است از کوچکترین عدد همینگ میان همه زوج‌های موجود در مجموعه. این مفهوم با نماد 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 است پس تنها می توانیم خطاهای تک بیتی را تصحیح کنیم. http://img.tebyan.net/big/1390/05/91911841185136771435021844221236254218235.jpg (http://www.tebyan.net/bigimage.aspx?img=http://img.tebyan.net/big/1390/05/23611635122373661662197424212514012516288.jpg)
دو روش مشهور که برای کشف خطا وجود دارد:


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