4 / 5. 6

فهرست مطالب

فهرست مطالب

Cyclic  Redundancy Check چیست؟

1- CRC (Cyclic Redundancy Check)

کد CRC  یا Cyclic  Redundancy Check چیست و چگونه کار می کند؟

Cyclic  Redundancy Check در واقع یک کد تشخیص خطا در بسته های شبکه می باشد.

در این روش، یک کد در انتهای رشته های داده، اضافه می شود.

بدین ترتیب، تغییراتی که در حین انتقال در محتوای آن ها رخ داده است را پیدا می کند.

این کد، توسط فرستنده به انتهای بسته های اضافه می شود و گیرنده آن ها را چک می کند تا از سالم بودن بسته ها اطمینیان حاصل کند.

کد CRC در لایه پیونده داده کار می کند و اگر از این کد به درستی استفاده شود به احتمال 99 درصد، خطا به درستی تشخیص داده می شوند.

2- کد CRC چگونه کار می کند؟

زمانی که یک بسته آماده ارسال می باشد، فرستنده باید کد تشخیص خطا را تولید کند. 

برای تولید کد CRC، فرستنده نیاز به یک کلید دارد که از قبل با گیرنده بر سر مقدار این کلید به توافق رسیده اند.

بعد از تفاهم بر سر مقدار کلید، فرستنده ابتدا تعدادی صفر به دیتای اصلی اضافه و سپس آن را بر کلید تقسیم میکند.

سپس حاصل تقسیم را به انتهای داده می چسباند و بسته را ارسال می کند.

زمانی که گیرنده بسته را دریافت می کند، داده و کد CRC را ضربدر کلید می کند. 

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

3- روش ایجاد کد CRC

3.1- افزودن صفر به ابتدای رشته

فرض کنید، قصد دارید برای رشته “1101101”  با استفاده از کلید “10101”، یک کد CRC تولید کنید. 

مراحل زیر باید طی شوند تا بتوانید کد تشخیص خطای آن را تولید کنید.

برای تولید یک کد CRC، ابتدا باید به انتهای رشته اصلی، تعدادی صفر اضافه کنیم.

برای به دست آوردن تعداد صفرها باید طول کلید را منهای 1 کنید. 

سپس به تعداد عدد به دست آمده، به انتهای داده، صفر اضافه می کنیم(مطابق شکل 1).

CRC - گام اول افزودن صفر به ابتدای رشته
شکل 1- محاسبه تعداد صفرها در کد CRC

3.2- عملیات متوالی XOR

در مرحله قبل، 4 صفر به رشته اضافه کردیم و رشته حاصل برابر با 11011010000 شد.

حالا باید “رقم اول از رشته” را در “کلید” ضرب(در شکل2 با فلش قرمز نشان داده شده)، سپس رشته و عدد حاصلضرب را زیر هم نوشته و اعداد متناظر را با یکدیگر XOR کنیم.

اگر رقم اول از رشته تولید شده، صفر بود، آن را حذف می کنیم.

از طرف دیگر، یک رقم از رشته اصلی قرض گرفته و به رشته ی به دست آمده اضافه می کنیم(در شکل 2 با فلش سبز نشان داده شده).

CRC - عملیات متوالی XOR
شکل2- محاسبه کلید و XOR با رشته اصلی برای تولید کد CRC

حالا رقم اول رشته به دست آمده را ضربدر کلید می کنیم (در شکل 3 با فلش قرمز نشان داده شده).

همچنین، حاصلضرب را با رشته مجددا XOR می کنیم(مثلث ها آبی در شکل 3).

اگر رقم اول صفر بود آن را حذف و از رشته اصلی یک رقم قرض می گیریم(فلش سبز رنگ در شکل 3) و این عملیات را تا انتها انجام می دهیم.

CRC- XORهای متوالی
شکل3- محاسبه کلید و XOR در روش کد CRC

هرجا رقم اول در رشته تولید شده، صفر باشد کلید را ضربدر صفر می کنیم.

در این مثال اگر کلید را ضربدر 0 کنیم، نتیجه 00000  می شود.

سپس، 00000 را با رشته حاصل شده XOR می کنیم(مطابق شکل 4 – فلش سبز رنگ).

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

اگر عملیات فوق را تا انتها تکرار کنید به عدد 1011 میرسید.

حالا فرستنده این کد را به انتهای رشته ی اصلی می چسباند.

در نتیجه رشته ای که توسط فرستنده به گیرنده ارسال می شود، بدین صورت است:  11011011011

شکل 4 - مراحل تولید کد CRC

4- چگونه با استفاده از کد CRC ، خطا را تشخیص دهیم؟

عملیات تشخیص خطا در سمت لایه پیونده داده ی گیرنده انجام می شود.

در مثال بالا، فرستنده، رشته را به شکل 11011011011 به گیرنده ارسال می کند.

در واقع چهار بیت آخر از سمت راست همان کد CRC می باشد که به رشته اصلی متصل شده است.

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

اگر نتیجه صفر شود، به معنای عدم خطا و اگر عددی غیر از صفر حاصل شود، نشان دهنده خطا می باشد.