Error Detection و اصلاح خطا در شبکه های کامپیوتری

Error Detection چیست؟

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

آشنایی با انواع خطا:

آشنایی با انواع خطا

خطاها را می توان به دو دسته طبقه بندی کرد:

ـ Single-Bit Error

ـ Burst Error

Single-Bit Error یا خطای تک بیتی چیست؟

تنها یک بیت از یک واحد داده معین از 1 به 0 یا از 0 به 1 تغییر می کند.

Single-Bit Error

در شکل بالا پیام ارسال شده به صورت تک بیتی خراب شده است یعنی 0 بیت به 1 تبدیل شده است. در انتقال داده سریال به احتمال زیاد ظاهر نمی شود. به عنوان مثال، Sender داده ها را با سرعت 10 مگابیت در ثانیه ارسال می کند، به این معنی که بیت فقط 1ثانیه دوام می آورد و برای اینکه خطای تک بیتی رخ دهد، نویز باید بیش از 1ثانیه باشد. Single-Bit Error عمدتاً در انتقال داده موازی رخ می دهد. به عنوان مثال، اگر از هشت سیم برای ارسال هشت بیت از یک بایت استفاده شود، اگر یکی از سیم ها نویز داشته باشد، یک بیت در هر بایت خراب می شود.

Burst Error یا خطای انفجار چیست؟

دو یا چند بیت از 0 به 1 تغییر می کنند یا از 1 به 0 به عنوان Burst Error شناخته می شود. این خطا از اولین بیت خراب تا آخرین بیت خراب تعیین می شود.

Burst Error

مدت زمان نویز در Burst Error بیشتر از مدت زمان نویز در Single-Bit است.خطاهای Burst  به احتمال زیاد در انتقال داده سریال رخ می دهد. تعداد بیت های تحت تأثیر به مدت زمان نویز و سرعت داده بستگی دارد.

تکنیک های تشخیص خطا:

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

1. Single parity check
2. Two-dimensional parity check
3. Checksum
4. Cyclic redundancy check

بیشتر بخوانید: مدل OSI چیست؟ تفاوت مدل OSI و TCP/IPو بررسی کامل

بررسی Single parity check:

• مکانیزمی ساده و ارزان برای تشخیص خطاها است.
• در این تکنیک، یک بیت اضافی به عنوان parity بیت نیز شناخته می شود که در انتهای واحد داده اضافه می شود تا تعداد 1 ها زوج شود. بنابراین، تعداد کل بیت های ارسالی 9 بیت خواهد بود.
• اگر تعداد بیت های 1 فرد باشد، parity بیت 1 اضافه می شود و اگر تعداد بیت های 1 زوج باشد، parity بیت 0 در انتهای واحد داده اضافه می شود.
• در سمت Receiver، parity بیت از بیت های داده دریافتی محاسبه شده و با parity بیت دریافتی مقایسه می شود.
• این تکنیک تعداد کل 1 های زوج را تولید می کند، بنابراین به عنوان even-parity checking نیز شناخته می شود.

بررسی Single parity check

معایب Single parity check:

• فقط می تواند خطاهای تک بیتی را شناسایی کند که بسیار نادر هستند.
• اگر دو بیت با هم عوض شوند، نمی تواند خطاها را تشخیص دهد.

بررسی Single parity check

بررسی Two-dimensional parity check:

عملکرد را می توان با استفاده از Two-dimensional parity check که داده ها را در قالب یک جدول سازماندهی می کند، بهبود بخشید. بیت های parity check برای هر ردیف محاسبه می شود که معادل Single parity check است. در اینجا، یک بلوک از بیت ها به ردیف ها تقسیم می شود و ردیف بیت های اضافی به کل بلوک اضافه می شود. در سمت Receiver ،parity بیت ها با بیت های محاسبه شده از داده های دریافتی مقایسه می شوند.

بررسی Two-dimensional parity check

معایب Two-dimensional parity check:

• اگر دو بیت در یک واحد داده خراب شده و دو بیت دقیقاً در موقعیت مشابه در واحد داده دیگر نیز خراب شده باشند، 2D parity check قادر به تشخیص خطا نخواهد بود.
• در برخی موارد نمی توان از این تکنیک برای شناسایی خطاهای 4 بیتی یا بیشتر استفاده کرد.

بررسی Checksum:

Checksum یک تکنیک تشخیص خطا بر اساس مفهوم افزونگی است.

به دو بخش تقسیم می شود:

ـ Checksum Generator:

یک Checksum در سمت ارسال (Sender) ایجاد می شود Generator Checksum  داده ها را به بخش های مساوی از هر کدام از n بیت تقسیم می کند و همه این بخش ها با استفاده از محاسبات متمم با هم جمع می شوند. مجموع تکمیل شده و به داده های اصلی که به عنوان فیلد Checksum  شناخته می شود، اضافه می شود. داده های توسعه یافته در سراسر شبکه منتقل می شود.

فرض کنید L مجموع کل بخش‌های داده‌ها باشد، آنگاه جمع کنترلی L خواهد بود

1. Receiver مراحل داده شده را دنبال می کند:
2. واحد بلوک به k بخش و هر یک از n بیت تقسیم می شود.
3. تمام بخش‌های k با استفاده از متمم برای بدست آوردن مجموع با هم جمع می‌شوند.
4. مجموع تکمیل می شود و به فیلد checksum تبدیل می شود.
5. داده های اصلی و فیلد checksum  در سراسر شبکه ارسال می شود.

ـ Checksum Checker:

یک Checksum در سمت دریافت کننده تأیید می شود. گیرنده، داده های دریافتی را به بخش های مساوی از n بیت تقسیم می کند و همه این بخش ها با هم جمع می شوند و سپس این مجموع تکمیل می شود. اگر متمم جمع صفر باشد، داده ها پذیرفته می شوند در غیر این صورت داده ها رد می شوند.

1. گیرنده (Receiver) مراحل داده شده را دنبال می کند:
2. واحد بلوک به k بخش و هر یک از n بیت تقسیم می شود.
3. تمام بخش‌های k با استفاده از الگوریتم متمم برای بدست آوردن مجموع با هم جمع می‌شوند.
4. جمع تکمیل می شود.
5. اگر حاصل جمع صفر باشد، داده ها پذیرفته می شوند در غیر این صورت داده ها دور ریخته می شوند.

بررسی Cyclic redundancy check (CRC):

CRC یک تکنیک خطای افزونگی است که برای تعیین خطا استفاده می شود.

مراحل زیر در CRC برای تشخیص خطا استفاده می شود:

• در تکنیک CRC، رشته‌ای از0ها بهn  واحد داده اضافه می‌شود و این n عدد کمتر از تعداد بیت‌های یک عدد از پیش تعیین‌شده است که به عنوان تقسیم شناخته می‌شود که n+1 بیت است.
• ثانیاً، داده‌های جدید توسعه ‌یافته توسط یک مقسوم ‌کننده با استفاده از فرآیندی به نام تقسیم باینری تقسیم می‌شوند. باقیمانده تولید شده از این تقسیم به عنوان باقیمانده CRC  شناخته می شود.
• ثالثاً، باقیمانده CRC جایگزین 0های اضافه شده در انتهای داده های اصلی می شود. این واحد تازه تولید شده به Receiver ارسال می شود.
• گیرنده داده ها را به دنبال باقیمانده CRC دریافت می کند. گیرنده کل این واحد را به عنوان یک واحد در نظر می گیرد و با همان مقسوم کننده ای تقسیم می شود که برای یافتن باقیمانده CRC استفاده شد.

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

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

بررسی Cyclic redundancy check (CRC)

بیایید این مفهوم را از طریق یک مثال درک کنیم:

فرض کنید داده اصلی 11100 و مقسوم علیه 1001 باشد.

CRC Generator:

• یک Generator CRC از یک تقسیم modulo-2 استفاده می کند. اولاً، سه صفر در انتهای داده ها اضافه می شود زیرا طول مقسوم علیه 4 است و می دانیم که طول رشته 0هایی که باید اضافه شود همیشه کمتر از طول مقسوم علیه است.
• اکنون رشته به 11100000 تبدیل می شود و رشته حاصل، بر مقسوم علیه 1001 تقسیم می شود.
• باقیمانده تولید شده از تقسیم باینری، به عنوان باقیمانده CRC شناخته می شود. مقدار تولید شده باقیمانده CRC 111 است.
• باقیمانده CRC جایگزین رشته 0 های اضافه شده در انتهای واحد داده می شود و رشته نهایی 11100111 خواهد بود که در سراسر شبکه ارسال می شود.

بررسی Cyclic redundancy check (CRC)

CRC Checker:

• عملکرد CRC Checker مشابه Generator CRC است.
• هنگامی که رشته 11100111 در سمت Receiver، دریافت می شود، چک کننده CRC تقسیم modulo-2 را انجام می دهد.
• یک رشته با همان مقسوم‌ کننده تقسیم می‌شود، یعنی 1001.
• در این حالت، CRC Checker باقیمانده صفر را تولید می کند. بنابراین داده ها پذیرفته می شوند.

بررسی Cyclic redundancy check (CRC)