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

بررسي 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 استفاده شد.

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

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

تكنيك CRC

بياييد اين مفهوم را از طريق يك مثال درك كنيم:

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

CRC Generator:

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

CRC Generator

CRC Checker:

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

CRC Checker

منبع : Error Detection