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

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

*خطای تک بیتی یا Single bit error

*خطای رگباری یا Burst error

*خطای تک بیتی

همان طور که از اسمش پیداست این خطا تنها در یک بیت انتقالی رخ می دهد. در واقع در یک بایت یا بسته ارسالی تنها یک بیت از صفر به یک یا از یک به صفر تغییر می کند.

در این حالت، دو یا چند بیت به صورت متوالی با خطا به گیرنده می رسند. طول خطا لزوما به انندازه بیت های معیوب نیست، بدین معنا که اگر خط بیت معیوب و سپس یک بیت سالم و دوباره چند بیت معیوب داشته باشیم، طول خطای رگباری از اولین بیت معیوب آغاز و تا آخرین بیت معیوب ادامه دارد.

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

 زیرا در مدت زمان کمتری، بیت های بیشتری ارسال می شوند. پس در فاصله اثر نویز، بیت های بیشتری خراب می شوند. برای مثال اگر نرخ انتقال 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